---

 
 
 

前言

---

C++ 的标准模板库（Standard Template Library，简称 STL）是一个非常强大和实用的库，它提供了许多常用的数据结构和算法，使得 C++ 编程更加高效和方便。下面是对 C++ STL 的一些介绍：

1. 容器（Containers）：STL 提供了一系列容器，用于存储和管理不同类型的数据。常见的容器包括向量（vector）、列表（list）、队列（queue）、栈（stack）、集合（set）、映射（map）等。每个容器都有其特定的特性和适用场景，可以根据数据的访问方式、插入和删除效率等需求选择合适的容器。
2. 算法（Algorithms）：STL 还提供了许多常用的算法，用于对容器中的数据进行操作。例如，排序算法、查找算法、遍历算法等。这些算法可以通过迭代器（iterator）来操作容器中的元素，而不需要关心容器的具体实现细节。这使得算法具有很好的通用性和可复用性。
3. 迭代器（Iterators）：迭代器是一种通用的指针类型，用于遍历容器中的元素。STL 中的算法通常通过迭代器来操作容器中的数据，而不是直接操作容器本身。迭代器提供了一种统一的接口，使得算法可以适用于不同类型的容器。
4. 适配器（Adapters）：适配器是一种将一个已有的容器或算法转换为另一种形式的工具。例如，栈适配器可以将向量或列表转换为具有栈行为的容器，队列适配器可以将向量或列表转换为队列。
5. 头文件：使用 STL 中的容器和算法，需要包含相应的头文件。这些头文件提供了所需的类和函数声明。
6. 模板（Templates）：STL 大量使用了模板技术，这使得它具有很高的灵活性和可扩展性。通过模板，可以定义通用的容器和算法，而不需要针对每种具体的数据类型进行单独的实现。
7. 效率和性能：STL 在设计时考虑了效率和性能，通常提供了高效的实现。但是，在实际使用中，需要根据具体情况选择合适的容器和算法，以满足性能要求。

STL的容器虽然它们底层实现的数据结构都有很大的区别，但设计师们通过封装的方式，将这些底层有很大区别的容器让我们能够快速上手使用这些容器，所以我们在使用STL中的容器时，许多操作都是类似的。我们可以通过这个网站去学习使用：C/C++学习

本文主要对一些容器（C++98）常用的接口进行粗略介绍，其他接口大家需要的话可以自行去查询文档，后续我也会学习并简单实现这些容器的底层结构。

 
 

1. string类

---

1.1 string类对象的常见构造

constructor（构造函数声明）	功能说明
string()	构造空的string类对象，即空字符串
string(const char* s)	用C-string来构造string类对象
string(n, c)	string类对象中包含n个字符c
string(const string& s)	拷贝构造函数

void Teststring()
{
	string s1; // 构造空的string类对象s1
	string s2("hello bit"); // 用C格式字符串构造string类对象s2
	string s3(s2); // 拷贝构造s3
}

 

1.2 string类对象的容量操作

函数名称	功能说明
size()	返回字符串有效字符长度
length()	返回字符串有效字符长度（和上面的size没有区别）
capacity()	返回空间总大小（能存有效字符的空间大小）
empty()	检测字符串是否为空串，是返回true，否则返回false
clear()	清空有效字符
reserve()	为字符串预留空间（只对空间有影响，对数据没有影响）
resize()	将有效字符的个数改成n个，多出来的空间用字符c填充

void Teststring()
{
void Teststring1()
{
	// 注意：string类对象支持直接用cin和cout进行输入和输出
	string s("hello, world");
	cout << s.size() << endl;
	cout << s.length() << endl;
	cout << s.capacity() << endl;
	cout << s << endl;

	// 将s中的字符串清空，注意清空时只是将size清0，不改变底层空间的大小
	s.clear();
	cout << s.size() << endl;
	cout << s.capacity() << endl;

	// 将s中有效字符个数增加到10个，多出位置用'a'进行填充
	// “aaaaaaaaaa”
	s.resize(10, 'a');
	cout << s.size() << endl;
	cout << s.capacity() << endl;

	// 将s中有效字符个数增加到15个，多出位置用缺省值'\0'进行填充
	// "aaaaaaaaaa\0\0\0\0\0"
	// 注意此时s中有效字符个数已经增加到15个
	s.resize(15);
	cout << s.size() << endl;
	cout << s.capacity() << endl;
	cout << s << endl;

	// 将s中有效字符个数缩小到5个
	s.resize(5);
	cout << s.size() << endl;
	cout << s.capacity() << endl;
	cout << s << endl;
}

//====================================================================================
void Teststring2()
{
	string s;
	// 测试reserve是否会改变string中有效元素个数
	s.reserve(100);
	cout << s.size() << endl;
	cout << s.capacity() << endl;

	// 测试reserve参数小于string的底层空间大小时，是否会将空间缩小
	s.reserve(50);
	cout << s.size() << endl;
	cout << s.capacity() << endl;
}


int main()
{
	Teststring2();
	return 0;
}
}

这里经过我的测试，在VS2022下reserve不会进行缩容操作，因为缩容操作的消耗确实很大。在实践中，因为现在的计算机都已经相对比较成熟了，很少会用时间去换空间。

总结：

1. size()与length()方法底层实现原理完全相同，引入size()的原因是为了与其他容器的接口保持一致，一般情况下基本都是用size()。
2. clear()只是将string中有效字符清空，不改变底层空间大小。
3. resize(size_t n) 与 resize(size_t n, char c)都是将字符串中有效字符个数改变到n个，不同的是当字符个数增多时：resize(n)用0来填充多出的元素空间，resize(size_t n, char c)用字符c来填充多出的元素空间。注意：resize在改变元素个数时，如果是将元素个数增多，可能会改变底层容量的大小，如果是将元素个数减少，底层空间总大小不变。
   4. reserve(size_t res_arg = 0)：为string预留空间，不改变有效元素个数，当reserve的参数小于string的底层空间总大小时，reserve不会改变容量大小。

 

1.3 string类对象的访问及遍历操作

函数名称	功能说明
operator[]	返回pos位置的字符
begin() & end()	begin()获取一个字符的迭代器；end()获取最后一个字符下一个位置的迭代器
rbegin() & rend()	rbegin()指向字符串反向开头的反向迭代器；rend()指向字符串反向末端的反向迭代器。
范围for	C++11支持更简洁的范围for的新遍历方式

void Teststring4()
{
	string s("hello world");
	// 3种遍历方式：
	// 需要注意的以下三种方式除了遍历string对象，还可以遍历是修改string中的字符，
	// 另外以下三种方式对于string而言，第一种使用最多
	// 1. for+operator[]
	for (size_t i = 0; i < s.size(); ++i)
		cout << s[i] << endl;

	// 2.迭代器
	string::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << endl;
		++it;
	}

	// string::reverse_iterator rit = s.rbegin();
	// C++11之后，直接使用auto定义迭代器，让编译器推到迭代器的类型
	auto rit = s.rbegin();
	while (rit != s.rend())
		cout << *rit << endl;

	// 3.范围for
	for (auto ch : s)
		cout << ch << endl;
}

 

1.4 string类对象的修改操作

函数名称	功能说明
push_back(str)	在字符串后尾插字符串c
append(str)	在字符串后追加一个字符串
operator+=	在字符串后面追加字符串str
c_str()	返回C格式字符串
find(strr,pos)	从字符串pos位置开始往后找，返回该字符在字符串中的位置
rfind(str,pos)	从字符串pos位置开始往前找字符c，返回该字符在字符串中的位置
substr(pos,n)	在str中从pos位置开始，截取n个字符，然后将其返回

void Teststring5()
{
	string str;
	str.push_back(' ');   // 在str后插入空格
	str.append("hello");  // 在str后追加一个字符"hello"
	str += 'b';           // 在str后追加一个字符'b'   
	str += "it";          // 在str后追加一个字符串"it"
	cout << str << endl;
	cout << str.c_str() << endl;   // 以C语言的方式打印字符串

	// 获取file的后缀
	string file("string.cpp");
	size_t pos = file.rfind('.');
	string suffix(file.substr(pos, file.size() - pos));
	cout << suffix << endl;

	// npos是string里面的一个静态成员变量
	// static const size_t npos = -1;

	// 取出url中的域名
	string url("http://www.cplusplus.com/reference/string/string/find/");
	cout << url << endl;
	size_t start = url.find("://");
	if (start == string::npos)
	{
		cout << "invalid url" << endl;
		return;
	}
	start += 3;
	size_t finish = url.find('/', start);
	string address = url.substr(start, finish - start);
	cout << address << endl;

	// 删除url的协议前缀
	pos = url.find("://");
	url.erase(0, pos + 3);
	cout << url << endl;
}

注意：

1. 在string尾部追加字符时，s.push_back(c) / s.append(1, c) / s += 'c'三种的实现方式差不多，一般情况下string类的+=操作用的比较多，+=操作不仅可以连接单个字符，还可以连接字符串。
2. 对string操作时，如果能够大概预估到放多少字符，可以先通过reserve把空间预留好。

 

1.5 string类非成员函数

函数	功能说明
operator+	尽量少用，因为传值返回，导致深拷贝效率低
operate>>	输入运算符重载
operator<<	输出运算符重载
getline	获取一行字符串（含空白符）
relational operators	大小比较

上面的几个接口大家了解一下，下面的OJ题目中会有一些体现他们的使用。string类中还有一些其他的操作，这里不一一列举，大家在需要用到时不明白了查文档即可。

 
 

2. vector

---

2.1 vector的介绍

1. vector是表示可变大小数组的序列容器。
2. 就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
3. 本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。
4. vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
5. 因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
6. 与其它动态序列容器相比（deque, list and forward_list）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起list和forward_list统一的迭代器和引用更好。

 

2.2 vector的使用

constructor（构造函数声明）	接口说明
vector()	无参构造
vector（n, val）	构造并初始化n个val
vector (x);	拷贝构造
vector (first, last);	使用迭代器进行初始化构造

int TestVector1()
{
    // constructors used in the same order as described above:
    vector<int> first;                                // empty vector of ints
    vector<int> second(4, 100);                       // four ints with value 100
    vector<int> third(second.begin(), second.end());  // iterating through second
    vector<int> fourth(third);                       // a copy of third

    
    // 迭代器构造函数也可用于从数组进行构造:
    int myints[] = { 16,2,77,29 };
    vector<int> fifth(myints, myints + sizeof(myints) / sizeof(int));

    cout << "The contents of fifth are:";
    for (vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it)
        cout << ' ' << *it;
    cout << '\n';

    return 0;
}

 

2.3 vector的迭代器

iterator的使用	接口说明
begin() & end()	获取第一个数据位置的iterator / const_iterator， 获取最后一个数据的下一个位置的iterator / const_iterator
rbegin() & rend()	获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的reverse_iterator

 

2.4 vector空间容量操作

函数名称	功能说明
size()	获取数据个数
capacity()	获取容量大小
empty()	判断容器是否为空
resize()	扩容，多出来的空间用默认类型的构造函数构造出来
reverse()	扩容

• capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。
• 这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。
• resize在开空间的同时还会进行初始化，影响size。

 

2.5 vector增删查改

vector增删查改	功能说明
push_back(val)	尾插
pop_back()	尾删
find(val)	查找
insert(pos,val)	在pos位置的数据
erase(pos)	删除pos位置的数据
swap(ve)	交换两个vector的数据空间
operator[]	像数组一样访问

void TestVector2()
{
	// 使用列表方式初始化，C++11新语法
	vector<int> v{ 1, 2, 3, 4 };

	// 在指定位置前插入值为val的元素，比如：3之前插入30,如果没有则不插入
	// 1. 先使用find查找3所在位置
	// 注意：vector没有提供find方法，如果要查找只能使用STL提供的全局find
	auto pos = find(v.begin(), v.end(), 3);
	if (pos != v.end())
	{
		// 2. 在pos位置之前插入30
		v.insert(pos, 30);
	}

	vector<int>::iterator it = v.begin();
	while (it != v.end()) 
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	pos = find(v.begin(), v.end(), 3);
	// 删除pos位置的数据
	v.erase(pos);

	it = v.begin();
	while (it != v.end()) {
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

 

2.6 vector迭代器失效问题

迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector的迭代器就是原生态指针T*（模版封装的类型T） 。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)。

 
 

3. list

---

3.1 list的介绍

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

 

3.2 list的使用

constructor（构造函数）	功能说明
list (n,val)	构造的list中包含n个值为val的元素
list()	构造空的list
list (x)	拷贝构造函数
list (first,last)	用[first, last)区间中的元素构造list

 

3.3 list的迭代器

此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点

函数声明	功能说明
begin() & end()	返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin() & rend()	返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的reverse_iterator,即begin位置

【注意】

1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动

 

3.4 list空间

函数声明	功能说明
empty()	检测list是否为空，是返回true，否则返回false
size()	返回list中有效节点的个数

 

3.5 list元素访问

函数声明	功能说明
front()	返回list的第一个节点中的值的引用
back()	返回list的最后一个节点中值的引用

 

3.6 list增删查改

函数声明	功能说明
push_front(val)	在list首元素前插入值为val的元素
pop_front()	删除list中第一个元素
push_back(val)	在list尾部插入值为val的元素
pop_back()	删除list中最后一个元素
insert(pos,val)	在list的pos位置中插入值为val的元素
erase(pos)	删除list的pos位置的元素
swap(ls)	交换两个list中的元素
clear()	清空list中的有效元素

list中还有一些操作，需要用到时大家可参阅list的文档说明。

 

3.7 list的迭代器失效

前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

 
 

4. stack

---

4.1 stack的介绍

1. stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。
2. stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。
3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：
   • empty：判空操作
   • back：获取尾部元素操作
   • push_back：尾部插入元素操作
   • pop_back：尾部删除元素操作
4. 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque。

 

4.2 stack的使用

函数名称	功能说明
stack()	构造不同格式的stack对象
empty()	检测stack是否为空
size()	返回stack中元素的个数
top()	返回栈顶元素的引用
push()	将元素val压入stack中
pop()	将stack中尾部的元素弹出

 
 

5. queue

---

5.1 queue的介绍

1. 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。
2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作 :
   • empty：检测队列是否为空
   • size：返回队列中有效元素的个数
   • front：返回队头元素的引用
   • back：返回队尾元素的引用
   • push_back：在队列尾部入队列
   • pop_front：在队列头部出队列
4. 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。

 
 

5.2 queue的使用

函数声明	功能说明
queue()	构造不同格式的queue对象
empty()	检测队列是否为空，是返回true，否则返回false
size()	返回队列中有效元素的个数
front()	返回队头元素的引用
back()	返回队尾元素的引用
push()	在队尾将元素val入队列
pop()	将队头元素出队列

 
 

6. priority_queue

---

6.1 priority_queue的介绍

1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。
3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：
   • empty()：检测容器是否为空
   • size()：返回容器中有效元素个数
   • front()：返回容器中第一个元素的引用
   • push_back()：在容器尾部插入元素
   • pop_back()：删除容器尾部元素
5. 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。
6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

 

6.2 priority_queue的使用

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆(关于堆，这篇博客有较详细的解释：堆的实现)，所有需要用到堆的位置，都可以考虑使用priority_queue。注意：默认情况下priority_queue是大堆。

函数声明	功能说明
priority_queue()	构造不同格式的priority_queue对象
empty()	检测优先级队列是否为空，是返回true，否则返回false
top()	返回优先级队列中最大(最小元素)，即堆顶元素
push(x)	在优先级队列中插入元素x
pop()	删除优先级队列中最大(最小)元素，即堆顶元素

【注意】

1. 默认情况下，priority_queue是大堆。

#include <vector>
#include <queue>
#include <functional> // greater算法的头文件
void TestPriorityQueue()
{
	// 默认情况下，创建的是大堆，其底层按照小于号比较
	vector<int> v{ 3,2,7,6,0,4,1,9,8,5 };
	priority_queue<int> q1;
	for (auto& e : v)
		q1.push(e);
	cout << q1.top() << endl;
	// 如果要创建小堆，将第三个模板参数换成greater比较方式
	priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
	cout << q2.top() << endl;
}

2. 如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供 > 或者 < 的重载。

 
 

7. 树形结构的关联式容器

---

7.1 关联式容器

在上面我们所说的容器称为序列式容器，比如：vector、list，，因为其底层为线性序列的数据结构，里面存储的是元素本身。

 

7.2 键值对

关于键值对，这篇博客有较详细的介绍：键值对pair的使用及模拟实现

在这里就简单的介绍一下：
用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。 比如：现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应该单词，在词典中就可以找到与其对应的中文含义。

 

7.3 树形结构的关联式容器

根据应用场景的不桶，STL总共实现了两种不同结构的管理式容器：树型结构与哈希结构。树型结构的关联式容器主要有四种：map、set、multimap、multiset。 这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列。下面一依次介绍每一个容器。

 
 

8. set

---

8.1 set的介绍

1. set是按照一定次序存储元素的容器
2. 在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。
3. 在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。
4. set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。
5. set在底层是用二叉搜索树(红黑树)实现的。

【注意】

1. 与map / multimap不同，map / multimap中存储的是真正的键值对<key, value>，set中只放value，但在底层实际存放的是由<value, value>构成的键值对。(这里看不懂没关系，后面模拟实现的时候会详细说)
2. set中插入元素时，只需要插入value即可，不需要构造键值对。
3. set中的元素不可以重复(因此可以使用set进行去重)。
4. 使用set的迭代器遍历set中的元素，可以得到有序序列
5. set中的元素默认按照小于来比较
6. set中查找某个元素，时间复杂度为：$O(lo{g}_{2}N)$
7. set中的元素不允许修改（如果能修改就会破坏平衡二叉树的规则）
8. set中的底层使用二叉搜索树(红黑树)来实现。

 

8.2 set的使用

T: set中存放元素的类型，实际在底层存储<value, value>的键值对。
Compare： set中元素默认按照小于来比较
Alloc： set中元素空间的管理方式，使用STL提供的空间配置器管理

函数声明	功能说明
set ()	构造不同格式的set对象

 

8.3 set的迭代器

函数声明	功能说明
begin()	返回set中起始位置元素的迭代器
end()	返回set中最后一个元素后面的迭代器
cbegin()	返回set中起始位置元素的const迭代器
cend()	返回set中最后一个元素后面的const迭代器
rbegin()	返回set第一个元素的反向迭代器，即end
rend()	返回set最后一个元素下一个位置的反向迭代器，即rbegin
crbegin()	返回set第一个元素的反向const迭代器，即cend
crend()	返回set最后一个元素下一个位置的反向const迭代器，即crbegin

 

8.4 set的容量

函数声明	功能说明
empty()	检测set是否为空，空返回true，否则返回true
size()	返回set中有效元素的个数

 

8.5 set的修改操作

函数声明	功能说明
insert (x)	在set中插入元素x，实际插入的是<x, x>构成的键值对，如果插入成功，返回<该元素在set中的位置，true>, 如果插入失败，说明x在set中已经存在，返回<x在set中的位置，false>
erase ( iterator pos )	删除set中pos位置上的元素
erase (x)	删除set中值为x的元素，返回删除的元素的个数
erase ( iterator first, iterator last )	删除set中[first, last)区间中的元素
swap(st)	交换set中的元素
clear()	将set中的元素清空
find(x)	返回set中值为x的元素的位置
count (x)	返回set中值为x的元素的个数

 

8.6 set的使用举例

#include <set>
void TestSet()
{
	// 用数组array中的元素构造set
	int array[] = { 2, 1, 3, 9, 6, 0, 5, 8, 4, 7,7,7,77,7,7 };
	set<int> s(array, array + sizeof(array) / sizeof(array[0]));
	cout << s.size() << endl;
	// 正向打印set中的元素，从打印结果中可以看出：set可去重
	for (auto& e : s)
		cout << e << " ";
	cout << endl;
	// 使用迭代器逆向打印set中的元素
	for (auto it = s.rbegin(); it != s.rend(); ++it)
		cout << *it << " ";
	cout << endl;
	// set中值为7的元素出现了几次
	cout << s.count(7) << endl;
}

 
 

9. multiset

---

9.1 multiset的介绍

1. multiset是按照特定顺序存储元素的容器，其中元素是可以重复的。
2. 在multiset中，元素的value也会识别它(因为multiset中本身存储的就是<value, value>组成的键值对，因此value本身就是key，key就是value，类型为T).multiset元素的值不能在容器中进行修改(因为元素总是const的)，但可以从容器中插入或删除。
3. 在内部，multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序。
4. multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢，但当使用迭代器遍历时会得到一个有序序列。
5. multiset底层结构为二叉搜索树(红黑树)。

【注意】

1. multiset中再底层中存储的是<value, value>的键值对
2. mtltiset的插入接口中只需要插入即可
3. 与set的区别是，multiset中的元素可以重复，set是中value是唯一的
4. 使用迭代器对multiset中的元素进行遍历，可以得到有序的序列
5. multiset中的元素不能修改
6. 在multiset中找某个元素，时间复杂度为$O(lo{g}_{2}N)$
7. multiset的作用：可以对元素进行排序

9.2 multiset的使用

此处只简单演示set与multiset的不同，其他接口接口与set相同，大家可参考set。

#include <set>
void TestSet()
{
	int array[] = { 2, 1, 3, 9, 6, 0, 5, 8, 4, 7,7,7,77,7,7 };

	// 注意：multiset在底层实际存储的是<int, int>的键值对
	multiset<int> s(array, array + sizeof(array) / sizeof(array[0]));
	for (auto& e : s)
		cout << e << " ";
	cout << endl;
}

 
 

10. map

---

10.1 map的介绍

1. map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
2. 在map中，键值（key）通常用于对元素进行排序和唯一标识，而映射值（value）存储与此键相关的内容。键和映射值的类型可以不同，并在成员类型value_type中组合在一起，value_type是将两者组合在一起的pair类型:
         typedef pair<const key, T> value_type;
3. 在内部，map中的元素总是按照键值key进行比较排序的。
4. map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。
5. map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。
6. map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。

 

10.2 map的使用

key: 键值对中key的类型
T： 键值对中value的类型
Compare : 比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)
Alloc： 通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器

由于构造函数这里的接口和set是相似的，所以我举一个例子就好了

函数声明	功能说明
map	构造不同格式的map对象

10.3 map的迭代器

函数声明	功能说明
begin() & end()	begin为首元素的位置，end为最后一个元素的下一个位置
cbegin() & cend()	与begin和end意义相同，但cbegin和cend所指向的元素不能修改
rbegin() & rend()	反向迭代器，rbegin在end位置，rend在begin位置，其++和–操作与begin和end操作移动相反
crbegin() & crend()	与rbegin和rend位置相同，操作相同，但crbegin和crend所指向的元素不能修改

 

10.4 map的容量与元素访问

函数声明	功能说明
empty()	检测map中的元素是否为空，是返回true，否则返回false
size()	返回map中有效元素的个数
operator[] (k)	返回去key对应的value

问题：当key不在map中，通过operator[]获取对应value时会发生什么问题？

• 如果k与容器中某个元素的键匹配，则该函数返回对其映射值的引用。

• 如果k与容器中任何元素的键不匹配，则该函数用该键插入一个新元素，并返回对其映射值的引用。注意，这总是将容器的大小增加1，即使没有将映射值赋给元素(元素是使用其默认构造函数构造的)。

• 类似的成员函数map::at在具有键的元素存在时具有相同的行为，但在不存在时抛出异常。

调用此函数相当于:

(*((this->insert(make_pair(k,mapped_type()))).first)).second
这里比较难看懂，我们举个例子看一下：

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap = { {1, "One"}, {2, "Two"}, {3, "Three"} };

    // 使用 operator[] 访问 map 中的值
    std::string value1 = myMap[1];
    std::string value2 = myMap[2];

    std::cout << "Value for key 1: " << value1 << std::endl;
    std::cout << "Value for key 2: " << value2 << std::endl;

    return 0;
}

在上面的示例中，我们创建了一个 map 对象 myMap ，并将一些键值对插入其中。然后，我们使用 operator[] 来访问 map 中的值，例如 myMap[1] 返回键为 1 对应的值。

需要注意的是，如果给定的键在 map 中不存在， operator[] 会自动插入一个键值对，其中值为默认构造的对象。如果你需要处理键不存在的情况，可以使用 map 的 find 函数来查找键是否存在，然后再进行相应的操作。

 

10.5 map中元素的修改

函数声明	功能说明
insert(x)	在map中插入键值对x，注意x是一个键值对，返回值也是键值对：iterator代表新插入元素的位置，bool代表释放插入成功
erase(iterator pos)	删除pos位置上的元素
erase(x)	删除键值为x的元素
verase(iterator first,iterator last)	删除[first, last)区间中的元素
swap(mp)	交换两个map中的元素
clear()	将map中的元素清空
find(x)	在map中插入key为x的元素，找到返回该元素的位置的迭代器，否则返回end
find(x)	在map中插入key为x的元素，找到返回该元素的位置的const迭代器，否则返回cend
count(x)	返回key为x的键值在map中的个数，注意map中key是唯一的，因此该函数的返回值要么为0，要么为1，因此也可以用该函数来检测一个key是否在map中

#include <string>
#include <map>
void TestMap()
{
	map<string, string> m;
	// 向map中插入元素的方式：
	// 将键值对<"peach","桃子">插入map中，用pair直接来构造键值对
	m.insert(pair<string, string>("peach", "桃子"));
	// 将键值对<"peach","桃子">插入map中，用make_pair函数来构造键值对
	m.insert(make_pair("banan", "香蕉"));

	// 借用operator[]向map中插入元素
	/*
	operator[]的原理是：
	 用<key, T()>构造一个键值对，然后调用insert()函数将该键值对插入到map中
	 如果key已经存在，插入失败，insert函数返回该key所在位置的迭代器
	 如果key不存在，插入成功，insert函数返回新插入元素所在位置的迭代器
	 operator[]函数最后将insert返回值键值对中的value返回
	*/
	// 将<"apple", "">插入map中，插入成功，返回value的引用，将“苹果”赋值给该引用结果，
		m["apple"] = "苹果";
	// key不存在时抛异常
		//m.at("waterme") = "水蜜桃";
		cout << m.size() << endl;
		// 用迭代器去遍历map中的元素，可以得到一个按照key排序的序列
		for (auto& e : m)
			cout << e.first << "--->" << e.second << endl;
		cout << endl;
		// map中的键值对key一定是唯一的，如果key存在将插入失败
		auto ret = m.insert(make_pair("peach", "桃色"));
		if (ret.second)
			cout << "<peach, 桃色>不在map中, 已经插入" << endl;
		else
			cout << "键值为peach的元素已经存在：" << ret.first->first << "--->"
			<< ret.first->second << " 插入失败" << endl;
		// 删除key为"apple"的元素
		m.erase("apple");
		if (1 == m.count("apple"))
			cout << "apple还在" << endl;
		else
			cout << "apple被吃了" << endl;
}

【总结】

1. map中的的元素是键值对
2. map中的key是唯一的，并且不能修改
3. 默认按照小于的方式对key进行比较
4. map中的元素如果用迭代器去遍历，可以得到一个有序的序列
5. map的底层为平衡搜索树(红黑树)，查找效率比较高$O(lo{g}_{2}N)$
6. 支持[]操作符，operator[]中实际进行插入查找。

 
 

11. multimap

---

11.1 multimap的使用

1. Multimaps是关联式容器，它按照特定的顺序，存储由key和value映射成的键值对<key,value>，其中多个键值对之间的key是可以重复的。
2. 在multimap中，通常按照key排序和惟一地标识元素，而映射的value存储与key关联的内容。key和value的类型可能不同，通过multimap内部的成员类型value_type组合在一起，value_type是组合key和value的键值对 :
   typedef pair<const Key, T> value_type;
3. 在内部，multimap中的元素总是通过其内部比较对象，按照指定的特定严格弱排序标准对key进行排序的。
4. multimap通过key访问单个元素的速度通常比unordered_multimap容器慢，但是使用迭代器直接遍历multimap中的元素可以得到关于key有序的序列。
5. multimap在底层用二叉搜索树(红黑树)来实现。

 

11.2 multimap的使用

multimap中的接口可以参考map，功能都是类似的。

【注意】

1. multimap中的key是可以重复的。
2. multimap中的元素默认将key按照小于来比较
3. multimap中没有重载operator[]操作。
4. 使用时与map包含的头文件相同

 
 

12. unordered_map

---

12.1 unordered_map的介绍

1. unordered_map是存储<key, value>键值对的关联式容器，其允许通过keys快速的索引到与其对应的value。
2. 在unordered_map中，键值通常用于唯一的标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。
3. 在内部, unordered_map没有对<kye, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。
4. unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。
5. unordered_map实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问value。
6. 它的迭代器至少是单向链表的迭代器。

 

12.2 unordered_map使用

函数声明	功能说明
unordered_map	构造不同格式的unordered_map对象

 

12.3 unordered_map的容量

函数名称	功能说明
empty()	检测unordered_map是否为空
size()	获取unordered_map的有效元素个数

 

12.4 unordered_map的迭代器

函数名称	功能说明
begin()	返回unordered_map第一个元素的迭代器
end()	返回unordered_map最后一个元素下一个位置的迭代器
cbegin()	返回unordered_map第一个元素的const迭代器
cend()	返回unordered_map最后一个元素下一个位置的const迭代器

 

12.5 unordered_map的元素访问

函数名称	功能介绍
operator[]	返回与key对应的value，没有一个默认值

注意：该函数中实际调用哈希桶的插入操作，用参数key与V()构造一个默认值往底层哈希桶中插入，如果key不在哈希桶中，插入成功，返回V()，插入失败，说明key已经在哈希桶中，将key对应的value返回。

 

12.6 unordered_map的查询

函数名称	功能说明
find(key)	返回key在哈希桶中的位置
count(key)	返回哈希桶中关键码为key的键值对的个数

【注意】
unordered_map中key是不能重复的，因此count函数的返回值最大为1

 

12.7 unordered_map的修改操作

函数声明	功能说明
insert(val)	向容器中插入键值对
erase(val)	删除容器中的键值对
clear()	清空容器中有效元素个数
swap()	交换两个容器中的元素

 

12.8 unordered_map的桶操作

函数声明	功能说明
bucket_count()	返回哈希桶中桶的个数
bucket_size(n)	返回n号桶中有效元素的总个数
bucket(key)	返回元素key所在的桶号

 
 

13. unordered_set

---

13.1 unordered_set的介绍

1. unordered_set是存储没有特定顺序的唯一元素的容器，它允许基于它们的值快速检索单个元素。
2. 在unordered_set中，元素的值同时也是唯一标识它的键。键是不可变的，因此，在容器中不能修改unordered_set中的元素——但是可以插入和删除它们。
3. 在内部，unordered_set中的元素没有按照任何特定的顺序排序，而是根据它们的散列值组织到bucket中，以便通过它们的值直接快速访问单个元素(平均时间复杂度为常数)。
4. Unordered_set容器在按键访问单个元素时比set容器快，尽管它们在通过其元素子集进行范围迭代时通常效率较低。
5. 容器中的迭代器至少是单向链表的迭代器

13.2 unordered_set的使用

函数名称	功能说明
unordered_set()	构造不同格式的unordered_set对象

13.3 unordered_set的容量

函数名称	功能说明
empty()	检测unordered_set是否为空
size()	获取unordered_set的有效元素个数

 

13.4 unordered_set的迭代器

函数名称	功能说明
begin()	返回unordered_set第一个元素的迭代器
end()	返回unordered_set最后一个元素下一个位置的迭代器
cbegin()	返回unordered_set第一个元素的const迭代器
cend()	返回unordered_set最后一个元素下一个位置的const迭代器

 

13.5 unordered_set的查询

函数名称	功能说明
find(key)	返回key在哈希桶中的位置
count(key)	返回哈希桶中关键码为key的键值对的个数

【注意】
unordered_map中key是不能重复的，因此count函数的返回值最大为1

 

13.6 unordered_set的修改操作

函数声明	功能说明
insert(val)	向容器中插入键值对
erase(val)	删除容器中的键值对
clear()	清空容器中有效元素个数
swap()	交换两个容器中的元素

 

12.8 unordered_set的桶操作

函数声明	功能说明
bucket_count()	返回哈希桶中桶的个数
bucket_size(n)	返回n号桶中有效元素的总个数
bucket(key)	返回元素key所在的桶号

 
 

总结

---

关于STL容器的使用，其实只要掌握一两个就可以使用起来了，因为它们大体都是相同的，只有少量的接口有所不同，当我们想使用某个功能时可以根据文档去查询我们所想要的接口来进行调用。写到后面我越写越少了，也不是因为后面这几个容器的接口少或者说是不重要（主要是因为太懒了），我们掌握了前面几个的使用，学习使用后面的容器也并不困难了。