CPP的STL

STL 概述

STL(Standard Template Library, 标准模板库) 主要由 container(容器)、algorithm(算法) 和 iterator(迭代器) 三大部分构成，容器用于存放数据对象(元素)，算法用于操作容器中的数据对象。

STL 容器

一个 STL 容器就是一种数据结构，比如链表、栈和队列等，这些数据结构在 STL 中已经实现好了，在算法设计中可以直接使用它们。

数据结构	说明	实现头文件
向量（vector）	连续存储元素，底层数据结构为数组，支持快速访问。
字符串（string）	字符串处理容器。
双端队列（deque）	连续存储的指向不同元素的指针所在的数组，底层数据结构为一个中央控制器和多个缓冲区，支持首尾元素的快速删除，也支持随机访问。
链表（list）	由结点组成的链表，每个结点包含着一个元素，底层数据结构为双向链表，支持结点的快速增删。
栈（stack）	后进先出的序列，底层一般用deque或者list实现。
队列（queue）	先进先出的序列，底层一般用deque或list实现。
优先队列（prority_queue）	元素的进出队顺序由某个谓词或者关系函数决定的一种队列，底层数据结构一般为vector或deque。
集合（set）/ 多重集合（multiset）	由结点组成的红黑树，每个结点都包含着一个元素，set中所有元素有序但不重复，multiset中所有关键字有序但不重复。
映射（map）/ 多重映射（multimap）	由（关键字，值）对组成的集合，底层数据结构为红黑树，map中所有关键字有序但不重复，multimap中所有关键字有序但可以重复。

STL 算法

STL 算法是用来操作容器中数据的模板函数，STL 提供了大约 100 个实现算法的模板函数。例如，STL 用 sort() 来对一个 vector 中的数据进行排序，用 find() 来搜索一个 list 中的对象。

STL 算法部分主要由头文件 <algorithm>、<numeric> 和 <functional> 组成。

// 用 sort() 实现数组排序的例子
# include <algorithm>
# include <iostream>

using namespace std;

int main(){
    int a[] = {2, 5, 4, 1, 3};
    sort(a, a+5);
    for (int i = 0; i < 5; i++)
        	printf("%d", a[i]);
    printf("\n");
    return 0;
}

STL 迭代器

STL 迭代器用于访问容器中的数据对象，每个容器都有自己的迭代器，只有容器自己才知道如何访问自己的元素。迭代器像 c/c++ 中的指针，算法通过迭代器来定位和操作容器中的数据。

常用的迭代器有：

iterator：指向容器中存放元素的迭代器，用于正向遍历容器中的元素。
const_iterator：指向容器中存放元素的常量迭代器，只能读取容器中的元素。
reverse_iterator：指向容器中存放元素的反向迭代器，用于反向遍历容器中的元素。
const_reverse_iterator：指向容器中存放元素的常量反向迭代器，只能读取容器中的元素。

迭代器常用运算有：

++：正向移动迭代器。
--：反向移动迭代器。
*：返回迭代器所指的元素值。

// 通过迭代器来迭代向量中的元素例子
# include <iostream>
# include <vector>

using namespace std;

int main(){
	vector<int> myv;
	myv.push_back(1);
	myv.push_back(2);
	myv.push_back(3);
	
	vector<int>::iterator it;	// 定义正向迭代器
	for (it = myv.begin(); it != myv.end(); it++)
		printf("%d ", *it);
	printf("\n");
	
	vector<int>::reverse_iterator rit;	// 定义反向迭代器
	for (rit=myv.rbegin(); rit!=myv.rend(); rit++)
		printf("%d ", *rit);
	printf("\n");
	 
	return 0;
}

补充：符号重载

C++ 中的运算符重载允许重新定义或重载大部分内置的运算符，使其适用于自定义类型。

实际上，运算符重载是一种特殊的函数，其函数名由关键字 operator 和要重载的运算符符号构成。
例如，可以重载加法运算符 +，使其适用于类对象之间的运算。

#include <iostream>
using namespace std;

class Box {
public:
    double getVolume() {
        return length * breadth * height;
    }
    void setLength(double len) {
        length = len;
    }
    void setBreadth(double bre) {
        breadth = bre;
    }
    void setHeight(double hei) {
        height = hei;
    }
    // 重载 + 运算符，用于把两个 Box 对象相加
    Box operator+(const Box& b) {
        Box box;
        box.length = this->length + b.length;
        box.breadth = this->breadth + b.breadth;
        box.height = this->height + b.height;
        return box;
    }
private:
    double length; // 长度
    double breadth; // 宽度
    double height; // 高度
};

int main() {
    Box Box1, Box2, Box3;
    // 设置 Box1 和 Box2 的属性...
    // 把两个对象相加，得到 Box3
    Box3 = Box1 + Box2;
    // 输出 Box3 的体积
    cout << "Volume of Box3: " << Box3.getVolume() << endl;
    return 0;
}

常用的STL容器

顺序容器

（1）vector 向量容器：

它是一个向量类模板，向量容器相当于数组。
用于存储具有相同数据类型的一组元素，可以从末尾快速的插入与删除元素，快速地随机访问元素，但是在序列中间插入、删除元素比较慢，因为需要移动插入或删除处于后面的所有元素。

/* 定义 vector 容器的方式 */
vector<int> v1;		// 定义元素为 int 的向量 v1
vector<int> v2(10);		// 指定向量 v2 的初始大小为 10 个 int 元素
vector<double> v3(10， 1.23);	// 指定向量 v3 的 10 个初始元素值都为 1.23
vector<int> v4(a, a+5);		// 用数组 a[0..4] 共5个元素初始化v4

vector 常用的成员函数有：

[]：返回指定下标的元素。
empty()：判断当前向量容器是否为空。
size()：返回当前向量容器的中的实际元素个数。
reverse(n)：为当前向量容器预分配 n 个元素的存储空间。
capacity()：返回当前向量容器在重新进行内存分配以前所能容纳的元素个数。
resize(n)：调整当前向量容器的大小，使其能容纳 n 个元素个数。
push_back()：在当前向量容器尾部添加一个元素。
insert(pos, elem)：在 pos 位置插入元素 elem，即将元素 elem 插入到迭代器 pos 指定元素之前。
front()：获取当前向量容器的第一个元素。
back()：获取当前向量容器的最后一个元素。
erase()：删除当前向量容器中某个迭代器或者迭代器区间指定的元素。
clear()：删除当前向量容器中所有元素。
迭代函数：begin()、end()、rbegin()、rend()。

# include <iostream>
# include <vector>

using namespace std;

int main() {

	vector<int> myv;
	vector<int>::iterator it;

	myv.push_back(1);
	it = myv.begin();

	myv.insert(it, 2);
	myv.push_back(3);
	myv.push_back(4);

	it = myv.end();
	it--;
	myv.erase(it);

	for (it = myv.begin(); it != myv.end(); it++)
		cout << *it << " ";

	return 0;
}

（2）string 字符串容器：

它是一个保存字符序列的容器，所有元素为字符类型，类似 vector<char>。
除了有字符串的一些常用操作以外，还有包含了所有的序列容器的操作。字符串的常用操作包括增加、删除、修改、查找比较、连接、输入、输出等。

/* string 容器初始化 */
char cstr[] = "China! Greate Wall";		// C 字符串
string s1(cstr);		// s1:China! Greate Wall
string s2(s1);			// s2:China! Greate Wall
string s3(cstr, 7, 11);		// s3:Greate Wall
string s4(cstr, 6);		// s4:China!
string s5(5, 'A');	// s5:AAAAA

empty()：判断当前字符串是否为空串。
size()：返回当前字符串的实际字符个数（返回结果为size_type类型）。
length()：返回当前字符串的实际字符个数。
[index]：返回当前字符串位于 index 位置的字符，index 从0开始。
at(index)：返回当前字符串位于 index 位置的字符。
compare(const string& str)：返回当前字符串与字符串 str 的比较结果。在比较时，若两者相等，返回0；前者小于后者，返回-1；否则返回1。
append(c_str)：在当前字符串的末尾添加一个字符串 str。
insert(size_type index，const string& str) ：在当前字符串的 index 处插入一个字符串 str。
迭代函数：begin()、end()、rbegin()、rend()。

# include <iostream>
# include <string>

using namespace std;

int main() {

	string s1 = "", s2, s3 = "Bye";

	s1.append("Good moring");		// s1 = "Good morning"

	s2 = s1;		// s2 = "Good morning"

	int i = s2.find("morning");	// i = 5
	s2.replace(5, s2.length() - i + 1, s3);
	cout << "s1: " << s1 << endl;
	cout << "s2: " << s2 << endl;

	return 0;
}

（3）deque双端队列容器：

它是一个双端队列类模板。
双端队列容器由若干个块构成，每个块中元素地址是连续的，块之间的地址是不连续的，有一个特定的机制将这些块构成一个整体。可以从前面或后面快速插入与删除元素，并可以快速地随机访问元素，但删除元素较慢。

/* 定义 deque 双端队列容器的几种方式  */
deque<int> dq1;		// 定义元素为 int 的双端队列 dq1
deque<int> dq2(10);		// 指定 dq2 的初始化大小为 10 个 int 元素
deque<double> dq3(10, 1.23);	// 指定 dq3 的 10 个初始元素的初值为 1.23
deque<int> dq4(dq2.begin(), dq2.end());		// 用 dq2 创建 dq4

empty()：判断双端队列容器是否为空队。
size()：返回双端队列容器中元素个数。
push_front(elem)：在队头插入元素 elem。
push_back(elem)：在队尾插入元素 elem。
pop_front()：删除队头一个元素。
pop_back()：删除队尾一个元素。
erase()：从双端队列容器中删除一个或几个元素。
clear()：删除双端队列容器中所有元素。
迭代器函数：begin()、end()、rbegin()、rend()。

# include <iostream>
# include <deque>

using namespace std;

void printDeque(deque<int> &dq) {
	// 定义迭代器
	deque<int> :: iterator iter;

	for (iter = dq.begin(); iter != dq.end(); iter++)
		cout << *iter << " ";
	cout << endl;
}

int main() {
	deque<int> dq;
	// 队头插入元素
	dq.push_front(1);
	// 队尾插入元素
	dq.push_back(2);

	cout << "dq: ";
	printDeque(dq);

	// 弹出队头元素和队尾元素
	dq.pop_front();
	dq.pop_back();

	cout << "dq: ";
	printDeque(dq);

	return 0;
}

（4）list链表容器：

它是一个双链表类模板。
可以从任何地方快速插入与删除。它的每个结点之间通过指针链接，不能随机访问元素。

/* 定义 list 容器的几种方法  */
list<int> l1;	// 定义元素为 int 的链表 l1
list<int> l2(10);	// 定义初始大小为 10 int 元素
list<double> l3 (10, 1.2);	// 定义初始有 10 个值为 1.2 的链表
list<int> l4(a, a+5);	// 用数组初始化 l4

empty()：判断链表容器是否为空。
size()：返回链表容器中实际元素个数。
push_back()：在链表尾部插入元素。
pop_back()：删除链表容器的最后一个元素。
remove ()：删除链表容器中所有指定值的元素。
remove_if(cmp)：删除链表容器中满足条件的元素。
erase()：从链表容器中删除一个或几个元素。
unique()：删除链表容器中相邻的重复元素。
clear()：删除链表容器中所有的元素。
insert(pos，elem)：在pos位置插入元素elem，即将元素elem插入到迭代器pos指定元素之前。
insert(pos，n，elem)：在pos位置插入n个元素elem。
insert(pos，pos1，pos2)：在迭代器pos处插入**[pos1，pos2)**的元素。
reverse()：反转链表。
sort()：对链表容器中的元素排序，因为 sort() 排序算法主要用于支持随机访问的容器，而 list 容器不支持随机访问，所以 list 容器提供了 sort() 采用函数用于元素排序。
迭代器函数：begin()、end()、rbegin()、rend()。

# include <iostream>
# include <list>

using namespace std;

void printList(list<int> &lst) {
	list<int>::iterator iter;

	for (iter = lst.begin(); iter != lst.end(); iter++)
		printf("%d ", *iter);
	cout << endl;
}

int main() {

	list<int> lst;

	// 插入元素
	lst.push_back(5);
	lst.push_back(2);
	lst.push_back(7);
	printList(lst);

	// 中间插入元素
	list<int>::iterator it, start, end;
	it = lst.begin();
	start = ++lst.begin();
	end = --lst.end();
	lst.insert(it, start, end);
	printList(lst);

	return 0;
}

适配器容器

（1）stack 栈容器：

它是一个栈类模板，和数据结构中的栈一样，具有后进先出的特点。
栈容器默认的底层容器是 deque。也可以指定其他底层容器。

empty()：判断栈容器是否为空。
size()：返回栈容器中实际元素个数。
push(elem)：元素 elem 进栈。
top()：返回栈顶元素。
pop()：元素出栈。

注意：stack 容器没有 begin() / end() 和 rbegin() / rend() 这样的用于迭代器的成员函数。

# include <iostream>
# include <stack>

using namespace std;

int main() {

	stack<int> st;

	st.push(1);
	st.push(2);
	st.push(3);

	printf("栈顶元素: %d\n", st.top());
	printf("出栈顺序: ");
	while (!st.empty()) {	 	//	栈不空时出栈所有元素
		printf("%d ", st.top());
		st.pop() ;
	}
	printf("\n");


	return 0;
}

（2）queue 队列容器：

它是一个队列类模板，和数据结构中的队列一样，具有先进先出的特点。
不允许顺序遍历，没有 **begin()/end() ** 和 rbegin()/rend() 这样的用于迭代器的成员函数。

empty()：判断队列容器是否为空。
size()：返回队列容器中实际元素个数。
front()：返回队头元素。
back()：返回队尾元素。
push(elem)：元素 elem 进队。
pop()：元素出队。

# include <iostream>
# include <queue>

using namespace std;

int main() {

	queue<int> qu;

	qu.push(2);
	qu.push(3);
	printf("队头元素: %d\n", qu.front());
	printf("队尾元素: %d\n", qu.back());
	printf("出队顺序: ");
	while (!qu.empty()) {	//出队所有元素
		printf("%d ", qu.front());
		qu.pop();
	}
	printf("\n");

	return 0;
}

它是一个优先队列类模板。
优先队列是一种具有受限访问操作的存储结构，元素可以以任意顺序进入优先队列。一旦元素在优先队列容器中，出队操作将出队列最高优先级元素。

empty()：判断优先队列容器是否为空。
size()：返回优先队列容器中实际元素个数。
push(elem)：元素 elem 进队。
top()：获取队头元素。
pop()：元素出队。

# include <iostream>
# include <queue>

using namespace std;

int main() {

	priority_queue<int> qu;
	qu.push(3);
	qu.push(1);
	qu.push(2);
	printf("队头元素: %d\n", qu.top());
	printf("出队顺序: ");
	while (!qu.empty()) {	//出队所有元素
		printf("%d ", qu.top());
		qu.pop();
	}
	printf("\n");

	return 0;
}

关联容器

（1）set 集合容器 / multiset 多重集容器：

set 和 multiset 都是集合类模板，其元素值称为关键字。
set 中元素的关键字是唯一的，multiset 中元素的关键字可以不唯一，而且默认情况下会对元素按关键字自动进行升序排列。查找速度比较快，同时支持集合的交、差和并等一些集合上的运算，如果需要集合中的元素允许重复那么可以使用multiset。

empty()：判断容器是否为空。
size()：返回容器中实际元素个数。
insert()：插入元素。
erase()：从容器删除一个或几个元素。
clear()：删除所有元素。
count(k)：返回容器中关键字k出现的次数。
find(k)：如果容器中存在关键字为k的元素，返回该元素的迭代器，否则返回**end()**值。
upper_bound()：返回一个迭代器，指向关键字大于k的第一个元素。
lower_bound()：返回一个迭代器，指向关键字不小于k的第一个元素。
迭代器函数：begin()、end()、rbegin()、rend()。

# include <iostream>
# include <set>

using namespace std;

int main() {
	/* set 和 multiset 类似这里就不演示了 */
	// 初始化		
	set<int> s;
	set<int>::iterator it;

	// 插入元素
	s.insert(1);
	s.insert(3);
	s.insert(4);

	for (it = s.begin(); it != s.end(); it++)
		printf("%d ", *it);
	printf("\n");


	return 0;
}

（2）map 映射容器和 multimap 多重映射容器：

map 和 multimap 都是映射类模板。
映射是实现关键字与值关系的存储结构，可以使用一个关键字 key 来访问相应的数据值 value。在 set/multiset 中的 key 和 value 都是 key 类型，而 key 和 value 是一个 pair 类结构。

// pair 类结构的声明形如
struct pair{
    T first;
    T second;
}

map/multimap 利用 pair 的 < 运算符将所有元素即 key-value 对按 key 的升序排列，以红黑树的形式存储，可以根据 key 快速地找到与之对应的 value（查找时间为O(log2n)）。
map中不允许关键字重复出现，支持 [] 运算符；而 multimap 中允许关键字重复出现，但不支持 [] 运算符。

empty()：判断容器是否为空。
size()：返回容器中实际元素个数。
map[key]：返回关键字为 key 的元素的引用，如果不存在这样的关键字，则以 key 作为关键字插入一个元素（不适合 multimap ）。
insert(elem)：插入一个元素 elem 并返回该元素的位置。
clear()：删除所有元素。
find()：在容器中查找元素。
count()：容器中指定关键字的元素个数（map中只有1或者0）。
迭代器函数：begin()、end()、rbegin()、rend()。

在 map 中修改元素并不困难，因为 map 容器已经对 [] 运算符进行了重载。

map<char,int> mymap;	// 定义map容器mymap，其元素类型为pair<char,int>
mymap['a'] = 1;   // 或者mymap.insert(pair<char，int>('a',1) );
int ans = mymap['a']; // 获取 map 中的一个值

注意：只有当 map中有这个关键字（‘a’）时才会成功，否则会自动插入一个元素，值为初始化值。可以使用 find() 方法来发现一个关键字是否存在。

# include <iostream>
# include <map>

using namespace std;

int main() {
	map<char, int> mymap;

    // 第一种插入方式
	mymap.insert(pair<char, int> ('a', 1));

    // 第二种插入方式
	mymap.insert(map<char, int>::value_type('b', 2));

    // 第三种插入方式
	mymap['c'] = 3;

	map<char, int>::iterator iter;

	for (iter = mymap.begin(); iter != mymap.end(); iter++)
		printf("[%c, %d]", iter->first, iter->second);
	printf("\n");

	return 0;
}