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;
}