问题 对std :: map的插入提示有任何位置限制吗？


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


3628
2017-12-03 03:29


起源

答案:

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

来自 SGI STL 现场

复杂性保证

带提示的插入是对数的   一般，但它是摊销不变的   如果t立即插入的时间   在p之前。

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

新数据必须介于这两个项目之间，并更新它们之间的链接。至少（对于可向前迭代的容器），必须更新项目A以指向新数据，该数据随后指向B.如果包含的是反向可迭代的，则还必须更新B以指向新数据。

应该如何指定位置？人们必须知道A或B是枯萎的。正如Cubbi指出的那样，并进行了讨论 alt.comp.lang.learn.c-CPP 2003标准在暗示应该是什么上有所不同。 SGI文件表明B是需要的，而标准建议A.可能（鉴于此 std::map 有bidriectional迭代器）没关系。不过，我建议较低的项目（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的小上网本上，我得到了：

提示始终是前一个值的位置
     94 109 109 109 109 109 110 110 110 94
     提示始终是以下值的位置
     109 94 109 94 110 110 109 109 110 110
     提示始终是容器的开始
     188 172 172 187 172 172 235 187 172 187
     没有提示
     172 171 172 172 172 172 172 172 171 172

所以我要说任何一方的暗示都给出了相同的结果，并且总是好于没有任何暗示。选择一个糟糕的提示位置（例如开始）比没有提示更糟糕。


11
2017-12-03 03:41


如果在p之后立即插入t，它是否摊销了恒定时间？ - Thomson
@Thomson-tan：是的，应该是相同的，并且可能在p之后插入更好。查看更新的答案。 - beldaz
@Thomson-tan：看起来没有区别 - 请参阅更新后答案中的数字。 - beldaz

答案:

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

来自 SGI STL 现场

复杂性保证

带提示的插入是对数的   一般，但它是摊销不变的   如果t立即插入的时间   在p之前。

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

新数据必须介于这两个项目之间，并更新它们之间的链接。至少（对于可向前迭代的容器），必须更新项目A以指向新数据，该数据随后指向B.如果包含的是反向可迭代的，则还必须更新B以指向新数据。

应该如何指定位置？人们必须知道A或B是枯萎的。正如Cubbi指出的那样，并进行了讨论 alt.comp.lang.learn.c-CPP 2003标准在暗示应该是什么上有所不同。 SGI文件表明B是需要的，而标准建议A.可能（鉴于此 std::map 有bidriectional迭代器）没关系。不过，我建议较低的项目（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的小上网本上，我得到了：

提示始终是前一个值的位置
     94 109 109 109 109 109 110 110 110 94
     提示始终是以下值的位置
     109 94 109 94 110 110 109 109 110 110
     提示始终是容器的开始
     188 172 172 187 172 172 235 187 172 187
     没有提示
     172 171 172 172 172 172 172 172 171 172

所以我要说任何一方的暗示都给出了相同的结果，并且总是好于没有任何暗示。选择一个糟糕的提示位置（例如开始）比没有提示更糟糕。


11
2017-12-03 03:41


如果在p之后立即插入t，它是否摊销了恒定时间？ - Thomson
@Thomson-tan：是的，应该是相同的，并且可能在p之后插入更好。查看更新的答案。 - beldaz
@Thomson-tan：看起来没有区别 - 请参阅更新后答案中的数字。 - beldaz

从 唯一排序关联容器 概念：

具有提示的插入通常是对数的，但如果在p之前插入t，则它是分摊的常量时间。

只有这个提示迭代器：

争论 p 是一个提示：它指向搜索开始的位置。

1
2017-12-03 03:38



热门问题

不使用eval / new函数的JavaScript模板库 当涉及内部类时，Java继承如何工作 .NET Windows服务的奇怪问题 在.ipa或.app下查找App ID 快速入门XSLT参考[关闭] 如何找出Android应用程序中未使用的资源 Ruby中并发的同步方法[重复] 将std :: chrono :: system_clock :: time_point转换为struct timeval并返回 Google Drive API V3（javascript）更新文件内容 Bootstrap 3.0 - 将元素推到底部 受密码保护的.NET ClickOnce部署？ 如何用postgresql安装wordpress coq Set或Type如何成为命题 硒滚动元素进入（中心）视图 在Spring Transaction JUnit测试中自动装配Hibernate会话的正确方法 Git的Dockerfile策略 如何在FOS_PICKFOLDER中使用IFileDialog，同时仍在对话框中显示文件名 在Firefox扩展中复制Google Chrome浏览器操作弹出效果 CakePHP找到MAX 芹菜 - 完成任务的召唤功能 从使用fmemopen创建的流中读取宽字符 .NET是否为每个程序集创建一个字符串实习池？ DefaultModelBinder不绑定嵌套模型 Navigator.MediaDevices.getUserMedia（）使用了哪些相机通信标准？ 选择命名空间名称时应该知道什么？ cout Swagger Codegen CLI Java客户端 - 如何正确使用它 一个很好的哈希函数用于采访整数，字符串？ Maven 3 ciManagement配置的目的是什么？ 如何通过语言文化获取代码页？
licensed under cc by-sa 3.0 with attribution.
隐私政策 往来