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

问题描述：

Before marking this as duplicate, I have been here, here, and here, a duplicate of the first.

我知道 boost::multi_index，并使用我缺少它的环境，并且 std::unordered_set 没有绑定到将元素存储在确定性插入顺序.

I'm aware of boost::multi_index, and use an environment where I lack it, and that a std::unordered_set is not bound to store elements in a deterministic insertion order.

我发现使用两个容器的概念，比如额外的 std::vector 是粗俗的.

I find the concept of using two containers, say an additional std::vector as uncouth.

我喜欢是一个涉及比较器的解决方案，我可以在 std::set 的模板参数中使用它(澄清，这可能是一个微不足道的函子struct，包含 bool operator()() 重载、常规函数或 lambda).可能吗?

What I would love is a solution involving a comparator that I can use in a std::set's template parameters (clarification, this could be a trivial functor struct, containing a bool operator()() overload, a regular function, or a lambda). Is it possible?

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

Initialization must occur through a std:: container's begin iterator/end iterator constructor, such as in this snippet.

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

另外，另一个有趣的用例是创建一个愚蠢的哈希包装函子，它允许将插入顺序推送到 std::unordered_set 的模板参数中.p>

答

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

You cannot directly have a lambda expression as the set's template parameter, because a lambda expression is a value, and the set's template parameter is a type. The obvious correction of the question, whether a construction using a lambda and decltype can work, leads to the interesting problem that a lambda expression denotes a unique type (a "closure type"), so you can never make two separate lambda expressions of the same closure type.*

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

However, in a more abstract sense what you want can be achieved in a local context using template argument deduction, for example:

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:

Now you can call f with a lambda expression as the argument, thus effectively "using a lambda as the set's comparator". Or, for a simpler example, you could just have a named variable for the lambda (putting all the template deduction into a single auto:

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

_{*) 有一项提议允许在未评估的上下文中使用 lambda 来解决这一点，但其前景尚不确定.它有一些有趣的副作用，比如让闭包类型影响名称修改.}

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

相关推荐