Effective STL-2 vector 和 string

2022-10-10  本文已影响0人  my_passion

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如何支持 "通过代理来存取其元素的容器"

人们在实现自己的 基于代理的容器 时就有了一个现成的参考

上一篇下一篇

猜你喜欢

热点阅读