Reading Note of CppPrimer-Chapter9

发表于 2022-06-15 更新于 2024-08-06 分类于 C++ 阅读次数：本文字数： 15k 阅读时长 ≈ 14 分钟

Sequential Containers

Overview

顺序容器：提供控制元素存储和访问顺序的能力，这种顺序不依赖于元素的数值，而是与元素加入容器时的位置相对应；
不同 sequential container 的特点:
- vector，可变大小数组。支持可变大小，随机访问，但在尾部之外的地方插入删除需要遍历，复杂度为 o(n)；
- deque，双端队列。支持可变大小，随机访问，在头尾插入删除速度快，其他地方需要遍历，复杂度 o(n)；
- list，双向链表。支持可变大小，只支持双向顺序访问，复杂度 o(n)。插入和删除的速度很快，复杂度 o(1)；
- forward_list，单向链表。支持可变大小，只支持单向顺序访问，复杂度 o(n)。插入和删除的速度很快，复杂度 o(1)；
- array，固定大小数组。只支持随机访问，不支持插入删除操作；
- string，类似于 vector 的容器。只用于保存字符，支持可变大小随机访问，在尾部之外的地方入或删除需要遍历，复杂度为 o(n)；
容器迭代器

begin 和 end 迭代器有多个版本，带 r 的是反向迭代器，带 c 的是常量迭代器；

不以 c 开头的都是重载过的，即都有 const 版本和 non-const 版本；当容器本身为 const 的时候，返回的迭代器也是 const 版本；当不需要写访问的时候，如果容器是不是 const 的，记得使用 cbegin 和 cend;
1
2
3
4
5
std::vector<int> vec;
vec.begin(); vec.end();
vec.rbegin(); vec.rend();
vec.cbegin(); vec.cend();
vec.crbegin(); vec.crend();
使用迭代器指定顺序容器的范围（迭代器范围，iterator range）的话，实际上是一个左闭右开区间 (left inclusive interval)；
1
[begin, end) // 左闭右开区间
- 如果 begin 和 end 相同，则范围为空
- 如果 begin 小于 end，则范围了至少有一个元素
- begin 可以递增若干次使得 begin == end
容器类型成员
- iterator, const_iterator, reverse_iterator
- size_type, value_type
- type alias: reference, const_reference, pointer, const pointer

容器的构造

对于接受另一个容器进行构造的容器的 constructor 来说，两个容器的类型和元素的类型必须相同 (对于 array，大小还必须相同)；
通过迭代器 (iterator) 进行拷贝的构造函数，只需要容器内部的元素类型可以互相转换即可；
使用列表初始化进行初始化的容器，列表中的元素必须可以和容器元素类型进行转换，对于 array 来说，列表中遗漏的元素会进行值初始化；
给定容器大小和可选的初始值 (array 除外)；如果不提供初始值则进行值初始化

std::list<std::string> authors = {"Milton", "ShapeSpeare", "Austen"};
std::vector<const char*> articals = {"a", "an", "and"};
std::list<std::string> list1(authors);          // valid，容器类型和元素类型都相同
std::deque<std::string> authLists(authors);     // invalid，容器类型不相同
std::vector<std::string> words(articals);       // invalid，元素类型不相同
std::forward_list<std::string> words(articals.begin(), articals.end());// valid，元素可以只一次转换即可完成转换

只有顺序容器的构造函数支持指定大小，包含显式的或者隐式的（不包含 array，因为 array 声明的时候就定义了大小），关联容器就不支持指定大小；
1
2
std::vector<int> vec(100); // size is 100
std::vector<int> vec1 = {1,2,3,4}; // size is 4

顺序容器的赋值运算符要求左右两边的容器具有相同的类型；除 array 外，顺序容器还定义了 assign 运算，允许从不同但是相容的容器类型中拷贝；

std::list<std::string> names;
std::vector<const char*> oldstyles;

names = oldstyles;                                                                            // invalid
names.assign(oldstyles.cbegin(), oldstyle.cend());            // valid

容器 swap

swap 要求两个容器的类型必须相同 ;

【地址不变，元素不变】除 array 外，可以保证常数时间 o(1) 里完成；swap 不进行任何元素的拷贝删除或者插入，只是交换了两个容器的内部数据结构；意味着 swap 后指针、引用、迭代器属于不同的容器了，但是他们所绑定的元素不变，仍指向 swap 之前的那些元素

【地址不变，元素变】array 的 swap 时间复杂度是 o(n)，与其他顺序容器不同，因为他会真正交换两个 array 的元素；在 swap 操作后指针、引用、迭代器还是指向原来的容器，但是绑定的值却是交换后的，即另一个容器的了

std::vector<int> a = {1,2,3,4,5};
std::vector<int> b = {6,7,8,9,10};

auto iter1 = a.begin();
auto iter2 = b.begin();
std::cout << "a_begin: " << *iter1 << ", b_begin(): " << *iter2 << std::endl;
a.swap(b);
std::cout << "a_begin: " << *iter1 << ", b_begin(): " << *iter2 << std::endl;

std::array<int, 5> c = {1,2,3,4,5};
std::array<int, 5> d = {6,7,8,9,10};
auto iter3 = c.begin();
auto iter4 = d.begin();
std::cout << "c_begin: " << *iter3 << ", d_begin(): " << *iter4 << std::endl;
c.swap(d);
std::cout << "c_begin: " << *iter3 << ", d_begin(): " << *iter4 << std::endl;

// a_begin: 1, b_begin(): 6
// a_begin: 1, b_begin(): 6
// c_begin: 1, d_begin(): 6
// c_begin: 6, d_begin(): 1

容器关系运算符
1. 所有容器都支持相等运算符 ==
2. 除无序容器外其他容器都支持关系运算符 <, >, <=, >=
3. 关系运算符两边的元素必须有相同的类型
4. 比较方式为字典序
5. 只有当容器的元素类型定义了相应的比较运算符 (== and <)，才可以使用关系运算符比较两个容器
字典序 (lexicographical order)

在英文字典中，排列单词的顺序是先按照第一个字母以升序排列（即 a、b、c……z 的顺序）；如果第一个字母一样，那么比较第二个、第三个乃至后面的字母。如果比到最后两个单词不一样长（比如，sigh 和 sight），那么把短者排在前。

通过这种方法，我们可以给本来不相关的单词强行规定出一个顺序。“单词” 可以看作是 “字母” 的字符串，而把这一点推而广之就可以认为是给对应位置元素所属集合分别相同的各个有序多元组规定顺序：下面用形式化的语言说明。
1
2
3
'ab' < 'ac'
'abc' < 'ac'
'abc' < 'abcd'

Sequential Container Operation

push_back: 除了 array 和 forward_list 不支持 push_back，其他顺序容器都支持
push_front: list, forward_list, deque 支持 push_front

insert 是在指定的 iterator 前面插入元素，返回指向插入元素的 iterator；可以利用这样的特性，在一个位置一直插入；不过如果已知要插入的个数，可以考虑使用插入一段数据的 insert 的重载函数；

vec.insert(iter, item);                 // insert item before iter and return iterator point to newly 
                                        // add item
vec.insert(iter, num, item);            // insert item before iter for num times and return iterator 
                                        // point to the first added item
vec.insert(iter, iter_begin, iter_end); // insert the range from iter_begin to iter_end before iter 
                                        // and return iterator point to the first added item
vec.insert(iter, initializer_list);     // insert an initializer-list before iter and return iterator 
                                        // point to the first item in initializer-list

// vector iterator遍历过程中insert元素矫正迭代器示例：
// 在iterator的过程中，删除或者插入元素，可能会使得iterator失效，所以我们需要手动矫正；
vector<int>::iterator iter = iv.begin(), mid = iv.begin() + iv.size() / 2;
while (iter != mid {
    if (*iter == some_val) {
        iter = v.insert(iter, 2 * some_val);
        ++iter;   // 手动矫正
    }
    ++iter;       // 对于insert, 事实上iter加了2，因为要略过当前插入的元素，略过当前元素
}

emplace 函数是直接在容器中初始化构造元素；传递给 emplace 函数的参数必须和元素的构造函数的参数列表匹配；
1
2
template< class... Args >
iterator emplace( const_iterator pos, Args&&... args );
Inserts a new element into the container directly before pos.

The element is constructed through std::allocator_traits::construct, which typically uses placement-new to construct the element in-place at a location provided by the container. However, if the required location has been occupied by an existing element, the inserted element is constructed at another location at first, and then move assigned into the required location.

The arguments args... are forwarded to the constructor as std::forward(args)…. args... may directly or indirectly refer to a value in the container.

If the new size() is greater than capacity(), all iterators and references are invalidated. Otherwise, only the iterators and references before the insertion point remain valid. The past-the-end iterator is also invalidated.
在容器中访问元素的成员函数 (front, back, operator []，at) 返回的都是元素的引用；at 会检查是否越界，operator [] 不会；

调用 front 和 back 之前要确保容器不为空，否则 UB
1
2
3
4
std::vector<int> vec = {1,2,3,4,5};
auto& v1 = vec.back();
auto& v2 = vec[1];
auto& v3 = vec.at(10); // throw out of range exception
pop_front: 和 push_front 类似，list，deque，forward_list 支持 pop_front；
pop_back: 和 push_back 类似，除了 array 和 forward_list 不支持 push_back，其他顺序容器都支持

erase，删除容器迭代器指向的元素，返回指向被删元素之后的元素的迭代器；vector iterator 遍历过程中 erase 元素矫正迭代器示例

vec.erase(iter);                 // erase the item at iterator iter and return the iterator point to 
                                 // the one next to deleted item
vec.erase(iter_begin, iter_end); // erase the items between [iter_begin, iter_end) and return the 
                                 // iterator point to the one next to deleted item

std::list<int> lst = {0,1,2,3,4,5,6,7,8,9};
auto it = lst.begin();
while (it != lst.end()){
    if (*it & 0x01){
        it = lst.erase(it);
    }
    else{
        ++it;
    }
}

resize: 可以使用 resize 来扩大或缩小容器；不适用于 array

1
2

vec.resize(n);  // resize the container size to n, n>vec.size mean enlarging, n<vec.size means truncation
vec.resize(n, t); // resize the container size to n and using t to initialize the newly add item

forward_list 的特殊操作

对于单向链表 forward_list，删除一个元素需要改变这个元素前面的那个元素 (前驱) 指向的下一个元素；但是因为是单向链表，所有没有简单的办法直接获取当前元素的前驱；出于这个原因，在一个 forward_list 中添加或者删除元素，是通过操作给定元素的之后的元素来完成的；于是不同与其他顺序容器的 insert, erase，forward_list 对应的是 insert_after 和 erase_after; 也引出了一个新的不存在的位置：before_begin;

std::forward_list<int> flist;
flist.before_begin();
flist.cbefore_begin();
flist.insert_after(iter, item);
flist.insert_after(iter, num, item);
flist.insert_after(iter, iter_begin, iter_end);
flist.insert_after(iter, initializer-list);
flist.emplace_after(iter, args);
flist.erase_after(iter);
flist.erase_after(iter_begin, iter_end);

std::forward_list<int> flst = {0,1,2,3,4,5,6,7,8,9};
auto prev = flst.before_begin();
auto curr = flst.begin();
while (curr != flst.end){
    if (*curr & 0x01){
        curr = flst.erase_after(curr);
    }
    else{
        prev = curr;
        ++curr;
    }
}

容器操作可能使得迭代器失效 (iterator invalidate)

记得使用 erase 和 insert 返回的值更新 iterator

不要在循环开始前缓存 end iterator，每次都显式调用 end 来做判断，否则是未定义的，可能陷入死循环；

// invaild: undefined behavior
std::vector<int> v = {1,2,3,4};
auto begin = v.begin();
auto end = v.end();                   // cache end iterator, results in undefined behavior
while (begin != end ){
    // do somethine
    ++begin;                          // iterator operation
    begin = v.insert(begin, 43);
    ++begin;                          // iterator operation
}

迭代器失效 (iterator invalidate)

array

As a rule, iterators to an array are never invalidated throughout the lifetime of the array. One should take note, however, that during swap, the iterator will continue to point to the same array element, and will thus change its value.
list

Adding, removing and moving the elements within the list or across several lists does not invalidate the iterators or references. An iterator is invalidated only when the corresponding element is deleted.
forward_list

Adding, removing and moving the elements within the list, or across several lists, does not invalidate the iterators currently referring to other elements in the list. However, an iterator or reference referring to an element is invalidated when the corresponding element is removed (via erase_after) from the list.

vector

Operations	Invalidated
All read only operations	Never
swap, std::swap	past-the-end iterator end(). Every iterator referring to an element in one container before the swap shall refer to the same element in the other container after the swap. The `end()` iterator does not refer to any element, so it may be invalidated. ref: stackoverflow
clear, operator=, assign	All iterators, pointers and references to the elements of the container are invalidated. The past-the-end iterator is also invalidated.
reserve, shrink_to_fit	If the vector changed capacity, all of them. If not, none.
erase	Erased elements and all elements after them (including end())
push_back, emplace_back	If the vector changed capacity, all of them. If not, only end().
insert, emplace	If the vector changed capacity, all of them. If not, only those at or after the insertion point (including end()).
resize	If the vector changed capacity, all of them. If not, only end() and any elements erased.
pop_back	The element erased and end().

deque

push_back() and push_front() are defined in terms of insert(). Similarly, pop_back() and pop_front() are defined in terms of erase().

stackoverflow, cppreference

Operations	Invalidated
All read only operations	Never
swap, std::swap	Only past-the-end iterator end(). Every iterator referring to an element in one container before the swap shall refer to the same element in the other container after the swap. The `end()` iterator does not refer to any element, so it may be invalidated. Ref: stackoverflow
shrink_to_fit, clear,	All iterators and references are invalidated. Past-the-end iterator is also invalidated.
erase, pop_front, pop_back	If erasing at begin - only erased elements, does not invalidate any references to non-erased elements If erasing at end - only erased elements and the past-the-end iterator, does not invalidate any references to non-erased elements Otherwise - all iterators and reference are invalidated (including the past-the-end iterator).
resize	If the new size is smaller than the old one : only erased elements and the past-the-end iterator, does not invalidate any references to non-erased elements; If the new size is bigger than the old one : all iterators are invalidated, does not invalidate any references to elements of the deque.; Otherwise, none iterators and no references are invalidated.
insert, emplace, push_front, emplace_front, push_back, emplace_back	An insert in the middle of the deque invalidates all the iterators and references to elements of the deque. An insert at either end of the deque invalidates all the iterators to the deque, but has no effect on the validity of references to elements of the deque.<br /

Common Sequential Containers

vector

vector 容器 (包含 string) 重新分配内存：

因为容器是连续存储的，当添加新的元素导致超出现有的容器的大小的时候，容器需要新分配连续内存存储所有元素；容器不能简单的将新的元素分配到新的内存，可见每次重新分配，代价很大；此时容器会：
- 分配新的内存空间，存储现有的元素以及新添加的元素；
- 释放旧空间；

vector 的 reserver 函数、capacity 函数、size 函数、resize 函数；

size vs capacity：size 是指容器里面元素的数量，capacity 是指在不分配新空间的情况下容器最大可以存的元素的数量；
reserve(int n)：分配至少可以容纳 n 个元素的内存空间；不改变容器的 size，只增加容器的 capacity；只有在 n 大于当前容器的 capacity 的时候，reserver 才会起作用；否则什么也不做；同时 reserve 永远不会减小容器的 capacity;
resize 只是改变容器元素的 size，如果 resize 的 size 大于当前的 size，则添加元素，值初始化；如果 resize 的 size 小于 size，则容器被截断；
shrink_to_fit：收回大于 size 但是小于 capacity 的空间；
不同的实现会有不同的分配策略，但是有一个原则是一致的：只有迫不得已的时候开多分配空间

std::vector<int> vec;
for (int i=0; i<20; i++){
    vec.push_back(1);
    std::cout << "vec size: " << vec.size() << " " << "vec capacity: " << vec.capacity() << std::endl;
}

vec size: 1 vec capacity: 1
vec size: 2 vec capacity: 2
vec size: 3 vec capacity: 4
vec size: 4 vec capacity: 4
vec size: 5 vec capacity: 8
vec size: 6 vec capacity: 8
vec size: 7 vec capacity: 8
vec size: 8 vec capacity: 8
vec size: 9 vec capacity: 16
vec size: 10 vec capacity: 16
vec size: 11 vec capacity: 16
vec size: 12 vec capacity: 16
vec size: 13 vec capacity: 16
vec size: 14 vec capacity: 16
vec size: 15 vec capacity: 16
vec size: 16 vec capacity: 16
vec size: 17 vec capacity: 32
vec size: 18 vec capacity: 32
vec size: 19 vec capacity: 32
vec size: 20 vec capacity: 32

string

从一个 const char* 的数组创建一个 string 的时候，指针指向的数组必须以空字符结尾，拷贝操作到空字符结尾；如果传递了长度，且长度小于等于数组的尺寸，则不需要数组以空字符结束；

string s(cp, n);          // s指向cp指向的数组中前n个字符
string s(s1, pos1);       // s指向string s1从pos1开始的所有字符，到\0结束
string s(s2, pos2, n);    // s指向string s2从pos2开始的n个字符

s.substr(pos, n);         // 从pos开始的n个字符

string 常见接口

s.substr(pos, n);    // slice n chars from pos and return a sliced string
s.insert(pos, args); // args can only be char, not be string
s.erase(pos, len);   // erase len chars from pos
s.append(pos, args); // args can only be string, not be char
s.replace(iter_begin, iter_end, args);  // args can only be string, not be char

find_first_of(args) 和 find_last_of(args) 返回字符串里 args 中任何一个字符第一次 / 最后一次出现的位置，而不是整个 args 字符串出现的第一个位置；

find(args) 和 rfind(args) 才是在字符串里寻找 args 字符串第一次 / 最后一次出现的位置

s.find(args);
s.rfind(args);
s.find_first_of(args);
s.find_last_of(args);
s.find_first_not_of(args);
s.find_last_not_of(args);

std::string str = "0abc567890bc";
str.find_first_of("0");      // 0
str.find_first_of('0');      // 0
str.find_first_of('0', 3);   // 9
str.find_first_of("56c", 3); // 3

str.find("56c", 0);  // 18446744073709551615, equal to static_cast<unsigned long>(-1)
str.find("c56", 0);  // 3

string 找不到的时候返回的是 string::npos，定义为 signed long -1，转换为 unsigned long 的时候是个最大的 unsigned long；

array

与内置数组一样，std::array 的大小也是类型的一部分；

内置数组是不允许拷贝或者对象赋值的，但是 std::array 并没有这个限制；

和内置数组一样，但和其他顺序容器不同，默认构造的 array 的元素是非空的，会执行默认初始化；

当使用初始化列表的时候，前面的部分使用初始化列表来初始化，剩余的元素执行值初始化；

std::array<int, 42> arr;           // 大小为42的int数组
std::array<int, 42>::size_type i;  // valid
std::array<int>::size_type j;      // invalid

// built-in array copy and assignment
int digs[6] = {0,1,2,3,4,5,6};
int cpy[6] = digs;                 // invalid

// std::array copy and assignment
std::array<int,6> digs = {0,1,2,3,4,5,6};
std::array<int,6> cpys = digs;     // valid

std::array<int, 10> ia1;           // 默认初始化，元素非空
std::vector<int> vec1(10);         // 元素为空
std::array<int, 10> ia2 = {0,1,2,3,4,5,6,7,8,9};    // 列表初始化
std::array<int, 10> = {1,2,3};     // 1,2,3,0,0,0,0,0,0,0

container adaptor

容器适配器 (container adaptor) 是标准库中的通用概念；本质上，一个适配器是一种机制，能使某种事物的行为看起来像是另一种事物一样；本质是在底层顺序容器的接口的基础上提供了一部分接口的类型；

The class template acts as a wrapper to the underlying container - only a specific set of functions is provided.

stack 可以使用除了array 和 forward_list 之外的容器来构造；

queue 可以基于 list 和 deque 构造；priority_queue 可以基于 vector 和 deque 构造；

默认情况下 stack 和 queue 是基于 deque 的，priority_queue 是在 vector 上实现的；

// 使用默认container
std::stack<int> stack;

// 指定container和comparer
std::priority_queue<int, std::vector<int>, std::greater<int>> queue;

// 指定container和comparer using lambda
using value_type = int;
using container_type = std::deque<value_type>;
auto cmp_func = [](const value_type &a, const value_type &b){return a < b;};
std::queue<value_type, container_type, decltype(cmp_func)> mannul_queue(cmp_func);

std::stack 接口
std::queue 接口
std::priority_queue 接口