c++ - C++ 标准库是否有按插入顺序排序的集合？

Question

C++ 标准库是否具有“有序集”数据结构？所谓有序集合，我的意思是与普通集合完全相同，std::set但会记住您添加项目的顺序。

如果没有，模拟一个的最佳方法是什么？我知道你可以做一些事情，比如有一组对，每对存储它添加的数字和实际值，但如果有更简单的解决方案，我不想跳过箍。

Answer 1

没有一个单一的、同质的数据结构将具有此属性，因为它要么是顺序的（即元素按插入顺序排列），要么是关联的（元素根据值按某种顺序排列）。

最好的、干净的方法可能是Boost.MultiIndex之类的，它允许您在容器上添加多个索引或“视图”，因此您可以拥有顺序和有序的索引。

Answer 2

与其制作您正在使用的任何类型的 std::set，为什么不将对象的 std::pair 和在每次插入时递增的索引传递给它呢？

Answer 3

不，不是的。

这样的容器可能需要两个不同的迭代器，一个以添加顺序定义的顺序进行迭代，另一个以通常的set顺序进行迭代。标准库中没有这种东西。

模拟它的一个选项是set，除了您关心的实际数据之外，还有一个包含侵入式链表节点的类型。向 中添加元素后set，将其附加到链表中。在从 中删除元素之前set，将其从链表中删除。这保证没问题，因为指向设置元素的指针不会被除删除该元素之外的任何操作无效。

Answer 4

我认为答案相当简单，将集合与另一个可迭代结构（比如队列）结合起来。如果您想按照元素插入的顺序迭代集合，请先将元素推入队列，对最前面的元素进行处理，然后弹出，放入集合中。

Answer 5

[免责声明：我已经对这个问题给出了类似的答案]

如果可以使用 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;
  }
}

需要使用时髦的类型别名 ininsertByOrder()将元素插入到boost::bimap以下行中的 a 中（请参阅参考文档）。

Answer 6

是的，它被称为向量或列表（或数组）。只需附加到向量即可将元素添加到集合中。