C++标准库(Standard Template Library,STL)
- 里面有很多常用的数据结构和算法的模板,可直接使用。
容器(container):是用于存放数据的类模板。
顺序容器
顺序容器有以下三种:可变长动态数组 vector、双端队列 deque、双向链表 list。
关联容器
关联容器有以下四种:set、multiset、map、multimap。关联容器内的元素是排序的。插入元素时,容器会按一定的排序规则将元素放到适当的位置上,因此插入元素时不能指定位置。
除了以上两类容器外,STL 还在两类容器的基础上屏蔽一部分功能,突出或增加另一部分功能,实现了三种容器适配器:栈 stack、队列 queue、优先级队列 priority_queue。
所有容器都有以下两个成员函数:
int size():返回容器对象中元素的个数。
bool empty():判断容器对象是否为空。
顺序容器和关联容器还有以下成员函数:
begin():返回指向容器中第一个元素的迭代器。
end():返回指向容器中最后一个元素后面的位置的迭代器。
rbegin():返回指向容器中最后一个元素的反向迭代器。
rend():返回指向容器中第一个元素前面的位置的反向迭代器。
erase(…):从容器中删除一个或几个元素。该函数参数较复杂,此处省略。
clear():从容器中删除所有元素。
如果一个容器是空的,则 begin() 和 end() 的返回值相等,rbegin() 和 rend() 的返回值也相等。
顺序容器还有以下常用成员函数:
front():返回容器中第一个元素的引用。
back():返回容器中最后一个元素的引用。
push_back():在容器末尾增加新元素。
pop_back():删除容器末尾的元素。
insert(…):插入一个或多个元素。该函数参数较复杂,此处省略。
在遍历访问容器元素的时候
- 一来可以定义迭代器如: 容器类名::iterator 迭代器名;
- 二者直接用auto,自动配变量
迭代器遍历vector容器中的所有元素
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> v; //v是存放int类型变量的可变长数组,开始时没有元素
for (int n = 0; n<5; ++n)
v.push_back(n); //push_back成员函数在vector容器尾部添加一个元素
vector<int>::iterator i; //定义正向迭代器
for (i = v.begin(); i != v.end(); ++i) { //用迭代器遍历容器
cout << *i << " "; //*i 就是迭代器i指向的元素
*i *= 2; //每个元素变为原来的2倍
}
cout << endl;
//用反向迭代器遍历容器
for (vector<int>::reverse_iterator j = v.rbegin(); j != v.rend(); ++j)
cout << *j << " ";
return 0;
}
迭代器的辅助函数
STL 中有用于操作迭代器的三个函数模板,它们是:
advance(p, n):使迭代器 p 向前或向后移动 n 个元素。
distance(p, q):计算两个迭代器之间的距离,即迭代器 p 经过多少次 + + 操作后和迭代器 q 相等。如果调用时 p 已经指向 q 的后面,则这个函数会陷入死循环。
iter_swap(p, q):用于交换两个迭代器 p、q 指向的值。
要使用上述模板,需要包含头文件 algorithm。下面的程序演示了这三个函数模板的 用法。
#include <list>
#include <iostream>
#include <algorithm> //要使用操作迭代器的函数模板,需要包含此文件
using namespace std;
int main()
{
int a[5] = { 1, 2, 3, 4, 5 };
list <int> lst(a, a+5);
list <int>::iterator p = lst.begin();
advance(p, 2); //p向后移动两个元素,指向3
cout << "1)" << *p << endl; //输出 1)3
advance(p, -1); //p向前移动一个元素,指向2
cout << "2)" << *p << endl; //输出 2)2
list<int>::iterator q = lst.end();
q--; //q 指向 5
cout << "3)" << distance(p, q) << endl; //输出 3)3
iter_swap(p, q); //交换 2 和 5
cout << "4)";
for (p = lst.begin(); p != lst.end(); ++p)
cout << *p << " ";
return 0;
}
程序的输出结果是:
1) 3
2) 2
3) 3
4) 1 5 3 4 2
下面来简绍在容器中两个比较好用的函数
find:在容器中查找元素。
count_if:统计容器中符合某种条件的元素的个数。
find的函数用法如下
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
int a[10] = {10,20,30,40};
vector<int> v;
v.push_back(1); v.push_back(2);
v.push_back(3); v.push_back(4); //此后v里放着4个元素:1,2,3,4
vector<int>::iterator p;
p = find(v.begin(),v.end(),3); //在v中查找3
if(p != v.end()) //若找不到,find返回 v.end()
cout << "1) " << * p << endl; //找到了
p = find(v.begin(),v.end(),9);
if(p == v.end())
cout << "not found " << endl; //没找到
p = find(v.begin()+1,v.end()-1,4); //在,3 这两个元素中查找4
cout << "2) " << * p << endl;
int * pp = find(a,a+4,20);
if(pp == a + 4)
cout << "not found" << endl;
else
cout << "3) " <<* pp << endl;
}
count_if的用法如下
其实comp比较函数才是整个count_if函数的核心,comp比较函数是编程的人写的,返回值是一个布尔型,我相信看完我的例题后,就可以理解这个函数的应用。例题:统计1-10奇数的个数(我的代码):
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
bool comp(int num)
{
return num%2;
}
int main()
{
vector <int> V;
for(int i=1;i<=10;i++)
V.push_back(i);
cout<<count_if(V.begin(),V.end(),comp)<<endl;
return 0;
}
输出:5
发现了函数的奥秘了吗?我们来看一下count_if函数STL的源代码:
template <class InputIterator, class Predicate>
ptrdiff_t count_if ( InputIterator first, InputIterator last, Predicate pred )
{
ptrdiff_t ret=0;
while (first != last)
if (pred(*first++)) ++ret;
return ret;
}
再看一个例题:输入一串学生的信息,统计出成绩大于90分的同学个数(我的代码):
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
struct student
{
string name;
int score;
};
bool compare(student a)
{
return 90<a.score;
}
int main()
{
int n;
cin>>n;
vector<student> V;
for(int i=0;i<n;i++)
{
student temp;
cin>>temp.name>>temp.score;
V.push_back(temp);
}
cout<<count_if(V.begin(),V.end(),compare)<<endl;
return 0;
}
看了代码之后,理解这个函数就不难了。注意:count函数和count_if函数的复杂度是线性的,在数据量大的时候,要使用更加好的方法。
下面的程序演示了 vector 的基本用法。
#include <iostream>
#include <vector> //使用vector需要包含此头文件
using namespace std;
template <class T>
void PrintVector(const vector <T> & v)
{ //用于输出vector容器的全部元素的函数模板
typename vector <T>::const_iterator i;
//typename 用来说明 vector <T>::const_iterator 是一个类型,在 Visual Studio 中不写也可以
for (i = v.begin(); i != v.end(); ++i)
cout << *i << " ";
cout << endl;
}
int main()
{
int a[5] = { 1, 2, 3, 4, 5 };
vector <int> v(a, a + 5); //将数组a的内容放入v
cout << "1) " << v.end() - v.begin() << endl; //两个随机迭代器可以相减,输出:1)5
cout << "2)"; PrintVector(v); //输出:2)1 2 3 4 5
v.insert(v.begin() + 2, 13); //在 begin()+2 位置插人 13
cout << "3)"; PrintVector(v); //输出:3)1 2 13 3 4 5
v.erase(v.begin() + 2); //删除位于 begin()+2 位置的元素
cout << "4)"; PrintVector(v); //输出:4)1 2 3 4 5
vector<int> v2(4, 100); //v2 有 4 个元素,都是 100
v2.insert(v2.begin(), v.begin() + 1, v.begin() + 3); //将v的一段插入v2开头
cout << "5)v2:"; PrintVector(v2); //输出:5)v2:2 3 100 100 100 100
v.erase(v.begin() + 1, v.begin() + 3); //删除 v 上的一个区间,即 [2,3)
cout << "6)"; PrintVector(v); //输出:6)1 4 5
return 0;
}
vector 还可以嵌套以形成可变长的二维数组。例如:
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<vector<int> > v(3); //v有3个元素,每个元素都是vector<int> 容器
for(int i = 0;i < v.size(); ++i)
for(int j = 0; j < 4; ++j)
v[i].push_back(j);
for(int i = 0;i < v.size(); ++i) {
for(int j = 0; j < v[i].size(); ++j)
cout << v[i][j] << " ";
cout << endl;
}
return 0;
}
0 1 2 3
0 1 2 3
0 1 2 3
list 的示例程序如下:
#include <list> //使用 list 需要包含此头文件
#include <iostream>
#include <algorithm> //使用STL中的算法需要包含此头文件
using namespace std;
class A {
private: int n;
public:
A(int n_) { n = n_; }
friend bool operator < (const A & a1, const A & a2);
friend bool operator == (const A & a1, const A & a2);
friend ostream & operator << (ostream & o, const A & a);
};
bool operator < (const A & a1, const A & a2) {
return a1.n < a2.n;
}
bool operator == (const A & a1, const A & a2) {
return a1.n == a2.n;
}
ostream & operator << (ostream & o, const A & a) {
o << a.n;
return o;
}
template <class T>
void Print(T first, T last)
{
for (; first != last; ++first)
cout << *first << " ";
cout << endl;
}
int main()
{
A a[5] = { 1, 3, 2, 4, 2 };
A b[7] = { 10, 30, 20, 30, 30, 40, 40 };
list<A> lst1(a, a + 5), lst2(b, b + 7);
lst1.sort();
cout << "1)"; Print(lst1.begin(), lst1.end()); //输出:1)1 2 2 3 4
lst1.remove(2); //删除所有和A(2)相等的元素
cout << "2)"; Print(lst1.begin(), lst1.end()); //输出:2)1 3 4
lst2.pop_front(); //删除第一个元素
cout << "3)"; Print(lst2.begin(), lst2.end()); //输出:3)30 20 30 30 40 40
lst2.unique(); //删除所有和前一个元素相等的元素
cout << "4)"; Print(lst2.begin(), lst2.end()); //输出:4)30 20 30 40
lst2.sort();
lst1.merge(lst2); //合并 lst2 到 lst1 并清空 lst2
cout << "5)"; Print(lst1.begin(), lst1.end()); //输出:5)1 3 4 20 30 30 40
cout << "6)"; Print(lst2.begin(), lst2.end()); //lst2是空的,输出:6)
lst1.reverse(); //将 lst1 前后颠倒
cout << "7)"; Print(lst1.begin(), lst1.end()); //输出 7)40 30 30 20 4 3 1
lst2.insert(lst2.begin(), a + 1, a + 4); //在 lst2 中插入 3,2,4 三个元素
list <A>::iterator p1, p2, p3;
p1 = find(lst1.begin(), lst1.end(), 30);
p2 = find(lst2.begin(), lst2.end(), 2);
p3 = find(lst2.begin(), lst2.end(), 4);
lst1.splice(p1, lst2, p2, p3); //将[p2, p3)插入p1之前,并从 lst2 中删除[p2,p3)
cout << "8)"; Print(lst1.begin(), lst1.end()); //输出:8)40 2 30 30 20 4 3 1
cout << "9)"; Print(lst2.begin(), lst2.end()); //输出:9)3 4
return 0;
}
【实例】用 list 解决约瑟夫问题。
约瑟夫问题是:有 n 只猴子,按顺时针方向围成一圈选大王(编号为 1~n),从第 1 号开始报数,一直数到 m,数到 m 的猴子退到圈外,剩下的猴子再接着从 1 开始报数。就这样,直到圈内只剩下一只猴子时,这个猴子就是猴王。编程求输入 n、m 后,输出最后猴王的编号。
输入数据:每行是用空格分开的两个整数,第一个是 n,第二个是 m(0<m, n<=1 000 000)。最后一行是:
0 0
输出要求:对于每行输入数据(最后一行除外),输出数据也是一行,即最后猴王的编号。
输入样例:
6 2
12 4
8 3
0 0
输出样例:
5
1
7
#include <list>
#include <iostream>
using namespace std;
int main()
{
list<int> monkeys;
int n, m;
while (true) {
cin >> n >> m;
if (n == 0 && m == 0)
break;
monkeys.clear(); //清空list容器
for (int i = 1; i <= n; ++i) //将猴子的编号放入list
monkeys.push_back(i);
list<int>::iterator it = monkeys.begin();
while (monkeys.size() > 1) { //只要还有不止一只猴子,就要找一只猴子让其出列
for (int i = 1; i < m; ++i) { //报数
++it;
if (it == monkeys.end())
it = monkeys.begin();
}
it = monkeys.erase(it); //删除元素后,迭代器失效,
//要重新让迭代器指向被删元素的后面
if (it == monkeys.end())
it = monkeys.begin();
}
cout << monkeys.front() << endl; //front返回第一个元素的引用
}
return 0;
}
下面的程序演示了 pair 和 make_pair 的用法。
#include <iostream>
using namespace std;
int main()
{
pair<int,double> p1;
cout << p1.first << "," << p1.second << endl; //输出 0,0
pair<string,int> p2("this",20);
cout << p2.first << "," << p2.second << endl; //输出 this,20
pair<int,int> p3(pair<char,char>('a','b'));
cout << p3.first << "," << p3.second << endl; //输出 97,98
pair<int,string> p4 = make_pair(200,"hello");
cout << p4.first << "," << p4.second << endl; //输出 200,hello
return 0;
}
multiset 是关联容器的一种,是排序好的集合(元素已经进行了排序),并且允许有相同的元素。
set 是关联容器的一种,是排序好的集合(元素已经进行了排序)。set 和 multiset 类似,它和 multiset 的差别在于 set 中不能有重复的元素。multiset 的成员函数 set 中也都有。(去重)
#include <iostream>
#include <set> //使用set须包含此文件
using namespace std;
int main()
{
typedef set<int>::iterator IT;
int a[5] = { 3,4,6,1,2 };
set<int> st(a,a+5); // st里是 1 2 3 4 6
pair< IT,bool> result;
result = st.insert(5); // st变成 1 2 3 4 5 6
if(result.second) //插入成功则输出被插入元素
cout << * result.first << " inserted" << endl; //输出: 5 inserted
if(st.insert(5).second)
cout << * result.first << endl;
else
cout << * result.first << " already exists" << endl;
//输出 5 already exists
pair<IT,IT> bounds = st.equal_range(4);
cout << * bounds.first << "," << * bounds.second ; //输出:4,5
return 0;
}
multimap 是关联容器的一种,multimap 的每个元素都分为关键字和值两部分,容器中的元素是按关键字排序的,并且允许有多个元素的关键字相同。
map 是关联容器的一种,map 的每个元素都分为关键字和值两部分,容器中的元素是按关键字排序的,并且不允许有多个元素的关键字相同。
#include <iostream>
#include <map> //使用map需要包含此头文件
using namespace std;
template <class T1,class T2>
ostream & operator <<(ostream & o,const pair<T1,T2> & p)
{ //将pair对象输出为 (first,second)形式
o << "(" << p.first << "," << p.second << ")";
return o;
}
template<class T>
void Print(T first,T last)
{//打印区间[first,last)
for( ; first != last; ++ first)
cout << * first << " ";
cout << endl;
}
typedef map<int,double,greater<int> > MYMAP; //此容器关键字是整型,元素按关键字从大到小排序
int main()
{
MYMAP mp;
mp.insert(MYMAP::value_type(15,2.7));
pair<MYMAP::iterator,bool> p = mp.insert(make_pair(15,99.3));
if(!p.second)
cout << * (p.first) << " already exists" << endl; //会输出
cout << "1) " << mp.count(15) << endl; //输出 1) 1
mp.insert(make_pair(20,9.3));
cout << "2) " << mp[40] << endl;//如果没有关键字为40的元素,则插入一个
cout << "3) ";Print(mp.begin(),mp.end());//输出:3) (40,0)(20,9.3)(15,2.7)
mp[15] = 6.28; //把关键字为15的元素值改成6.28
mp[17] = 3.14; //插入关键字为17的元素,并将其值设为3.14
cout << "4) ";Print(mp.begin(),mp.end());
return 0;
}
STL 中的容器适配器
STL 中的容器适配器有 stack、queue、priority_queue 三种。它们都是在顺序容器的基础上实现的,屏蔽了顺序容器的一部分功能,突出或增加了另外一些功能。
容器适配器都有以下三个成员函数:
push:添加一个元素。
top:返回顶部(对 stack 而言)或队头(对 queue、priority_queue 而言)的元素的引用。
pop:删除一个元素。
容器适配器是没有迭代器的,因此 STL 中的各种排序、查找、变序等算法都不适用于容器适配器。
stack
例题:编写程序,输入一个十进制数 n 和进制 k(k≤10),输出 n 对应的 k 进制数。
#include <iostream>
#include <stack> //使用stack需要包含此头文件
using namespace std;
int main()
{
int n, k;
stack <int> stk;
cin >> n >> k; //将n转换为k进制数
if (n == 0) {
cout << 0;
return 0;
}
while (n) {
stk.push(n%k);
n /= k;
}
while (!stk.empty()) {
cout << stk.top();
stk.pop();
}
return 0;
}
queue
queue 就是“队列”。队列是先进先出的,和排队类似。队头的访问和删除操作只能在队头进行,添加操作只能在队尾进行。不能访问队列中间的元素。
priority_queue
priority_queue 是“优先队列”。它和普通队列的区别在于,优先队列的队头元素总是最大的——即执行 pop 操作时,删除的总是最大的元素;执行 top 操作时,返回的是最大元素的引用。
#include <queue>
#include <iostream>
using namespace std;
int main()
{
priority_queue<double> pq1;
pq1.push(3.2); pq1.push(9.8); pq1.push(9.8); pq1.push(5.4);
while(!pq1.empty()) {
cout << pq1.top() << " ";
pq1.pop();
} //上面输出 9.8 9.8 5.4 3.2
cout << endl;
priority_queue<double,vector<double>,greater<double> > pq2;
pq2.push(3.2); pq2.push(9.8); pq2.push(9.8); pq2.push(5.4);
while(!pq2.empty()) {
cout << pq2.top() << " ";
pq2.pop();
}
//上面输出 3.2 5.4 9.8 9.8
return 0;
}
min_element
min_element 返回区间中最小的元素。
作用:返回容器中最小值和最大值的指针。max_element(first,end,cmp);其中cmp为可选择参数!
#include<iostream>
#include<algorithm>
using namespace std;
bool cmp(int a,int b)
{
return a<b;
}
int main()
{
int num[]={2,3,1,6,4,5};
cout<<"最小值是 "<<*min_element(num,num+6)<<endl;
cout<<"最大值是 "<<*max_element(num,num+6)<<endl;
cout<<"最小值是 "<<*min_element(num,num+6,cmp)<<endl;
cout<<"最大值是 "<<*max_element(num,num+6,cmp)<<endl;
return 0;
}
string
- length 成员函数返回字符串的长度。
- append 成员函数返回对象自身的引用。(其实就是在一个字符串后面追加一个字符串)。
string s1("123"), s2("abc"); s1.append(s2); // s1 = "123abc" s1.append(s2, 1, 2); // s1 = "123abcbc" s1.append(3, 'K'); // s1 = "123abcbcKKK" s1.append("ABCDE", 2, 3); // s1 = "123abcbcKKKCDE",添加 "ABCDE" 的子串(2, 3)
- compare 成员函数,可用于比较字符串。
小于 0 表示当前的字符串小;
等于 0 表示两个字符串相等;
大于 0 表示另一个字符串小
string s1("hello"), s2("hello, world");
int n = s1.compare(s2);
n = s1.compare(1, 2, s2, 0, 3); //比较s1的子串 (1,2) 和s2的子串 (0,3)
n = s1.compare(0, 2, s2); // 比较s1的子串 (0,2) 和 s2
n = s1.compare("Hello");
n = s1.compare(1, 2, "Hello"); //比较 s1 的子串(1,2)和"Hello”
n = s1.compare(1, 2, "Hello", 1, 2); //比较 s1 的子串(1,2)和 "Hello" 的子串(1,2)
- substr 成员函数可以用于求子串 (n, m) (字符串截取函数)
- swap 成员函数可以交换两个 string 对象的内容。
- replace 成员函数可以对 string 对象中的子串进行替换,返回值为对象自身的引用。例如:
string s1("Real Steel");
s1.replace(1, 3, "123456", 2, 4); //用 "123456" 的子串(2,4) 替换 s1 的子串(1,3)
cout << s1 << endl; //输出 R3456 Steel
string s2("Harry Potter");
s2.replace(2, 3, 5, '0'); //用 5 个 '0' 替换子串(2,3)
cout << s2 << endl; //输出 HaOOOOO Potter
int n = s2.find("OOOOO"); //查找子串 "00000" 的位置,n=2
s2.replace(n, 5, "XXX"); //将子串(n,5)替换为"XXX"
cout << s2 < < endl; //输出 HaXXX Potter
- erase 成员函数可以删除 string 对象中的子串
- insert 成员函数可以在 string 对象中插入另一个字符
string s1("Limitless"), s2("00");
s1.insert(2, "123"); //在下标 2 处插入字符串"123",s1 = "Li123mitless"
s1.insert(3, s2); //在下标 2 处插入 s2 , s1 = "Li10023mitless"
s1.insert(3, 5, 'X'); //在下标 3 处插入 5 个 'X',s1 = "Li1XXXXX0023mitless"
bitset
#include <iostream>
#include <bitset>
#include <string>
using namespace std;
int main()
{
bitset<7> bst1;
bitset<7> bst2;
cout << "1) " << bst1 << endl; //输出 1) 0000000
bst1.set(0,1);//将第0位变成1,bst1变为 0000001
cout << "2) " << bst1 << endl; //输出 2) 0000001
bst1 <<= 4; //左移4位,变为 0010000
cout << "3) " << bst1 << endl; //输出 3) 0010000
bst2.set(2);//第二位设置为1,bst2变成 0000100
bst2 |=bst1; // bst2变成 0010100
cout << "4) " << bst2 << endl; //输出 4) 0010100
cout << "5) " << bst2.to_ulong () << endl; //输出 5) 20
bst2.flip(); //每一位都取反,bst2变成 1101011
bst1.set(3); //bst1变成 0011000
bst2.flip(6); //bst2变成 0101011
bitset<7> bst3 = bst2^ bst1;//bst3 变成 0110011
cout << "6) " << bst3 << endl; //输出 6) 0110011
cout << "7) " << bst3[3] << "," << bst3[4] << endl; //输出 7) 0,1
return 0;
}