multimap insert behaviour with a hint

H

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::eek: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
 
C

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::eek: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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,757
Messages
2,569,543
Members
45,026
Latest member
camilin05

Latest Threads

Top