c++ - Is there any position limitation on the insert hint for std::map? -

i found std::map.insert accept iterator first parameter search hint insertion process, such map.insert(hintiterator, insertelement);. there position requirement hint element? need before or after insert position? way, how effect hint iterator position have on insertion efficiency?

it can anywhere begin() end(). if pass in iterator corresponding ideal insertion position can massively improve insertion cost searching correct location.

from sgi stl site

complexity guarantees

insert hint logarithmic in general, amortized constant time if t inserted before p.

to understand why is, think algorithm that's being applied. std::map has items arranged in order, , in order find correct insertion point items must walked through until finds position 1 item ("a") must precede new data , next item ("b") must follow it. given location in advance search can eliminated.

the new data has go between these 2 items, , update links between them. @ least (for forward-iterable containers) item must updated point new data, subsequently points b. if contained reverse-iterable, b must updated point new data.

how should location specified? 1 must know wither or b. cubbi points out, , discussed on alt.comp.lang.learn.c-cpp 2003 standard differs on hint should be. sgi documentation suggests b 1 needed, while standard suggests a. possibly (given std::map has bidriectional iterators) doesn't matter. suggest, though, position of lower item (a) best, since can expect able continue searching forwards.

update: since educated guesses useless until validated, here quick test:

#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 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 position of 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 position of 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 start of 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; } 

on little netbook running mingw gcc 4.5 got:

hint position of preceding value
94 109 109 109 109 109 110 110 110 94
hint position of following value
109 94 109 94 110 110 109 109 110 110
hint start of container
188 172 172 187 172 172 235 187 172 187
no hint
172 171 172 172 172 172 172 172 171 172

so i'd hinting on either side gives same result, , better no hint @ all. choosing poor hint position (such start) worse no hint @ all.