c – 对std :: map的插入提示有什么位置限制吗？

从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,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(),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

所以我会说暗示在任何一方给出了相同的结果,总是比没有提示更好.选择一个不好的提示位置(比如开始)比没有提示更糟糕.