C++ 删除元素、压缩容器的惯用法 gaunthan Posted on Nov 9 2016 ? C++ ? > 要真正地压缩容器的多余容量,应该使用“swap魔术“惯用法(swap-magic idiom)。要真正地删除容器中的元素,应该使用 erase-remove 惯用法。 ——《The C++ Coding Standard》 <!--more--> ## swap-magic惯用法 ### Example 有些容器(例如 vector、string、deque)可能最后会具有不再需要的多余容量。比如我们有一个周期收集、处理数据的过程: ```cpp ... vector<double> dvect; dvect.reserve(100); // 数据一般接近一百个,因此预留100个元素空间 .... // 收集数据,但今天的收集量比较少,可能只有20个 ... // 使用数据 ``` 上面这样的案例有大量的内存空间被空置着,导致资源利用率下降。因此需要有一种简单的方式,调整它的容量。 ### shrink-to-fit 惯用法 虽然 C++ 标准库容器没有提供一些保证可行的方法去除多余容量,但是下面的“swap魔术”惯用法确实可以去除类似 Container 类型容器 c 的多余容量: ```cpp Container<T>(c).swap(c); // 去除多余容量的shrink-to-fit惯用法 ``` 上面的代码首先调用了 Container<T> 的拷贝构造函数,生成了一个临时的容器对象,该容器中的元素是 c 的一个拷贝,但是它的总大小是合适的,没有多余的空间。之后通过 `swap` 成员函数交换两个容器,使得 c 的容量压缩到合适了。最后离开这个作用域时,临时容器对象会自动析构。 ### 去除全部内容和容量的惯用法 如果要将容器完全清空,清除所有存放的元素并去除所有可能的容量,则惯用法为: ```cpp Container<T>().swap(c); // 去除全部内容和容量的惯用法 ``` 需要注意的是使用 `clear` 成员函数只能清除容器中的元素,而不会去除容量。 ## erase-remove 惯用法 有一件事经常会使 STL 新手感到惊奇:`remove` 算法并不真正地从容器中删除元素,当然它也办不到,毕竟它只操作于迭代器范围,不调用容器的成员函数。 remove 所做的就是移动值的位置,将不应该“删除”的元素移到范围的开始处,并返回一个迭代器指向最后一个不应删除元素的下一位置(相当于是第一个应该被删除元素的位置)。要真正地删除元素,则需要在调用 remove 之后再调用 erase。这就是所谓地 erase-remove 惯用法。 如要删除容器中所有等于 value 的元素,可以这样编程: ```cpp c.erase(remove(c.begin(), c.end(), value), c.end()); ``` 对于有 remove 或 remove_if 成员函数的容器,应该尽量使用这两个函数的成员版本。 ## 注意事项 通常的 shrink-to-fit 惯用法对写时拷贝(copy-on-write)方式实现的 std::string 不适用。因为使用拷贝构造函数构建一个用于交换的临时对象时,其底层是和目标共享的。这意味着交换并没有起到实际作用。 总是可行的方法是: - 调用 `s.reserve(0)` - 通过编写 `string(s.begin(), s.end()).swap(s);`,用迭代器范围构造函数来压缩 string 的多余容量。 ## References - Meyers S. Effective C++[M]. 电子工业出版社, 2011. 赏 Wechat Pay Alipay C++ 留意迭代器操作 二维码的生成细节和原理