[RESOLVED] Managing pointers with STL map

I am having trouble with map containers. I have an information class called CInfo, and two map containers. I have typedef MAP_ONE as a <int, CInfo*>, and typedef MAP_TWO as a <int, MAP_ONE*>

I am able to use the containers well enough, but I am having trouble cleaning it up properly. Because the container class does not free the memory of the class the pointer is pointing to, I wanted to iterate through the maps and free up the memory myself. My first attempt was the code below. It resulted in a memory error when it tried to execute the code p_map_One->clear(); I then thought maybe once I have free the memory that the pointer was using, I should set the pointer in the map to NULL, so I added in the extra lines that are commented out below. When I uncomment these 2 lines I receive no errors, but when I observe the memory usage it looks like there is still a leak. Can anyone tell me if the below code is incorrect? Did I free up the memory correctly?

Code:

---

        //At this point I have a member variable MAP_TWO m_map_Two, which
        //has 2 entries. And for each entry there are 2 entries of MAP_ONE*
        MAP_ONE::iterator itrOne = NULL;
        MAP_ONE* p_map_One = NULL;
        CInfo* pInfo = NULL;
        for (MAP_TWO::iterator itr = m_map_Two.begin(); itr != m_map_Two.end(); ++itr)
        {
                p_map_One = itr->second;
                for (itrOne = p_map_One->begin(); itrOne != p_map_One->end(); ++itrOne)
                {
                        pInfo = itrOne->second;
                        delete pInfo;
                        //itrOne->second = NULL;
                }
                p_map_One->clear();
                delete p_map_One;
                //itr->second = NULL;
        }
        m_map_Two.clear();

---

This code looks fine, but I have had similar problems as well. In fact what happened to me was that clear() was crashing, but the real cause was an insertion operation previously that didn't work properly. So my guess is that your real problem lies somewhere else.

In any case, having pointers is not always particularly helpful when using maps. If you are careful you can pretty much avoid all copying without resorting to pointers and you'll have much easier syntax and memory management. The only deep copy that is worrysome happens when you would insert an existing (and large) MAP_ONE into a MAP_TWO. But if you construct this compound structure on the fly (i.e. you insert a new small MAP_ONE when you need and then enter elements into it) then I suggest dropping the pointers.

By the way, the code tags on forums are enclosed in square brackets [ and ], not angle brackets, that's why your post didn't come out right.

Thank you Yves M. I was wondering why my <code> tags were failing :) Below is an example of how I insert into the maps. I would never have thought that the problem could be in the insertion. Do you see any problems here? Unfortunetly I need to use pointers to avoid the costly copying of which you spoke of. But I have always found that as long as you stick to the pointer motto (if you 'new', then you must 'delete', and set to 'NULL'), there are few problems.

Code:

---

void CAreaMgr::AddSection(int nSection)
{
        int nArea = gn_Count++; //gn_Count is a static variable.
        CInfo* pInfo = new CInfo();
        pInfo->Init();
        MAP_ONE* p_map_One = new MAP_ONE();
        (*p_map_One)[nArea] = pInfo;
        m_map_Two[nSection] = p_map_One;
}

---

There is no significant copying in your example. I would only be concerned if CInfo is a large class that takes time with copying.

In terms of performance it's useful to think of maps in terms of trees. You allocate a node once and then it can get moved around, but it will not be copied or reallocated. So this is not the same as with std::vector for example where reallocation and copying occurs regularly when the container grows. So a map of pointers only cuts down on one single copy: the one when the object is inserted into the container.

Now your insertion also looks allright. So that's probably not it either.

Quote:

---

When I uncomment these 2 lines I receive no errors, but when I observe the memory usage it looks like there is still a leak

---

Which compiler and which STL do you use? Some STL implementations internally use non-default allocators, so they don't just use new/delete for allocating single elements. This means that memory usage can seem inconsistent with what you are actually doing in your program. The only reliable way I have found to debug memory leakage is with dedicated tools like Purify.

I am using visual studio 6.0 with service pack 6. I'm not sure about the specific compiler or STL library version. I'll give purify a try to see what it turns up. With regards to my first post... could you write a piece of sample code of the same format, and then try the cleanup code that I wrote? Leave the commented lines commented, and see if your debugger gets an error when it gets to the clear() method. If it does, can you explain why?

Can you post the code where you create a map and then create the other map containing the first set of maps? Also, the code that is used to fill the map elements? Looks like, you create map one objects dynamically and the map one itself is a dynamically created object.. but if it is not that of course, the way to clean up your map/map elements is flawed causing problems.

Just a curious question:

What is the scenario that made you use map of maps?
Is it possible that you can apply a simpler design?

I recommend using a good smart pointer, that will automatically delete the pointer in your map container.
The smart_ptr class can do this for you, and there's an example usage for map in the following link:
http://axter.com/smartptr/

Quote:

---

Originally Posted by Axter

I recommend using a good smart pointer, that will automatically delete the pointer in your map container.
The smart_ptr class can do this for you, and there's an example usage for map in the following link:
http://axter.com/smartptr/

---

Ideally, there shouldn't be a need of smart pointers because there isn't a need to store pointers to those objects. maps are node-based containers, so you don't really get anything much out of dynamic allocations and storing pointers (copying is not a problem there). Yves mentions this point and that is how the OP should proceed.

Quote:

---

Originally Posted by nice_guy_mel

Unfortunetly I need to use pointers to avoid the costly copying of which you spoke of.

---

1) Is this just a feeling on your part, or have you concrete evidence that this is the case (costly copying)?

2) Please post the "CInfo" class members, so that others can conclude whether there is any costly copying that's done.

3) Regardless of all of this, the goal would have been to write the program so that it works first (i.e. store objects, not newed objects). Then after the program is working, then and only then should you start to determine what parts can be sped up by using pointers or whatever.

Quote:

---

could you write a piece of sample code of the same format, and then try the cleanup code that I wrote? Leave the commented lines commented, and see if your debugger gets an error when it gets to the clear() method.

---

This is what you should be responsible for doing. You may find the problem yourself if you took the time to come up with a smaller example. It really isn't fair to ask anyone else to take partial code, and try to duplicate your error.

I always point to the following link as a user-friendly way of posting code that doesn't work:

http://www.parashift.com/c++-faq-lit...t.html#faq-5.8

Regards,

Paul McKenzie

Nice to see my post generated some interest. So far it looks like most responses state to either change the design, post more code, or to find the problem myself... laughing... really helpful.
But of course we all understand. You can't very well post your life story here and expect people to be all caught up with your code before posting your question. You just post the jist of it and hope that somebody else just 'gets it'. The story is that I was put in charge of a project that was working fine, but needed to be updated to handle about 3000 times more input than before. The whole goal here is SPEED. Getting rid of any uneeded copy constructors was my first priority. After enhancing all code lines that use the String class, my next priority was to change any containers using classes, to use pointer to classes. I think someone already mentioned using objects first and then try to use pointers. This is exactly what happend. As far as the design goes, I wasn't here for that, I was put in charge of it, and took on all the ups and downs from previous coders (I'm sure we can all relate to this... ha ha).
I should have mentioned that the CInfo class is a small class that only has 4 member variables, all integers. 'Costly Copying' was too strong a term to use. I just want to avoid ANY copying, even if it's a small copy like the CInfo class. The operation is performed approximately 500 times a second, so it's a matter of 'trimming the fat' to speed up the program.
The memory crash occurs even if I add the elements in manually such as

Code:

---

typedef map<int, CInfo*> MAP_ONE;
typedef map<int, MAP_ONE*> MAP_TWO;

MAP_TWO m_map_Two;
MAP_ONE* p_map_One = new MAP_ONE();
(*p_map_One)[1] = new CInfo();
(*p_map_One)[2] = new CInfo();
m_map_Two[5] = p_map_One;
p_map_One = new MAP_ONE();
(*p_map_One)[3] = new CInfo();
(*p_map_One)[4] = new CInfo();
m_map_Two[6] = p_map_One;

---

The class CInfo is:

Code:

---

class CInfo
{
public:
        CInfo& operator=(const CInfo& info) {
                m_a = info.m_a;
                m_b = info.m_b;
                m_c = info.m_c;
                m_d = info.m_d;
                return *this;
        }
        int m_a;
        int m_b;
        int m_c;
        int m_d;
};

---

From this code and the cleanup code posted previously, you can easily create a simple console application to test with. I want to stress that I'm not some student with a project that is due, and quickly looking for someone else to do my work for me (we've all read post from those guys in here... ha ha). As far as I'm concerned the matter is closed. When I uncomment the lines that set the map's pointer to NULL, the clean up code works fine, so my project is moving ahead. Next I'm taking all the constructors and giving them an initialization list (again hoping to trim the fat). I simply thought that the crash was interesting, and wanted to throw it into a forum, to see if anyone else had come across this themselves.

Interesting. So how much overall speed increase do you get when changing to pointers?

Quote:

---

Originally Posted by nice_guy_mel

The whole goal here is SPEED. Getting rid of any uneeded copy constructors was my first priority. After enhancing all code lines that use the String class, my next priority was to change any containers using classes, to use pointer to classes.

---

Did you determine this by using a profiler to profile your code, or is this whole thing of what needs to be optimized determined "by feel"? (Basically asking the same question as before).

Bottom line -- you just can't make up what you think needs to be optimized. That usually leads down the path of making the code more buggy and less maintainable, with no speed gains whatsoever. To add, in many cases, it causes a degradation of speed, since you changed the code enough so as the compiler's own optimization strategy is compromised.

Before embarking on making the code "optimized", you should make sure that what you're doing is going to make any appreciable difference by properly profiling the code with profiling tools.

See the link below -- it pertains to Linux, but it is valid for any OS.

http://movementarian.org/linux-profi...ilingcode.html

Regards,

Paul McKenzie

From the amount of information you have provided, here are my comments/guesses/questions:

1. It should not cause any problems, ideally. If that is how you are populating and cleaning up.
2. What STL are you using?
3. Do you ever use array form of new to allocate objects mixed with non-array form of new to insert into the map?
4. Looking at CInfo for which you have defined the operator=, do you have a copy constructor? Do you have pointer members in it? You don't need explicit copy assignment operator. The code looks suspicious to me or else you have provided wrong/incomplete information.
5. Are there any classes derived from CInfo?
6. What crash do you get? Is it std::bad_alloc exception? Can you post the error or exception details?
7. Are the maps cleaned up twice (ownership problems)?
8. Are you passing the map2 by value somewhere (esp. before the cleanup code)?

That code should not fail under normal circumstances..

Quote:

---

Originally Posted by nice_guy_mel

The class CInfo is:

Code:

---

class CInfo
{
public:
        CInfo& operator=(const CInfo& info) {
                m_a = info.m_a;
                m_b = info.m_b;
                m_c = info.m_c;
                m_d = info.m_d;
        }
        int m_a;
        int m_b;
        int m_c;
        int m_d;
};

---

---

1) You don't need a user-defined assignment operator. The default assignment operator does exactly what your code does, and it is safer. If you added a member to CInfo, and you forgot to add it to your list of assignments in your function, you will get a very hard to find error when you run your program. The default assignment operator doesn't make this mistake.

2) Given that you did write a user-defined assignment operator, your code does not return a reference to itself. This should not have even compiled.

Quote:

---

Next I'm taking all the constructors and giving them an initialization list (again hoping to trim the fat).

---

Which goes to the thrust of my initial posts. Instead of "hoping to trim the fat", you must make certain that what you are doing is going to do anything in terms of speed. Otherwise, you're just wasting your time, and worse, adding to the additional number of problems that your code is encountering.

Quote:

---

I simply thought that the crash was interesting, and wanted to throw it into a forum, to see if anyone else had come across this themselves.

---

Crashes occur mostly because of mismanaging pointers and memory. Mismanaging memory and pointers can be done in an umpteen number of ways. So there really isn't anything unique about a program that crashes that contains pointer manipulation and dynamically allocated memory.

Regards,

Paul McKenzie

Exterminator questions:
1. N/A
2. I don't know how to check for an STL version number. Whatever I am using was installed before I was hired.
3. I don't know what the array form of new is, so that must be a no.
4. No copy constructor. No pointer members. Comment on = overload below.
5. No child classes.
6. See below.
7. Called just once by the destructor for the manager class.
8. No passing by value.

My initial intent with this post was to get other developers to try it with their debugger to see if the results were the same. Now that I am back in the offic, I began running the same code on the computer of my coworkers, who also had VS 6.0. There was no crash at all! Very suspicious. I rebuilt every project in my workspace, and now it runs as expected. I guess the problem was simply with one of the compiled files.

Paul you're right, it doesn't compile. I was too hasty when trying to copy/paste my cpp file and h file together in the one post and accidentally left off my return *this. Thank you for catching it.

Thank you Paul for your information about the default = operator. I didn't realize it would copy all the variables for me. I'm sure there are other mini classes where I could apply the default = operator.

Paul you have given me much to consider... I may even have to start a new thread (only after first searching older post of course:). Yes I am going by my instincts, not an actual profilling tool. It's no doubt due to my lack of experience, but I just assumed that using variables by reference, instead of by value would make my functions perform faster. Same for the String classes. I replaced all functions that returned String as a void function that had as one of it's arguments a String& strOut. Most of my 'speed optimizations' resulted from google searches on code performance, instead of profilers. I certainly hope I haven't just made things worse as you suggest.

I'm interested in what you mentioned about the "compiler's own optimization strategy". I'll have to take some time and google the topic for a while. Thank you to all who responded to the post. Sorry for wasting your time, but thankfully I learned some new things that I didn't know before so this has been a successful post afterall :)

Quote:

---

Originally Posted by nice_guy_mel

I replaced all functions that returned String as a void function that had as one of it's arguments a String& strOut.

---

Most modern C++ compilers do this optimization automatically. It's called Named Return Value Optimization or NRVO, and it is one (maybe the only) optimization that is described in the ANSI C++ standard document.

http://blogs.msdn.com/aymans/archive...13/480699.aspx

So if you had one of these compilers, you didn't have to change your code. The latest versions of Visual C++ has this optimization, as does gcc. Basically, if a modern compiler doesn't do this optimization, IMO it can be considered as "lacking" and is a minus.

Quote:

---

I'm interested in what you mentioned about the "compiler's own optimization strategy".

---

If you use well known constructs, the compiler will recognize them and attempt to optimize them. For example, if you use std::sort with a predicate instead of writing your own sort (or using qsort), the compiler can optimize the code by doing "inlining".

If you try and be too elaborate with esoteric pointer usage, the code will contain too many pointers and pointer aliases. Then the compiler cannot do anything with the code in terms of optimizations, since none of the optimization techniques are guaranteed to produce the same results when the code is unoptimized. That is basically what I mean when I stated about "compiler optimization strategy".

Regards,

Paul McKenzie

Quote:

---

Originally Posted by nice_guy_mel

Sorry for wasting your time, but thankfully I learned some new things that I didn't know before so this has been a successful post afterall :)

---

Well I don't think it's wasted time if you learned something from it.

So honestly, I would stop all code changes right now and spend a few hours on profiling. You may even have to change the algorithms that are used in some parts to make the code faster. The "cosmetic" changes rarely affect speed much unless it's something really stupid like a for (i = 0; i < strlen(s); ++i) loop.

Looking at your code, and ignoring the error, I would say switching to pointers may well be a pessimisation, since you've had to add lots of calls to "new". You may well find that this code is faster:

Code:

---

typedef map<int, CInfo> MAP_ONE;
typedef map<int, MAP_ONE> MAP_TWO;

MAP_TWO m_map_Two;
MAP_ONE& map_One1 = m_map_Two[5];
map_One1[1]; //default constructs
map_One1[2]; //default constructs

MAP_ONE& map_One2 = m_map_Two[6];
map_One2[3];
map_One2[4];

---

Note that the end aim is not to reduce the number of object copies, but to speed the code up. Generally, the only reason reducing object copying improves speed is because it reduces the number of memory allocations. However, your CInfo class doesn't make any allocations, so dynamically allocating instances to avoid copying may well be a pessimization.

I have spotted the bug immediately. You are deleting the "second" in all of your map nodes but these "second" pointers are not necessarily unique, i.e. they don't appear in only one place. In fact you place one pointer in there twice:

Code:

---

m_map_Two[5] = p_map_One;
p_map_One = new MAP_ONE();
(*p_map_One)[3] = new CInfo();
(*p_map_One)[4] = new CInfo();
m_map_Two[6] = p_map_One;

---

so you are deleting p_map_One twice, once for m_map_Two[5] and once for m_map_Two[6].

Now if these really are the same map, and I will assume they are, this is a perfect case for using shared_ptr. shared_ptr will be reasonably efficient in that it won't have to copy the maps, it would just copy the pointer and up the reference count.

And it would take away from you having to handle the issues of deletion.

At the other level where the maps are unique, you might possibly these use value rather than pointer.

No, he is not. He is using the same pointer to refer to two different map_one objects but not deleting the same one twice. Here (see bolded statements):

Code:

---

typedef map<int, CInfo*> MAP_ONE;
typedef map<int, MAP_ONE*> MAP_TWO;

MAP_TWO m_map_Two;
MAP_ONE* p_map_One = new MAP_ONE();
(*p_map_One)[1] = new CInfo();
(*p_map_One)[2] = new CInfo();
m_map_Two[5] = p_map_One;
p_map_One = new MAP_ONE();
(*p_map_One)[3] = new CInfo();
(*p_map_One)[4] = new CInfo();
m_map_Two[6] = p_map_One;

---

Yes you're right, I was looking too quickly. My next criticism is that I think map is the wrong collection to use. As the key is int and the indices are low and bunched, I'd use vector.

In this case vector< vector < CInfo * > >

may be the best option (although I'd prefer vector< vector< shared_ptr< CInfo > > )

You want to use a pointer here for CInfo because it might be NULL if there is no entry.

Now we'll modify this function:

Code:

---

std::vector< std::vector< CInfo * > > sectionTable; // probably member of CAreaMgr

void CAreaMgr::AddSection(int nSection)
{
  int nArea = gn_Count++; //gn_Count is a static variable.

  if ( sectionTable.size() < nSection + 1 )
  {
      sectionTable.resize( nSection + 1 );
  }

  if ( sectionTable[ nSection ].size() < nArea + 1 )
  {
      sectionTable[ nSection ].resize( nArea + 1  );
  }
 
  CInfo* pInfo = new CInfo;
  pInfo->Init(); // funny I don't see an Init() function in your definition of CInfo

  sectionTable[ nSection ] [ nArea ] = pInfo;
}

---

There seems to still be something flawed here. If nArea is a counter then there is one single unique pInfo for each nArea so why not just use vector here.

At this point I'm also going to do away with using new and will just use instances of CInfo. As it is just a collection of 4 integers and has no problems with deep copy (i.e. no pointers to other classes), it is assumed cheap to copy. (Note: it is even cheaper to copy than a std::string).

Code:

---

// these two are both members of CAreaMgr

std::multimap< int, std::vector<CInfo>::size_type > sectionMap;
std::vector< CInfo > infoTable;

void CAreaMgr::AddSection(int nSection)
{
//  int nArea = gn_Count++; //gn_Count is a static variable.
// May I assume there is only one area manager?

    infoTable.push_back( CInfo() );
    sectionMap.insert( std::make_pair( nSection, infoTable.size() - 1 ) );

 // wow! down to just 2 lines
}

---

sectionMap is a multi-map from section to all the indices (or areas) that are in it.
Note that if you want to be able to trace the other way, either use std:: pair< CInfo, int > as your value type where int has the section in it, or extend CInfo to contain another int, that being the section that it is in (or write your own struct in place of std:: pair )

Well, vectors of vectors of objects really are a performance problem when they grow dynamically. And this is what is happening here, so I don't think this is a good solution at all. And one of the main problems may be that sometimes AddSection takes a really unreasonable time when it shouldn't, just because the outer vector needs to grow its reserve.

Looking back on this thread I realized I didn't tell you why I chose a map of maps as a container in the first place. What I was doing was tracking vessel identification numbers. When we receive a vessel message we are primarily concerned with two things. The first is what basestation the message came from, this is an integer used in the MAP_TWO. The second is the vessel id number, this is an integer used in the MAP_ONE. CInfo was in charge of holding the timestamp of when the message came in, along with a few other parameters. In a standard setup, we would only be working with 10 or less basestations, so MAP_TWO would rarely if ever consist of more then 10 MAP_ONE's. The problem was that we were getting close to 600 messages a second. Each message represents either a new instance of CInfo, or updating an existing CInfo object from one of the MAP_ONE's.
I thought it would speed things up a bit to store CInfo as a pointer instead of an object. I no longer get the crash when I use map->clear() because I always make sure to set mapItr->second = NULL after I delete the CInfo object.