Каков хороший способ * временной * сортировки вектора?

Question

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

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

Приветствия

Answer 1

Вы можете создать std :: vector, который будет содержать все индексы первого вектора. Затем вы можете отсортировать индексный вектор, как вам нравится. Это должно быть быстро и, самое главное, не означает, что вам нужно скопировать первый вектор (что, вероятно, дороже!).

Answer 2

Если вы не против немного Boost, вы можете использовать библиотеку MultiIndex. Посмотрите этот ответ от меня, где вы найдете пример кода.

По сути, это позволяет вам сохранять несколько «просмотров» одних и тех же данных, каждый в разном порядке. В вашем случае вы сможете сохранить представление «последовательность», в котором данные расположены в порядке вставки (например, вектор), и представление «сортировка», в котором данные сортируются в соответствии с некоторым критерием (например, карта) ,

Answer 3

Любой данный вектор будет отсортирован не более чем одним способом в любое время.

Есть две альтернативы:

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

В качестве альтернативы, вы могли бы сохранить способ (отметку времени, который вы упомянули?), Чтобы иметь возможность сортировать вектор обратно в исходный порядок. Это будет медленно, так как вы захотите сделать это, только если вектор был очень большим, но если вы не можете создать временный вектор, это единственный способ сделать это.

Answer 4

Я предлагаю хранить умные указатели, к исходным данным, в каждом vector. std::vector позволяет указывать разные методы сортировки. Кроме того, с помощью умных указателей они будут автоматически уничтожены при удалении всех ссылок на элемент.

Answer 5

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

struct someThing
{
    int sortOrder1;
    int sortOrder2;
    ...
    int sortOrderN;
    //payload data object here
} //note: this code may have some sytax errors (I haven't actually tried compiling this ;), but hope the idea is clear

(или, возможно, добавить порядки сортировки в саму базовую структуру?)

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