How to destructor STL container correctly?/如何正确使用erase释放STL容器？

crazyzlj commented 7 years ago

STL中容器的释放：到底如何使用erase()

STL中erase()函数的功能是用来删除容器中元素的，在析构函数中释放容器内内存资源尤其重要。

然而，看似简单的动作，对不同类型的容器，内部缺做了截然不同的事情，而且不同编译器的实现也有差异。

容器按内存分配方式可以分为链表容器和数组容器，所谓链表容器是指一种表现方式，包括list、slist等这样基于节点的容器（动态分配内存块）和set、map、multiset、multimap等关联容器（平衡树实现），而数组容器则指的是在一块连续的内存上保存元素的连续内容容器，比如vector、deque、string等。

先看结论

 /// 链表容器，以map为例
for (map<int, float*>::iterator it = map1.begin(); it != map1.end(); ) {
    //it = map1.erase(it); /// VS支持，Intel C++ 12，GCC 4.4.6不支持
    map1.erase(it++); /// 推荐用法
}

/// 数组容器，以vector为例
for (vector<Info *>::iterator it = vec1.begin(); it != vecs.end(); ) {
    it = vec1.erase(it); /// 推荐用法
    //vec1.erase(it++); /// Intel C++ 12，GCC 4.4.6支持，VS不支持
    //vec1.erase(it); /// Intel C++, GCC,及VS2005支持，但是不推荐
}

链表容器以map为例，当执行map1.erase(it)时，确实第一个满足条件的元素删除了，但这时it指针已经被删除了，它也不指向任何元素了，所以也只能到此为止了，也就是说上面的代码对于链表容器来说只能正确删除第一个满足条件的元素，针对这个问题我们首先想到的就是在删除指针之前，给其做个备份。将这个临时变量直接建立在erase实现里，这样做更简洁，也显得专业些，map1.erase(it++)。
链表容器使用erase删除节点还有一个特点，就是会将下一个元素的地址返回，所以也可以这样实现，it = map1.erase(it)，然而这种用法不一定所有的编译器都支持。
数组容器以vector为例，当执行vec1.erase(it)时，和上面提到的一样，第一个满足条件的元素删除了，但这时数组容器不允许中间有“空隙”，所以会做个大动作，就是将被删元素后面所有的元素前移（参考STL源码），而数组容器记录的是下标，所以删除元素后，当前下标定位的元素也就顺理成章的变成了原有队列中的下一个元素，理论上可以直接用vec1.erase(it)，但是由于不同编译器的实现差异，保险起见，建议it = vec1.erase(it)。

crazyzlj commented 6 years ago

Use auto when declaring iterators (C++11).

/// 链表容器，以map为例
for (auto it = map1.begin(); it != map1.end(); ) {
    //it = map1.erase(it); /// VS支持，Intel C++ 12，GCC 4.4.6不支持
    map1.erase(it++); /// 推荐用法
}

/// 数组容器，以vector为例
for (auto it = vec1.begin(); it != vecs.end(); ) {
    it = vec1.erase(it); /// 推荐用法
    //vec1.erase(it++); /// Intel C++ 12，GCC 4.4.6支持，VS不支持
    //vec1.erase(it); /// Intel C++, GCC,及VS2005支持，但是不推荐
}

crazyzlj commented 2 years ago

clear() vs erase()

Takes std::vector as an example.

`vector::clear()`

The vector::clear() function is used to remove all the elements of the vector container, thus making it size 0. Its time complexity is O(N). All elements are destroyed one by one.

`vector::erase()`

The vector::erase() function is used to remove elements from a container from the specified position or range. Its time complexity O(N^2) in the worst case as an erase takes linear time.

When to use what?

clear() removes all the elements from a vector container, thus making its size 0. All the elements of the vector are removed using the clear() function. erase() function, on the other hand, is used to remove specific elements from the container or a range of elements from the container, thus reducing its size by the number of elements removed.

简言之，当需要全部删除容器中元素时要用clear()，当然，需要注意的是，如果容器元素需要释放内存，一定要在clear()之前逐个释放；当需要删除容器中已知位置的某个或某些元素时，用erase()。

Reference: vector-erase-and-clear-in-cpp

lreis2415 / SEIMS