Skip to content

Latest commit

 

History

History
135 lines (89 loc) · 5.26 KB

09. 顺序容器.md

File metadata and controls

135 lines (89 loc) · 5.26 KB

9. 顺序容器

9.1. 容器库概览

9.1.1. 迭代器

  • 迭代器 (Iterator) 模式又称游标 (Cursor) 模式, 用于提供一种方法顺序访问一个聚合对象中各个元素, 而又不需暴露该对象的内部表示.

  • 迭代器本质上是类模板, 只是表现地像指针.

9.2. 顺序容器操作

9.2.1. emplace

当调用 push 或 insert 成员函数时, 我们将元素类型的对象传递给它们, 这些对象被拷贝到容器中. 而当我们调用一个 emplace 成员函数时, 则是将参数传递给元素类型的构造函数. emplace 成员使用这些参数在容器管理的内存空间中直接构造元素.

9.2.2. resize/reserve

  • resize: 改变容器内含有元素的数量.

  • reserve: 改变容器的最大容量.

9.2.3. 容器操作可能使迭代器失效

在向容器中添加元素后:

  • 如果容器是 vector 或 string, 且存储空间被重新分配, 则指向容器的迭代器, 指针和引用都会失效.

  • 对于 deque, 插入到除首尾位置之外的任何位置都会导致迭代器指针和引用失效.

  • 对于 list, 指向容器的迭代器指针和引用仍然有效.

从容器删除元素后:

  • 对于 list, 指向容器的迭代器指针和引用仍然有效.

  • 对于 deque, 在首尾之外的任何位置删除元素, 其他元素的迭代器也会失效.

  • 对于 vector 或 string, 被删元素之前的迭代器仍有效, 尾后迭代器失效.

  • 对于关联式容器 (如 std::set / std::map), 插入元素不会使任何迭代器失效.

  • 对于无序关联式容器 (如 std::unordered_set / std::unordered_map), 插入元素之后如果发生了 Rehash(新元素的个数大于 max_load_factor() * bucket_count()), 则所有迭代器将失效.

9.3. vector

//动态申请数组
const int M = 10;
const int N = 10;

//使用new申请一个一维数组.访问p_arr[i].
int* p_arr = new int[N];
//使用new申请一个二维数组.访问:p_arr[i][j].
int(*p_arr)[N] = new int[M][N];
//一维数组转化为二维数组.访问:p_arr[i*N+j].
int* p_arr = new int[M*N];
//指向指针的指针(指向一维指针数组).访问p[i][j]
int** p_arr = new int* [M]
for(int i = 0; i < M; i++)
    p_arr[i] = new int[N];
//回收内存
for(int i = 0; i < M; i++)
    delete [] p_arr[i];
delete [] p_arr;

//使用vector申请一个一维数组
vector<int> v_arr(n, 0);
vector<int> v_arr{1, 0};
//使用vector申请一个二维数组, 如果不初始化, 使用[]会报错
vector<vector<int>> v_arr(m, vector<int>(n, 0));
vector<vector<int>> v_arr = {{1,0}};

//一维数组作为函数参数
void function(int* a);
void function(int a[]);
void function(int a[N]);
//二维数组作为函数参数,他们合法且等价
void function(int a[M][N]);
void function(int a[][N]);
void function(int (*a)[N])

9.4. string

string s("hello world")
string s2 = s.substring(0, 5); // s2 = hello
string s3 = s.substring(6);    // s3 = world
string s4 = s.substring(6, 11);// s4 = world
string s5 = s.substring(12);   // 抛出一个out_of_range异常

isalpha(ch); //判断一个字符是否是字母
isalnum(ch); //判断一个字符是数字或字母
tolower(ch); //将字母转化成小写
toupper(ch); //将字母转化为大写

string str = to_string(num); //将数字转换成字符串

9.5. vector 对象是如何增长的

当不得不获取新的内存空间时, vector 和 string 的实现通常会分配一个比新的空间需求更大的内存空间. 容器预留这些空间作为备用, 可以用来保存更多的新元素. 这样, 就不需要每次添加新元素都重新分配容器的内存空间了.

  • capacity 操作告诉我们容器在不扩张内存空间的情况下可以容纳多少个元素. reserve 操作允许我们通知容器它应该准备保存多少个元素.

  • 初始时刻 vector 的 capacity 为 0, 塞入第一个元素后 capacity 增加为 1.

  • 不同的编译器实现的扩容方式不一样, VS2015 中以 1.5 倍扩容, GCC 以 2 倍扩容.

  • 从空间上分析, 扩容因子越大, 意味着预留空间越大, 浪费的空间也越多, 所以从空间考虑, 扩容因子应越小越好.

  • 从时间上分析, 如果预留空间不足的话, 就需要重新开辟一段空间, 把原有的数据复制到新空间, 如果扩容因子无限大的话, 那显然就不再需要额外开辟空间了. 所以时间角度看, 扩容因子越大越好.

9.6. 容器适配器

除了顺序容器外, 标准库还定义了三个顺序容器适配器: stack、queue 和 priority_queue.

本质上, 一个适配器是一种机制, 能使某种事物的行为看起来像另外一种事物一样.

默认情况下, stack 和 queue 是基于 deque 实现的, priority_queue 是在 vector 之上实现的.

9.6.1. priority_queue

std::priority_queue<int> q1; // 默认大根堆
std::priority_queue<int, std::vector<int>, std::greater<int>>
    q2(data.begin(), data.end()); // 小根堆
// 使用lambda表达式
auto cmp = [](int left, int right) { return (left ^ 1) < (right ^ 1); };
std::priority_queue<int, std::vector<int>, decltype(cmp)> q3(cmp);