multimap insert behaviour with a hint

[hurcan solter]

Consider the following snippet

#include <map>
#include <iostream>
#include <algorithm>
#include <iterator>

typedef std::multimap<int ,int> map_type;

template <typename Pair>
struct select2nd
{
typedef Pair argument_type ;
typedef typename Pair::second_type result_type ;

const result_type &
operator()(const argument_type &p) const
{
return p.second ;
}
} ;

int main()
{
map_type mymap;
map_type::iterator iter;
iter = mymap.insert(map_type::value_type(1,1));
iter = mymap.insert(iter,map_type::value_type(1,2));
iter =mymap.insert(iter,map_type::value_type(1,3));
iter =mymap.insert(iter,map_type::value_type(1,4));
iter =mymap.insert(iter,map_type::value_type(1,5));

std::transform(mymap.begin(),mymap.end(),std:stream_iterator<int>
(std::cout," ")
,select2nd<map_type::value_type>());



};

prints out as 5 4 3 2 1 whereas the insert without hint sorts the key
as 1 2 3 4 5
which is the desired behaviour for me.

according to defect report ;
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1780.html

insertion before the hint is the sensible behaviour , but i need the
keys sorted as
in the order as they are added(they are guaranteed to be in ascending
order) to the multimap and also need the performance improvement.
(tens or hundred of thousands of entries)

so doing something like
iter = mymap.insert(map_type::value_type(1,1));
iter = mymap.insert(++iter,map_type::value_type(1,2));
....
do you think i still get the performance boost or should I stick with
the hintless version

Thanks in advance
Hurcan

 

[coal]

Consider the following snippet

#include <map>
#include <iostream>
#include <algorithm>
#include <iterator>

typedef std::multimap<int ,int> map_type;

template <typename Pair>
struct select2nd
{
        typedef Pair argument_type ;
        typedef typename Pair::second_type result_type ;

        const result_type &
                operator()(const argument_type &p) const
        {
                return p.second ;
        }

} ;

int main()
{
        map_type mymap;
        map_type::iterator iter;
        iter = mymap.insert(map_type::value_type(1,1));
        iter = mymap.insert(iter,map_type::value_type(1,2));
        iter =mymap.insert(iter,map_type::value_type(1,3));
        iter =mymap.insert(iter,map_type::value_type(1,4));
        iter =mymap.insert(iter,map_type::value_type(1,5));

        std::transform(mymap.begin(),mymap.end(),std:stream_iterator<int>
(std::cout," ")
                ,select2nd<map_type::value_type>());

};

prints out as 5 4 3 2 1 whereas the insert without hint sorts the key
as 1 2 3 4 5
which is the desired behaviour for me.

according to defect report ;http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1780.html

insertion before the hint is the sensible behaviour , but i  need the
keys sorted as
in the order as they are added(they are guaranteed to be in ascending
order) to the multimap and also need the performance improvement.
(tens or hundred of thousands of entries)

so doing something like
iter = mymap.insert(map_type::value_type(1,1));
iter = mymap.insert(++iter,map_type::value_type(1,2));
...

I think this works:

map_type::iterator endIt = mymap.end();
mymap.insert(endIt, map_type::value_type(1,1));
mymap.insert(endIt, map_type::value_type(1,2));

do you think i still get the performance boost or should I stick with
the hintless version

I've done a few tests using set<int> with the two insert functions on
Linux 2.6.27.5 and gcc 4.3.2. In general I ran each of the two
programs twice in a row using a semicolon between the commands.
First I ran the insert with a hint program twice and then the
regular insert version twice. I did that 8 times.
7 of the 8 times the slowest time for regular insert was slower
than both the times for hinted insert. And 6 out of 8 times
the fastest time of the hinted insert was faster than both
of the regular insert times. I would probably use the
insert with a hint function here.

Brian Wood
Ebenezer Enterprises
www.webEbenezer.net