c++ - 高效地将值插入 map 。更好的递增或递减键？

Question

我有一个按键按递减顺序排序的对 vector 。我想有效地将​​其转换为 map 。这是我目前所做的:

int size = vect.size();
for (int i = 0; i < size; i++)
    map[vect[i].key] = vect[i];

向后遍历 vector 并首先插入具有最低键的值是否有意义？我不确定插入在内部如何工作以及它是否重要......

如何使用 map 构造函数并将 vector 传递给它而不是循环？这将是重新创建 map ，而不是我目前在两次运行之间执行的 map.clear()。

我阅读了一些关于 [key]=val 与 insert() 大致相同但没有涉及插入顺序的其他 SO 答案。

Answer 1

std::map 通常实现为 Red-Black Tree .因此，增加或减少 key 并不重要。它仍将使用 O(log n) 执行搜索复杂性和再平衡。

要加快插入速度，您可以使用 insert或 emplace_hint带有“提示”，这是一个迭代器，用作关于在何处插入新元素的建议。

用范围构建 map 不会有什么不同。

如果不了解它所处理的程序和数据的详细信息，就很难为您推荐最好的数据结构。一般来说，RB 树是一般情况下最好的(这就是为什么它是 std::map 的选择实现)。

希望对您有所帮助。祝你好运!