Есть ли в стандартной библиотеке С++ структура данных "упорядоченный набор"? Под упорядоченным набором я подразумеваю то же самое, что и обычный std::set, но который запоминает порядок, в котором вы добавляли в него элементы.
Если нет, то как лучше всего смоделировать его? Я знаю, что вы могли бы сделать что-то вроде набора пар, где каждая пара хранит число, в которое она была добавлена, и фактическое значение, но я не хочу прыгать через обручи, если есть более простое решение.
Ни одна однородная структура данных не будет обладать этим свойством, так как она либо последовательная (т.е. элементы располагаются в порядке вставки), либо ассоциативна (элементы располагаются в некотором порядке в зависимости от значения).
Лучшим, чистым подходом, возможно, будет что-то вроде Boost.MultiIndex, который позволяет вам добавлять несколько индексы или «представления» в контейнере, поэтому вы можете иметь последовательный и упорядоченный индекс.
Вместо создания std::set любого типа, который вы используете, почему бы не передать ему пару std::: объект и индекс, который увеличивается при каждой вставке?
std::map<T, unsigned int> был бы немного более элегантным, так как его тип значения уже является парой (и вы получаете изменяемые отображаемые элементы).
- person Kerrek SB; 18.10.2011
map::size, чтобы найти самый большой индекс, верно?
- person Seth Carnegie; 18.10.2011
size(), я об этом не подумал!
- person Kerrek SB; 18.10.2011
map<T, unsigned int>, это операция O(n) для поиска элемента с заданным индексом. Итерация в порядке вставки O(n^2) без дополнительной памяти или O(n log n) с O(n) дополнительной памятью, если вы копируете всю партию в массив и сортируете перед итерацией. Может и подойдет для целей Сета, но довольно ограничительно...
- person Steve Jessop; 18.10.2011
Нет.
Предположительно, такому контейнеру потребуются два разных итератора: один для итерации в порядке, определяемом порядком добавления, а другой для итерации в обычном порядке set. В стандартных библиотеках ничего подобного нет.
Один из вариантов симуляции — иметь set некоторого типа, который содержит навязчивый узел связанного списка в дополнение к фактическим данным, которые вас интересуют. После добавления элемента в set добавьте его в связанный список. Прежде чем удалять элемент из set, удалите его из связанного списка. Это гарантированно будет в порядке, так как указатели на установленные элементы не становятся недействительными ни при каких операциях, кроме удаления этого элемента.
Я думал, что ответ довольно прост: объединить набор с другой итерируемой структурой (скажем, с очередью). Если вы хотите повторять набор в том порядке, в котором элемент был вставлен, сначала поместите элементы в очередь, выполните свою работу над передним элементом, а затем вытащите его и поместите в набор.
[Отказ от ответственности: я дал аналогичный ответ на этот вопрос уже]
Если вы можете использовать Boost, очень простым решением будет использование библиотеки только для заголовков Boost.Bimap (двунаправленные карты).
Рассмотрим следующий пример программы, которая будет отображать некоторые фиктивные записи в порядке вставки (попробуйте здесь ):
#include <iostream>
#include <string>
#include <type_traits>
#include <boost/bimap.hpp>
using namespace std::string_literals;
template <typename T>
void insertByOrder(boost::bimap<T, size_t>& mymap, const T& element) {
using pos = typename std::remove_reference<decltype(mymap)>::type::value_type;
// We use size() as index, therefore indexing the elements with 0, 1, ...
mymap.insert(pos(element, mymap.size()));
}
int main() {
boost::bimap<std::string, size_t> mymap;
insertByOrder(mymap, "stack"s);
insertByOrder(mymap, "overflow"s);
// Iterate over right map view (integers) in sorted order
for (const auto& rit : mymap.right) {
std::cout << rit.first << " -> " << rit.second << std::endl;
}
}
Псевдоним фанк-типа в insertByOrder() необходим для вставки элементов в boost::bimap в следующей строке (см. ссылочную документацию).
Да, это называется вектором или списком (или массивом). Просто добавляется к вектору, чтобы добавить элемент в набор.
setвас интересуют? Уникальность? Производительность удаления? - person Robᵩ schedule 18.10.2011