Need advice with datastructure

[Philip Nicoletti]

It took me too long to post ...

[Philip Nicoletti]

another point : you have a number of loops which are basically like this :

std::map<int,CGroup>::iterator g_pos = m_logData.m_groups.begin();

while (g_pos != m_logData.m_groups.end())
{
   if (g_pos->first == g)
   {
   }
   g_pos++;
}

You are looping thru the map looking for a particular key. This
is O(N). std::map has a find function that is O(LOG(N)) :

std::map<int,CGroup>::iterator g_pos = m_logData.m_groups.find(g);

if (g_pos != m_logData.m_groups.end())
{
   // found
}
else
{
   // not found
}

[Mza]

Well, thanks anyway for the reply. It teaches me alot about the inner working of maps. By the way, that first solution you suggested does not seem to work in my case, that was the first thing I tried after I Deciphered those cryptic compiler messages. And another thing, "Effective STL". is that a book or an online guide or something? I would love to have some additional documentation on STL. Currently I only have the "Standard Template Library Programmer's Guide" but that's a bit too abstract for me.

[Philip Nicoletti]

The Meyers book is not available online. The first book I would
recommend is "The C++ Standard Library : A Tutorial and
Reference" by Nicolai Josuttis. (I also recommend the Meyers
book, but I would get Josuttis first)

Besides being a good reference, the "Tutorial" in the name
is accurate. You can see the types of code presented
in the book at :

http://www.josuttis.com/libbook/toc.html

Note: I don't know if my post concerning using map::find()
instead of loop thru crossed paths with your post. If not,
take a look at it.

[PadexArt]

A lot of people is asking aout STL and I for one only know what I actually worked with. maybe it would be a good ideea to have a forum dedicated to STL exclusivelly.

[Graham]

STL is an official part of the C++ language, so this forum is the perfect place for discussing STL.

[Mza]

Originally posted by Philip Nicoletti
The Meyers book is not available online. The first book I would
recommend is "The C++ Standard Library : A Tutorial and
Reference" by Nicolai Josuttis. (I also recommend the Meyers
book, but I would get Josuttis first)

Besides being a good reference, the "Tutorial" in the name
is accurate. You can see the types of code presented
in the book at :

http://www.josuttis.com/libbook/toc.html

Looks good to me. I'm getting it ASAP.

Note: I don't know if my post concerning using map::find()
instead of loop thru crossed paths with your post. If not,
take a look at it.

Yes, it is much better. Not only faster but also more logical en better to understand.

[Kheun]

Originally posted by Mza
But this raises another question. How to directly acces the vector's elements (with O(1), like in an array). I thought Vectors should be able to do that but I saw it only with an integer or string, not with a class. The integer value that every class has could act as a key.

I just read from the book, Effective STL, which shown that if the vector is sorted, we can use binary search to locate the required element in O(log n). The caveat is that using a sorted vector is most appropriate only when once the vector is initialized, there is very little chance of adding/removing element during lookup phase.