c++ - 地图迭代器与手动

Question

我试图比较两种填充地图的技术，一种使用迭代器，一种没有。我听说迭代器使它更快，但是如何？

//With Iterator
map<int, int>::iterator insert = fibHash.begin();
fibHash.insert(begin, pair<int, int> (n, fib_val));

//Without iterator
fibHash.insert(pair<int, int> (n, fib_val));

Answer 1

首先，您必须记住这std::map是一个有序结构，因此您不能将元素放置在任意位置。根据严格的弱排序关系（满足某些条件的小于关系），某个元素只能相对于其他元素放置在某个位置。

第一个变体将迭代器作为元素良好位置的提示，并且只有在插入发生在输入迭代器旁边时才使插入更快（摊销常数时间）。否则，复杂度与第二个变体（对数）相同。

第一个变体使用第一个参数作为提示，并尝试插入。如果提示很好，则需要较少的比较来找到插入的正确位置。

Answer 2

第一种形式，您提供一个迭代器，在运行时有可能更快——但前提是您选择了一个好的迭代器，即使这样，也只有当您的实现使用提示时。您发送到的迭代器insert只是一个提示。 insert不一定要在那里插入元素，因为 amap是一个排序容器。相反，实现可以将迭代器用作寻找将插入元素的位置的起点。

因此，如果您将一个精心挑选的迭代器（begin()通常不会）传递给它，使用带有insert提示迭代器的版本，理论上您可以接近插入的摊销常数时间，而使用您正在寻找的非提示版本在O(log n)插入。

Answer 3

添加到已经说过的内容：如果您关心速度，还可以考虑使用新的 C++11 方法std::map ::emplace和std::map::emplace_hint将元素插入到std::map. emplace 不会将 Key/Value 对的副本传递给容器，而是仅传递用于在正确位置就地创建该对的参数。这可以为您节省昂贵的副本（尽管在您的 int,int 示例中，这与矩阵等较大的数据结构相比并没有太大的区别）。

std::map<int,int> MyMap;
MyMap.emplace(5,10); // passing 5,10 to ctor of std::pair<const int,int> in-place
MyMap.insert(std::pair<const int,int>(5,10)); // construct a std::pair<const int,int> and pass it to insert, such that it creates a copy in the right location within the map

//similarly with the 'hint' methods
MyMap.emplace_hint(MyMap.end(),6,20);
MyMap.insert(MyMap.end(),std::pair<const int,int>(6,20));

顺便说一句，std::map<int,int>::value_type真的是一个std::pair<const int,int>，而不是一个std::pair<int,int>。

Answer 4

迭代器是一种设计模式，所有程序员都应该考虑到这一点。是的，迭代器并不是真的更快，但更干净，它们允许您以安全和干净的方式“迭代”数据结构，因此您不必担心会弄乱真实信息。

在这种特殊情况下，您一次只插入一个值，因此迭代器并不是真正“最快”的解决方案，只是某些函数也可以使用它。

在您的第一个示例中，您在数据结构的“开始”处插入一个值，并且迭代器正在帮助您确定位置。

在第二个中，您只是在末尾或默认插入位置插入值，因此您实际上不需要迭代器。