Есть следущее задание:
На вход поступают значения в формате <value><name>, т.е например 123Object, где <value> = 123, <name> = Object. Значения могут повторяться.
На выходе необходимо получить сортированный по <value> вектор уникальных имен <name>.
Например
на входе: 3Boria, 32Victor, 11Vasia, 3Boria, 20Petia
на выходе нужен вектор: Boria, Vasia, Petia, Victor
Помогите написать с помощью stl оптимальный алгоритм!

Здравствуйте, Аноним, Вы писали:

А>Есть следущее задание:
А>На вход поступают значения в формате <value><name>, т.е например 123Object, где <value> = 123, <name> = Object. Значения могут повторяться.
А>На выходе необходимо получить сортированный по <value> вектор уникальных имен <name>.
А>Например
А>на входе: 3Boria, 32Victor, 11Vasia, 3Boria, 20Petia
А>на выходе нужен вектор: Boria, Vasia, Petia, Victor
А>Помогите написать с помощью stl оптимальный алгоритм!
А map использовать нельзя? При вставке в map по ключу-имени они и станут сортированными сразу...

Здравствуйте, Аноним, Вы писали:

А>Есть следущее задание:
А>На вход поступают значения в формате <value><name>, т.е например 123Object, где <value> = 123, <name> = Object. Значения могут повторяться.
А>На выходе необходимо получить сортированный по <value> вектор уникальных имен <name>.
А>Например
А>на входе: 3Boria, 32Victor, 11Vasia, 3Boria, 20Petia
А>на выходе нужен вектор: Boria, Vasia, Petia, Victor
А>Помогите написать с помощью stl оптимальный алгоритм!

Например map. Можно обойтись вектром например так:

class record
{
public:
  std::string name;
  int num;
};


struct NamesEqual
{
  bool operator() (const recored& rl, const record& rr) const
  {
    // Do it faster, probably with string hashing, as static member funtcion 'CompareNames'
    return rl.name == rr.name;
  }
};


struct SortNameAndNum
{
  bool operator() (const recored& rl, const record& rr) const
  {
    // Do it faster, probably with string hashing, as static member funtcion 'CompareNames'
    if (rl.name < rl.name)
      return true;
    if (rl.name > rl.name)
      return true;

    // FIXME: I dont tested, but if numbers would be bad ordered just replace < with >
    return rl.num < rr.num;
  }
};


int main()
{
  // 'record' is our type with int number and string
  std::vector<record> v;

  // fill-up it

  // sort it. Predicate 'SortNameAndNum' is pretty sophisticated. See it.
  std::sort(v.begin(), v.end(), SortNameAndNum());

  // Physically remove 
  v.erase(std::unique(v.begin(), v.end(), NamesEqual()), v.end());  

  // output...

  return 0;
}

Здравствуйте, demi, Вы писали:

Тама пара опечаток в SortNameAndNum (rr вместе rl справа, конечно). И второе — предлагаю завести статическую функцию в классе record:

int record::CompareNames(const record& rl, const record& rr)
{
// Here we probably use hash value. Which wshould be in privates!
// The return value is just like 'strcmp': <0 if rl.name < rr.name, == 0, if rl.name < rr.name and > if rl.name > rr.name.
// This is done faster than 2 comparisions.
}

Все

Здравствуйте, LaptevVV, Вы писали:

LVV>А map использовать нельзя? При вставке в map по ключу-имени они и станут сортированными сразу...

Нет, т.к <value> приходит только для сортировки и в дальнейшем его хранение не требуется. На выходе должен быть vector< name > сортированный по <value>

Здравствуйте, demi, Вы писали:


D>Например map. Можно обойтись вектром например так:
D>

D>class record
D>{
D>public:
D>  std::string name;
D>  int num;
D>};


D>struct NamesEqual
D>{
D>  bool operator() (const recored& rl, const record& rr) const
D>  {
D>    // Do it faster, probably with string hashing, as static member funtcion 'CompareNames'
D>    return rl.name == rr.name;
D>  }
D>};


D>struct SortNameAndNum
D>{
D>  bool operator() (const recored& rl, const record& rr) const
D>  {
D>    // Do it faster, probably with string hashing, as static member funtcion 'CompareNames'
D>    if (rl.name < rl.name)
D>      return true;
D>    if (rl.name > rl.name)
D>      return true;

D>    // FIXME: I dont tested, but if numbers would be bad ordered just replace < with >
D>    return rl.num < rr.num;
D>  }
D>};


D>int main()
D>{
D>  // 'record' is our type with int number and string
D>  std::vector<record> v;

D>  // fill-up it

D>  // sort it. Predicate 'SortNameAndNum' is pretty sophisticated. See it.
D>  std::sort(v.begin(), v.end(), SortNameAndNum());

D>  // Physically remove 
D>  v.erase(std::unique(v.begin(), v.end(), NamesEqual()), v.end());  

D>  // output...

D>  return 0;
D>}

D>

Условия достаточно жесткие, на входе вектор <value><name>, на выходе должен быть сортированный вектор <name> по <value>. Само <value> нужно только для сортировки. Значений на входе может быть >10 000, нужен оптимальный алгоритм.
Т.е желательно переложить значения за 1 проход по входному вектору, если это возможно.

Здравствуйте, <Аноним>, Вы писали:

А>На вход поступают значения в формате <value><name>, т.е например 123Object, где <value> = 123, <name> = Object. Значения могут повторяться.
А>На выходе необходимо получить сортированный по <value> вектор уникальных имен <name>.

Задача поставлена неполно.
Допустим, есть (3,Vasya), (2,Petya), (1,Vasya).
На выходе должны быть Petya и Vasya, но в каком порядке?

сортировать нужно по
— минимальному
— максимальному
— среднеарифметическому
— сумме
из всех value, связанных с данным name?

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, <Аноним>, Вы писали:

А>>На вход поступают значения в формате <value><name>, т.е например 123Object, где <value> = 123, <name> = Object. Значения могут повторяться.
А>>На выходе необходимо получить сортированный по <value> вектор уникальных имен <name>.

К>Задача поставлена неполно.
К>Допустим, есть (3,Vasya), (2,Petya), (1,Vasya).
К>На выходе должны быть Petya и Vasya, но в каком порядке?

К>сортировать нужно по
К>- минимальному
К>- максимальному
К>- среднеарифметическому
К>- сумме
К>из всех value, связанных с данным name?

Такое не возможно. За каждым <value> однозначно закреплено <name>

Здравствуйте, <Аноним>, Вы писали:

А>Такое не возможно. За каждым <value> однозначно закреплено <name>

В таком случае тебе нужно
1) отсортировать пары (value,name) по value
2) убедиться, что все name уникальны (можно просто поверить пользователю на слово )
3) пробежаться по коллекции и вывести name

#include <map>
#include <algorithm>
#include <iterator>
#include <sstream>
using namespace std;

struct parse_pair
{
    pair<int,string> operator()(string const& src) const
    {
        istringstream stm(src);
        int value; string name;
        stm >> value >> name;
        return make_pair(value,name);
    }
};

struct get_second
{
    template<class Pair>
    typename Pair::second_type operator()(Pair const& p) const
    {
        return p.second;
    }
};

int main()
{
    map<int,string> dataset; // сортировать будем прямо в момент вставки
    transform(istream_iterator<string>(cin), istream_iterator<string>(), inserter(dataset, dataset.begin()), parse_pair());
    transform(dataset.begin(), dataset.end(), ostream_iterator<string>(cout," "), get_second());
}

Здравствуйте, Кодт, Вы писали:

К>    map<int,string> dataset; // сортировать будем прямо в момент вставки

очень плохой перформанс может быть, если поэлементно вставлять в мап, если записей много.
сначала в список вставить надо, потом его отсортировать — так шустрее будет имхо

Здравствуйте, uzhas, Вы писали:

U>очень плохой перформанс может быть, если поэлементно вставлять в мап, если записей много.
U>сначала в список вставить надо, потом его отсортировать — так шустрее будет имхо
"Ну, или так".