stl::map的erase与std::vector的erase行为不同

Question

 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);

我已经调试了这两种情况。在两种情况下，我都在删除第二个元素。对于向量，它会将第3个元素复制到第2个位置，然后再删除第3个位置。

所以当您说...

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

它正在调用赋值运算符（CSensor =），然后调用析构函数。

在使用map时，当我执行

   ListSensor.erase(2);

它只调用析构函数。

我阅读了关于STL vector vs map erase的文章（英文），其中涉及到迭代器，但无法解释其行为。

我的问题是：为什么这两个STL容器的erase行为不同？

- Vikram Ranabhatt

---

因为它们是不同的容器？你为什么会期望它们以完全相同的方式工作？那它们为什么都存在呢？！ - Lightness Races in Orbit

C++ 是一种大小写敏感的编程语言，因此在交流时保持精确性非常重要。 - David Rodríguez - dribeas

Answer 1

这并不是.erase本身的行为，而是每个相应容器工作方式的结果。

从向量中删除

从一个向量中删除时^{（顺便说一句，List作为一个向量来说，名称真的非常糟糕）}，它的内容必须重新排列以填补空缺，因为向量中的元素始终以连续方式存储在内存中。

通常通过复制（或移动）元素，然后裁剪余下的部分来完成这一操作：

• 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 |
  +---+---+---+---+---+---+---+---+
  

---

从地图中删除数据

对于一个地图，它的内容并不一定是在内存中连续存储的（其复杂度要求意味着它几乎总是由指向不连续数据的树结构填充而成）。

- Lightness Races in Orbit

---

我同意@Tomalak Geret'kal的观点。我只是想扩展一下讨论。数据结构是导致向量无效迭代器的原因，而在映射中不会使迭代器失效。 - Vikram Ranabhatt

@Chris_vr：那个问题实际上没有什么意义。向量和映射都是容器类型，所以“数据结构”（正如你所说）对我们讨论的_所有内容_都是相关的。 - Lightness Races in Orbit

非常漂亮的图解回答 :) - moka

@Chris_vr：（然而，是的，元素在各自容器中存储方式的差异_导致了_每个容器具有不同的迭代器失效规则。） - Lightness Races in Orbit

@Tomalak Geret'kal 好的好的，你是对的！特别是当你是正确的时候，你不喜欢被反驳;-) - Pedro Ferreira

Answer 2

这就是拥有不同容器的原因之一！

向量必须复制跟在已删除元素后面的元素，以填补它所留下的“空洞”。否则，元素将不再是连续的。

映射将其元素保存在树结构中，只需调整一些指针即可重新平衡树。

为了保护向量：复制一些元素可能比单独分配树节点并保持树平衡更便宜。总是存在权衡！

- Bo Persson

---

小问题；标准并不要求std::map使用树结构。它只是设置了一些要求，以在合理的实现中引导您到达那里。 - Lightness Races in Orbit