Prev: using operator++() without its side-effect
Next: const is an overrated concept that is a source of extra typing and mai
From: Andre Kaufmann on 10 Apr 2010 07:34
Stephen Howe wrote:
> On Thu, 8 Apr 2010 00:56:34 CST, "Jim Z. Shi" <jim.z.shi(a)gmail.com> wrote:
>
>> I use map a lot in my daily work, so the performance of map is very
>> important to me.
>
> Well if it is, I would not use
>
> imap[i] = "test";
>
> to insert in a map. For std::map
>
> imap.insert(std::map<int,string>::value_type(i, "test"));

I would always agree for a C++0x compiler, which supports rvalue references.

But for an older compiler I think it depends on the value type:

imap[i] = "test"

Will call the default constructor std::string() and then the assignment
operator (const char*). Which should result for a long string in only a
single heap allocation.

A shortcut would be imap[i].assign("test");

While

imap.insert (x)

Results in: Temporary x -> 1 heap allocation
Assignment: string = x -> 2 heap allocation

So if the compiler can't get rid of the temporary, I would assume
the first assignment for this case to be faster (for longer strings).

> [...]
> Stephen Howe

Andre

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Ulrich Eckhardt on 10 Apr 2010 07:33
Stephen Howe wrote:
> On Thu, 8 Apr 2010 03:33:00 CST, Ulrich Eckhardt
> <eckhardt(a)satorlaser.com> wrote:
>
>>Maps are trees, sorted by the key. Since your key increases monotonically,
>>every time you insert an element that insert takes place at the same
>>branch of the tree, so it becomes unbalanced.
>
> No it doesnt. The trees used are self-balancing like Red-Black trees, AVL
> trees, Scapegoat Trees
> If they were not self-balancing, the complexity requirements for std::map
> would not be met.
>
>>This doesn't help performance at all.
>
> Nonsense. He should be able enter key-values pairs in montonically
> increasing order, decreasing order, random order and it
> should make no real difference to speed of std::map.find(). The only
> increase of speed whould be a suitable hint for insert().

I worded myself badly. What I meant is, that when inserting the insert first
looks for a place to insert and then optionally rebalances the tree. Of
course it must rebalance the tree, otherwise it couldn't fulfill complexity
requirements for lookup. Inserting the elements in order means that you will
have a worst-case scenario for frequency of rebalancing, and that is what
doesn't help performance.

Sorry for the confusion.

Uli


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

First  |  Prev  | 
Pages: 1 2 3
Prev: using operator++() without its side-effect
Next: const is an overrated concept that is a source of extra typing and mai