Имеется ли в стандартной библиотеке С++ "упорядоченный набор" datastructure? По упорядоченному набору я имею в виду то, что в точности совпадает с обычным std::set, но помнит порядок, в который вы добавили элементы к нему.
Если нет, то какой способ имитировать? Я знаю, что вы могли бы сделать что-то вроде набора пар с каждой парой, сохраняя число, в которое оно было добавлено, и фактическое значение, но я не хочу прыгать через обручи, если есть более простое решение.
Ни одна однородная структура данных не будет обладать этим свойством, поскольку она либо последовательна (т.е. элементы расположены в порядке вставки), либо ассоциативно (элементы расположены в некотором порядке в зависимости от значения).
Лучший, чистый подход мог бы быть чем-то вроде Boost.MultiIndex, который позволяет добавлять несколько индексов или "взгляды" на контейнер, поэтому вы можете иметь последовательный и упорядоченный индекс.
Вместо того, чтобы создавать std:: set любого типа, который вы используете, почему бы не передать ему std:: пару объекта и индекс, который увеличивается при каждой вставке?
Нет, это не так.
Такой контейнер, по-видимому, должен был бы иметь два разных итератора, один для итерации в порядке, определяемом порядком добавления, а другой для итерации в обычном порядке set. Там нет ничего подобного в стандартных библиотеках.
Один из вариантов имитации заключается в том, чтобы иметь set какого-либо типа, который содержит навязчивый связанный список node в дополнение к фактическим данным, которые вас волнуют. После добавления элемента в 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 в следующей строке (см. boost::bimap документацию).
Да, он называется вектором или списком (или массивом). Просто присоединяется к вектору, чтобы добавить элемент в набор.