"In STL maps, is it better to use map::insert than []?"

[Lynn McGuire]

"In STL maps, is it better to use map::insert than []?"
http://stackoverflow.com/questions/326062/in-stl-maps-is-it-better-to-use-mapinsert-than

I have a std::map where insert works better than []. The code compiles but crashes in the 2nd or 2rd copy constructor call with a
null right hand side.

Lynn

[Victor Bazarov]

http://www.dietmar-kuehl.de/mirror/c++-faq/how-to-post.html#faq-5.8

V
--
I do not respond to top-posted replies, please don't ask

[Paavo Helde]

Lynn McGuire <l...@winsim.com> wrote in news:mv91f8$st5$1...@dont-email.me:

> "In STL maps, is it better to use map::insert than []?"

Depends on the usage, otherwise STL would not offer both options.

> The code
> compiles but crashes in the 2nd or 2rd copy constructor call with a
> null right hand side.

There is a bug in your code.

Cheers
Paavo

[bartekltg]

On 09.10.2015 20:38, Lynn McGuire wrote:
> "In STL maps, is it better to use map::insert than []?"
>
> http://stackoverflow.com/questions/326062/in-stl-maps-is-it-better-to-use-mapinsert-than



>
> I have a std::map where insert works better than [].

It works in different ways.
map<int,int> M;
M.insert(make_pair(2,44));
cout<<M[2]<<endl;
M.insert(make_pair(2,55));
cout<<M[2]<<endl;
M[2]=66;
cout<<M[2]<<endl;

The output is:
44
44
66

> The code compiles
> but crashes in the 2nd or 2rd copy constructor call with a null right
> hand side.

Your code contain an error.


>"Strictly speaking, this member function is unnecessary: it exists
> only for convenience."

Strictly speaking, the for-loop is unnecessary, (while-loop is
enough), it exist only for convenience. ;-)

bartekltg

[Lynn McGuire]

Yes, there was a bug having to do with nulls in the copy constructor.

Thanks,
Lynn

[Lynn McGuire]

Here is my code:

// find the first unused integer key and use it
if ( ! found)
{
m_FormsMainCacheIndex = 0;
while ( g_FormsMainCache.find (m_FormsMainCacheIndex) != g_FormsMainCache.end () )
m_FormsMainCacheIndex++;
// In STL maps, is it better to use map::insert than []?
// http://stackoverflow.com/questions/326062/in-stl-maps-is-it-better-to-use-mapinsert-than
g_FormsMainCache.insert ( std::pair <int, FormsMain> (m_FormsMainCacheIndex, * FmWindow) );
}

Thanks,
Lynn

[Ian Collins]

Lynn McGuire wrote:
>
> Here is my code:
>
> // find the first unused integer key and use it
> if ( ! found)
> {
> m_FormsMainCacheIndex = 0;
> while ( g_FormsMainCache.find (m_FormsMainCacheIndex) != g_FormsMainCache.end () )
> m_FormsMainCacheIndex++;
> // In STL maps, is it better to use map::insert than []?
> // http://stackoverflow.com/questions/326062/in-stl-maps-is-it-better-to-use-mapinsert-than
> g_FormsMainCache.insert ( std::pair <int, FormsMain> (m_FormsMainCacheIndex, * FmWindow) );
> }

A good example why variable name prefixes make code hard to read!

In this case, you have already determined the item does not exist in the
map. So the clarity over potential premature optimisation rule should
apply. Just write (with the suffixes if you really insist)

FormsMainCache[FormsMainCacheIndex] = *FmWindow;

--
Ian Collins

[Paavo Helde]

Lynn McGuire <l...@winsim.com> wrote in news:mv9qpk$d4g$2...@dont-email.me:

> Here is my code:
>
> // find the first unused integer key and use it
> if ( ! found)
> {
> m_FormsMainCacheIndex = 0;
> while ( g_FormsMainCache.find (m_FormsMainCacheIndex) !=
> g_FormsMainCache.end () )
> m_FormsMainCacheIndex++;
> // In STL maps, is it better to use map::insert than
> []? //
> http://stackoverflow.com/questions/326062/in-stl-maps-is
> -it-better-to-use-mapinsert-than
> g_FormsMainCache.insert ( std::pair <int, FormsMain>
> (m_FormsMainCacheIndex, * FmWindow) );
> }

The complexity of your algorithm is O(N*log(N)). A better approach would
be just iterate over the map,this would be just O(N):

int index = 0;
std::map<int, FormsMain>::iterator iter = cache.begin();
while(true) {
if (iter==cache.end() || iter->first!=index) {
cache[index] = *FmWindow;
break;
} else {
++iter;
++index;
}
}

Another option would be to use insert with a hint instead of []

cache.insert(iter, std::make_pair(index, *FmWindow));

This would avoid a bit of meaningless work (we already have located the
place where the insert should happen), but OTOH it can be considered as a
premature optimization as it would not change the overall complexity.

hth
Paavo

[Paavo Helde]

Ian Collins <ian-...@hotmail.com> wrote in
news:d7r9pu...@mid.individual.net:

> Lynn McGuire wrote:
>>
>> Here is my code:
>>
>> // find the first unused integer key and use it
>> if ( ! found)
>> {
>> m_FormsMainCacheIndex = 0;
>> while ( g_FormsMainCache.find (m_FormsMainCacheIndex) !=
>> g_FormsMainCache.end () )
>> m_FormsMainCacheIndex++;
>> // In STL maps, is it better to use map::insert than
>> []? //
>> http://stackoverflow.com/questions/326062/in-stl-maps-i
>> s-it-better-to-use-mapinsert-than
>> g_FormsMainCache.insert ( std::pair <int, FormsMain>
>> (m_FormsMainCacheIndex, * FmWindow) );
>> }
>
> A good example why variable name prefixes make code hard to read!

The main problem with these names is even not the prefixes, but that they
differ only in some 25% of letters. IOW, the signal/noise ratio of these
names is pretty low.

[bartekltg]

Did you read Victor's Bazarov post? He posted this link.
http://www.dietmar-kuehl.de/mirror/c++-faq/how-to-post.html#faq-5.8

> // find the first unused integer key and use it
> if ( ! found)
> {
> m_FormsMainCacheIndex = 0;
> while ( g_FormsMainCache.find (m_FormsMainCacheIndex) !=
> g_FormsMainCache.end () )
> m_FormsMainCacheIndex++;
> // In STL maps, is it better to use map::insert than []?
> //
> http://stackoverflow.com/questions/326062/in-stl-maps-is-it-better-to-use-mapinsert-than
>
> g_FormsMainCache.insert ( std::pair <int, FormsMain>
> (m_FormsMainCacheIndex, * FmWindow) );
> }

What can I do with this code? I can't run it. I even dont know
what "FmWindow" is and why you dereferenced it.
I do not see anything wrong. Error is probably somewhere else:)

And I think you still haven't posted error message from your compiler.


bartekltg

[bartekltg]

I'm afraid OP should rethink a big part of this code.
If he has a lot of windows, and this operation is called often,
it will be quadratic.

If we do not care about indexes, it can by done in similar way
like in a pool.
Just a vector of union of an integer (or size_t) and our type;
and an index first_index pointing to the first free element in
the vector.
"Occupied" elementd just contain a type, free elements points
at the next free elements.
Inserting and deleting has constant running time, and we use
much less memory than in a map.

bartekltg

[Lynn McGuire]

I care very much about the cache indexes. They are key to my serialization scheme.

Lynn

[Lynn McGuire]

It was just a null dereference at runtime. I did not understand that the copy constructor will get called with a null object in the
map process of inserting.

FmWindow (a FormsMain object) is a very large object with 100+ instance variables and many descendent classes. It can be from 50 KB
to 50 MB in size. I am using a cache since I potentially can have thousands of the FormsMain objects and many will be equivalent. I
actually have many object caches and also use string reduction. Otherwise we would be pushed into 64 bit and our customers are not
ready to go there yet.

Thanks,
Lynn

[Paavo Helde]

Lynn McGuire <l...@winsim.com> wrote in news:mvgnhg$pa1$1...@dont-email.me:

> FmWindow (a FormsMain object) is a very large object with 100+
> instance variables and many descendent classes. It can be from 50 KB
> to 50 MB in size. I am using a cache since I potentially can have
> thousands of the FormsMain objects and many will be equivalent. I
> actually have many object caches and also use string reduction.
> Otherwise we would be pushed into 64 bit and our customers are not
> ready to go there yet.

If your objects are expensive to copy, then you might find it useful to
minimize their default construction and copies by using e.g.
std::map::emplace() or std::map::emplace_hint(). See also rvalue
references, std::move() and perfect forwarding. It might be beneficial to
add a move constructor and assignment operator to your classes.

And yes, if the objects stored in the map are expensive to default-
construct or assign, then indeed map::insert() can work better than
assignment via []. This is one usage case where one is better than the
other.

hth
Paavo

[bartekltg]

On 12.10.2015 18:31, Lynn McGuire wrote:

>
> I care very much about the cache indexes. They are key to my
> serialization scheme.

But what "I care very much" mean. Do you want to have all indexes
from 0(or 1) to N without holes? I don't think so, because you
just was looking for a hole.

The simplest scheme: you have your map. But instead of looking
for the first unused indes, you use firs not touched yet index.

Let put_here be additional integer.

start with
int (or uint, or size_t ) put_here=0;


void my_inc( int &x)
{
if ( x < numeric_limits<int>::max())
x++
else
x=0;
}

tu put something:

while ( cache_map.find (put_here) != cache_map.end () )
my_inc(put_here);
cache_map[put_here] = *stuff_to_insert;


You will not get any collisions until you create (and destroy most
of them) 2^31 forms.

Why this wouldn’t work for you?


bartekltg