Effective STL - 02 - Vector and String

Vector and String

条款13：尽量使用vector和string来代替动态分配的数组

无论何时，你发现你自己准备动态分配一个数组（也就是，企图写“new T[…]”），你应该首先考虑使用一个vector或一个string。

坦白地说，我想到了一个（也是唯一一个）用vector或string代替动态分配数组会出现的问题，而且它只关系到string。很多string实现在后台使用了引用计数（参见条款15），一个消除了不必要的内存分配和字符拷贝的策略，而且在很多应用中可以提高性能。事实上，一般认为通过引用计数优化字符串很重要，所以C++标准委员会特别设法保证了那是一个合法的实现。

唉，一个程序员的优化就是其他人的抱怨，而且如果你在多线程环境中使用了引用计数的字符串，你可能发现避免分配和拷贝所节省下的时间都花费在后台并发控制上了。（细节请参考Sutter的文章《Optimizations That Aren’t (In a Multithreaded World)》[20]。）如果你在多线程环境中使用引用计数字符串，就应该注意线程安全性支持所带来的的性能下降问题。

条款14：使用reserve来避免不必要的重新分配

如果我们知道、或者能够预测出 vector 的大小，那么就能够使用 reserve 预先申请足够的大小。

以下是四个与内存分配有关的函数的介绍：

  • size() 获取到 vector 中元素的数量
  • capacity() 获取 vector 中已分配的内存可以容纳多少元素
  • resize() 强制将当前容器的大小设置为 n。
    • 如果 n > size() ，会销毁元素到 n 个，size() 会返回 n 的大小，不会影响 capacity() 的大小
    • 如果 capacity() > n > size() ，会以默认值填充，不影响 capacity
    • 如果 n > capacity() ，会构造新元素（按照添加新元素的方法去申请内存），再填充
  • reserve() 会申请容纳 n 个元素的内存，但是不会影响 size，影响的是 capacity。reserve 应该应用在使用尾插法增加元素的 vector 中，如果完全确定容器的大小，可以使用 resize 。
    • 如果完全确定容器的大小，应该先使用 reserve 申请足够的内存，然后使用 resize 改变容器的大小，这样不会导致额外的内存占用

测试如下：

1
2
3
4
5
6
7
8
9
10
11
vector<int> v = {0, 1, 2, 3, 4};
v.reserve(100);  // size=5, capacity=100
cout << "size of v: " << v.size() << ", capacity of v: " << v.capacity() << endl;
v.resize(50);    // size=50, capacity=100
cout << "size of v: " << v.size() << ", capacity of v: " << v.capacity() << endl;
v.reserve(101);  
v.resize(101);  // size=101, capacity=101
cout << "size of v: " << v.size() << ", capacity of v: " << v.capacity() << endl;
// size=5, capacity=101
v.resize(5);    // capacity() 不受影响, 因此才有后面的 shrink
cout << "size of v: " << v.size() << ", capacity of v: " << v.capacity() << endl;

条款15：小心string实现的多样性

介绍了 string 的 4 中实现，每种实现由不同的性质，例如可能使用了引用计数（TODO：检查 string 中的引用计数）。

Untitled.png

Untitled 1.png

Untitled 2.png

Untitled 3.png

总结如下：

  • 字符串值可能是或可能不是引用计数的。默认情况下，很多实现的确是用了引用计数，但它们通常提供了关闭的方法，一般是通过预处理宏。条款13给了一个你可能要关闭的特殊环境的例子，但你也可能因为其他原因而要那么做。比如，引用计数只对频繁拷贝的字符串有帮助，而有些程序不经常拷贝字符串，所以没有那个开销。
  • string对象的大小可能从1到至少7倍char指针的大小。（部分 string 的实现只有一个 char 指针，有些还可能存放了 size、capacity）
  • 新字符串值的建立可能需要0、1或2次动态分配。
  • string对象可能是或可能不共享字符串的大小和容量信息。
  • string可能是或可能不支持每对象配置器。
  • 不同实现对于最小化字符缓冲区的配置器有不同策略。（类似 vector 那样的 capacity）

条款16: 如何将vector和string的数据传给遗留的API

vector 代表了 T，而 string 并不一定代表了 char，因为有些 string 的实现可能并不会保留 \0 ，因为 string 带有 size 信息。

1
2
3
4
5
6
7
// 获取 数组指针
vector<int> v;
doSth(&v[0]);

// 获取 字符串指针
string s{"1234abcd"};
doSth(s.c_str());

使用数组指针和字符串指针时需要注意：

  • 不要修改大小，以及在未申请的内存中构造元素

一个通用的方法是 构造-拷贝 ： 

1
2
3
4
5
6
7
8
9
10
size_t fillArray(double *pArray, size_t arraySize); // 同上

// 如果使用 C API 构造了元素，需要及时 resize
// 否则 vector 再也无法知道自己的大小了
vector<double> vd(maxNumDoubles); // 一样同上
vd.resize(fillArray(&vd[0], vd.size()));

deque<double> d(vd.begin(), vd.end()); // 拷贝数据到deque
list<double> l(vd.begin(), vd.end()); // 拷贝数据到list
set<double> s(vd.begin(), vd.end()); // 拷贝数据到se

条款17：使用“交换技巧”来修整过剩容量

1
2
3
4
5
6
7
8
9
vector<int> v(100, 1);
// 使用 shrink_to_fit
v.resize(10);
v.shrink_to_fit();

// 使用 swap 技巧
v.reserve(100);
v.resize(10);
vector<int>(v).swap(v);

shrink_to_fit：

1
2
3
4
5
6
7
8
9
10
11
12
_CONSTEXPR20 void shrink_to_fit() { // reduce capacity to size, provide strong guarantee
    auto& _My_data         = _Mypair._Myval2;
    const pointer _Oldlast = _My_data._Mylast;
    if (_Oldlast != _My_data._Myend) { // something to do
        const pointer _Oldfirst = _My_data._Myfirst;
        if (_Oldfirst == _Oldlast) {  // 如果数组为空, 释放所有内存
            _Tidy();
        } else {  // 否则重新分配
            _Reallocate_exactly(static_cast<size_type>(_Oldlast - _Oldfirst));
        }
    }
}

条款18：避免使用vector

作为一个 vector，它既不 vector，也不 bool。

vector 的实现是一个位域，即一个字节，包含了 8 个 bool。所以，无法得到 vector 的元素的指针。只能得到一个 代理对象：

1
2
// reference 不是真正的指针, 只是一个 “代理对象”
vector<bool>::reference

在 MSVC 的实现中，vector<bool> 做了额外的模板特化。

如果需要使用 vector，可以使用 deque 或者 bitset 。vector不满足STL容器的必要条件，你最好不要使用它；而deque和bitset是基本能满足你对vector提供的性能的需要的替代数据结构。

条款19：了解相等和等价的区别

相等 等价
operator==(lhs, rhs) !(lhs < rhs) && !(rhs < lhs)
== 返回 True 两个对象 互相不大于 对方

一些函数对于相等和等价的要求不同：

  • find 函数是基于相等的
  • sort、标准关联容器（set、map、multiset、multimap）以及多种基于比较的标准函数，都是基于等价的。

条款20：为指针的关联容器指定比较类型

指针的关联容器只会比较指针的值，即对指针的 size_t 排序，而不是对 *T 进行排序。对于普通指针和只能指针，都需要手动提供一个比较类型

条款21: 永远让比较函数对相等的值返回false

你所要记住的就是比较函数的返回值表明的是在此函数定义的排序方式下，一个值是否大于另一个。相等的值绝不该一个大于另一个，所以比较函数总应该对相等的值返回false。

如果发生了小于等于，程序会直接报错（segment fault）。

1
2
3
4
5
6
7
8
9
// 错误
[] (int& lhs, int& rhs) {
    return lhs <= rhs;
}

// 正确
[] (int& lhs, int& rhs) {
    return lhs < rhs;
}

sort 的手动实现可以查看 排序 ，在这个实现中，如果使用了小于等于，会存在变量的排序位置错误。

条款22：避免原地修改set和multiset的键

set 的声明：set<T> ，map 的声明：map<const K, V> ，因此，map 的 key 是无法被修改的，但是 set 的 key 是可以被修改的。修改了 set 的 key 之后会导致 set 内部的有序性被破坏，容器再也不是一个 set 了。

为什么 set 是 T 而不是 const T？

因为自定义的 operator<() 函数可能只使用到了类中的部分成员，举例如下：

1
2
3
4
5
6
7
8
9
10
11
struct IDNumberLess{
 public binary_function<Employee, Employee, bool> { // 参见条款40
 bool operator()(const Employees lhs,
 const Employee& rhs) const
 {
 return lhs.idNumber() < rhs.idNumber();
 }
};
typedef set<Employee, IDNumberLess> EmpIDSet;
EmpIDSet se; // se是雇员的set，
 // 按照ID号排序

如果你要总是可以工作而且总是安全地改变set、multiset、map或multimap里的元素，按五个简单的步骤去做：

  1. 定位你想要改变的容器元素。如果你不确定最好的方法，条款45提供了关于怎样进行适当搜寻的指导。
  2. 拷贝一份要被修改的元素。对map或multimap而言，确定不要把副本的第一个元素声明为const。毕竟，你想要改变它！
  3. 修改副本，使它有你想要在容器里的值。
  4. 从容器里删除元素，通常通过调用erase（参见条款9）。
  5. 把新值插入容器。如果新元素在容器的排序顺序中的位置正好相同或相邻于删除的元素，使用insert的“提示”形式把插入的效率从对数时间改进到分摊的常数时间。使用你从第一步获得的迭代器作为提示。
1
2
3
4
5
6
7
set<int> s = {5, 3, 6, 8, 1, 2, 0};

// 删除一个 key, 并在重新插入时 给定 hint
auto it = s.find(2);
// s.erase(it++);          // 自增迭代器, 以确保迭代器有效
it = s.erase(it);    // 更新迭代器, 以确保迭代器有效
s.insert(it, 2);

MSVC 的实现就是一个 set<const T> ：

1
2
3
4
set<pair<int, int>> sp = {{0, 1}, {-1, 2}, {3, 9}, {2, 6}};
for_each(sp.begin(), sp.end(), [] (const pair<int,int>& p) {  // 必须是 const 或者 auto
    cout << "<" << p.first << ", " << p.second << ">, ";
});

条款23：考虑用有序vector代替关联容器

因为 关联容器 的内部保存了一个有序的结构，因此 一个有序的 vector 能够用于替代关联容器。使用有序 vector 代替关联容器的关键在于：

  • vector 的插入和删除较少，或者没有。因为移动会带来大量的数据拷贝。
  • 对于查找操作，可以使用 binary_search、lower_bound 等
  • 有序 vector 比关联容器更优秀的地方在于：
    • 内存局部性更高
    • 减少了指针，内存页能够容纳的数据更多

条款24：当关乎效率时应该在map::operator[]和map-insert之间仔细选择

这项工作的原理是operator[]返回一个与k关联的值对象的引用。然后v赋值给所引用（从operator[]返回的）的对象。当要更新一个已存在的键的关联值时很直接，因为已经有operator[]可以用来返回引用的值对象。但是如果k还不在map里，operator[]就没有可以引用的值对象。那样的话，它使用值类型的默认构造函数从头开始建立一个，然后operator[]返回这个新建立对象的引用。

因此出于对效率的考虑，当给map添加一个元素时，我们断定insert比operator[]好；而从效率和美学考虑，当更新已经在map里的元素值时operator[]更好。

如下是一个结合 insert 和 operator[] 的函数，能够结合二者的好处：

1
2
3
4
5
6
7
8
9
10
11
12
13
template <typename K, typename V>
map<K,V>::iterator dynamicInsert(map<K, V>& s, K k, V v) {
    // 找到  距离 k 最近的元素
    auto it = s.lower_bound(k);
    if (it->first == k) {
        // 更新元素
        it->second = v;
        return it;
    } else {
        // 插入元素, 注意插入时会返回新元素的迭代器
        return s.insert(it, {k, v});
    }
}

条款25：熟悉非标准散列容器

在C++标准委员会的议案中，散列容器的名字是unordered_set、unordered_multiset、unordered_map和unordered_multimap。恰好是为了避开现存的hash_*名字。

哈希冲突的解决方案：开放地址法、拉链法。

Effective STL
#C++ #STL #Vector #String
Effective STL - 02 - Vector and String
http://hebangwen.github.io/2024/03/17/Vector-and-String/
作者
何榜文
发布于
2024年3月17日
许可协议