C++ 删除元素、压缩容器的惯用法

gaunthan Posted on Nov 9 2016

? C++ ?

> 要真正地压缩容器的多余容量，应该使用“swap魔术“惯用法(swap-magic idiom)。要真正地删除容器中的元素，应该使用 erase-remove 惯用法。 ——《The C++ Coding Standard》

## 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.