一.stack容器

1.stack理解

概念： stack是一种先进后出的数据结构，它只有一个出口。

它在C++中也叫栈，类似于我们在《数据结构和算法》里面的栈，只不过在C++中把其封装成库，我们可以直接使用。

注意：栈中只有顶端的元素才可以被外界使用，因此栈不允许有遍历行为。

2.stack常用接口

构造函数：

stack<T> stk;                               //stack采用模板类实现，stack对象的默认构造
stack(const stack &stk);                    //拷贝构造函数

赋值操作：

stack& operator=(const stack &stk);             //重载=，类似于拷贝构造

数据存取：

push(elem);                                 //向栈顶添加元素
pop();                                      //从栈顶移除一个元素
top();                                      //返回栈顶元素

大小操作：

empty();                                                  //判断堆栈是否为空
size();                                                   //返回栈的大小

二.queue容器

1.queue理解

概念： Queue是一种先进先出的数据结构，它有两个端口，一个用来进入数据，一个用来拿出数据。

它在C++中也叫队列，类似于我们在《数据结构和算法》里面的队列，只不过在C++中把其封装成库，我们可以直接使用。

• 队列容器允许从一端新增元素，从另一端移除元素。
• 队列中只有队头和队尾才可以被外界使用，因此队列不允许有遍历行为

2.queue常用接口

构造函数：

queue<T> que;                             //queue采用模板类实现，默认构造形式
que(const queue &que);                    //拷贝构造函数

赋值操作：

queue& operator=(const queue &que);                 //重载等号操作符

数据存取：

push(elem);                           //往队尾添加元素
pop();                                //从对头移除第一个元素
back();                               //返回最后一个元素
front();                              //返回第一个元素

大小操作：

empty();                     //判断队列是否为空
size();                      //返回栈的大小

三.list容器

1.list理解

功能：将数据进行链式存储

链表(list)是一种物理存储单元上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的

链表的组成：链表由一系列结点组成

结点的组成：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

在《数据结构与算法》中，我们说的链表一般是单向不循环链表，而STL中的链表是双向循环链表。

由于链表的存储方式并不是连续的内存空间，因此链表list中的迭代器只支持前移和后移，属于双向迭代器。

list的优点：

• 采用动态存储分配，不会造成内存浪费和溢出
• 链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素

list的缺点:

• 链表灵活，但是空间(指针域)和 时间 (遍历)额外耗费较大
• list有一个重要的性质，插入操作和删除操作都不会造成原有list迭代器的失效，这在vector是不成立的.

总结: STL中list和vector是两个最常被使用的容器，各有优缺点。

所以无论如何，务必掌握好这两个容器。

2.list构造函数

list<T> lst;                          //list采用模板类实现，默认构造
list(beg,end);                        //区间拷贝，将[beg,end)区间中的元素拷贝给当前对象
list(n,elem);                         //构造函数将n个elem拷贝给本身
list(const list &lst);                //拷贝构造

list容器与其他的STL容器构造方式几乎没什么区别。

3.list赋值和交换

assign(beg,end);                               //将[beg，end)区间的数据拷贝赋值给当前对象
assign(n,elem);                                //将n个elem拷贝赋值给本身
list& operator=(const list &lst);              //重载=，拷贝赋值
swap(lst);                                     //将lst与当前对象的元素交换

其实一般在构造时就完成了赋值操作，而这里的赋值更多的是采用默认构造后追加赋值。

注意：

• vector和list中的swap()都是类模板的成员函数，而不需要算法库
• vector中的swap()常用来收缩空间

4.list大小操作

size();                            //返回容器中元素的个数
empty();                           //判断容器是否为空
resize(num);                       //重新指定容器的长度为num，若容器变成，则以默认值填充新位置
                                   //若容器变短，则末尾超出容器长度被删除
resize(num,elem);                  //重新指定容器的长度为num，若容器变成，则以elem填充新位置
                                   //如果容器变短，则末尾超出容器长度的元素被删除

5.list插入和删除

push_back(elem);              //在容器尾部添加一个数据
push_front(elem);             //在容器头部插入一个数据
pop_back();                   //删除容器的最后一个数据
pop_front();                  //删除容器的第一个数据

insert(pos,elem);              //在pos位置插入一个elem元素的拷贝，返回新数据的位置
insert(pos,n,elem);            //在pos位置下插入n个elem数据，无返回值
insert(pos,beg,end);           //在pos位置插入[beg,end)区间的数据，无返回值
clear();                       //情况容器的所有数据
erase(beg,end);                //删除[beg,end)区间的数据，无返回值
erase(pos);                    //删除pos位置的数据，返回下一个数据的位置
remove(elem);                  //删除容器中所有与elem值匹配的元素

可以看到这些STL的容器，封装的成员函数完成相似功能用的都是同一个函数名，这样有助于我们使用。

注意的是：知名位置进行插入和删除时，不能使用下标，而是用迭代器指明哪个位置。

6.list数据存取

front();                                          //返回第一个元素
back();                                           //返回最后一个元素

STL中的链表和《数据结构与算法》中的链表一样，不支持随机存取，所以这里没有重载[]和at()的成员函数来进行访问。

7.链表反转和排序

reverse();                                             //反转链表
sort();                                                //链表排序

注意：

• 我们之前deque的排序算法sort(beg,end)是全局函数，需要包含算法的头文件；而这里的sort()是成员函数
• 链表的迭代器是双向迭代器，不是随机访问迭代器；所有不支持随机访问迭代器的容器，都不可以用标准算法
• 对于不支持随机访问迭代器的容器模板类，内部往往会提供一些对应的成员方法

8.排序案例练习

案例描述：将Person自定义数据类型进行排序，Person中属性有姓名、年龄、身高
排序规则：按照年龄进行升序，如果年龄相同按照身高进行降序

#include <iostream>
#include <string>
#include <list>
using namespace std;

//选手类
class Person 
{
public:
    Person(string name, int age,int heigh)
    {
        this->m_name = name;
        this->m_age = age;
        this->m_heigh = heigh;
    }
    string m_name;
    int m_age;
    int m_heigh;
};

//指定比赛规则
bool compare(Person& p1, Person& p2)
{
    if (p1.m_age == p2.m_age)
        return p1.m_heigh < p2.m_heigh;
    return p1.m_age < p2.m_age;
}

void test01()
{
    list<Person> lst;
    Person p1("小明", 20, 180);
    Person p2("小红", 18, 170);
    Person p3("小绿", 30, 185);
    Person p4("小蓝", 28, 180);
    Person p5("小紫", 20, 175);

    lst.push_back(p1);
    lst.push_back(p2);
    lst.push_back(p3);
    lst.push_back(p4);
    lst.push_back(p5);

    lst.sort(compare);
    for (list<Person>::iterator it = lst.begin(); it != lst.end(); it++)
    {
        cout << "姓名：" << it->m_name << "  年龄：" << it->m_age << "  身高：" << it->m_heigh << endl;
    }
}


int main()
{
    test01();
    return 0;
}

四.set/multiset容器

1.set/multiset理解

翻译过来的意思是集合，所有元素都会在插入时自动被排序。

所以set/multiset的属于关联式容器（在进入时自动排序），底层结构是由二叉树实现的。

set与multiset的区别：

• set不允许容器中有重复的元素
• multiset允许容器中有重复的元素

它两的头文件都是<set>，只是在用法上区分。

2.构造与赋值

构造：

set<T> st;                      //默认构造函数
set(const set &st);             //拷贝构造函数

赋值：

set& operator=(const set &st);           //重载=

学过《数据结构与算法》，应该知道集合并不是一种线性结构，所以它不可能有区间构造，且set不允许重复元素，那么也不可能用n个同一元素赋值。

集合没有端口，所以不可能还有push和pop的操作。

3.大小和交换

size();            //返回容器中元素的数目
empty();           //交换容器是否为空
swap(st);          //交换两个集合容器

集合不存在resize()重新设定大小。

4.插入和删除

insert(elem);                   //在容器中插入元素
clear();                        //清除所有元素
erase(pos);                     //删除pos迭代器所指的元素，返回下一个元素的迭代器
erase(beg,end);                 //删除区间[beg，end)的所有元素，返回下一个元素的迭代器
erase(elem);                    //删除容器中值为elem的元素

集合没有push和pop，只有insert一种插入方式，另外它可以提供值删除。

注意：删除时集合的顺序是排序后的结果而不是插入的顺序。

5.查找和统计

find(key);                         //查找key是否存在，若存在返回该元素的迭代器；若不存在，返回set.end()
count(key);                        //统计key的元素个数

count()对于set容器的统计，结果要么是0要么是1。

6.set/multiset区别

区别：

• set不可以插入重复数据，而multiset可以
• set插入数据的同时会返回插入结果，表示插入是否成功
• multiset不会检测数据，因此可以插入重复数据

这部分主要从底层原理剖析了set的insert的返回值，它的返回值是一个pair对组，第一个参数是迭代器，第二个参数是bool类型，我们可以根据bool数据判断是否插入成功。而multiset的insert函数返回的是迭代器，并不做出判断。可以转到set/multiset的insert函数定义处查看返回值类型。

7.pair对组

两种创建方式：

pair<type,type> p (value1,value2);                //类似于对组的默认构造
pair<type,type> p = make_pair(value1,value2);     //类似于对组的构造成员函数

此外，要访问pair对组的两个元素，需要使用first和second的成员函数。

8.set容器排序

set容器默认从小到大排序，但可以利用仿函数改变排序规则。

class Mycampare
{
	bool operator()(int v1,int v2)
    {
        return v1>v2;
    }
};

经过这么多的指定排序，我们也了解到指定排序顺序有两种方式，一种是之前的全局函数，二就是现在的自定义类的重载()的仿函数，二者都是返回bool类型的值。

对于自定义的数据类型，必须自定义排序规则，才能正确插入。

五.map/multimap容器

1.map/multimap理解

map中所有元素都是pair

• pair中第一个元素为key (键值)，起到索引作用，第二个元素为value (实值)
• 所有元素都会根据元素的键值自动排序

本质：

• map/multimap属于关联式容器，底层结构是用二叉树实现。

优点：

• 可以根据key值快速找到value值

map和multimap区别:

• map不允许容器中有重复key值元素
• multimap允许容器中有重复key值元素

2.构造和赋值

构造：

map<T1,T2> mp;                                 //默认构造函数
map(const map& mp);                            //拷贝构造函数

赋值：

map& operator=(const map& mp);                 //重载=

3.大小和交换

size();            //返回容器中元素的数目
empty();           //交换容器是否为空
swap(mp);          //交换两个集合容器

4.插入和删除

insert(elem);                   //在容器中插入元素
clear();                        //清除所有元素
erase(pos);                     //删除pos迭代器所指的元素，返回下一个元素的迭代器
erase(beg,end);                 //删除区间[beg，end)的所有元素，返回下一个元素的迭代器
erase(key);                    //删除容器中值为key的元素

我们知道map数组的元素是一个对组，所以插入时由于创建对组方式的多样性，这里的插入方式也有多样性。

m.insert(pair<int,int>(1,10));                    //第一种
m.insert(make_pair(2,20));                        //第二种
m.insert(map<int,int>::value_type(3,30));         //第三种
m[4]=40;                                          //第四种，但不建议

之所以不建议第四种，虽然map对[]进行了重载，但是[]在map里更多的是通过key来访问value，而不是进行插入。

5.查找和统计

find(key);                                 //查找key是否存在，若存在返回该元素的迭代器；若不存在，返回set.end()
count(key);                                //统计key的元素个数

map不允许重复插入，对于统计count()来说其结果要么是1要么是0。

6.排序

这么多的仿函数排序，应该也会了。

六.案例练习

1.案例要求

• 公司今天招聘了10个员工 (ABCDEFGHIJ)，10名员工进入公司之后
• 需要指派员工在哪个部门工作
• 员工信息有：姓名 工资组成;部门分为: 策划、美术、研发
• 随机给10名员工分配部门和工资
• 通过multimap进行信息的插入 key(部门编号)value(员工)
• 分部门显示员工信息

2.实现步骤

• 创建10名员工，放到vector容器中
• 便利vector容器，取出每个员工，进行随机分组
• 分组后，将员工部门编号作为key，具体员工为value，放到multimap容器中
• 分部门显示员工信息

3.案例代码

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <ctime>
using namespace std;

/*
    部门编号：
    1：策划；
    2：美术；
    3：研发。
*/

//员工类
class Worker 
{
public:
    Worker(string name, int salary)
    {
        this->m_name = name;
        this->m_salary = salary;
    }
    string m_name;
    int m_salary;

};

void creatworker(vector<Worker>& v)
{
    string namestd = "ABCDEFGHJK";
    for (int i = 0; i < 10; i++)
    {
        string name = "员工";
        name += namestd[i];
        Worker worker(name, rand()%10000+10000);
        v.push_back(worker);
    }
}

void setworker(vector<Worker>& v, multimap<int, Worker>& w)
{
    for (vector<Worker>::iterator it = v.begin(); it != v.end(); it++)
    {
        int depid = rand() % 3+1;
        w.insert(make_pair(depid, *it));
    }
}

void showbg(multimap<int, Worker>& w)
{
    cout << "策划部门的信息如下：" << endl;
    multimap<int, Worker>::iterator pos = w.find(1);
    int count1 = w.count(1);
    for (int index = 0; index< count1; index++,pos++)
    {
        cout << "姓名：" << pos->second.m_name << "    工资：" << pos->second.m_salary << endl;
    }

    cout << "------------------" << endl;
    cout << "美术部门的信息如下：" << endl;
    pos = w.find(2);
    int count2 = w.count(2);
    for (int index = 0; index < count2; index++, pos++)
    {
        cout << "姓名：" << pos->second.m_name << "    工资：" << pos->second.m_salary << endl;
    }

    cout << "------------------" << endl;
    cout << "研发部门的信息如下：" << endl;
    pos = w.find(3);
    int count3 = w.count(3);
    for (int index = 0; index < count3; index++, pos++)
    {
        cout << "姓名：" << pos->second.m_name << "    工资：" << pos->second.m_salary << endl;
    }
}

void test01()
{
    srand((unsigned int)time(NULL));
    //1.创建员工
    vector<Worker> v;
    creatworker(v);

    //2.进行分组
    multimap<int,Worker> mw;
    setworker(v, mw);

    //3.分组显示员工
    showbg(mw);
}


int main()
{
    test01();
    return 0;
}