【笔记】C++之SLT的常用容器

总结于《算法笔记》——胡凡、曾磊

本博客使用的IDE为Dev C++，若要使用C++11的新特性，需在工具>编辑选项里勾上“编译时加入以下指令”，并在下面框框里复制粘贴上-std=c++11。

文章目录

1 vector1.1 定义1.2 vecor内元组的访问(1) 通过下标(2) 通过迭代器 1.3 常用函数(1) push_back()(2) pop_back()(3) size()(4) clear()(5) insert()(6) erase() 1.4 常见用途(1) 存储数据(2) 用邻接表存储图 2 set2.1 定义2.2 set内元素的访问2.3 常用函数(1) insert()(2) find()(3) size()(4) clear()(5) erase() 2.4 常见用途 3 string3.1 定义3.2 string中内容的访问(1) 通过下标(2) 通过迭代器 3.3 常用函数(1) +=(2) 比较(3) length()/size()(4) insert()(5) erase()(6) clear()(7) substr()(8) string::npos(9) find()(10) replace() 4 map4.1 定义4.2 map内内容的访问(1) 通过下标(2) 通过迭代器 4.3 常用函数(1) find()(2) erase()(3) size()(4) clear() 4.4 常见用处 5 queue5.1 定义5.2 queue内内容的访问5.3 常用函数(1) push()(2) front()、back()(3) pop()(4) empty()(5) size() 5.4 常见用处 6 priority_queue6.1 定义6.2 priority_queue内内容的访问6.3 常用函数(1) push()(2) top()(3) pop()(4) empty()(5) size() 6.4 priority_queue内元素优先级的设置(1) 基本数据类型(2) 结构体 6.5 常见用处 7 stack7.1 定义7.2 stack内内容的访问7.3 常用函数(1) push()(2) top()(3) pop()(4) empty()(5) size() 7.4 常见用处 8 pair8.1 定义8.2 pair内内容的访问8.3 常用函数比较操作数 8.4 常见用处

1 vector

vector（向量），是长度可以根据需要改变的数组。

使用时要加上#include <vector>，然后在下一行加上using namespace std;

1.1 定义

vector<typename> name;

//例： vector<double> name; vector<int> name; vector<char> name; //注意：如果 typename也是一个STL容器，定义的时候要记得在>>符号之间加上空格，因为有的编译器可能会把它视为移位操作，导致编译错误。如下面定义二维数组。

vector数组：

vector<typename> arrayname[arraysize];

vector<int> v[100]; //一维长度已经固定为100 vector<vector<int> > name; //两维的长度都可变

1.2 vecor内元组的访问

有两种方法：

(1) 通过下标

vector[index]

(2) 通过迭代器

迭代器(iterator)可以理解为指针。

vector<typename>::iterator it;

//例： #include <cstdio> #include <vector> using namespace std; int main(){ vector<int> v; for(int i = 1; i <= 5; i++) { v.push_back(i); //push_back(i)在v的末尾添加元素i } //v.begin()为取v的首元素地址，而it指向这个地址 vector<int>::iterator it = v.begin(); for(int i = 0; i < 5; i++) { printf("%d", *(it + i)); //v[i]等同于*(v.begin() + i) } return 0; }

此外，迭代器还可进行自加操作：++it和it++：

#include <cstdio> #include <vector> using namespace std; int main(){ vector<int> v; for(int i = 1; i <= 5; i++) { v.push_back(i); } // v.begin()是取v的首地址，而v.end()取v尾元素地址的下一个地址 // vector的迭代器不支持it < vi,end()写法，因此循环条件只能用it != vi.end() for(vector<int>::iterator it = v.begin(); it != v.end(); it++) { printf("%d", *it); } return 0; }

最后需要指出，在常用STL容器中，只有在vector和 string中，才允许使用 v.begin() + 3这种迭代器加上整数的写法。

1.3 常用函数

(1) push_back()

push_back(x)就是在vector后加一个元素x。

(2) pop_back()

pop_back()用以删除vector的尾元素

(3) size()

size()用来获得vector中元素个数。

size返回的是 unsigned类型，不过一般来说用%d不会出很大问题，这一点对所有STL容器都是一样的。

(4) clear()

clear()用于清空vector中的所有元素。

(5) insert()

insert(it, x)用来向 vector的任意迭代器it处插入一个元素x。

(6) erase()

erase()有两种用法：

删除单个元素：

erase(i)即删除迭代器为it处的元素。

删除一个区间内所有的元素：

erase(first, last)即删除[first, last)内的所有元素。

1.4 常见用途

(1) 存储数据

在一些元素不确定的场合可以使用。

(2) 用邻接表存储图

2 set

set翻译为集合，是一个内部自动有序且不含重复元素的容器。

使用时要加上#include <set>，然后在下一行加上using namespace std;

2.1 定义

set<typename> name;

set数组：

set<typename> arrayname[arraysize];

2.2 set内元素的访问

set只能通过迭代器访问：

set<typename>::iterator it;

由于除开vector和string之外的STL容器都不支持*(it + i)的访问方式，因此只能按如下方式枚举：

#include <cstdio> #include <set> using namespace std; int main(){ set<int> st; for(int i = 1; i <= 5; i++) { st.insert(i); // insert(i)将i插入set中 } for(set<int>::iterator it = st.begin(); it != st.end(); it++) { printf("%d", *it); } return 0; }

2.3 常用函数

(1) insert()

insertx(x)和将x插入set容器中，并自动递增排序和去重。

(2) find()

find(value)返回set中对应值为value的迭代器。

#include <cstdio> #include <set> using namespace std; int main(){ set<int> st; for(int i = 1; i <= 5; i++) { st.insert(i); } set<int>::iterator it = st.find(2); printf("%d\n", *it); //也可以写成 //printf("%d\n", *(st.find(2))); return 0; }

(3) size()

size()用来获得set中元素个数。

(4) clear()

clear()用于清空set中的所有元素。

(5) erase()

erase()有两种用法：

删除单个元素：

有两种方法：

st.erase(it)，it为所需要删除元素的迭代器，可结合find()函数使用。

#include <cstdio> #include <set> using namespace std; int main(){ set<int> st; for(int i = 1; i <= 5; i++) { st.insert(i); } st.erase(st.find(1)); st.erase(st.find(3)); for(set<int>::iterator it = st.begin(); it != st.end(); it++) { printf("%d", *it); } return 0; }

输出结果：

245

st.erase(value)，value为所需要删除的元素。

#include <cstdio> #include <set> using namespace std; int main(){ set<int> st; for(int i = 1; i <= 5; i++) { st.insert(i); } st.erase(4); for(set<int>::iterator it = st.begin(); it != st.end(); it++) { printf("%d", *it); } return 0; }

输出结果：

1235

删除一个区间内所有的元素：

erase(first, last)即删除[first, last)内的所有元素。

#include <cstdio> #include <set> using namespace std; int main(){ set<int> st; for(int i = 1; i <= 5; i++) { st.insert(i); } set<int>::iterator it = st.find(4); st.erase(it, st.end()); //删除元素4至set末尾之间的元素，即4和5 for(it = st.begin(); it != st.end(); it++) { printf("%d", *it); } return 0; }

输出结果：

123

2.4 常见用途

遇到需要去重但不方便直接开数组的情况，可尝试用set解决。

3 string

使用时要加上#include <string>（注意string.h和string不是一样的头文件），然后在下一行加上using namespace std;

3.1 定义

string str;

初始化：

string str = "abcd";

3.2 string中内容的访问

(1) 通过下标

str[index]

如果要读入和输出整个字符串，则只能用cin和cout。

(2) 通过迭代器

string不想其他STL容器那样需要参数，因此可以直接如下定义：

string::iterator it;

string和vector一样，支持直接对迭代器进行加减，如str.begin() + 3。

3.3 常用函数

(1) +=

string的加法，可以将两个string直接拼接起来。

#include <iostream> #include <string> using namespace std; int main(){ string str1 = "abc", str2 = "xyz", str3; str3 = str1 + str2; str1 += str2; cout << str1 << endl; cout << str3 << endl; return 0; }

(2) 比较

两个string类型可直接用==、!=、< 、<=、>、>=比较大小，比较规则是字典序（即"aac"小于"aba"）。

(3) length()/size()

size()和length()基本相同

(4) insert()

insert(pos, string)，在pos号位置插入string（从0开始）。

#include <iostream> #include <string> using namespace std; int main(){ string str1 = "abcxyz", str2 = "opq"; str1.insert(3, str2); cout << str1 << endl; return 0; }

输出结果：

abcopqxyz

insert(it, it2, it3)，it为原字符串的欲插入位置，it2和it3为待插字符串的首尾迭代器，表示[it2, it3)将被插在it的位置上。

#include <iostream> #include <string> using namespace std; int main(){ string str1 = " Hi, man!", str2 = "See you."; str1.insert(str1.begin(), str2.begin(), str2.end()); cout << str1 << endl; return 0; }

输出结果：

See you. Hi, man!

(5) erase()

删除单个元素：

erase(i)即删除迭代器为it处的元素。

删除一个区间内所有的元素：

str.erase(first, last)，其中first为区间的起始迭代器，而last为需要删除的区间的末尾迭代器的下一个地址。str.erase(pos, length)，其中pos为需要开始删除的起始位置，而length为删除的字符个数。

(6) clear()

clear()用于清空string中的所有元素。

(7) substr()

substr(pos, len)返回从pos号开始、长度为len的子串。

#include <iostream> #include <string> using namespace std; int main(){ string str = "abcxyz"; cout << str.substr(1, 3) << endl; return 0; }

输出结果：

bcx

(8) string::npos

string::npos是一个常数，其本身的值为-1，是unsighed_int类型。string::npos用以作为find()函数失配时的返回值。

(9) find()

str.find(str2)，当str2是str的子串时，返回其在str中第一次出现的位置；如果str2不是str的子串，则返回string::npos。

str.find(str2, pos)，从str的pos号开始匹配str2，返回值与上相同。

#include <iostream> #include <string> using namespace std; int main(){ string str = "Thank you for your help."; string str1 = "you"; string str2 = "me"; if(str.find(str1) != string::npos) cout << str.find(str1) << endl; if(str.find(str1, 7) != string::npos) cout << str.find(str1, 7) << endl; if(str.find(str2) != string::npos) cout << str.find(str2) << endl; else cout << "There is no position for me." << endl; return 0; }

输出结果：

6 14 There is no position for me.

(10) replace()

str.replace(pos, len, str2)把str从pos位开始、长度为len的字符串换成str2.

str.replace(it1, it2, str2)把str的迭代器[it1, it2)范围的子串换成str2.

#include <iostream> #include <string> using namespace std; int main(){ string str = "Thank you for your help."; string str1 = "HAPPY"; string str2 = "BITE"; cout << str.replace(10, 2, str1) << endl; cout << str.replace(str.begin(), str.begin() + 1, str2) << endl; return 0; }

输出结果：

Thank you HAPPYr your help. BITEhank you HAPPYr your help.

4 map

map可以将任何基本类型（包括STL容器）映射到任何基本类型（包括STL容器）。

使用时要加上#include <map>，然后在下一行加上using namespace std;

4.1 定义

map<typename1, typename2> mp;

如果是字符串到整型的映射，必须使用string而不能用char数组：

map<string, int> mp;

map的键和值也可以是STL容器：

map<set<int>, string> mp;

4.2 map内内容的访问

(1) 通过下标

map中的键是唯一的。

mp['key']

(2) 通过迭代器

map<typename1, typename2>::iterator it;

4.3 常用函数

(1) find()

代码：

#include <iostream> #include <map> using namespace std; int main(){ map<char, int> mp; mp['a'] = 1; mp['b'] = 2; mp['c'] = 3; map<char, int>::iterator it = mp.find('b'); printf("%c %d\n", it -> first, it -> second); return 0; }

输出结果：

b 2

(2) erase()

删除单个元素：

mp.erase(it)，it为欲删除的元素的迭代器。

mp.erase(key)，key为欲删除的映射的键。

#include <iostream> #include <map> using namespace std; int main(){ map<char, int> mp; mp['a'] = 1; mp['b'] = 2; mp['c'] = 3; mp['d'] = 4; map<char, int>::iterator it = mp.find('b'); mp.erase(it); // 利用迭代器删除b 2 mp.erase('c'); // 删除键为c的映射,即c 3 for(map<char, int>::iterator it = mp.begin(); it != mp.end(); it++) { printf("%c %d\n", it -> first, it -> second); } return 0; }

输出结果：

a 1 d 4

删除一个区间内所有的元素：

mp.erase(first, last)，删除[first, last)内的所有元素，first为起始迭代器，last为末尾迭代器的下一个地址。

#include <iostream> #include <map> using namespace std; int main(){ map<char, int> mp; mp['a'] = 1; mp['b'] = 2; mp['c'] = 3; map<char, int>::iterator it = mp.find('b'); mp.erase(it, mp.end()); for(map<char, int>::iterator it = mp.begin(); it != mp.end(); it++) { printf("%c %d\n", it -> first, it -> second); } return 0; }

输出结果：

a 1

(3) size()

(4) clear()

4.4 常见用处

需要建立字符（或字符串）与整数之间映射的题目；

判断大整数或其他类型数据是否存在的题目，可以把map当bool数组用；

字符串和字符串的映射。

5 queue

queue(队列)是STL中实现的一个先进先出的容器。

使用时要加上#include <queue>，然后在下一行加上using namespace std;

5.1 定义

queue<typename> name;

5.2 queue内内容的访问

因为队列是一种先进先出的数据结构，因此在SLT中只能用front()访问队首元素，通过back()访问队尾元素。

#include <iostream> #include <queue> using namespace std; int main(){ queue<int> q; for(int i = 1; i <= 5; i++) { q.push(i); //push(i)用以将i压入队列 } printf("%d %d\n", q.front(), q.back()); return 0; }

输出结果：

1 5

5.3 常用函数

(1) push()

push(x)将x压入队列。

(2) front()、back()

front()用于访问队首元素，back()用于访问队尾元素。

(3) pop()

pop()令队首元素出队。

#include <iostream> #include <queue> using namespace std; int main(){ queue<int> q; for(int i = 1; i <= 5; i++) { q.push(i); // push(i)用以将i压入队列 } for(int i = 1; i <= 5; i++) { printf("%d ", q.front()); // 输出队首元素 q.pop(); //出队首元素3次（依次为1 2 3） } printf("\n"); printf("%d\n", q.front()); return 0; }

输出结果：

1 2 3 4 5 0

(4) empty()

empty()检测 queue是否为空，返回true则空，返回false则非空。

#include <iostream> #include <queue> using namespace std; void isEmpty(queue<int> q){ // 判断队列是否为空的函数 if(q.empty() == true){ printf("Empty\n"); }else{ printf("Not empty\n"); } } int main(){ queue<int> q; isEmpty(q); // 一开始队列里没有元素，所以是空 q.push(1); isEmpty(q); // 在入队"1"后，队列非空 return 0; }

输出结果：

Empty Not empty

(5) size()

5.4 常见用处

当需要实现广度优先搜索时，可以不用自己手动实现一个队列，而是用queue作为代替，以提高程序的准确性。

**注意：**使用front()和pop()函数前，必须用empty()判断队列是否为空。

6 priority_queue

priority_queue又叫优先队列，其底层是用堆进行实现的。队首元素一定是当前队列中优先级最高的那一个。

可以在任何时间往优先队列里加入（push）元素，优先队列底层的堆（heap）会随时调整结构，使得每次的队首元素都是优先最大的。

关于这里的优先级则是规定出来的。

使用时要加上#include <queue>，然后在下一行加上using namespace std;

6.1 定义

priority_queue<typename> name;

6.2 priority_queue内内容的访问

和queue不同，priority_queue没有front()和back()函数，只能通过top()函数来访问队首元素（堆顶元素），也就是优先级最高的元素。

#include <iostream> #include <queue> using namespace std; int main(){ priority_queue<int> q; q.push(4); q.push(5); q.push(1); printf("%d", q.top()); return 0; }

输出结果：

4

6.3 常用函数

(1) push()

(2) top()

获得队首元素（即堆顶元素）出队。

#include <stdio.h> #include <queue> using namespace std; int main(void){ priority_queue<int> q; q.push(3); q.push(4); q.push(1); printf("%d\n", q.top()); q.pop(); printf("%d\n", q.top()); return 0; }

输出结果：

4 3

(3) pop()

(4) empty()

(5) size()

6.4 priority_queue内元素优先级的设置

(1) 基本数据类型

此处指的基本数据类型就是int型、 double型、char型等可以直接使用的数据类型，优先队列对他们的优先级设置一般是数字大的优先级越高。

下面两种定义方式是等价的(注意最后两个>之间有一个空格)：

priority_queue<int> q;

priority_queue<int, vector<int>, less<int> > q;

第二种定义方法尖括号内多了两个参数：

vector<int>填写的是来承载底层数据结构堆(heap)的容器。如果第一个参数是double型或char型，则此处只需填写vector<double>或vector<char>；

less<int>是对第一个参数的比较类。less<int>表示数字大的优先级越大，而greater<int>表示数字小的优先级越大。

示例：

#include <stdio.h> #include <queue> using namespace std; int main(void){ priority_queue<int, vector<int>, greater<int> > q; //让优先队列总是把最小的元素放队首 q.push(3); q.push(4); q.push(1); printf("%d\n", q.top()); return 0; }

输出结果：

1

(2) 结构体

通过改变小于号"<"的功能，即把它重载(overload)为大于号的功能。

现在希望按水果的价格高的为优先级高，需要重载小于号：

struct fruit { string name; int price; friend bool operator < (fruit f1, fruit f2) { // friend为友元，bool operator < (fruit f1, fruit f2)对fruit类型的操作符"<"进行重载 return f1.price < f2.price; // 重载后小于号还是小于号的作用。 } };

此时可以直接定义fruit类型的优先队列，其内部就是以价格高的水果为优先级高。priority_queue<fruit> q;

同理，希如果望按水果的价格低的为优先级高，只需要把return中的大于号改为小于号。

示例：

#include <iostream> #include <string> #include <queue> using namespace std; struct fruit { string name; int price; friend bool operator < (fruit f1, fruit f2) { return f1.price > f2.price; //优先最小的 } }f1, f2, f3; int main(void){ priority_queue<fruit> q; f1.name = "桃子"; f1.price = 3; f2.name = "苹果"; f2.price = 4; f3.name = "香蕉"; f3.price = 1; q.push(f1); q.push(f2); q.push(f3); cout << q.top().name << " " << q.top().price << endl; return 0; }

输出结果：

香蕉 1

记住：**优先队列的这个函数与sort中的函数效果是相反的！**在排序中，return f1.price > f2.price;表示按价格从高到低，而在优先队列中却是把价格低的放队首。这是因为优先队列本身默认的规则就是优先级高的放队首，因此把小于号重载为大鱼号的功能时只是把这个规则反了一下。

可以把sort中的cmp函数卸载结构体外面：

示例：

#include <iostream> #include <string> #include <queue> using namespace std; struct fruit { string name; int price; }f1, f2, f3; struct cmp { bool operator () (fruit f1, fruit f2) { return f1.price > f2.price; //优先最小的 } }; int main(void){ priority_queue<fruit, vector<fruit>, cmp> q; //这种情况只能这样定义优先队列 f1.name = "桃子"; f1.price = 3; f2.name = "苹果"; f2.price = 4; f3.name = "香蕉"; f3.price = 1; q.push(f1); q.push(f2); q.push(f3); cout << q.top().name << " " << q.top().price << endl; return 0; }

输出结果：

香蕉 1

如果结构体内的数据庞大（例如出现字符串或数组），建议使用引用来提升效率，此时比较类的参数中要加入const和&，如下所示：

friend bool operator () (const fruit &f1, const fruit &f2) { return f1.price > f2.price; } bool operator () (const fruit &f1, const fruit &f2) { return f1.price > f2.price; }

6.5 常见用处

priority_queue可以解决一些贪心问题，也可以对DijKstra算法进行优化（因为优先队列的本质是堆）。

注意：使用top()函数前，要用empty()判断优先队列是否为空。

7 stack

栈，是STL实现的一个后进后出的容器。

使用时要加上#include <stack>，然后在下一行加上using namespace std;

7.1 定义

stack<typename> name;

7.2 stack内内容的访问

由于栈本身就是一种后出先出的数据结构，在STL中的stack中只能通过top()来访问栈顶元素。

#include <stdio.h> #include <stack> using namespace std; int main(void){ stack<int> st; for(int i = 1; i <= 5; i++) { st.push(i); } printf("%d\n",st.top()); return 0; }

输出结果：

5

7.3 常用函数

(1) push()

(2) top()

(3) pop()

弹出栈顶元素。

#include <stdio.h> #include <stack> using namespace std; int main(void){ stack<int> st; for(int i = 1; i <= 5; i++) { st.push(i); } for(int i = 1; i <= 3; i++) { st.pop(); // 连续3次将栈顶元素出栈，即5, 4, 3出栈 } printf("%d\n",st.top()); return 0; }

输出结果：

2

(4) empty()

(5) size()

7.4 常见用处

stack用来模拟一些递归，防止程序对栈内存的限制而导致程序出错。

8 pair

pair可以看作内部有两个元素的结构体，且这两个元素的类型是可以指定的，如：

struct pair { typename1 first; typename2 second; };

使用时要加上#include <utility>，然后在下一行加上using namespace std;。注意：由于map的内部实现中涉及pair，因此添加map头文件时会自动添加utility头文件。因此可偷懒只添加#include <utility>。

8.1 定义

有两个参数，分别对应first和second的数据类型，他们可以是任意基本数据类型或容器。

pair<typename1, typename2> name;

如：

pair<string, int> p;

如果想在定义时初始化：

pair<string, int> p("haha", 5);

如果想在代码中临时构建一个pair，有如下两种方法：

pair<string, int>("haha", 5);make_pair("haha", 5);

8.2 pair内内容的访问

pair中只有两个元素，分别是first和second，只需按正常结构体的方式访问即可。

#include <iostream> #include <utility> #include <string> using namespace std; int main(void){ pair<string, int> p; p.first = "haha"; p.second = 5; cout << p.first << " " << p.second << endl; p = make_pair("xixi", 3); //自带函数 cout << p.first << " " << p.second << endl; p = pair<string, int>("wuwu", 555); cout << p.first << " " << p.second << endl; return 0; }

输出结果：

haha 5 xixi 3 wuwu 555

8.3 常用函数

比较操作数

两个pair类型数据可直接用==、！=、<等比较大小，规则是先比first，first相等时再比second。

#include <iostream> #include <utility> #include <string> using namespace std; int main(void){ pair<int, int> p1(5, 55); pair<int, int> p2(5, 555); pair<int, int> p3(10, 5); if(p1 < p3) cout << "p1 < p3" << endl; if(p1 <= p3) cout << "p1 <= p3" << endl; if(p1 < p2) cout << "p1 < p2" << endl; return 0; }

输出结果：

p1 < p3 p1 <= p3 p1 < p2

8.4 常见用处

用来代替二元结构体及其构造函数，可以节省编码时间。

作为map的键值对来进行插入。

#include <iostream> #include <map> #include <string> using namespace std; int main(void){ map<string, int> mp; mp.insert(make_pair("heihei", 5)); mp.insert(pair<string, int>("haha", 2)); for(map<string, int>::iterator it = mp.begin(); it != mp.end(); it++) { cout << it->first << " " << it -> second << endl; } return 0; }

输出结果：

haha 2 heihei 5