Effective STL-2 vector 和 string
part2 vector 和 string
2个最常用的容器
数组的用途是如此广泛, 设计 vector 和 string 的目的是为了代替大多数应用中使用的数组
[1] `为什么值得 从数组转` 到 vector 和 string
[2] `提高` vector 和 string `效率`的途径
[3] 指出 `不同 string 实现` 的重要区别
[4] 研究如何把 vector 和 string 的 `数据传给 C API`
[5] 避免 `不必要的内存分配`
[6] 特例 vector<bool>, 1个功能不完全的 vector
Note: 数组不能被 vector 完全替代的原因
vector 不是 POD
用 POD 表达数据, 无论嵌套多少层, 最终数据仍然是1块连续内存, 可方便 拷贝、清楚、dump 到硬盘
struct data
{
int a;
int arr[N];
int b;
};
struct data
{
int a;
vector<char> v;
int b;
};
item13：vector 和 string 优先于 动态分配的 数组
1 用 new 动态分配内存 -> client 将承担的责任
(1) 没有 delete -> 资源泄漏
(2) 正确形式的 delete: 分配单个对象/数组 -> delete / delete[] -> 否则, undefined behavior
(3) 必须保证只 delete 一次; 否则, 若 delete 多次 -> undefined behavior
2 每当想要 动态分配数组( new T[...] ) 时, 都应该考虑用 vector 或 string 来代替
(1) 原因
[1] vector 和 string 自己管理内存
当`元素被加入到容器中`时, 它们的 `内存会增长`;
当vector 或 string `被析构`时, 它们的 `Dtor` 会 `自动析构 容器中的(所有)元素` 并 `释放`包含这些元素的`内存`
[2] vector 和 string 是功能完全的STL序列容器, 所以, 凡是适合于序列容器的STL算法, 都可以使用
(2) 选 vector 还是 string
一般, T 是 字符类型时, 用 string; 否则, 用 vector.
特例: string 带 RCSP, 多线程下影响效率, vector<char> 可能更高效/合理
3 可能需要使用 动态分配的数组(取代 vector 和 string) 的1种情况, 且这种情况只对 string 适用
什么情况下 ???
(1) 想用 `字符数组` => 不要用 vector 或 vector<char>
(2) 但 `不需要 引用计数` => 不要用 string(大多 string 实现采用引用计数)
4 多线程 & string & 引用计数
(1) 多线程下的引用计数
引用计数: 避免不必要的 内存分配 和 字符拷贝 => 提高效率
但, 多线程下, 为了 保证引用计数的 线程安全 而引入的 同步控制 的耗时 > 由避免不必要的 内存分配 和 字符拷贝 所节省的时间
=> 多线程下, 引用计数 影响效率/性能问题
=> 多线程下, 若 选择 STL, 则应该避免 引用计数
[1] 看是否能 禁用 string 的引用计数
[2] 寻找或开发不使用引用计数 的 string (部分) 实现
[3] 考虑用 vector<char>: vector 实现不允许使用引用计数
舍弃使用 string 成员函数 -> `大多成员函数可同 STL 算法实现`
(2) 确定你的 STL string 是否使用 引用计数
看源码: string 是 basic_string<char> 的 类型定义
=> 检查 模板 basic_string
看 copy ctor 是否在某处增加了引用计数
item14：使用 reserve 来避免不必要的重新分配
0 总结
通常有2种方式 用 reserve 以避免不必要的重新分配
(1) 能大致预计 容器中最终会有多少元素 => 先 预留(reserve)适当大的空间
(2) 先 预留(reserve)足够大的空间 -> 加入所有数据 -> 去除多余的容量: swap (item17)
1 vector 和 string 的自动增长
需要更多空间时, 调用 realloc 类似操作
4步
`分配新内存`: 大小为当前容量的某个倍数(2倍)
所有旧元素 `复制` 到新内存
`析构` 旧内存中 对象
`释放` 旧内存
向 vector/string 中插入1个元素 -> 可能引起 vector/string 增长
成员函数 reserve: 最小化重新分配的次数
=> 避免了 重新分配 => 避免了 指针/迭代器/引用失效 带来的开销
2 4个关联 但易混淆的成员函数: 只有 vector 和 string 提供
(1) size() 元素个数
(2) capacity() 所能容纳的元素总数
剩余容量 = capacity() - size()
capacity() - size() == 0 => 下一个插入(insert / push_back 等) 将导致 重新分配
(3) resize(Container::size_type n): 强迫容器 改变到包含 n 个元素的状态
n < 当前 size => 尾部多余元素析构
n > 当前 size => 默认 Ctor 创建的新元素 加入到容器尾
n > 当前 capacity => 重新分配内存
(4) reserve(Container::size_type n) 强迫容器 改变容量至少为 n
vector
n > 当前容量 => 重新分配
n <= 当前容量 => 什么也不做
string
可能把 容量减为 size() 和 n 中的最大值
经验: 用 reserve 从 string 中 除去多余容量, 不如用 swap (item17)
避免重新分配的关键: 尽早使用 reserve, 把容器的容量设为足够大的值
vector<int> 若含 1-1000个元素, 如果不用 reserve, 直接循环中 push_back => 2到10次 重新分配
vector<int> v;
for(int i = 1; i <= 1000; ++i)
v.push_back(i);
vector<int> v;
v.reserve(1000);
for(int i = 1; i <= 1000; ++i)
v.push_back(i);
size 和 capacity 的大小关系, 使我们能 预知 插入操作什么时候会导致 vector/string 重新分配, 进而预知 插入操作什么时候会使 容器中的 指针/迭代器/引用失效
string s;
// ...
if(s.size() < s.capacity() )
s.push_back('x');
按照一般性的规则: string/vector 的 insert 操作(not push_back)总是伴随着迭代器失效, 从插入点到 string/vector 末尾的迭代器/指针/引用都将失效
item15 注意 string 实现 的多样性
实现 A.png
实现 B.png
实现 C.png
实现 C.png
string 对象 的 size 是多少 ? <=> sizeof(string) 返回值是什么 ? 取决于 string 的实现
string 的实现
(1) 必然包含
[1] `字符串大小(Size)` = 所含字符数
[2] 存储字符的 `内存容量(Capacity)`
[3] 字符串的 `值(Value)`
(2) 可能还包含
[1] 其分配子的拷贝 (Alloctor)
[2] 对值的 引用计数(RC)
1 string 4种实现, 考虑 32位系统, sizeof(char*) = 4
(1) string 含 Alloctor + Size + Capacity + ptr -> 动态分配的内存: RC + Value
=> sizeof(string) = sizeof(Size) + sizeof(Capacity) + sizeof(ptr) + sizeof(Alloctor)
= 4*sizeof(char*)
(2) string 含 ptr -> 动态分配的内存: Size + Capacity + RC + ptrValue ( -> 动态内存: Value ) + 同步控制(用于多线程)的 data (大小是指针大小的6倍)
=> sizeof(string) = sizeof(char*)
(3) string 含 ptr -> 动态分配的内存: Size + Capacity + RC + 值的共享性相关数据 + Value
=> sizeof(string) = sizeof(char*)
(4) 短字符串优化: 容量 = 15, 字符串的值直接放 string -> 无 RC => 不需要对多线程的特殊支持
=> sizeof(string) = sizeof(Alloctor) + sizeof(Value / ptr&unusedSpace) + sizeof(Size) + sizeof(Capacity)
= (3 + 16/4 = 7 ) * sizeof(char*)
string 含 Alloctor + Value(最多放15个字符, 末尾空字符 '\0'不算在容量里, 实际有16个字符) + Size + Capacity
string 含 Alloctor + ptr(-> 动态内存: Value) + unused Buffer + Size + Capacity, capacity = 15
2 基于引用计数的设计, string 对象之外 的一切都可以 被多个 string 共享(如果它们有同样的 Value)
(1) 共享能力 A < B/C
(2) C 不支持针对 单个对象的分配子 => 只有 C 可以共享分配子：所有 string 必须使用同一个分配子
(3) D 所有 string 不共享任何数据
(4) 不能完全从图表中推断出来的一个关于 string 行为: 对小字符串的内存分配策略, 有些 string 实现不会为 少于特定数目的字符分配内存
最小分配大小
A 32
C 16
D
3 总结
(1) string 的值 可能会被 引用计数, 也可能不会
默认RC, 关闭默认 RC -> 预处理宏
字符串被频繁复制时, 引用计数才有用
(2) string 对象大小范围: char* 指针大小的 1~7倍
(3) 0/1/2次 动态分配内存
(4) string 对象可能 共享 Size/Capacity 信息
(5) 可能支持 对 单个对象的分配子
(6) 字符内存的最小分配单位 策略不同
item16：了解如何把 vector 和 string 数据传给 C API
1 从vector/string到C API
(1) 从vector到C API
vector<int> v -> 容器首元素指针: &v[0], v[0] 是引用
元素数: v.size()
// C API
void f(const int* p, size_t n);
// [1] 安全
if(! v.empty() )
f(&v[0], v.size() );
// [2] 实在想用 begin() 得到相应指针: 用 &*v.begin()
if(! v.empty() )
f(&*v.begin(), v.size() );
// [3] 不安全, v 可能为空 => &v[0] 指向未知空间
f(&v[0], v.size() );
// [4] 不可移植/不正确: begin() 返回的是首迭代器, 对 vector 通常就是指针, 但不是所有实现都如此
if(! v.empty() )
f(v.begin(), v.size() );
(2) 从string到C API
string 内部字符串末尾必然带空字符'\0'
string s -> 容器首元素指针: s.c_str(): 返回 C 风格字符串指针
// C API
void f(const char* pStr);
[1] 字符串内部无空字符'\0'
vector 数据可以传给 C API, C API 能看到的字符串和 string 内部字符串相同
f(s.c_str() ); // s.size() == 0 也可以
[2] 字符串内部有空字符'\0'
vector 数据不能传给 C API, C API能看到的字符串和string内部字符串不同(C API 只看到了一部分)
(3) 接口约束
void f(const int* p, size_t n);
void f(const char* pStr);
若要传入的指针都是 指向const的指针 => vector/string数据被传递给 只读数据的 C API -> 安全
1) 对 string, C API 接口必须如此
原因: c_str() 返回的是 指向const的指针 => 所指元素不可被修改, 且可能指向 字符串数据的1个不可修改的拷贝
2) 对 vector, 多了一点灵活性
[1] C API 改变了 vector 中元素值, 通常没有问题
void f(int* p, size_t n);
有问题的 case, vector 对其元素有额外限制, 比如排序
把 排序的vector传给改变vector中数据的C API, 调用返回时, vector可能不再是排序的
[2] C API试图改变vector中元素个数 -> bug
1] 在未使用容量中 "创建"新元素 => vector 内部将变得不一致, v.size()将产生不正确的结果
2] size() == capacity()时, 向vector中加入数据, vector中内存重新分配 -> undefined behavior
2 从C API到vector/string
(1) 到vector: 利用数组和vector的内存布局兼容性
size_t fillArray(double* pArr, size_t arrSize);
vector<double> v(maxNum);
v.resize(fillArray(&vd[0], vd.size() ) );
(2) 到string: 用vector<char>中转, C API -> vector<char> --- 区间 Ctor: copy 到 ---> string
size_t fillString(char* pArr, size_t arrSize);
vector<char> vc(maxNum);
size_t charsWritten = fillArray(&vc[0], vc.size() )
string s(vc.begin(), vc.begin() + charsWritten);
3 其他STL容器(list/set/...)与C API的数据传输: 用vector中转
(1) C API -> 其他STL容器
[1] 先让C API把数据写入到1个vector中
[2] 把数据复制到其他STL容器: 区间Ctor
size_t fillArray(double* pArr, size_t arrSize);
vector<double> v(maxNum);
v.resize(fillArray(&vd[0], vd.size() ) );
list<double> lst(vd.begin(), vd.end() );
set<double> s(vd.begin(), vd.end() );
(2) 其他STL容器 -> C API
其他STL容器也能把它们的数据传递给C API
[1] 容器的元素 复制到1个vector中
[2] 传给 C API
set<int> s;
// ...
vector<int> v(s.begin(), s.end() );
if(!v.empty() )
f(&v[0], v.size() );
item17：用 "swap 技巧" 除去 vector/string 多余容量: shrink to fit(压缩至适当大小)
1 用 当前vector/string容器(capacity() > size() )Copy构造1个临时容器, 再用成员swap交换2个容器的内容 => 容量也交换
vector/string的Copy Ctor只为所拷贝的元素(size() 个)分配所需要的内存 => 临时容器没有多余容量, size() == capacity()
Container<T>(tContainer).swap(tContainer);
vector<W>(wVec).swap(wVec);
string(s).swap(s);
2 该swap 技巧并不保证一定能除去多余容量, 而是意味着"在容器当前的大小确定的情况下, 使容量在该实现下变为最小"
STL实现者可能需要一个最小的容量, 如 容量限制为2的乘幂数
3 swap 还可用于 清除(clear)容器(vector/string), 使其容量变为该实现下的最小值: 与默认Ctor构造临时对象swap
vector<W>().swap(wVec);
string().swap(s);
4 对vector, swap 交换内容和迭代器/指针/引用, 原迭代器/指针/引用依然有效, 且指向同样的元素, 只在另一个容器中
对string, swap只交换内容
item18：避免使用 vector<bool>
1 vector<bool> 只有两点不对
(1) 不是 STL容器
原因: operator[] 返回 Container<T>中 1个 T对象的引用 再 取地址, 得到的必须是 T 类型指针
但对 vector<bool>, 得到的是 代理对象 reference(表现得像是一个指向单个位的引用) 的指针
(2) 不存储 bool
只为所包含的每个值提供一位空间: 储存 bool 的二进制位, 与位域思想相同 与bool
2 bool 容器的两种选择: deque<bool> / bitset
3 vector<bool>留在STL中的原因
演示STL如何支持 "通过代理来存取其元素的容器"
人们在实现自己的 基于代理的容器 时就有了一个现成的参考
