Re: map.insert(key,val) vs. map[key]=val ?

From: Jeff Flinn (NONONE_at_nowhere.com)
Date: 10/19/04 

Date: Tue, 19 Oct 2004 13:59:52 -0400

"Patrick Guio" <patrickg@ii.uib.no> wrote in message
news:Pine.LNX.4.61.0410191824560.6010@eukalyptus.ii.uib.no...
> On Tue, 19 Oct 2004, Victor Bazarov wrote:
>
> >> I have benchmarked 2 different ways to add an element in a map
container.
> >>
> >> 1 map.insert(key,val)
> >> 2 map[key]=val
> >>
> >> I used gcc and it comes out that the second way is about twice as fast
as
> >> the first one.
> >> Is there a reason/case why I should use the insert() method rather the
> >> operator[]?
> >> Are the 2 different completely equivalent?
> >
> > No, they are not. According to the Standard, the second one creates
> > a default 'value' associated with 'key' in the container, and then uses
> > the assignment op to get the contents of 'val' into the newly created
> > value. The operator[] is said to be implemented in terms of 'insert'.
> > So, all things being standard, I'd expect 'insert' to work faster in
> > general.
>
> Strange, here is my very simple (maybe too simple?) benchmark
>
> #include <map>
> #include <string>
> #include <iostream>
> #include <ctime>
>
> typedef std::map<int, std::string> lut;
> typedef lut::value_type pair;
>
> #define BENCH(BLOCK,NAME,N) \
> { \
> lut a; \
> clock_t tic=clock(); \
> for (int i=0; i<N; i++) { \
> BLOCK \
> } \
> double elapsed = double(clock()-tic)/N/CLOCKS_PER_SEC; \
> std::cout << "Time elapsed = " << 1e9*elapsed << " ns" << std::endl; \
> } \
>
> int const N=100000;
>
> int main()
> {
> BENCH(a.insert(pair(i%1000,"foo1"));,"map::insert()",N)
> BENCH(a[i%1000]="foo1";,"map::operator[]",N)
>
> BENCH(lut a; a.insert(pair(i%1000,"foo1"));,"map::insert()",N)
> BENCH(lut a; a[i%1000]="foo1";,"map::operator[]",N)
> }
>
> And the output on a linux box runnig g++ 3.2.3 compiling without any
> optimisation
>
> Time elapsed = 900 ns
> Time elapsed = 500 ns
> Time elapsed = 1100 ns
> Time elapsed = 1200 ns

Try running each test case in it's own excitable, compare those results. I
bet the allocator on your implementation doesn't need to do as much work
after the first 1000 allocations have occurred.

Jeff F

Relevant Pages

  • Re: allocator requirements
    ... according to the C++ Standard. ... > the container will rebind the allocator to the correct type? ...
    (comp.lang.cpp)
  • "free space" with declared type
    ... and not exhausting the architectures ... >because it might have to align for a type you don't need). ... you could have a separate allocator for each type. ... Not imposing any task model and therefore not leaving the standard ...
    (comp.lang.c)
  • Re: "available for further allocation"?
    ... well (using a cell-based allocator for smaller objects, ... It would be nice if the language of the Standard was more explicit on this matter. ... we accumulate bills into a wallet, and try to use up the smallest bills first when performing transactions. ... this can be compared to the small but frequent memory objects found in memory allocators. ...
    (comp.std.c)
  • Re: "available for further allocation"?
    ... (using a cell-based allocator for smaller objects, ... It would be nice if the language of the Standard was more explicit on this matter. ... we accumulate bills into a wallet, and try to use up the smallest bills first when performing transactions. ... this can be compared to the small but frequent memory objects found in memory allocators. ...
    (comp.std.c)
  • Re: Question about C++ Allocators
    ... It's not contained by the container; ... > it needs through the static methods of an allocator class. ... reference to which can be passed into constructor of any STL ...
    (comp.lang.cpp)