Std :: map iterator behavior and insertions
Like a simple start
Map<key,val> map1=//filled up in some way;
Map<key,val> map2;
map2.insert(map1.begin(),map1.end());
We know that map::insert
- O (log (n)), no hint. Does this mean the above works in O (nlog (n)) or does it take advantage of the fact that map1 is already sorted and just inserts at the correct positions (incrementing the current iterator)? Since map1 is already sorted, we need to do this in linear time. What about
std::copy(map1.begin(),map1.end(),map2.end());
Does it embed in O (log (n)) every time, or copied in O (1) at a respected position marked with an iterator increment?
A more illustrative example, perhaps
template<class InIter, class OutIter, class ResIter>
ResIter foo(InIter first, OutIter last, ResIter res){
while(first!=last){
res=*first;
++first;
++res;
}
return res;
}
Does this run in O (n) or O (nlog (n)) when dealing with a map iterator? Are the inserts O (log (n)) or are they O (1) because we are specifying the position i.e. *res=*first
?
Edit for clarity:
whether
*res=*first
to behave as
map2.insert(res,*first)
inserting into map2 using an iterator res
pointing to the correct position as a hint, making it O (1) or doing the usual O (log (n)) setup?
source to share
After a quick read by the standard, void insert(InputIterator first, InputIterator last);
no difficulty requirements are required. So the lazy implementation is allowed to have O (n log (n)) complexity, even likely to be linear if map1
empty because of what follows.
As the standard requires linear complexity for the constructor if the input range is sorted, so this is O (n) needed:
Map<key,val> map1=//filled up in some way;
Map<key,val> map2(map1.begin(),map1.end()); // complexity in O(n)
For the second part of your question, since you want to give a hint as to where the element should be inserted, the correct way is:
template<class InIter, class OutIter, class ResIter>
ResIter foo(InIter first, OutIter last, ResIter res){
while(first!=last){
emplace_hint(res, *first);
++first;
++res;
}
return res;
}
Unfortunately, the standard does not require any complexity emplace
or emplace_hint
.
source to share