c++ - std::map 的插入提示是否有任何位置限制？

Question

我刚刚发现 std::map.insert 可以接受一个迭代器作为其第一个参数作为插入过程的搜索提示，例如 map.insert(hintIterator, insertElement);。但是提示元素有位置要求吗？它需要在插入位置之前还是之后？顺便问一下，提示迭代器位置对插入效率有多大影响？

Answer 1

它可以是 begin() 中的任何位置至end() .如果传入与理想插入位置相对应的迭代器，则可以大大提高搜索正确位置的插入成本。

来自 SGI STL网站

Complexity guarantees

Insert with hint is logarithmic in general, but it is amortized constant time if t is inserted immediately before p.

要了解为什么会这样，请考虑正在应用的算法。 std::map具有按某种顺序排列的项目，并且为了找到正确的插入点，必须遍历项目，直到找到一个位置(“A”)必须在新数据之前并且下一个项目(“B”)必须跟着它。预先给定这个位置，可以消除搜索。

新数据必须在这两项之间进行，并更新它们之间的链接。至少(对于可向前迭代的容器)项目 A 必须更新为指向新数据，该数据随后指向 B。如果包含的内容是可反向迭代的，则 B 也必须更新为指向新数据。

应该如何指定位置？必须知道 A 或 B。正如 Cubbi 指出的，并在 alt.comp.lang.learn.c-cpp 上讨论过2003 标准在提示应该是什么方面有所不同。 SGI 文档建议 B 是需要的，而标准建议 A。可能(假设 std::map 具有双向迭代器)这并不重要。不过，我建议较低项目 (A) 的位置最好，因为您始终可以期望能够继续向前搜索。

更新:由于有根据的猜测在得到验证之前是无用的，所以这里有一个快速测试:

#include <ctime>
#include <map>
#include <iostream>

int main() {
    typedef std::map<unsigned int,unsigned int> map;

    const unsigned int k=100000;
    const unsigned int reps=10;

    // Avoid edge cases by padding either end
    map srcMap;
    {
        for(unsigned int i=0; i!=k;++i) {
            srcMap.insert(std::make_pair(i,i));
        }
        unsigned int l=3*k;
        for(unsigned int i=2*k; i!=l;++i) {
            srcMap.insert(std::make_pair(i,i));
        }
    }

    std::cout << "Hint is always the position of the preceding value\n";
    for(unsigned int i=0; i!=reps;++i)
    {
        map testMap(srcMap);
        map::iterator p=testMap.lower_bound(k-1);
        unsigned int l=2*k;
        std::clock_t start = std::clock();
        for(unsigned int i=k; i!=l;++i) {
            p=testMap.insert(p,std::make_pair(i,i));
        }
        std::clock_t end = std::clock();
        std::cout << static_cast<double>((end - start) ) << " ";
    }
    std::cout << std::endl;

    std::cout << "Hint is always the position of the following value\n";
    for(unsigned int i=0; i!=reps;++i)
    {
        map testMap(srcMap);
        map::iterator p=testMap.lower_bound(2*k);
        unsigned int l=k-1;
        std::clock_t start = std::clock();
        for(unsigned int i=2*k-1; i!=l;--i) {
            p=testMap.insert(p,std::make_pair(i,i));
        }
        std::clock_t end = std::clock();
        std::cout << static_cast<double>((end - start) ) << " ";
    }
    std::cout << std::endl;

    std::cout << "Hint is always the start of the container\n";
    for(unsigned int i=0; i!=reps;++i)
    {
        map testMap(srcMap);
        unsigned int l=2*k;
        std::clock_t start = std::clock();
        for(unsigned int i=k; i!=l;++i) {
            testMap.insert(testMap.begin(),std::make_pair(i,i));
        }
        std::clock_t end = std::clock();
        std::cout << static_cast<double>((end - start)) << " ";
    }
    std::cout << std::endl;

    std::cout << "No hint\n";
    for(unsigned int i=0; i!=reps;++i)
    {
        map testMap(srcMap);
        unsigned int l=2*k;
        std::clock_t start = std::clock();
        for(unsigned int i=k; i!=l;++i) {
            testMap.insert(std::make_pair(i,i));
        }
        std::clock_t end = std::clock();
        std::cout << static_cast<double>((end - start)) << " ";
    }
    std::cout << std::endl;

    return 0;
}

在我运行 MinGW GCC 4.5 的小上网本上，我得到了:

Hint is always the position of the preceding value
94 109 109 109 109 109 110 110 110 94
Hint is always the position of the following value
109 94 109 94 110 110 109 109 110 110
Hint is always the start of the container
188 172 172 187 172 172 235 187 172 187
No hint
172 171 172 172 172 172 172 172 171 172

所以我想说，任何一方的提示都会产生大致相同的结果，而且总比没有提示要好。选择一个糟糕的提示位置(例如开始)比没有提示更糟糕。