3
 class CSensor
 {
    public:
    CSensor(int nVal1,char* pVal2,unsigned int nVal3);
    CSensor(const CSensor& refMessage);
    const CSensor& operator=(const CSensor& refMessage);
   ~CSensor(void);
   private:
   int m_nVal1;
   char* m_pVal2;   
   unsigned int m_nVal3;
 };

 // vector erase

 std::vector<CSensor> SensorList;
 CSensor obj1(1,"Test1",10);
 SensorList.push_back(obj1);
 CSensor obj2(2,"Test2",11);
 SensorList.push_back(obj2);
 CSensor obj3(3,"Test3",12);
 SensorList.push_back(obj3);

 SensorList.erase (SensorList.begin()+1);



// map erase
    std::map<int ,CSensor> ListSensor;
CSensor obj11(1,"Test1",10);    
CSensor obj12(2,"Test2",11);
CSensor obj13(3,"Test3",12);

ListSensor.insert(std::pair<int,CSensor>(1,obj11));
ListSensor.insert(std::pair<int,CSensor>(2,obj12));
ListSensor.insert(std::pair<int,CSensor>(3,obj13));

ListSensor.erase(2);

I debugged both the case. In both the cases i am deleting the second element.In case of vector it is copying 3 element to 2nd poition and than it it deleting the 3 rd location.

So when u say 

   List.erase (List.begin()+1);

it is calling assignment operator(CSensor=) and then calling destructor.

In case of map when i do 

   ListSensor.erase(2);

it only calls the destructor.

I have gone through STL vector vs map erase. It talks Iterator,couldn't explain the behavior.

My question is why erase behaves differently for these two STL container??

Community
  • 1
  • 1
Vikram Ranabhatt
  • 7,268
  • 15
  • 70
  • 133

2 Answers2

6

This is not a behaviour of .erase per se, but a consequence of how each respective container works.

Deleting from a vector

When you delete from a vector (List is a really poor name for a vector, btw), its contents must be shuffled along to fill the gap because the elements of a vector are always stored contiguously in memory.

This is generally done by copying (or moving) elements then chopping off the remainder:

  • Vector elements in memory:

    +---+---+---+---+---+---+---+---+---+
| a | b | c | d | e | f | g | h | i |
+---+---+---+---+---+---+---+---+---+

  • Erase 'e':

    +---+---+---+---+---+---+---+---+---+
| a | b | c | d |   | f | g | h | i |
+---+---+---+---+---+---+---+---+---+

  • Fill the gap by copying/moving across:

                       <--
+---+---+---+---+---+---+---+---+---+
| a | b | c | d | f | f | g | h | i |
+---+---+---+---+---+---+---+---+---+

                       <--
+---+---+---+---+---+---+---+---+---+
| a | b | c | d | f | g | g | h | i |
+---+---+---+---+---+---+---+---+---+

                           <--
+---+---+---+---+---+---+---+---+---+
| a | b | c | d | f | g | h | h | i |
+---+---+---+---+---+---+---+---+---+

                               <--
+---+---+---+---+---+---+---+---+---+
| a | b | c | d | f | g | h | i | i |
+---+---+---+---+---+---+---+---+---+

  • Resize the container:

    +---+---+---+---+---+---+---+---+
| a | b | c | d | f | g | h | i |
+---+---+---+---+---+---+---+---+

Deleting from a map

This is not the case for a map, whose contents are not necessarily stored contiguously in memory (in fact, the complexity requirements mean it's almost always a tree structure filled with pointers to discontiguous data).

Lightness Races in Orbit
  • 378,754
  • 76
  • 643
  • 1,055
  • I agree @Tomalak Geret'kal.I just want to expand the discussion . Is Data Structure the reason for Invalid iterator for vector where as in map doesn't invalidate the iterator. – Vikram Ranabhatt Aug 11 '11 at 09:06
  • @Chris_vr: That question doesn't really make sense. Both vector and map are types of containers, so "Data Structure" (as you put it) is relevant to _everything_ we're discussing. – Lightness Races in Orbit Aug 11 '11 at 09:08
  • very nicely illustrated answer :) – moka Aug 11 '11 at 09:08
  • @Chris_vr: (However, yes, the differences in the way elements are stored in the respective containers _contributes_ to the different [iterator invalidation rules](http://stackoverflow.com/questions/6438086/iterator-invalidation-rules) for each.) – Lightness Races in Orbit Aug 11 '11 at 09:08
  • this is a good explanation about memory internals but it doesn't answer the question about calling the operator=... – Pedro Ferreira Aug 11 '11 at 09:25
  • @Pedro: Yes it does. `operator=` is invoked to shuffle those elements along... "Fill the gap by copying/moving across" – Lightness Races in Orbit Aug 11 '11 at 09:27
  • @Tomalak Geret'kal ok ok, you're right! you don't like to be contradicted, specially when you're right ;-) – Pedro Ferreira Aug 11 '11 at 09:38
3

This is one reason to have different containers!

The vector has to copy the elements following the eased element to cover the "hole" that it left. Otherwise the elements wouldn't be contiguous anymore.

The map holds its elements in a tree structure and just has to adjust some pointers to rebalance the tree.

To the vector's defense: Copying a couple of elements might be cheaper than allocating tree nodes separately and keeping the tree balanced. There are always tradeoffs!

Bo Persson
  • 90,663
  • 31
  • 146
  • 203