emplace_hint在地图中有什么用？

Question

我知道map :: emplace_hint用于在地图中的指定位置放置一个键值对,但最后地图会被排序,那么将它放在某个地方的重点是什么？例如,当我运行此代码时:

#include <iostream>
#include <map>
#include <unordered_map>

int main()
{
    std::map<char, int> mymap;
    auto it = mymap.end();
    std::unordered_map<char, int> mymap2;


    it = mymap.emplace_hint(it, 'b', 10);
    mymap.emplace_hint(it, 'z', 12);
    mymap.emplace_hint(mymap.end(), 'a', 14);
    mymap.emplace_hint(mymap.end(), 'c', 10);

    auto it2 = mymap2.end();
    it2 = mymap2.emplace_hint(it2, 'b', 10);
    mymap2.emplace_hint(it2, 'z', 12);
    mymap2.emplace_hint(mymap2.end(), 'a', 14);
    mymap2.emplace_hint(mymap2.end(), 'c', 10);


    std::cout << "mymap contains:";
    for (auto& x : mymap)
        std::cout << " [" << x.first << ':' << x.second << ']';
    std::cout << '\n';

    for(auto& y :mymap2)
        std::cout << " [" << y.first << ':' << y.second << ']';
    char c;
    std::cin >> c;
    return 0;
}

它给了我这个o/p:

mymap contains: [a:14] [b:10] [c:10] [z:12]
 [z:12] [b:10] [a:14] [c:10]

Answer 1

假设您只想在密钥不存在时才将元素插入到地图中.你当然可以调用insert,但进一步假设操作是昂贵的或不可逆的(例如从不可复制的对象移动).

在这种情况下,您需要将查找与插入分开.这就是提示的来源,并结合lower_bound:

auto it = m.lower_bound(key);

if (it != m.end() && it->first == key) {
  // key already exists
} else {
  m.insert(it, std::make_pair(key, compute_expensively()));
  // or:
  m.emplace_hint(it, key, compute_expensively());
}

诀窍是,lower_bound返回迭代器,其中的关键将是,如果它是在地图上,不管它是否确实是存在的.如果提示正确,则提示插入的时间复杂度是恒定的.

使用带有错误迭代器的暗示插入是没有意义的(即未获得作为给定键的下限的那个).

请注意,提示插入仅适用于有序关联容器.无序容器也提供那些重载,但它们没有效果,因为无法获得无序容器的有用提示.

Answer 2

我知道map :: emplace_hint用于在地图中的指定位置放置一个键值对

不,不是.

如你所说,你无法自己控制元素的位置.地图决定了这一点.

这个提示是告诉编译器你认为地图将决定放在哪里,这样地图就不必花费很长时间来解决它本身.

例如,如果您已经知道(因为这是您的程序!),某些新元素肯定会在地图的"开始"结束,那么您可以将这些知识传递到容器上.然后它只需要检查你是否正确,而不是扫描整个树,最终得出结论.

如果您的提示有误,那就不会改变元素最终的位置,但是您要为地图提供更多工作要做.