STL容器的内存以及元素删除注意事项

STL中各个容器的内存的释放

1.vector总是不会释放内存
删除向量容器的元素时，并不会使空闲的空间被释放，这时可以使用下面的语句达到释放多余空间的目的（ s 表示目的容器，T表示容器的元素类型）：
vector<T>(s.begin(), s.end(), swap(s));
即首先用 s 的内容创建一个临时的向量容器对象，再将该容器和 s 交换，这时 s 原先占有的空间已经属于临时对象，该语句执行完成后临时对象会被析构，空间被释放。

2.deque有时会释放内存
deque的内存区块不再被使用时，会被释放。deque的内存大小是可缩减的。不过，是不是这么做以及怎么做由实际版本定义。

3.list,set,multiset,map,multimap总是会释放内存
list一般实现为一个双向链表，而set、multiset、map、multimap一般实现为一个平衡二叉树。当容器中元素被删除时，元素所占的内存被释放。

容器删除的坑.

对于关联容器(如map, set, multimap,multiset)，删除当前的iterator，仅仅会使当前的iterator失效，只要在erase时，递增当前iterator即可。这是因为map之类的容器，使用了红黑树来实现，插入、删除一个结点不会对其他结点造成影响

1. for (iter = container.begin(); it != container.end();)
2. {
3.   (*iter)->doSomething();
4.   if (shouldDelete(*iter))
5.     container.erase(iter++);
6.   else
7.     ++iter;
8. }

===========================================================
对于序列式容器(如vector,deque)，删除当前的iterator会使后面所有元素的iterator都失效。这是因为vetor,deque使用了连续分配的内存，删除一个元素导致后面所有的元素会向前移动一个位置。还好erase方法返回的是下一个有效的iterator。

1. for (iter = container.begin(); iter != container.end();)
2. {
3.   (*it)->doSomething();
4.   if (shouldDelete(*iter))
5.     iter = container.erase(iter);
6.   else
7.     ++iter;
8. }

==========================================================
对于list来说，它使用了不连续分配的内存，并且它的erase方法也会返回下一个有效的iterator，因此上面两种方法都可以使用。

******************************************************************************
******************************************************************************
******************************************************************************

其他技巧

删除值为val的元素. 最标准的在vector中删除值为5的元素的方法
void EraseVec()
{
    std::vector vec{ 1, 2, 3, 4, 5, 5, 6, 7 };
    vec.erase(std::remove(vec.begin(), vec.end(), 5), vec.end());
}
remove做的操作是移除而erase是删除. remove 仅仅是把移除的内容放到了相应的内存末尾.

iterator erase (iterator begin, iterator end);
//tips : 删除容器中迭代器在[first; last)范围内的元素
//return : 最后一个被删除的元素的下一个元素的迭代器

iterator remove(iterator begin, iterator end, val);
//tips : 移除容器中迭代器在[first; last)范围内的值为val的元素
//return : 被成功移除的之后，剩余的有效元素的下一个元素的迭代器

删除满足某个条件的元素
void EraseVecIf()
{
    std::vector vec{ 1, 2, 3, 4, 5, 5, 6, 7 }; 
    vec.erase(std::remove_if(vec.begin(), vec.end(), 
    [](int elem)
    {
        return elem % 2 == 0;
    }), 
    vec.end());
}

void EraseList()
{
    std::list ls{ 1, 2, 3, 4, 5, 5, 6, 7 };
    ls.remove(5);
    ls.remove_if([](int elem) { return elem % 2 == 0; });
}