选择具有唯一性并保持插入顺序的STL容器

Question

在以下情况下，我无法决定使用哪个 STL 容器：

1. 我想保留元素的插入顺序
2. 容器中的元素必须是唯一的。

有没有现成的容器可用于此？ 我不想使用向量，然后在每次执行 push_back 之前执行 std::find 。

Answer 1

Boost MultiIndex 应该能够完全满足您的要求 - 您只需使用一个排序索引即可满足“按插入顺序排序”的要求，以及 hashed_unique 或 ordered_unique 索引以获得唯一性要求。

Answer 2

可能有一种很好的内置方法可以做到这一点，但一种相当简单的方法是同时使用 hash_map 和列表。 每次插入之前检查 hash_map，然后插入到两者中。 您可能希望将其封装在一个类中。

Answer 3

没有标准库容器可以直接提供您想要的内容。 我将从 std::vector 开始，编写一个自由函数来执行插入操作，为您执行 find 和 push_back 操作。 如果这就足够了，就不要再继续了。 如果您遇到性能问题，请考虑更复杂的解决方案。

Answer 4

您可以这样做：

• 使用两个成员围绕您的元素类创建一个包装器：您的元素和索引。 我们称之为“InsertedElement”。 索引将是插入顺序。

• 为此类定义比较运算符，它仅考虑您的元素，但不考虑索引。 这将确保元素的唯一性，同时记住它们的插入顺序。

• 将 std::set 和插入计数器包装在另一个类中。 然后，当您想要插入新元素时，可以：

• 它已经存在，无需执行任何操作。
• 它不会：将其插入到地图中，同时为其指定当前最大索引 + 1。

类似于：

class CMagicContainer
{
  public:
    std::set<InsertedElement> collection;
    int indexGenerator;

    ...
};

Answer 5

在您选择的容器（例如列表、向量、双端队列）上实现一个包装类，并重写insertion/push_back 方法以在插入元素之前检查插入的元素是否唯一。

不幸的是，我不知道任何 STL 容器符合您的标准。

Answer 6

正如其他人所说，没有任何一个 STL 容器可以做到这一点。 我喜欢尼尔·巴特沃斯的回答。 另一种选择是同时使用集合和向量。 当你去插入时，检查该元素是否在集合中。 如果是，则无法插入，因为这会违反您的唯一性要求。 如果不是，请将其添加到集合中，然后将其插入向量中。 这很容易实现并且可以包装到单个类中。 代价是增加了内存开销。 但是，您可以通过在单个向量上进行查找来换取增加的计算时间。 这完全取决于您在问题域中处理的数据量以及您的时间和内存限制（如果有）。

Answer 7

如果您已经安装了 boost，我喜欢这个选项。 否则，为什么不只使用列表或向量并在插入时添加检查 (find(k) == std::npos) 呢？ 我想在一个非常非常大的列表上它可能会变得有点慢，但在大多数情况下它会工作得很好。

Answer 8

嗯，我曾经有过类似的情况。 我想到的一件事是“我可以使用多键”吗？ 我用谷歌搜索了一段时间，找到了一个使用 std::set 的示例。 所以，如果你无法使用 boost（我推荐它，没有必要重新发明轮子）； 你可以尝试类似下面的例子。 我认为你可以使用辅助键作为插入位置（自动增量）。 从我在互联网上找到的例子； 我根据我的需要定制了它。 这是同一版本的修改版本。

Cavaet：它使用宏。 我知道它们通常是邪恶的，但我想这种用途是可以的。

#include <set>
#include <functional>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <string>

#define MULTIKEYDEF(NAME,TYPE) \
    inline TYPE const & NAME() const { return d_##NAME; } \
    inline void NAME(TYPE const & t) { d_##NAME = t; } \
    TYPE d_##NAME; \
class T##NAME \
    : public std::unary_function<Tmultikey*,bool> { \
private: \
    TYPE d_compare; \
public: \
    T##NAME(TYPE t) : d_compare(t) {} \
    T##NAME(T##NAME const & self) \
    : d_compare(self.d_compare) {} \
    bool operator()(Tmultikey * mk) { \
    return d_compare == mk->##NAME(); \
    } \
   inline TYPE const& name() const { return d_compare; } \
    }

class Tmultikey {
public:
    // Actual keys
    // Can be accessed through d_primary and d_secondary,
    // or primary() and secondary()
    MULTIKEYDEF(primary , std::string);
    MULTIKEYDEF(secondary, unsigned int);
    // Mandatory
    bool operator < (Tmultikey const& mk) const {
        if(primary() < mk.primary()) return true;
        else if(primary() == mk.primary()) {
            return secondary() < mk.secondary();
        }
        return false;
    }
    // Constructor
    Tmultikey(std::string p, unsigned int s)
        : d_primary(p), d_secondary(s) {}

    // Eraser for std::set
    template<typename Compare>
        static void erase(std::set<Tmultikey> & c, Compare op) {
            typename std::set<Tmultikey>::iterator pos = c.begin();
            while(pos != c.end()) {
                if(op(&(*pos))) {
                    c.erase(pos++);
                } else ++pos;
            }
        }
      // Eraser for std::set
      template<typename Compare>
      static std::set<Tmultikey>::iterator find_ex(std::set<Tmultikey> & c, Compare op) {
         typename std::set<Tmultikey>::iterator pos = c.begin();
         while(pos != c.end()) {
            if(op(&(*pos))) {
               break;
            } else ++pos;
         }
         return pos;
      }
};

int main(int argc, char* argv[])
{
    std::set<Tmultikey> mkset;

    mkset.insert(Tmultikey("1",5));
    mkset.insert(Tmultikey("6",4));
    mkset.insert(Tmultikey("3",7));
    mkset.insert(Tmultikey("1",6));

   std::set<Tmultikey>::iterator bg = mkset.begin();
   for (;bg != mkset.end(); ++bg)
   {
      std::cout<<(*bg).primary()<<std::endl;
   }

    Tmultikey::erase(mkset,Tmultikey::Tsecondary(4));
    //Tmultikey::erase(mkset,Tmultikey::Tprimary("1"));

   std::cout<<"After erase ....\n";
   bg = mkset.begin();
   for (;bg != mkset.end(); ++bg)
   {
      std::cout<<(*bg).primary()<<std::endl;
   }
   bg = mkset.find(Tmultikey("3",7));
   if (bg != mkset.end())
   {
      std::cout<<"Absolute Find:"<<(*bg).primary()<<" "<<(*bg).secondary()<<std::endl;
   }
   //bg = Tmultikey::find_ex(mkset,Tmultikey::Tprimary("1"));
   bg = Tmultikey::find_ex(mkset,Tmultikey::Tsecondary(5));
   if (bg != mkset.end())
   {
      std::cout<<"Partial Find:"<<(*bg).primary()<<" "<<(*bg).secondary()<<std::endl;
   }
   else {
      std::cout<<"Partial Find: FAILED\n";
   }

   return 0;
}

哈特哈，