一、容器库概述

1、容器内元素的类型约束

使用 C++ 标准库容器存储元素时，对于元素类型有一些要求：

1. 元素类型必须支持复制语义，即可以使用赋值运算符（=）将一个元素赋值给另一个元素，这是因为标准库容器需要在内部存储和复制元素。
2. 元素类型必须支持等价性，即可以使用等价比较运算符（==）比较两个元素是否相等，这是因为标准库容器需要支持查找和删除元素等操作。
3. 对于不同的标准库容器，元素类型要求也不尽相同。例如，std::vector 和 std::deque 都是动态数组，但 std::vector 支持随机访问，而 std::deque 支持在队列首尾进行 O(1) 操作。因此，在使用容器时需要根据具体的需求来选择适当的容器类型。 总的来说，如果您的元素类型支持复制语义和等价性，那么它就可以作为标准库容器的元素类型。如果您的元素类型不支持复制语义和等价性，那么您可以使用 C++ 指针或其他技巧来将它存储在容器

2、容器操作

容器的操作分成三类：

1. 所有容器都提供的操作
2. 按照顺序容器，关联容器，无序容器分类，分别提供不同的操作
3. 一小部分容器提供的操作

⚠️ 随后的表格中，列出了所有顺序容器的操作，某些不提供这些操作的容器，在表后有说明！

2.1 类型别名

2.2 构造函数

• 只有顺序容器的构造函数才接受大小参数，关联容器并不支持。
• array具有固定大小。
• 和其他容器不同，默认构造的array是非空的。
• array可以拷贝和对象赋值 , 这一点与内置数组不同
• 直接复制：将一个容器复制给另一个容器时，类型必须匹配：容器类型和元素类型都必须相同。
• 使用迭代器复制：不要求容器类型相同，容器内的元素类型也可以不同。

2.3 赋值和swap

2.3.1 赋值

• 赋值左右大小若不一致，则两边都和右边一致

• [[顺序容器#4.3 array的拷贝与对象赋值| array赋值操作]]

• 使用非成员版本的swap是一个好习惯。 swap不会导致容器的指针,迭代器,引用,失效, 他们仍然指向或者引用之前所指向或引用的那些元素，但是已经属于不同的容器了

• assign操作不适用于关联容器和array

2.3.2 使用assign （仅顺序容器）

顺序容器（array除外）还定义了一个名为assign的成员， 允许我们从一个不同但相容的类型赋值，或者从容器的一个子序列赋值，只要能转换

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

list<string> names; 
vector<const char*> oldstyle; 
names = oldstyle; // 错误：容器类型不匹配 
// 正确：可以将const char* 转换为 string
names.assign(oldstyle.cbegin(), oldstyle.cend());

// 等价于slistl.clear(); 
// 后跟slistl.insert(slistl.begin(), 10, "Hiya!");
list<string> slistl (1) ;       // 1个元素，为空 string 
slistl.assign (10, "Hiya!") ;   // 10个元素，每个都是"Hiya!"

2.3.3 使用swap

swap操作交换两个相同类型容器的内容。调用swap之后，两个容器中的元素将会交换；

1
2

vector<string> svecl (10) ; // 10 个元素的 vector 
vector<string> svec2 (24) ; // 24 个元素的 vector swap(svecl, svec2);

交换两个容器内容的操作保证会很快—— 元素本身并未交换，swap只是交换了两个 容器的内部数据结构 除 array外，swap不对任何元素进行拷贝、删除或插入操作，因此可以保证生 在常数时间内完成，但是array会真正的交换 这也意味着，指向容器的迭代器、引用和指针在swap操作之后不会失效，仍旧指向之前的元素 例如：假定iter在 swap之前指向svec1 [3]的string,那么在swap之后它指向svec2 [3]的元素

2.4 大小

2.5 添加元素/删除元素

2.6 获取迭代器

• 以c开头的版本是C++11新标准引入的
• 当不需要写访问时，应该使用cbegin和cend。

2.7 反向容器的额外成员

• 不支持forward_list

2.8 关系运算符

graph LR
    s[比较]
	s-->c_1[不相等:元素个数不同]
    s-->c_2[相等:元素个数和元素大小都相等]

    c_1-->c_2_1[存在包含关系,比个数]
	c_1-->c_2_2[有交集不包含,比较第一个不等的元素]

所谓元素的大小：容器的关系运算符使用元素的关系运算符完成比较

2.9 迭代器

什么是迭代器？ 在 C++ 中，迭代器是一个对象，它提供了在容器（如数组、链表等）中遍历元素的方法。通俗地说，迭代器就像是容器中的一个指针，可以通过迭代器来访问容器中的元素，比如获取、修改、插入元素等。 C++ 中的迭代器类型分为五种：输入迭代器、输出迭代器、前向迭代器、双向迭代器和随机访问迭代器。每种类型的迭代器都有不同的功能和性能，例如，随机访问迭代器支持 O(1) 的随机访问，而输入迭代器仅支持递增的遍历。 使用迭代器的好处是，它可以使代码变得更加简洁和可移植，因为迭代器抽象了对容器的遍历，从而使得代码对容器的具体实现细节更加独立。

迭代器

• forward_list , list 不支持迭代器的算数运算
• 迭代器范围：begin到end，即第一个元素到最后一个元素的后面一个位置。
• 左闭合区间：[begin, end)
• 左闭合范围蕴含的编程设定：
  • 如果begin和end相等，则范围为空。
  • 如果二者不等，则范围至少包含一个元素，且begin指向该范围中的第一个元素。
  • 可以对begin递增若干次，使得begin == end。

2.10 容器定义和初始化

![[Pasted image 20230211004318.png]]

2.10.1 利用拷贝初始化

1. 拷贝整个容器 两个容器的类型及其元素类型必须匹配

2. 拷贝由一个迭代器对指定的元素范围 当传递迭代器参数来拷贝一个范围时，就不要求容器类型是相同的了。而且，新容器和原容器中的元素类型也可以不同，只要能将要拷贝的元素转换 为要初始化的容器的元素类型即可

1
2
3
4
5
6
7

//每个容器有三个元素，用给定的初始化器进行初始化
list<string> authors = {"Milton", "Shakespeare", "Austen"};
vector<const char*> articles = {"a", "an"， "the"}; list<string> list2(authors); // 正确 类型匹配
deque<string> authList (authors) ; // 错误 容器类型不匹配
vector<string> words (articles) ; // 错误 容器类型必须匹配
// 正确：可以将const char*元素转换为string
forward_list<string> words(articles.begin(), articles.end());

2.10.2 列表初始化

1
2

list<string> authors = {"Milton" , "Shakespeare", "Austen"};
vector<const char*> articles = {"a"， "an", "the"};

对于除array之外的容器类型, 初始化列表还隐含地指定了容器的大小：容器将包含与初始值一样多的元素

2.10.3 顺序容器特有的构造函数

除了与关联容器相同的构造函数外，顺序容器（array除外）还提供另一个构造函数, 它接受一个容器大小和一个（可选的）元素初始值。如果我们不提供元素初始值，则标准库会创建一个值初始化器

1
2
3
4

vector<int> ivec(10,-1);
list<string> svec(10,"hi!");
forward_list<int> ivec(10);     //10个元素，初始为0
deque<string> svec(10);         //10个元素，初始化为空

如果元素类型是类类型，只有当该类有默认构造函数才能不指定初始值，否则必须显示初始化

二、顺序容器

顺序容器（sequential container）：顺序容器都提供了快速顺序访问元素的能力。这种顺序不依赖于元素的值，而是与元素加入容器时的位置相对应。

1、顺序容器类型

• 除了固定大小的array外，其他容器都提供高效、灵活的内存管理。
• forward_list和array是新C++标准增加的类型。
• 通常使用vector是最好的选择，除非你有很好的理由选择其他容器。
• 每个容器都定义在一个头文件中，文件名与类型名相同，容器均定义为模板类，按照[[模板与泛型编程|模板]]的使用规则来使用
• 新标准库的容器比旧版的快得多。

2、顺序容器操作

2.1 添加元素

• 因为这些操作会改变大小，因此不适用于array。

• forward_list有自己专有版本的insert和emplace。

• forward_list不支持push_back和emplace_back。

• vector 和 string 不支持 push_front 和 emplace_front

• 当我们用一个对象去初始化容器或者将对象插入到容器时，实际上放入的是对象的拷贝。

• emplace开头的函数是新标准引入的，这些操作是构造而不是拷贝元素。将参数传递给元素类型的构造函数。emplace成员使用这些参数在容器管理的内存空间中直接构造元素

1

c.emplace_back("978-0590353403 ", 25, 15.99);

• 传递给emplace的参数必须和元素类型的构造函数相匹配。

2.2 访问元素

• 访问成员函数返回的是引用。
• at和下标操作只适用于string、vector、deque、array。
• back不适用于forward_list。
• 如果希望下标是合法的，可以使用at函数。

2.3 删除元素

• 会改变容器大小，不适用于array。
• forward_list有特殊版本的erase
• forward_list不支持pop_back
• vector和string不支持pop_front

2.4 特殊的forward_list操作

• 链表在删除元素时需要修改前置节点的内容，双向链表会前驱的指针，但是单向链表没有保存，因此需要增加获取前置节点的方法。
• forward_list定义了before_begin，即首前（off-the-begining）迭代器，允许我们再在首元素之前添加或删除元素。

2.5 改变容器的大小

• resize不适用与array

3、容器操作可能使迭代器失效

• 在向容器添加元素后：
  • 如果容器是vector或string，且存储空间被重新分配，则指向容器的迭代器、指针、引用都会失效。
  • 对于deque，插入到除首尾位置之外的任何位置都会导致指向容器的迭代器、指针、引用失效。如果在首尾位置添加元素，迭代器会失效，但指向存在元素的引用和指针不会失效。
  • 对于list和forward_list，指向容器的迭代器、指针和引用依然有效。
• 在从一个容器中删除元素后：
  • 对于list和forward_list，指向容器其他位置的迭代器、引用和指针仍然有效。
  • 对于deque，如果在首尾之外的任何位置删除元素，那么指向被删除元素外其他元素的迭代器、指针、引用都会失效；如果是删除deque的尾元素，则尾后迭代器会失效，但其他不受影响；如果删除的是deque的头元素，这些也不会受影响。
  • 对于vector和string，指向被删元素之前的迭代器、引用、指针仍然有效。
  • 注意：当我们删除元素时，尾后迭代器总是会失效。
  • 注意：使用失效的迭代器、指针、引用是严重的运行时错误！
  • 建议：将要求迭代器必须保持有效的程序片段最小化。
  • 建议：不要保存end返回的迭代器。

4、array

4.1 array 定义

与内置数组一样，标准库array的大小也是类型的一部分。当定义一个array时， 除了指定元素类型，还要指定容器大小

1
2
3
4
5
6

array<int , 42>
array<string, 10>

//通过类型别名获得元素类型
array<int ,10>::size_type i ;
array<int>::size_type j ;    //wrong

4.2 array 初始化

4.2.1 默认初始化

array默认初始化包含和定义中一样多的元素，元素的值都被默认初始化，而非空，这一点与其他顺序容器不同

4.2.2 列表初始化

如果我们对array进行列表初始化，初始值的数目必须等于或小于array的大小 如果元素类型是类类型，那么就一定要有可以值初始化的构造函数

4.3 array的拷贝与对象赋值

array不同于内置数组类型，可以拷贝或对象赋值

1
2
3
4

int digs[10] = {0,1,2,3,4,5,6,7,8,9};
int cpy[10] = digs;    //错误，内置数组不能拷贝和赋值
array<int, 10> digits = {0,1,2,3,4,5,6,7,8,91}; 
array<int, 10> copy = digits; // 正确: 只要数组类型匹配即合法

两个限制：1.初始值类型一致 ； 2.大小必须一样

三、vector对象是如何增长的

vector和string在内存中是连续保存的，如果原先分配的内存位置已经使用完，则需要重新分配新空间，将已有元素从就位置移动到新空间中，然后添加新元素。

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

管理容量的成员函数 vector和 string类型提供了一些成员函数，允许我们与它的实现中内存分配部分互动

• shrink_to_fit只适用于vector、string和deque
• capacity和reverse只适用于vector和string。

1
2
3
4

ivec.reserve (50) ; // 将 capacity至少设定为50,可能会更大 
//size应该为24; capacity应该大于等于50,具体值依赖于标准库实现
cout<<"ivec: size: "<<ivec.size()
    << "capacity: " << ivec.capacity() << endl;

总结一哈 只要size不超过capacity就不重新分配，reserve可以要求每次扩容，不少于reserve的实参，但是如果实参也满足不了，就会超过这个值，shrink_to_fit只是一个请求，并非一定会执行

四、额外的string操作

string操作

1、构造string的其他方法

^5f2418

• n,len2,pos2都是无符号值
• 这些构造函数接受const char* 和string参数 , 当从const char *创建string时,这样的数组必须以空字符结尾拷贝，操作遇到空字符时停止，如果我们还给构造函数一个计数值，数组就不必以空字符结尾。

substr操作

2、改变string的其他方法

3、string搜索操作

• string类提供了6个不同的搜索函数，每个函数都有4个重载版本。
• 每个搜索操作都返回一个string::size_type值，表示匹配发生位置的下标。如果搜索失败则返回一个名为string::npos的static成员（类型是string::size_type，初始化值是-1，也就是string最大的可能大小）。

args必须是一下的形式之一：

4、compare函数

逻辑类似于C标准库的strcmp函数，根据s是等于、大于还是小于参数指定的字符串，s.compare返回0、正数或负数。

s.compare()的几种参数形式

5、string和数值转换

五、容器适配器（adapter）

1、什么是适配器

C++ 中的适配器是指一种对标准库容器或其他数据结构进行包装或修饰的结构，以提供不同的接口或行为。适配器在 C++ 中被广泛用于容器库中，可以简化程序代码，提高代码可读性和可维护性。 C++ 标准库提供了以下几种适配器：

1. std::stack：使用底层容器作为栈，提供了一个顶部的元素访问接口，支持 push 和 pop 操作。
2. std::queue：使用底层容器作为队列，提供了一个队列头部的元素访问接口，支持入队和出队操作。
3. std::priority_queue：使用底层容器作为优先队列，提供了一个优先级最高的元素访问接口，支持入队和出队操作。

2、适配器的通用操作和类型

• 可以使用适配器操作，而不能使用底层容器类型的操作。

3、定义一个适配器

stack和queue是基于deque实现的，priority_queue是在vector之上实现的，可以在创建一个适配器时将一个命名的顺序容器作为第二个类型参数，来重载默认容器类型

1
2
3
4

// 在 vector _h实现的空栈 
stack<string, vector<string>> str_stk; 
// str_stk2在vector上实现，初始化时保存svec的拷贝 
stack<string, vector<string>str_stk2(svec);

每个适配器都定义两个构造函数 1.默认构造函数创建一个空对象

1

stack<int> s;

2.接受一个容器的构造函数拷贝该容器来初始化适配器

1
2

//假定deq是一个deque<int>
stack<int> stk(deq);

4、stack

• 定义在stack头文件中。
• stack默认基于deque实现，也可以在list或vector之上实现。

5、queue和priority_queue

• 定义在queue头文件中。
• queue默认基于deque实现，priority_queue默认基于vector实现。
• queue可以在list或vector之上实现，priority_queue也可以用deque实现。