question on map<K, V>::insert(iterator, const value& v)

[subramanian100in]

consider the following program:

#include <cstdlib>
#include <iostream>
#include <map>
#include <utility>
#include <string>

using namespace std;

int main()
{
typedef map<int, string> container_type;

container_type m;

m[0] = "zero";
m[1] = "one";
m[2] = "two";

container_type::iterator it = m.find(0);

++it;
++it;

container_type::iterator res = m.insert(m.end(), make_pair(0,
"Test"));

if (res == m.begin())
cout << "res equals m.begin()" << endl;
else
cout << "res != m.begin()" << endl;

cout << res->second << endl;

return EXIT_SUCCESS;
}

The output of the above program is

res equals m.begin()
zero

My question: From the output, it looks like, the insert() operation
starts searching from the begin() position even though the hint is to
start at m.end() which is passed as the first argument to m.insert().
I am unable to understand this.

What actually does 'passing the iterator as hint' to the insert()
function mean ?

Does it mean, it will start searching ONLY from this hint iterator or
it will search from begin() irrespective of whatever 'hint iterator'
argument is passed(ie, in essence, it is ignored). ? How does this
version of insert() work ?

Kindly explain.

Thanks
V.Subramanian

 

[Erik Wikström]

consider the following program:

#include <cstdlib>
#include <iostream>
#include <map>
#include <utility>
#include <string>

using namespace std;

int main()
{
typedef map<int, string> container_type;

container_type m;

m[0] = "zero";
m[1] = "one";
m[2] = "two";

container_type::iterator it = m.find(0);

++it;
++it;

container_type::iterator res = m.insert(m.end(), make_pair(0,
"Test"));

if (res == m.begin())
cout << "res equals m.begin()" << endl;
else
cout << "res != m.begin()" << endl;

cout << res->second << endl;

return EXIT_SUCCESS;
}

The output of the above program is

res equals m.begin()
zero

My question: From the output, it looks like, the insert() operation
starts searching from the begin() position even though the hint is to
start at m.end() which is passed as the first argument to m.insert().
I am unable to understand this.

You can not draw any such conclusion from the above code since the
(observable) result will be the same regardless of where the search
begins. You might be able to tell the difference if you use a larger
tree and measure the time needed to perform the insert, if the search
starts at the hint it will take longer than if it starts from the beginning.

Of course the difference might be really small since it probably works
like this: If a hint is given a check is made to see if the element to
insert will be a child to the hint, if it is it will be inserted at that
point, if not the search will start from the beginning. A more advanced
algorithm might also detect if the hint will be an ancestor and then
search from the hint until the correct insert point is found. Note
though that the standard only mandates the simple approach.

What actually does 'passing the iterator as hint' to the insert()
function mean ?

It means that the complexity of the insert operation can be reduced from
O(log n), which is the normal complexity, to amortised O(1) provided
that the element will be inserted right after the hint.

Does it mean, it will start searching ONLY from this hint iterator or
it will search from begin() irrespective of whatever 'hint iterator'
argument is passed(ie, in essence, it is ignored). ? How does this
version of insert() work ?

No, since the map stores the elements in order only searching from the
hint is not possible (what would happen to the order if you inserted an
element after the hint when it should come before?). What happens is
that a check is made to see if the element can be inserted after the
hint (in which case that is what happesn), if not a normal insert will
take place with the search starting at the beginning.

In sort, if you are inserting a lot of pre-ordered elements you can
speed up operations quite a bit by passing the iterator from the
previous insert as a hint to the next