CODEWITHSUNDEEP
c++stldictionaryiterator
Josh
Josh

Reputation: 3311

Map iterator vs. manual

I was trying to compare 2 techniques of filling maps, one with iterators and one without. I have heard iterators make it faster, but how?

//With Iterator
map<int, int>::iterator insert = fibHash.begin();
fibHash.insert(begin, pair<int, int> (n, fib_val));

//Without iterator
fibHash.insert(pair<int, int> (n, fib_val));

Upvotes: 1

Views: 323

Answers (4)

Darkdragon84
Darkdragon84

Reputation: 901

Adding to what has been said: If you are concerned with speed, also consider the new C++11 methods std::map::emplace and std::map::emplace_hint for inserting elements into a std::map. Instead of passing a copy of a Key/Value pair to the container, emplace passes only the arguments for creating this pair in-place at the right position. This can save you expensive copies (although in your int,int example this wouldn't make much of a difference, as opposed to larger data structures such as matrices, etc.).

std::map<int,int> MyMap;
MyMap.emplace(5,10); // passing 5,10 to ctor of std::pair<const int,int> in-place
MyMap.insert(std::pair<const int,int>(5,10)); // construct a std::pair<const int,int> and pass it to insert, such that it creates a copy in the right location within the map

//similarly with the 'hint' methods
MyMap.emplace_hint(MyMap.end(),6,20);
MyMap.insert(MyMap.end(),std::pair<const int,int>(6,20));

Btw., std::map<int,int>::value_type is really a std::pair<const int,int>, not a std::pair<int,int>.

Upvotes: 0

John Dibling
John Dibling

Reputation: 101456

The first form, where you provide an iterator, has the potential to be faster at runtime -- but only if you pick a good iterator, and even then only if your implementation uses the hint. The iterator you send to insert is just a hint. insert doesn't necessarily insert the element there, since a map is a sorted container. Rather, the iterator can be used by the implementation as a starting point for when it looks for where it will insert the element.

So, if you pass it a well-chosen iterator (which begin() often will not be), using the version of insert which takes the hint iterator, you could theoretically approach amortized constant time for inserts, whereas with the non-hint version you're looking at O(log n) for inserts.

Upvotes: 4

juanchopanza
juanchopanza

Reputation: 227390

First of all, you have to bear in mind that std::map is an ordered structure, so you cannot place elements at arbitrary position. A certain element can only be placed in a certain position relative to others, according to a strict weak ordering relation (a less-then relation satisfying certain conditions).

The first variant takes an iterator as a hint for a good position for the element, and only makes the insertion faster (amortized constant time) if the insertion happens next to the input iterator. Otherwise, the complexity is the same as the second variant (logarithmic).

The first variant uses the first argument as a hint, and tries the insertion. If the hint is good, then less comparisons are required to find the right position for insertion.

Upvotes: 4

eLRuLL
eLRuLL

Reputation: 18799

Iterator is a Design Pattern, something all programmers should take into account. Yes, iterators aren't really faster, but cleaner, they allow you to "iterate" data structures in a safe and clean way, so you shouldn't worry about messing with the real information.

In this particular case, u are only inserting one value at a time, so iterators aren't really the "fastest" solution, just happens to be that certain functions can use it as well.

In Your first example, you are inserting a value at the "begin"ing of the data structure, and the iterator is helping you to determine the position.

In the second one, you are just inserting the value at the end, or in the default intersion position, so you really don't need an iterator for that.

Upvotes: -2

Related Questions