需要按插入顺序设置STL

Question

如何以插入顺序存储集合中的元素.例如.

set<string>myset;

myset.insert("stack");
myset.insert("overflow");

如果你打印,输出是

overflow
stack

需要的输出:

stack
overflow

Answer 1

一种方法是使用两个容器,a std::deque用于按插入顺序存储元素,另一种方法是std::set确保没有重复.

插入元素时,检查它是否在set第一个元素中,如果是,则将其丢弃; 如果不存在,请将其插入deque和set.

一种常见的情况是首先插入所有元素,然后处理(不再插入),如果是这种情况,set可以在插入过程之后释放.

Answer 2

Aset是保持插入顺序的错误容器，它会根据排序标准对其元素进行排序并忘记插入顺序。为此，您必须使用排序容器，例如 vector、deque 或 list。如果您还需要关联访问set，则必须同时将元素存储在多个容器中，或者使用非 STL 容器，如boost::multi_index，它可以同时维护多个元素顺序。

PS：如果您在将元素插入集合之前对元素进行排序，则集合会将它们按插入顺序排列，但我认为这不会解决您的问题。

如果除了插入顺序之外不需要任何顺序，您还可以将插入编号存储在存储元素中并将其作为排序标准。但是，为什么在这种情况下会使用 set 完全让我无法理解。;)

Answer 3

我是这样做的：

template <class T>
class VectorSet
{
public:
  using iterator                     = typename vector<T>::iterator;
  using const_iterator               = typename vector<T>::const_iterator;
  iterator begin()                   { return theVector.begin(); }
  iterator end()                     { return theVector.end(); }
  const_iterator begin() const       { return theVector.begin(); }
  const_iterator end() const         { return theVector.end(); }
  const T& front() const             { return theVector.front(); }
  const T& back() const              { return theVector.back(); }
  void insert(const T& item)         { if (theSet.insert(item).second) theVector.push_back(item); }
  size_t count(const T& item) const  { return theSet.count(item); }
  bool empty() const                 { return theSet.empty(); }
  size_t size() const                { return theSet.size(); }
private:
  vector<T> theVector;
  set<T>    theSet;
};

当然，可以根据需要添加新的转发功能，并且可以转发到两个数据结构中实现效率最高的一个。如果您打算在这方面大量使用 STL 算法（到目前为止我还不需要），您可能还想定义 STL 期望找到的成员类型，例如 value_type 等。