c++ - 在 std::set 或 std::unordered_set 上保留插入顺序

Question

在将此标记为重复之前，我已经 here , here , 和 here, a duplicate of the first .

我知道 boost::multi_index ，并使用我缺少它的环境，那是一个 std::unordered_set不一定以确定的插入顺序存储元素。

我找到了使用两个容器的概念，再说一个 std::vector粗鲁。

我会喜欢的是一个涉及比较器的解决方案，我可以在 std::set 中使用它的模板参数(澄清一下，这可能是一个普通的仿函数结构，包含一个 bool operator()() 重载、一个常规函数或一个 lambda)。可能吗？

附录

1. 初始化必须通过 std::容器的开始迭代器/结束迭代器构造函数进行，例如在此代码段中。

   std::string str; cin >> str;
   std::set<char>(str.begin(), str.end());
   

2. 此外，另一个有趣的用例是创建一个哑哈希包装仿函数，允许将插入顺序插入 std::unordered_set 中。的模板参数。

Answer 1

您不能直接将 lambda 表达式作为集合的模板参数，因为 lambda 表达式是一个值，而集合的模板参数是一种类型。问题的明显更正，使用 lambda 和 decltype 的构造是否可行，导致了一个有趣的问题，即 lambda 表达式表示唯一类型(“闭包类型” "), 所以你永远不能创建相同闭包类型的两个单独的 lambda 表达式。*

但是，在更抽象的意义上，您可以使用模板参数推导在本地上下文中实现您想要的，例如:

template <typename F>
int f(int* first, int* last, F comp)
{
    std::set<int, F> s(comp);
    while (first != last) s.insert(*first++);
    ...
}

现在您可以使用 lambda 表达式作为参数调用 f，从而有效地“使用 lambda 作为集合的比较器”。或者，对于一个更简单的示例，您可以只为 lambda 命名变量(将所有模板推导放入单个 auto:

auto comp = [](...) { ... };
std::set<int, decltype(comp)> s(comp);

_{*) 有一项提案允许在未计算的上下文中使用 lambda 来解决这一点，但其前景不确定。它有一些有趣的副作用，例如使闭包类型影响名称修饰。}