Алгоритмы обхода коллекции в отсортированном порядке без изменения коллекции?

Question

Допустим, у нас есть коллекция, подобная следующей: {12, 10, 4, 5, 7}

Я бы хотел сохранить порядок коллекции, чтобы индексы оставались неизменными, но проходить через коллекцию в отсортированном порядке, например {12, 10, 7, 5, 4}.

Я подумал о том, чтобы создать еще одну коллекцию указателей на элементы и затем отсортировать указатели.

Что ты думаешь? Был ли такой алгоритм реализован в C ++?

Редактировать: В моем случае, у меня есть vector<vector<double>>, и я хотел бы перебрать коллекцию внешних векторов в неубывающем порядке на основе суммы внутренних векторов.

Answer 1

Не уверен, каковы ваши ограничения времени выполнения / памяти, но самое простое и практичное решение IMHO - просто вставить все элементы из std::vector в std::multiset и просто пройти multiset от начала до конца. Общее время выполнения будет O (n * log (n)) и потребует O (n) дополнительной памяти для multiset.

#include <set>
#include <vector>
#include <iostream>

using namespace std;

int main()
{
    vector<int> data;
    data.push_back(12);
    data.push_back(10);
    data.push_back(4);
    data.push_back(5);
    data.push_back(7);
    multiset<int> sorted(data.begin(), data.end());
    for (multiset<int>::iterator it=sorted.begin();it!=sorted.end();it++)
        cout<<*it<<" ";
    cout<<endl;

    for(vector<int>::iterator it=data.begin();it!=data.end();it++)
        cout<<*it<<" ";
    cout<<endl;
    return 0;
}

Answer 2

Вы можете сохранить значения индекса в массиве, а затем написать / адаптировать алгоритм сортировки, который сортирует значения индекса на основе того, что они индексируют в исходном массиве.

Answer 3

Если вы хотите, чтобы оба ордера были постоянными, а элементы добавлялись и удалялись, вы можете использовать мультииндекс надстройки:

http://live.boost.org/doc/libs/1_34_0/libs/multi_index/doc/tutorial/basics.html#multiple_sort

Этот пример с этой страницы очень похож на тот, который вы хотите, за исключением того, что он отсортирован в обратном порядке:

multi_index_container<
  int,
  indexed_by<
    sequenced<>,           // sequenced type
    ordered_unique<identity<int> > // another index
  >
> s;

Если вы хотите использовать его как разовую операцию, ваша идея сортировки указателей звучит хорошо. В качестве небольшого варианта вы можете создать вектор std::pair<int,size_t>, каждая пара которого состоит из значения, за которым следует его индекс. Затем отсортируйте вектор пар с помощью std::sort и укажите std::greater<std::pair<int,size_t> > в качестве компаратора.

Edit:

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

typedef vector<vector<double> >::const_iterator It;
typedef pair<double, It> Pair; 

vector<Pair> pairvec;
pairvec.reserve(input.size());

for (It it = input.begin(); it != input.end(); ++it) {
    // some people would split this over multiple lines
    pairvec.push_back(make_pair(accumulate(it->begin(), it->end(), 0.0), it));
}

sort(pairvec.begin(), pairvec.end(), greater<Pair>());

Тогда вы можете перебрать парочку. Сделайте It неконстантным итератором, если вам нужно.

Answer 4

Один из способов сделать это (для связанного списка) состоит в том, чтобы поддерживать два уровня указателей: один для исходного порядка, а второй для спуска, как в

typedef struct node{
    int key;
    struct node* next;
    struct node* next_descending;
};