Есть ли в стандартной библиотеке C ++ набор, упорядоченный по порядку вставки?

Question

Имеется ли в стандартной библиотеке C ++ структура данных "упорядоченный набор"?Под упорядоченным набором я подразумеваю нечто, точно такое же, как обычный std::set, но при этом запоминается порядок, в котором вы добавили к нему элементы.

Если нет, каков наилучший способ имитации?Я знаю, что вы могли бы сделать что-то вроде набора пар, каждая из которых хранит номер, в котором она была добавлена, и фактическое значение, но я не хочу прыгать через обручи, если есть более простое решение.

Answer 1

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

НаилучшееЧистый подход, возможно, будет выглядеть примерно так: Boost.MultiIndex , который позволяет вам добавлять несколько индексов или «представлений» для контейнера, чтобы вы могли иметь последовательный и упорядоченный индексы.

Answer 2

Вместо создания std :: set любого типа, который вы используете, почему бы не передать ему std :: pair объекта и индекс, который увеличивается с каждой вставкой?

Answer 3

Нет, это не так.

Для такого контейнера, вероятно, потребуются два разных итератора: один для итерации в порядке, определяемом порядком добавления, а другой для итерации в обычном порядке set.Ничего подобного в стандартных библиотеках нет.

Один из вариантов имитации - иметь set некоторого типа, который содержит навязчивый узел связанного списка в дополнение к фактическим данным, которые вас интересуют.После добавления элемента в set добавьте его в связанный список.Прежде чем удалять элемент из set, удалите его из связанного списка.Это гарантированно будет в порядке, поскольку указатели для установки элементов не аннулируются никакими операциями, кроме удаления этого элемента.

Answer 4

[Отказ от ответственности: я дал аналогичный ответ на этот вопрос уже]

Если вы можете использовать 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 в следующей строке (см. Ссылочную документацию).

Answer 5

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

Answer 6

Да, это называется вектор или список (или массив). Просто добавляет вектор, чтобы добавить элемент в набор.