STL, noob: отсортировать лист векторов

darin06

Столкнулся с такой задачей. Есть два одномерных массива, хочется отсортировать их связаным образом, в порядке возрастания значений элементов первого. Я придумал построить list из векторов (vector каждый вектор состоит из элемента первого и соответсвующего элемента второго массива. Поместить элементы массивов в лист у меня получилось, а вот как отсортировать лист по первым элемента векторов не знаю (потом еще удалиить повторяющиеся по первому элементу). Разъясните как такое можно сделать. Да, по производительности не критично.

Serab

ну можно так, хотя мне не нравится это все



template<class T>

bool compareFirstElements(const vector<T>& lhs, const vector<T>& rhs) { return lhs[0] < rhs[0]; }



template<class T>

bool firstElementsEqual(const vector<T>& lhs, const vector<T>& rhs) { return lhs[0] == rhs[0]; }



list<vector<int>> l;

l.sort(compareFirstElements);

unique(l.begin l.end firstElementsEqual);

darin06

А что тебе не нравится?

Serab

вот лучше решение, имхо http://stackoverflow.com/questions/3909272/sorting-two-corre...
не нравится тем, что доп. памяти много: приходится все копировать в отдельную структуру. Вообще задача часто встречается, да.

agent007new

Только, все-таки, нужно l.sort; вызывать - у листа не random-access итераторы, поэтому вызов обычного std::sort будет неэффективным

Serab

ему же пофиг на производительность

да, налошил, исправлю

evgen5555

А на дополнительную память ограничения есть? Если нет, с мапом имхо нагляднее, чем с функторами:

 std::multimap<int, int> mm;

    for(int i = 0; i < v2.size; ++i)

        mm.insert(std::make_pair(v1[i], v2[i];



    std::multimap<int, int>::const_iterator it = mm.begin;

    v2.clear;

    while(it != mm.end

    {

        v2.push_back( it->second );

        ++it;

    }

Serab

кстати да, там уж лучше список не из vector'ов, а из pair делать как минимум.

darin06

Мне такую функцию надо вызывать один раз, для сортировки массива размером максимум в 10^20 элементов (обычные гораздо меньше, 10^16 и время которое на эту сортировку требуется совершенно не критично, перед этим идут вычисления, которые занимают порядка 8-10 часов.
Мне очень понравилась идея с сортиовкой индексов, потому что на самом деле таких у меня массивов несколько, а первый (по которому сортируем) у них общий.
Про pair просто не знал — это конечно намного логичней. А так конечно надо подучить матчасть. Кстати, какие бы могли порекомендовать туториалы по STL?

elenangel

http://www.cplusplus.com/reference/stl/

Serab

10^20 int'ов это же ~ 2^69 байтов памяти o_O

Serab

это не туториал, а референс и его лошат

elenangel

имхо, это то что надо, чтобы быстро посмотреть существующие контейнеры и алгоритмы, а также посмотреть у какого контейнера что как называется - insert, push_back, push etc, как перегружено, какие типы возвращает.

Serab

да, и это же не туториал, правильно?
В любом случае cppreference более почитаем

elenangel

не думаю что ТС надо что-то в духе: "А теперь, дети, мы создадим массив из 3 элементов и применим к нему алгоритм сортировки"

elenangel

10^20 int'ов это же ~ 2^69 байтов памяти o_O

там основание степени в двоичной системе записано

darin06

Да, я фигню написал, 2^20 элементов максимум. Так что показатель степени в двоичном виде, да )

erotic

А на дополнительную память ограничения есть? Если нет, с мапом имхо нагляднее, чем с функторами

Имхо с явной сортировкой и лямбдами еще нагляднее

И память не так мучает:



vector<int> v1, v2;

vector<pair<int,int>> m;

m.reserve(v1.size;

for (auto i = v1.begin j = v2.begin; i != v1.end; ++i, ++j)

    m.push_back(make_pair(*i, *j;

std::sort(m.begin m.end [] (const pair<int,int>& l, const pair<int,int>& r) { return l.first < r.first; });

На компилируемость не проверял.

darin06

Кстати, если уж на то пошло, чтобы восполнить пробелы в области алгоритмов, как правильно сформулированная мною задача называется?

Serab

сейчас c++11 уже default?

erotic

Так уже и год почти 2013-й, пора: )

smit1

for (auto i = v1.begin j = v2.begin; i != v1.end; ++i, ++j)

    m.push_back(make_pair(*i, *j;

Так уже и год почти 2013-й, пора: )

Ну тогда уж надо писать так:

for (auto i = v1.cbegin j = v2.cbegin; i != v1.cend; ++i, ++j)

    m.push_back(make_pair(*i, *j;

или так:

for (auto i = begin(v1 j = begin(v2); i != end(v1); ++i, ++j)

    m.push_back(make_pair(*i, *j;

(А std::cbegin и std::cend комитетчики _забыли_, лол!)

erotic

Я бы еще push_back не стал бы использовать в таком случае



for (auto i = v1.cbegin j = v2.cbegin; i != v1.cend; ++i, ++j)

    m.emplace_back(*i, *j);

apl13

Лучше http://en.cppreference.com/w/, мне кажется.
Более новый и глубокий, хотя статей гораздо меньше, конечно.

apl13

for (auto i = v1.begin j = v2.begin; i != v1.end; ++i, ++j)
m.push_back(make_pair(*i, *j;

Фу.
Хоть бы

std::transform(i.cbegin i.cend j.cbegin m.begin [](int i, int j){return std::make_pair(i, j);});

vlad88

Кстати, если уж на то пошло, чтобы восполнить пробелы в области алгоритмов, как правильно сформулированная мною задача называется?

Sorting two corresponding arrays - вполне ок название. По-русски будет примерно так: "Сортировка двух связанных массивов".
з.ы. я в таких случаях всегда делал структурку (с реализованным сравнением) и сортировал вектор структур. Получалось и коротко, и наглядно.

jakal222

хм, а точно хочешь stl использовать? всякие бусты не помогут?
тут уже все много описали, так что я бы только добавил, что в с++11 есть еще и std::array, но применение его сомнительно в твоей ситуации (2^20 ~~~ 10^6 элементов)

Оставить комментарий