Do map::erase() and list::erase depends on the amount of data in containers?

Paltform: HP-UX11 ia64
Compiler: aCC A.06.06

I am debugging a part of code which was reported to be consuming huge amount of memory. After lot of testing and debugging I found out that there was no real memory leak but a strange behavior of functions/code related to STL map and list.

Basically there are two maps (of same definition) and the data from one map is simply moved to other in a non-stop cycle. These maps are defined as:

typedef list   < MY_CLASS > List;
typedef map < time_t,  List > Map;

So a list containing random number of objects is mapped to a timestamp as a key. Overall the count of the objects is around 2 Million.

During a 'data moving' functionality each mapped list is iterated, and under some condition elements of the list are erased. Then if the list is empty, the corresponding element of map is erased as well.  I put some counters for all iterated and erased elements of the list printed these counts on each call of a function. Technically these counters tells the total number and erased number of objects from the Map.

I observed that while there were lot of list elements erased, the total count of objects was always same on each call of the function. I tested the same functionality in a sample program and it worked properly. The only difference was the amount of data is small in the sample program (added below).

Interestingly just by changing one line in the actual program made it work as well but I could not understand that behavior when the sample program is working without the change I made.

The corresponding change in this sample program would be:

Replace  list = mit->second;   in the remove() function to
               List &list = mit->second;

Can anyone explain this behavior?

// My class
class ZAB
{
public:
  ZAB () ;
 
  ZAB ( const ZAB&  rRefObj ) ;
 
  ZAB& operator = ( const ZAB&  rRefObj ) ;
 
  // Member
  int     a;
  int     b;
  int     c;
  long  d;
  int     e;
  int     f;
};
 
//
//  Map and list
//
 
typedef list    < ZAB >        List;
typedef map  < time_t, List > Map;
 
Map map;
 
//
// erase items from the list and map
//
 
void remove()
{
   List list;
   List::iterator lit;
   Map::iterator mit;
 
   int total=0, erased=0 ;
 
   for ( mit = map.begin(); mit != map.end();  )
   {
      // The actual program worked by
      // changing this to List &list = mit->second;
      list = mit->second;  
      
      for ( lit = list.begin();  lit != list.end();  )
      {
          ++ total;
 
          if (cond)
          {  
             lit = list.erase( lit );
             ++ erased;
          }
      }
 
      if( list.empty() )
      {
         map.erase( mit++ );
      }
      else
         ++mit;
   }
 
   printf( "Total objects = %d,  Erased objects = %d \n",  total, erased );
}
 
//
// main
//
int main()
{
   List::iterator lit;
   Map::iterator mit;
 
   ZAB zab;
 
   for(int i=1; i<=100;  ++i )
   {
      for(int  j=1; j<=100; ++j )
      {
         zab.a = j;
         zab.b = 0;
         zab.d = i+j;
 
         map[i].push_back(zab);
      }
   }
   
   remove();
   .
   .
   .
   remove();   
 
   return 0;
}

Open in new window

zabbasAsked:
Who is Participating?
 
Infinity08Connect With a Mentor Commented:
Your test code "works", because you erase ALL of the list items, and thus this line :

>>       gMap.erase(mit++);

is executed for every map entry.

After the first remove() call, the map will be completely empty, so the second remove() call has nothing to remove any more.

Try modifying your test code so that you only remove some of the list items, and you'll see that the map remians unchanged, and the second remove() call will try to remove the same items once again.
0
 
mrjoltcolaConnect With a Mentor Commented:
I am not clear on your specific question, it seems there are several:

>> list = mit->second;   in the remove() function to
>>               List &list = mit->second;


list = mit->second makes a _copy_ of the whole list, so then if you call list.erase() it will only remove from list, not mit->second, so the item being removed is still left in the original mit->second list, which is not correct. As well, the assignment will likely take a while for a lot of elements.

List &list = mit->second uses a reference, so list points to the original mit->second list, so remove works as expected.
0
 
zabbasAuthor Commented:
Yes I understand the copy/reference difference but what I do not understand is that the sample code above worked correctly even with copy list.
0
Cloud Class® Course: Microsoft Office 2010

This course will introduce you to the interfaces and features of Microsoft Office 2010 Word, Excel, PowerPoint, Outlook, and Access. You will learn about the features that are shared between all products in the Office suite, as well as the new features that are product specific.

 
efnCommented:
It might help if you provide sample code that compiles.
0
 
zabbasAuthor Commented:
Here is the compilable code:
#include <stdlib.h>
#include <stdio.h>
#include <list>
#include <map>
 
using namespace std;
 
class ZAB 
{  
  public:
 
    ZAB () ;
 
    ZAB (const ZAB& rRefObj) ;
 
    ZAB& operator = (const ZAB& rRefObj) ;
 
 
    int     a;
    int     b;
    int     c;
    
 
};
 
ZAB::ZAB () : 
  a (0),
  b (0),
  c (0)
{}
 
ZAB& ZAB::operator = (const ZAB& rRefObj)
{
  a    = rRefObj.a ; 
  b    = rRefObj.b ;
  c    = rRefObj.c ;
  return *this;   
}
 
ZAB::ZAB (const ZAB& rRefObj) :
  a (rRefObj.a),
  b (rRefObj.b),
  c (rRefObj.c),  
{}
 
 
typedef list <ZAB> List;
typedef map  <long, List> Map;
 
Map gMap;
 
void remove()
{
  List tmpList;
  List::iterator lit;
  Map::iterator mit;
  
  int t=0;
     
  for ( mit=gMap.begin(); mit!=gMap.end(); )
  {
    tmpList = mit->second;
 
    for ( lit=tmpList.begin(); lit!=tmpList.end(); )
    {
      lit = tmpList.erase(lit);
      ++t;
    }
 
    if( tmpList.empty() )
      gMap.erase(mit++);
    else
      mit++;
  }
 
  printf("Total %d\n", t);
}
 
int main(void)
{
 
   List::iterator lit;
   Map::iterator mit;
 
   ZAB zab;
 
   for(int i=1; i<=100; i++ )
   {  
     for(int j=1; j<=100; j++ )
     {
       zab.a = j;
       zab.b = 0;
       zab.c = j+1;  
       
       gMap[i].push_back(zab);
     }
   }
 
   remove();
   remove();  
   
   return 0;
}

Open in new window

0
 
mrjoltcolaCommented:
I pointed out that copying a container, then removing the item from the copy, is incorrect. You say your code works correctly either way. It is still incorrect, so I don't understand your latest question. Please clarify. Thanks.
0
 
zabbasAuthor Commented:
@Infinity08

Thanks for the hint. I actually did that couple of times before posting this question but I guess I was not careful about the results and assumed it is working as expected. But now when I thought again about the actual code, I realized what was wrong in my statistics. You are right the elements are erased only from copy list and if it is not empty map items will not be removed but the incrementing counter for each iteration gives false stats.

Now I am confused to whom I should award points. mrjoltcola obviously pointed the copy/reference thing which is the main bug. However the hint from infinity08 made me realized that the method for statistics was wrong.

What do you both say about points? Is it ok if I divide the points between you?

0
 
mrjoltcolaCommented:
@zabbas - divide according to how the advice helped you, I'm glad I could contribute. Good luck.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.