[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 498
  • Last Modified:

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

0
zabbas
Asked:
zabbas
2 Solutions
 
mrjoltcolaCommented:
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
 
efnCommented:
It might help if you provide sample code that compiles.
0
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
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
 
Infinity08Commented:
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
 
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

Featured Post

Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now