C++标准模板库

STL包含了容器类（container）、迭代器（iterator）和算法（algorithm）三个部分

• 容器（Container） － 某类对象的集合
• 迭代器（Iterator） － 在对象集合上进行遍历
• 算法（Algorithm） － 处理集合内的元素

容器是用于存储某种给定类型对象的模板类型。容器分类如下

1. 顺序容器（Sequence containers）
   在顺序容器中，所有元素根据它的位置排列和访问。
   每个元素都有固定位置，元素的位置取决于插入时机和地点，和元素值无关。vector、deque、list
2. 关联容器（Associated containers）
   每个元素都没有固定位置，元素位置取决于容器自己特定的排序规则，与键值有关，与插入顺序无关。根据键来访问元素。set、multiset、map、multimap
3. 其它容器 Hash_set, hash_map, bitset，stack, queue等等

标准库容器类

标准库容器类	说明
顺序容器
vector（矢量）	从容器尾部快速插入与删除，可随机直接访问任何元素
deque（双端队列）	从容器头部或尾部快速插入与删除，直接访问任何元素
list（链表）	从任何地方快速插入与删除，双向链表
关联容器
set（集合）	快速查找，不允许重复值
multiset（多重集合）	快速查找，允许重复值
map（映射）	一对一映射，基于关键字快速查找，不允许重复值
multimap（多重映射）	一对多映射，基于关键字快速查找，允许重复值
其它容器
stack（栈）	后进先出（LIFO）
queue（队列）	先进先出（FIFO）
priority_queue（优先级队列）	最高优先级元素总是第一个出列

标准容器库的头文件

头文件	说明
<deque>	两端队列deque的头文件
<list>	表list的头文件
<map>	映射map和多重映射multimap的头文件
<set>	集合set和多重集合multimap的头文件
<queue>	队queue和优先级队列priority_queue的头文件
<stack>	栈stack的头文件
<vector>	向量vector的头文件

知识要点

1. 所有容器都提供有效的动态内存管理。用户在添加元素时，不必担心元素存储在哪里，删除元素时，也不必担心元素的释放。
2. 要用作容器的元素类型，必须满足以下两个条件：
   （1）元素类型必须支持赋值运算
   （2）元素类型的对象必须可以复制
   引用不支持赋值，所以没有元素是引用类型的容器。
   IO库类型不支持复制或者赋值，不能创建存放IO类型对象的容器。
3. 容器如果是存储类类型的元素，最好这个类定义默认的构造函数。

迭代器

迭代器是一种检查容器内元素并遍历元素的数据类型。
迭代器操作提供了比下标操作更通用化的方法访问元素。
迭代器指向容器中的一个特定位置。

标准库为每一种容器定义了一种迭代器类型。

vector<int>::iterator iter;

不同容器上支持的迭代器功能强弱有所不同。
容器的迭代器的功能强弱，决定了该容器是否支持STL中的某种算法。

begin和end操作

每一种容器都定义了一对名为 begin () 和 end () 的操作，用来返回迭代器。

如果容器中有元素，则 begin () 返回的迭代器指向第一个元素。
end () 返回的迭代器指向容器 “末端元素的下一个”，即超出末端迭代器。这个元素是一个不存在的元素。起一个标识提醒的作用，表示已经处理完容器内的所有元素。

Picture1.png

迭代器的基本操作

类似普通指针的操作

操作	效果
*	返回当前位置上的元素值。如果该元素有成员，可以通过迭代器以 ->取用
++	将迭代器前进至下一元素
== 和 !=	判断两个迭代器是否指向同一位置
=	为迭代器赋值（将所指元素的位置赋值给迭代器）

vector类的常用操作

// 1. 获取元素的操作：
front()        // 返回第一个元素
back()         // 返回最末一个元素
at(i)          // 返回第i个元素
[i]            // 返回第i个元素

// 2. 迭代器的操作：
begin()     // 返回指向第一个元素的迭代器
end()       // 返回超出末端迭代器
rbegin()    // 返回逆序迭代器，指向最后一个元素
rend()      // 返回逆序迭代器，指向第一个元素前面的位置

// 3. 容器容量的操作：
size()      // 返回vector元素数量的大小
capacity()  // 返回容器需要分配更多存储空间之前所能存储的元素总数
max_size()  // 返回vector所能容纳元素的最大数量（上限）
reserve( size_t size )  // 设定预留size个元素的存储空间
empty()     // 判断vector是否为空（返回true时为空）

// 4. 对vector的元素进行修改的操作：
pop_back()      // 移除最后一个元素
push_back(x)        // 在vector最后添加一个元素x
clear()             // 清空所有元素
erase(begin，end)    // 删除迭代器begin和end所辖范围内的元素，左闭右开，范围是 [begin, end) 也就是说 end 部分的元素不会被删除
erase(i)            // 删除迭代器i所指向的元素，返回 i 的下一个元素，同时使得 itr 指向下一个
insert(i，x)         // 把x插入vector中由迭代器i所指明的位置
insert(i，begin，end)     // 把迭代器begin和end所辖范围内的元素插入到vector中由迭代器所指明的位置
insert(i，n，x)         // 把x的n个副本插入向量中由迭代器i所指明的位置
assign(begin, end)  // 用迭代器begin和end所辖范围内的元素替换vector元素，复制操作， v1会被整个替换掉，如果v1不够，则扩容来装
assign(num, val)    // 用val的num个副本替换vector元素，同上面，也是复制

删除具有某值得所有元素例子

#include <iostream>
#include <vector>


using namespace std;

int main()
{
    vector<int> v1;

    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(3);
    v1.push_back(4);

    vector<int>::iterator itr;

    for(itr = v1.begin(); itr != v1.end(); )
    {
        if(*itr == 3) 
            v1.erase(itr);
        else 
            ++itr;
    
    }

    for(itr = v1.begin(); itr != v1.end(); ++itr)
    {
        cout << *itr << endl;
    }
}

输出

1
2
4

插入例子

#include <iostream>
#include <vector>


using namespace std;

int main()
{
    vector<int> v1;
    vector<int> v2;

    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    v1.push_back(5);

    v2.push_back(6);
    v2.push_back(7);
    v2.push_back(8);
    v2.push_back(9);
    v2.push_back(10);

    // 指向第三个
    vector<int>::iterator itr = v1.begin() + 2;
    // 删除第三个
    v1.erase(itr);

    // 插入一整段
    v1.insert(itr, v2.begin(), v2.end());
    
    for(itr = v1.begin(); itr != v1.end(); ++itr)
    {
        cout << *itr << endl;
    }

}

输出

1
2
6
7
8
9
10
4
5

deque

双端队列类模板deque类似vector。
区别是支持高效地在头部插入和删除元素。

图例

pop_back()      // 移除最后一个元素
pop_front()     // 移除第一个元素
push_back(x)    // 在deque最后添加一个元素x
push_front(x)   // 在deque最前面添加一个元素x

list

双向链表容器

list 图例
不支持随机访问，访问某个元素要求遍历所涉及的其他元素。
任意位置插入和删除元素所花费的时间是固定的，与位置无关，效率高。

顺序容器选择的规则

1. 如果要求随机访问元素，则使用vector和deque。
2. 如果必须在容器的中间位置插入或删除元素，则使用list。
3. 如果不是在中间位置，而是在容器的首部或者尾部插入删除，则使用deque。
4. 如果即需要随机访问，又要在中间位置插入或删除，则选择哪种容器要取决于下面两种操作付出的相对代价：
   （1）随机访问list元素的代价。
   （2）在vector或deque中插入或删除元素时复制元素的代价。
   实际程序中更多的使用是访问还是插入删除，来决定相对代价小的容器。

用一个顺序表复制构造另一个顺序表例子

只要是顺序表，则可以用其中复制出另一个，而且不限定限定于线性表类型。比如 list 可以用来复制出 deque 来。

#include <iostream>
#include <vector>
#include <list>
#include <deque>

using namespace std;

int main()
{
    list<int> l; 
    l.push_back(1);
    l.push_back(2);
    l.push_back(4);
    l.push_back(7);
    l.push_back(9);
    l.push_back(10);

    // 用 list 初始化 d
    deque<int> d1(l.begin(), l.end());

    deque<int>::iterator itr;

    for(itr = d1.begin(); itr != d1.end(); ++itr)
    {
        cout << *itr << endl;
    }

}

输出

1
2
4
7
9
10

问题总结

• STL的三个基本组件是什么？
  容器、迭代器、算法

• 引用类型是否可以作为容器元素的类型？
  不可以，因为引用类型不支持复制操作。

• vector 的 capacity 操作与 size 操作的区别是什么？
  capacity 是 vector 的容量，即预留空间，当插入时超过预留空间，则 vector 重新分配 2 倍于当期 capacity 空间的内存，并把数据复制进新的空间，同时释放旧的空间。
  size () 操作这是返回当前 vector 中元素的个数。

• 容器的end()操作返回什么？
  返回容器最后一个元素的下一个元素，代表空元素，不含具体值。

• vector容器的元素在内存中是顺序存储的吗？
  是，是动态数组。

关联容器

关联容器和顺序容器的本质区别：
关联容器通过 键 (key) 访问元素。
顺序容器通过元素在容器中位置存储和访问元素。

• set: 仅包含一个键。

• map: 元素以键－值 (key-value) 对的形式组织
  key 用作元素在 map 中的索引
  value 则表示所存储和读取的数据。

  
  set 和 map

set

为二叉查找树，只能添加，不能修改，要修改只能先删除，在添加元素，因为添加时会动态保持平衡，直接修改的话会破会平衡。

#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include <set>
#include <string>

using namespace std;

class Stu
{
public:
    Stu(int id, string name)
    {
        this->id = id;
        this->name = name;
    }

    string getname() const 
    {
        return name;
    }

    int getId() const
    {
        return id;
    }
private:
    friend struct StuFunction;
    string name;
    int id;
};


struct StuFunction
{
    bool operator()(const Stu &s1, const Stu &s2)
    {
        return s1.id < s2.id;
    }
};

int main()
{
    set<Stu, StuFunction > s;

    s.insert(Stu(5, "AAA"));
    s.insert(Stu(2, "BBB"));
    s.insert(Stu(8, "CCC"));
    s.insert(Stu(1, "DDD"));

    set<Stu, StuFunction>::iterator itr = s.begin();
   
 
    for( ; itr != s.end(); ++itr)
        cout << (*itr).getId()  << " " << (*itr).getname() << endl;
    
}

关联容器map

1. map 的本质是元素的值与某个特定的键相关联，而并非通过元素在容器中的位置来获取。
2. map 类型的对象所包含的元素必须具有不同的键。
3. map 支持很多顺序容器也提供的操作，同时还提供管理或使用键的特殊操作。

字典是 map 的一个典型应用。
单词是 key，而这个单词的解释说明是 value。

#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include <set>
#include <string>
#include <map>

using namespace std;

int main()
{
    map<int, string> m;

    // map 的插入比较特殊，需要借助 pair，因为 map  是一对一对的
    m.insert(pair<int, string>(1, "AAA"));
    m.insert(pair<int, string>(2, "BBB"));
    m.insert(pair<int, string>(3, "CCC"));
    // 或者使用 make_pair 函数的方式,make_pair返回值就是 pair  
    m.insert(make_pair<int, string>(4, "DDD"));
    
    // insert 返回值是一个 pair 类型 pair<map<>::iterator, bool>
    // 通过 second 可以判断插入是否失败，这里 key = 4 重复，所以失败
    // 如果成功 first 会指向插入的那个的迭代器
    if(m.insert(pair<int, string>(4, "DDD")).second == true) 
        cout << "OK" << endl;
    else 
        cout << "False" << endl;

    pair<map<int, string>::iterator, bool> ret = m.insert(pair<int, string>(5, "EEE"));

    cout << "插入成功返回的pair中的迭代器的内容为：" << ret.first->first << " "
         << ret.first->second << endl;

    // 更简单的插入方式，但是这种插入方式是一种暴力插入，如果 已经有键值对则会进行修改，所以也就不用什么返回值提醒用户插入失败。
    m[6] = "FFF";
    map<int, string>::iterator itr = m.begin();

    

    for( ; itr != m.end(); ++itr)
    {
        cout << itr->first << " "
             << itr->second << endl;
    }

}

自定义对象作为 key 值?

#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include <set>
#include <string>
#include <map>

using namespace std;


class Stu {
public:
    Stu(int number, string name)
    {
        this->number = number;
        this->name = name;
    }

    string getName() const
    {
        return name;
    }

    int getNumber() const 
    { 
        return number;
    }
    friend struct StuCompair;
private:
    int number;
    string name;
};


// 函数对象
struct StuCompair
{   
    bool operator()(const Stu &s1, const Stu &s2)
    {
        return s1.number > s2.number;
    }

};


int main()
{
    map<Stu, string, StuCompair> m;

    m.insert(pair<Stu, string>(Stu(2, "AAA"), "good"));
    m.insert(pair<Stu, string>(Stu(2, "AAA"), "good"));
    m.insert(pair<Stu, string>(Stu(2, "AAA"), "good"));
    m.insert(pair<Stu, string>(Stu(2, "AAA"), "good"));
    m.insert(pair<Stu, string>(Stu(2, "AAA"), "good"));


    map<Stu, string, StuCompair>::iterator itr;


    for(itr = m.begin(); itr != m.end(); ++itr) {
        cout << itr->first.getNumber() << " "
             << itr->first.getName() << endl;
    }
}

课后作业

map 实现增删改查

#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include <set>
#include <string>
#include <map>

using namespace std;

int main()
{

    // 定义 map， 以 key 值降序插入
    map<int, string, less<int> > m;

    // 增
    m.insert(pair<int ,string>(2, "小明"));
    m.insert(pair<int ,string>(8, "小红"));
    m.insert(pair<int ,string>(6, "小王"));
    m.insert(pair<int ,string>(1, "王授"));
    m.insert(pair<int ,string>(3, "田晶"));
    m.insert(pair<int ,string>(9, "梦哥"));


    map<int, string>::iterator itr;
    
    for(itr = m.begin(); itr != m.end(); ++itr)
    {
        cout << itr->first << " "
             << itr->second << endl;
    }

    // 删
    m.erase(2);
    cout << "删" << endl;
    for(itr = m.begin(); itr != m.end(); ++itr)
    {
        cout << itr->first << " "
             << itr->second << endl;
    }

    // 改
    m[8] = "小李";
    cout << "改" << endl;
    for(itr = m.begin(); itr != m.end(); ++itr)
    {
        cout << itr->first << " "
             << itr->second << endl;
    }


    // 查
    cout << "查" << endl;
    cout << m[9] << endl;
    cout << m.find(9)->second << endl;

}

实现四则运算计算器