需要按插入顺序使用STL set。

Question

如何按插入顺序在集合中存储元素。 例如。

set<string>myset;

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

如果您选择打印，输出结果将会是：

overflow
stack

需要的输出：

stack
overflow

- Charan Rai

---

你能提供更详细的信息吗？ - Chase

你需要的是 #include <unordered_set> //std::unordered_set<std::string>。 - SSpoke

@SSpoke那是错误的。即使一个人不知道什么是无序集合，名称已经表明它不可能是一个解决方案 :-) - andreee

Answer 1

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

在插入一个元素时，首先检查它是否已经在 set 中，如果是，则将其抛弃；如果不在，就同时将它插入到 deque 和 set 中。

一种常见的情况是首先插入所有元素，然后处理它们（不再插入），如果是这种情况，则可以在插入过程之后释放 set。

- Yu Hao

Answer 2

一个 set 容器不适合保持插入顺序，它会根据排序标准对其元素进行排序并忘记插入顺序。您必须使用序列化容器，如 vector，deque 或 list。如果您还需要set提供的关联访问，您将不得不同时在多个容器中存储元素或使用非STL容器，如 boost::multi_index，它可以同时维护多个元素顺序。

附注：如果您在将元素插入 set 之前对其进行排序，则 set 将按照插入顺序保留它们，但我认为这并不解决你的问题。

如果除了插入顺序以外您不需要任何其他顺序，您还可以在存储的元素中存储插入数字，并将其作为排序标准。然而，在这种情况下为什么要使用 set 对我来说是无法理解的。 ;)

- Peter G.

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等。

- Some Guy

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 insertCallOrdered(boost::bimap<T, size_t>& mymap, const T& element) {
  // We use size() as index, therefore indexing with 0, 1, ... 
  // as we add elements to the bimap.
  mymap.insert({ element, mymap.size() });
}

int main() {
  boost::bimap<std::string, size_t> mymap;

  insertCallOrdered(mymap, "stack"s);
  insertCallOrdered(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;
  }
}

- andreee

Answer 5

我想知道为什么没有人建议使用如此好的Boost MultiIndex库。以下是一个示例，演示如何使用它：

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/indexed_by.hpp>
#include <boost/multi_index/identity.hpp>
#include <boost/multi_index/sequenced_index.hpp>
#include <boost/multi_index/ordered_index.hpp>

#include <iostream>

template<typename T>
using my_set = boost::multi_index_container<
    T,
    boost::multi_index::indexed_by<
        boost::multi_index::sequenced<>,
        boost::multi_index::ordered_unique<boost::multi_index::identity<T>>
    >
>;

int main() {
    my_set<int> set;
    set.push_back(10);
    set.push_back(20);
    set.push_back(3);
    set.push_back(11);
    set.push_back(1);
    
    // Prints elements of the set in order of insertion.
    const auto &index = set.get<0>();
    for (const auto &item : index) {
        std::cout << item << " ";
    }

    // Prints elements of the set in order of value.
    std::cout << "\n";
    const auto &ordered_index = set.get<1>();
    for (const auto &item : ordered_index) {
        std::cout << item << " ";
    }
}

- Deedee Megadoodoo

Answer 6

你需要的是这个，非常简单且标准库。示例在线编译器链接：http://cpp.sh/7hsxo。

#include <iostream>
#include <string>
#include <unordered_set> 
static std::unordered_set<std::string> myset;


int main()
{
    myset.insert("blah");
    myset.insert("blah2");
    myset.insert("blah3");

    int count = 0;
    for ( auto local_it = myset.begin(); local_it!= myset.end(); ++local_it ) {
          printf("index: [%d]: %s\n", count,  (*local_it).c_str());
          count++;
    }
    printf("\n");
    for ( unsigned i = 0; i < myset.bucket_count(); ++i) {
        for ( auto local_it = myset.begin(i); local_it!= myset.end(i); ++local_it )
              printf("bucket: [%d]: %s\n", i,  (*local_it).c_str());
    }
}

- SSpoke

---

无序集合，以随机顺序存储元素，那么它是如何解决问题的呢？ - UNREAL