C++：10.STL和常用容器

C++ STL

1. STL的诞生

• 长久以来，软件界一直希望建立一种可重复利用的东西

• C++的面向对象和泛型编程思想，目的就是复用性的提升

• 大多情况下，数据结构和算法都未能有一套标准,导致被迫从事大量重复工作

• 为了建立数据结构和算法的一套标准,诞生了STL

2. STL基本概念

• STL(Standard Template Library,标准模板库)
• STL 从广义上分为: 容器(container) 算法(algorithm) 迭代器(iterator)
• 容器和算法之间通过迭代器进行无缝连接。
• STL 几乎所有的代码都采用了模板类或者模板函数

3. STL六大组件

STL大体分为六大组件，分别是:容器、算法、迭代器、仿函数、适配器（配接器）、空间配置器

1. 容器：各种数据结构，如vector、list、deque、set、map等,用来存放数据。
2. 算法：各种常用的算法，如sort、find、copy、for_each等
3. 迭代器：扮演了容器与算法之间的胶合剂。
4. 仿函数：行为类似函数，可作为算法的某种策略。
5. 适配器：一种用来修饰容器或者仿函数或迭代器接口的东西。
6. 空间配置器：负责空间的配置与管理。

4. STL中容器、算法、迭代器

4.1 容器：置物之所也

STL容器就是将运用最广泛的一些数据结构实现出来

常用的数据结构：数组, 链表,树, 栈, 队列, 集合, 映射表 等

这些容器分为序列式容器和关联式容器两种:

• 序列式容器:强调值的排序，序列式容器中的每个元素均有固定的位置。
• 关联式容器:二叉树结构，各元素之间没有严格的物理上的顺序关系

4.2 算法：问题之解法也

有限的步骤，解决逻辑或数学上的问题，这一门学科我们叫做算法(Algorithms)

算法分为:质变算法和非质变算法。

• 质变算法：是指运算过程中会更改区间内的元素的内容。例如拷贝，替换，删除等等

• 非质变算法：是指运算过程中不会更改区间内的元素内容，例如查找、计数、遍历、寻找极值等等

4.3 迭代器：容器和算法之间粘合剂

提供一种方法，使之能够依序寻访某个容器所含的各个元素，而又无需暴露该容器的内部表示方式。

每个容器都有自己专属的迭代器

迭代器使用非常类似于指针，初学阶段我们可以先理解迭代器为指针

迭代器种类：

种类	功能	支持运算
输入迭代器	对数据的只读访问	只读，支持++、==、！=
输出迭代器	对数据的只写访问	只写，支持++
前向迭代器	读写操作，并能向前推进迭代器	读写，支持++、==、！=
双向迭代器	读写操作，并能向前和向后操作	读写，支持++、–，
随机访问迭代器	读写操作，可以以跳跃的方式访问任意数据，功能最强的迭代器	读写，支持++、–、[n]、-n、<、<=、>、>=

常用的容器中迭代器种类为双向迭代器，和随机访问迭代器

STL常用容器

string容器 – 字符串

vector容器 – 单端动态数组，随机访问迭代器

deque容器 – 双端动态数组，随机访问迭代器。内部有中控器，维护缓冲区地址，缓冲区里存放数据

stack容器 – 堆栈，先进后出，只有栈顶元素可被外界使用，无迭代器，不允许遍历

queue容器 – 队列，先进先出，只有队头队尾可被外界使用，无迭代器，不允许遍历

list容器 – 链表，由结点(数据域、指针域)组成。只支持前移和后移，双向迭代器

1 string容器

1.1 基础信息

本质：string是C++风格的字符串，而string本质上是一个类

string和char * 区别：

• char * 是一个指针
• string是一个类，类内部封装了char*，管理这个字符串，是一个char*型的容器。

特点：

• string 类内部封装了很多成员方法。例如：查找find，拷贝copy，删除delete 替换replace，插入insert

• string管理char*所分配的内存，不用担心复制越界和取值越界等，由类内部进行负责

1.2 string构造函数

构造函数原型：

• string(); //创建一个空的字符串，无参构造函数
• string(const char* s); //使用字符串s初始化，有参构造函数
• string(const string& str); //使用一个string对象初始化另一个string对象，拷贝构造函数
• string(int n, char c); //使用n个字符c初始化

#include <iostream>
#include <string>
using namespace std;
int main() {
    string s1; //创建空字符串，调用无参构造函数
    cout << "str1 = " << s1 << endl;

    //回顾下字符串基础，char*是在定义一个字符数组，里面可以存放多个字符，要用双引号
    //即等同于const char str[] = "hello world";
    const char str[] = "hello world";
    string s2(str); //把c风格的字符串char*转换成了string

    cout << "str2 = " << s2 << endl;

    string s3(s2); //调用拷贝构造函数
    cout << "str3 = " << s3 << endl;

    string s4(10, 'a');
    cout << "str4 = " << s4 << endl;

    return 0;
}

str1 =
str2 = hello world
str3 = hello world
str4 = aaaaaaaaaa

总结：string的多种构造方式没有可比性，灵活使用即可

1.3 string赋值操作

功能描述：

• 给string字符串进行赋值

赋值的函数原型：

• string& operator=(const char* s); //char*类型字符串 赋值给当前的字符串
• string& operator=(const string &s); //把字符串s赋给当前的字符串
• string& operator=(char c); //字符赋值给当前的字符串
• string& assign(const char *s); //把字符串s赋给当前的字符串
• string& assign(const char *s, int n); //把字符串s的前n个字符赋给当前的字符串
• string& assign(const string &s); //把字符串s赋给当前字符串
• string& assign(int n, char c); //用n个字符c赋给当前字符串

常用的还是第一种等号的重载，即operator=

string s1 = "hello world!";

1.4 string字符串拼接

功能描述：

• 实现在字符串末尾拼接字符串

函数原型：

• string& operator+=(const char* str); //重载+=操作符
• string& operator+=(const char c); //重载+=操作符
• string& operator+=(const string& str); //重载+=操作符
• string& append(const char *s); //把字符串s连接到当前字符串结尾
• string& append(const char *s, int n); //把字符串s的前n个字符连接到当前字符串结尾
• string& append(const string &s); //同operator+=(const string& str)
• string& append(const string &s, int pos, int n); //字符串s中从pos开始的n个字符连接到字符串结尾

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

int main() {
    string str1 = "我";

    str1 += "爱玩游戏";
    cout << "str1 = " << str1 << endl;

    str1 += ':';
    cout << "str1 = " << str1 << endl;

    string str2 = "LOL DNF";
    str1 += str2;
    cout << "str1 = " << str1 << endl;

    string str3 = "I";
    str3.append(" love ");
    str3.append("game abcde", 4);
    //str3.append(str2);
    str3.append(str2, 3, 4); // 从下标3位置开始 ，截取4个字符，拼接到字符串末尾
    cout << "str3 = " << str3 << endl;

    return 0;
}

str1 = 我爱玩游戏
str1 = 我爱玩游戏:
str1 = 我爱玩游戏:LOL DNF
str3 = I love game DNF

一般用+=就很直观，append()适用于把字符串作为参数传入的场景，比如循环

1.5 string查找和替换

功能描述：

• 查找：查找指定字符串是否存在，找到返回位置，找不到返回-1

  第一次出现的位置：find

  • int find(const string& str, int pos = 0) const; //查找str第一次出现位置,从pos开始查找
  • int find(const char* s, int pos = 0) const; //查找s第一次出现位置,从pos开始查找
  • int find(const char* s, int pos, int n) const; //从pos位置查找s的前n个字符第一次位置
  • int find(const char c, int pos = 0) const; //查找字符c第一次出现位置

  最后一次出现的位置：rfind

  • int rfind(const string& str, int pos = npos) const; //查找str最后一次位置,从pos开始查找
  • int rfind(const char* s, int pos = npos) const; //查找s最后一次出现位置,从pos开始查找
  • int rfind(const char* s, int pos, int n) const; //从pos查找s的前n个字符最后一次位置
  • int rfind(const char c, int pos = 0) const; //查找字符c最后一次出现位置

• 替换：在指定的位置替换字符串，replace在替换时，要指定从哪个位置起，多少个字符，替换成什么样的字符串

  • string& replace(int pos, int n, const string& str); //替换从pos开始n个字符为字符串str
  • string& replace(int pos, int n,const char* s); //替换从pos开始的n个字符为字符串s

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

int main() {

    //查找
    string str1 = "abcdefgde";
    //find
    int pos = str1.find("de");
    if (pos == -1)
        cout << "未找到" << endl;
    else
        cout << "pos = " << pos << endl;
    //rfind
    pos = str1.rfind("de");
    cout << "pos = " << pos << endl;

    //替换
    //从第1个位置开始，将三个字符替换为1111
    str1.replace(1, 3, "1111");
    cout << "str1 = " << str1 << endl;

    return 0;
}

pos = 3
pos = 7
str1 = a1111efgde

1.6 string字符串比较

功能描述：

• 字符串之间的比较

比较方式：

• 字符串比较是按逐个字符的ASCII码进行对比，字符串对比主要是用于比较两个字符串是否相等，判断谁大谁小的意义并不是很大

= 返回0

> 返回1

< 返回-1

函数原型：

• int compare(const string &s) const; //与字符串s比较
• int compare(const char *s) const; //与字符串s比较

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

int main() {

    string s1 = "hello";
    string s2 = "hello";
    string s3 = "aello";

    int ret1 = s1.compare(s2);
    int ret2 = s1.compare(s3);

    cout<< "ret1 = " <<ret1 << ", " << "ret2 = " << ret2 << endl;

    return 0;
}

ret1 = 0, ret2 = 1

1.7 string字符存取

string中单个字符存取方式有两种：

• char& operator[](int n); // 通过[]方式取字符
• char& at(int n); // 通过at方法获取字符

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

int main() {

    string str = "hello world";
    cout << sizeof(str) << endl;  //g++版本不一样，string所占的字节数也不一样，此处占32个字节
    for (int i = 0; i < str.size(); i++)  //不要写成了i < sizeof(str)
        cout << str[i] << " ";
    cout << endl;
    
    for (int i = 0; i < str.size(); i++)
        cout << str.at(i) << " ";
    cout << endl;

    return 0;
}

1.8 string插入和删除

功能描述：

• 对string字符串进行插入和删除字符操作

函数原型：

插入：

• string& insert(int pos, const char* s); //在指定位置插入字符串
• string& insert(int pos, const string& str); //在指定位置插入字符串
• string& insert(int pos, int n, char c); //在指定位置插入n个字符c

删除：

• string& erase(int pos, int n = npos); //删除从Pos开始的n个字符

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

int main() {
    string str = "hello";
    str.insert(1,"111");
    cout << str << endl;

    str.erase(1,3);
    cout << str << endl;

    return 0;
}

1.9 string子串

功能描述：

• 从字符串中获取想要的子串

函数原型：

• string substr(int pos = 0, int n = npos) const; //返回由pos开始的n个字符组成的字符串

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

int main() {
    string str = "abcdefg";
    string subStr = str.substr(1, 3);
    cout << "subStr = " << subStr << endl;

    //灵活的运用求子串功能，可以在实际开发中获取有效的信息
    string email = "wanyu@sina.com";
    int pos = email.find("@");
    string username = email.substr(0, pos);
    cout << "username: " << username << endl;

    return 0;
}

2 vector容器

STL中最常用的容器为Vector

补充一下vector里的{}操作符

2.1 vector基本概念

功能：

• vector数据结构和数组非常相似，是一种动态数组。不同之处在于数组是静态空间，而vector可以动态扩展

• 动态扩展：并不是在原空间之后续接新空间，而是找更大的内存空间，然后将原数据拷贝新空间，释放原空间

• vector容器的迭代器是支持随机访问的迭代器

2.2 vector构造函数

函数原型：

• vector<T> v; //采用模板实现类实现，默认构造函数
• vector(v.begin(), v.end()); //将v[begin(), end())区间中的元素拷贝给本身。
• vector(n, elem); //构造函数将n个elem拷贝给本身。
• vector(const vector &vec); //拷贝构造函数。

一般常用第一种搭配赋值操作，或者第四种拷贝构造

#include <iostream>
#include <vector>
using namespace std;

void printVector(vector<int>& v) {

    for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
}

int main() {

    vector<int>v1;  //无参构造
    for (int i = 0; i < 10; ++i) {
        v1.push_back(i);   //push_back()尾插法，向vector中加入新元素
    }
    printVector(v1);

    vector<int>v2(v1.begin(), v1.end());  //将 v [begin(), end()) 区间中的元素拷贝给本身，前闭后开
    printVector(v2);

    vector<int>v3(5,100);  //构造函数将 5个 100 拷贝给本身
    printVector(v3);

    vector<int>v4(v3);  //拷贝构造函数
    printVector(v4);
    
    return 0;
}

0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
100 100 100 100 100
100 100 100 100 100

2.3 vector迭代器

vector迭代器形式是：vector<T>::iterator

v.begin() 返回迭代器，这个迭代器指向容器中第一个数据

v.end() 返回迭代器，这个迭代器指向容器元素的最后一个元素的下一个位置

#include <iostream>
#include <vector>
using namespace std;

void printVector(vector<int>& v) {
    //构造迭代器it，指向第一个位置，当他不等于最后一个位置的下一位时，一直++
    //输出时解引用
    for(vector<int>::iterator it = v.begin(); it != v.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
}

int main() {

    vector<int>v1;
    for (int i = 0; i < 10; ++i) {
        v1.push_back(i);
    }
    printVector(v1);

    return 0;
}

2.4 vector赋值操作

功能描述：

• 给vector容器进行赋值

函数原型：

• vector& operator=(const vector &vec); //重载等号操作符

• assign(beg, end); //将[beg, end)区间中的数据拷贝赋值给本身。

• assign(n, elem); //将n个elem拷贝赋值给本身。

常用第一个，二三了解即可

#include <iostream>
#include <vector>
using namespace std;

void printVector(vector<int>& v) {
    for(vector<int>::iterator it = v.begin(); it != v.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
}

int main() {

    vector<int>v1;
    for (int i = 0; i < 10; ++i) {
        v1.push_back(i);
    }
    printVector(v1);

    vector<int>v2 = v1;
    printVector(v2);

    vector<int> v3;
    v3.assign(v1.begin(),  v1.end());
    printVector(v3);

    vector<int> v4;
    v4.assign(5,100);
    printVector(v4);

    return 0;
}

0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
100 100 100 100 100

2.5 vector容量和大小

功能描述：

• 对vector容器的容量和大小操作

函数原型：

• empty(); //判断容器是否为空，为空返回True

• capacity(); //容器的容量

• size(); //返回容器中元素的个数

• resize(int num); //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。

• resize(int num, elem); //重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除

#include <iostream>
#include <vector>
using namespace std;

void printVector(vector<int>& v) {
    for(vector<int>::iterator it = v.begin(); it != v.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
}

int main() {

    vector<int>v1;
    for (int i = 0; i < 10; ++i) {
        v1.push_back(i);
    }
    if (v1.empty()){
        cout << "v1为空" << endl;
    }
    else{
        cout << "v1不为空" << endl;
        //值得一提的是，当vector的大小和容量相等时，容器每次增加多少容量取决于算法的实现，
        //不同的环境可能不同，win10环境下vs以1.5倍扩充，CLion以2倍扩充
        cout << "v1的容量 = " << v1.capacity() << endl;
        cout << "v1的大小 = " << v1.size() << endl;
    }

    // resize 重新指定大小 ，
    // 若指定的更大，默认用0填充新位置，可以利用重载版本替换默认填充
    v1.resize(15,10);
    printVector(v1);

    // resize 重新指定大小 ，若指定的更小，超出部分元素被删除
    v1.resize(5);
    printVector(v1);

    return 0;
}

v1不为空
v1的容量 = 16
v1的大小 = 10
0 1 2 3 4 5 6 7 8 9 10 10 10 10 10
0 1 2 3 4

值得注意的是，当使用拷贝构造函数去赋值一个大小容量不等的vector时，复制过来的vector容量会和大小保持一致

#include <iostream>
#include <vector>

using namespace std;

void printVector(vector<int> &v) {
    for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
}

int main() {
    vector<int> v1;
    for (int i = 0; i < 100000; i++) {
        v1.push_back(i);
    }
    cout << "v1的容量为：" << v1.capacity() << endl;
    cout << "v1的大小为：" << v1.size() << endl;

    //rsize之后大小只为5
    v1.resize(5);
    cout << "v1的容量为：" << v1.capacity() << endl;
    cout << "v1的大小为：" << v1.size() << endl;

    //拷贝构造，拷贝过来容量会和大小保持一致
    vector<int> v2(v1);
    cout << "v2的容量为：" << v2.capacity() << endl;
    cout << "v2的大小为：" << v2.size() << endl;

    //添加新元素后，容量才会继续扩展
    v2.push_back(10);
    cout << "v2的容量为：" << v2.capacity() << endl;
    cout << "v2的大小为：" << v2.size() << endl;
    
    return 0;
}

v1的容量为：131072
v1的大小为：100000
v1的容量为：131072
v1的大小为：5
v2的容量为：5
v2的大小为：5
v2的容量为：10
v2的大小为：6

2.6 vector插入和删除

功能描述：

对vector容器进行插入、删除操作

函数原型：

• push_back(ele); //尾部插入元素ele
• insert(const_iterator pos, ele); //迭代器指向位置pos插入元素ele
• insert(const_iterator pos, int count,ele); //迭代器指向位置pos插入count个元素ele
• pop_back(); //删除最后一个元素
• erase(const_iterator pos); //删除迭代器指向的元素
• erase(const_iterator start, const_iterator end); //删除迭代器从start到end之间的元素
• clear(); //删除容器中所有元素

#include <iostream>
#include <vector>
using namespace std;

void printVector(vector<int>& v) {
    for(vector<int>::iterator it = v.begin(); it != v.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
}

int main() {
    vector<int>v1;
    //尾插法
    v1.push_back(10);
    v1.push_back(20);
    v1.push_back(30);
    printVector(v1);

    //指定位置插入，注意指定的格式是迭代器
    v1.insert(v1.begin(), 100);   //指定插在第0个位置
    
    vector<int>::iterator it = v1.begin();
    it++;
    v1.insert(it, 200);           //指定插在第1个位置
    printVector(v1);

    v1.insert(v1.begin(), 2, 1000);  //在开头插2个1000
    printVector(v1);

    //尾删
    v1.pop_back();
    printVector(v1);

    //删除指定位置的元素
    v1.erase(v1.begin());
    printVector(v1);

    //清空
    //v1.erase(v1.begin(), v1.end());
    v1.clear();
    printVector(v1);

    return 0;
}

10 20 30
100 200 10 20 30
1000 1000 100 200 10 20 30
1000 1000 100 200 10 20
1000 100 200 10 20

2.7 vector数据存取

除了用迭代器获取vector容器中元素，[ ]和at也可以

功能描述：

• 对vector中的数据的存取操作

函数原型：

• at(int idx); //返回索引idx所指的数据
• operator[]; //返回索引idx所指的数据
• front(); //返回容器中第一个数据元素
• back(); //返回容器中最后一个数据元素

注意区分：front(v) back(v) 返回首尾元素， v.begin() v.end() 返回首尾位置（迭代器）

#include <iostream>
#include <vector>
using namespace std;

void printVector(vector<int> &v) {
    for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
}

int main() {
    vector<int> v1;
    for (int i = 0; i < 10; ++i) {
        v1.push_back(i);
    }
    //printVector(v1);
    for (int i = 0; i < v1.size(); ++i) {
        cout << v1[i] << " ";
    }
    cout << endl;

    for (int i = 0; i < v1.size(); ++i) {
        cout << v1.at(i) << " ";
    }
    cout << endl;

    cout << v1.front() << endl;
    cout << v1.back();

    return 0;
}

2.8 vector互换容器

功能描述：

• 实现两个容器内元素进行互换

函数原型：

• swap(vec); // 将vec与本身的元素互换

#include <iostream>
#include <vector>
using namespace std;

void printVector(vector<int> &v) {
    for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
}

int main() {
    vector<int>v1;
    for (int i = 0; i < 10; i++)
    {
        v1.push_back(i);
    }
    printVector(v1);

    vector<int>v2;
    for (int i = 10; i > 0; i--)
    {
        v2.push_back(i);
    }
    printVector(v2);

    //互换容器
    cout << "互换后" << endl;
    v1.swap(v2);
    printVector(v1);
    printVector(v2);

    return 0;
}

swap可以使两个容器互换，可以达到实用的收缩内存效果

#include <iostream>
#include <vector>
using namespace std;

void printVector(vector<int> &v) {
    for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
}

int main() {
    vector<int> v1;
    for (int i = 0; i < 100000; i++) {
        v1.push_back(i);
    }
    cout << "v1的容量为：" << v1.capacity() << endl;
    cout << "v1的大小为：" << v1.size() << endl;

    //rsize之后大小只为5
    v1.resize(5);
    cout << "v1的容量为：" << v1.capacity() << endl;
    cout << "v1的大小为：" << v1.size() << endl;

    // vector<int>(v1)是用拷贝构造函数以v1为对象，复制一个vector容器，
    // 这个复制的容器大小和容量都是3，容量并不是十万多，拷贝过来的容量和大小保持一致
    // 同时vector<int>(v1)这种格式并没有指定赋值给新的容器，属于匿名对象。正常的拷贝构造函数语句为vector<int> v2(v1)  注意对比
    // 让这个匿名对象和v1互换，v1就指向了容量是3大小也是3的匿名对象
    // 而匿名对象指向了容量十万多的容器，但又因为它是匿名对象，所以这行语句结束后，编译器就自动释放掉，达到收缩内存的效果
    vector<int>(v1).swap(v1); //vector<int>(v1)匿名对象

    cout << "v的容量为：" << v1.capacity() << endl;
    cout << "v的大小为：" << v1.size() << endl;

    return 0;
}

2.8 vector预留空间

功能描述：

• 如果数据量较大，可以一开始利用reserve预留空间，减少vector在动态扩展容量时的扩展次数

函数原型：

• reserve(int len);//容器预留len个元素长度，预留位置不初始化，元素不可访问。resize会将变长的位置用默认的0填充

#include <iostream>
#include <vector>
using namespace std;

void printVector(vector<int> &v) {
    for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
}

int main() {
    vector<int> v;
    int num;       //定义计数值
    int *p = NULL; //定义空指针
    for (int i = 0; i < 100000; ++i) {
        v.push_back(i);
        //如果p不指向容器的首地址，就让他指向首地址，num+1
        //当容器动态扩展时，原首地址失效，每扩展一次，num+1
        if (p != &v[0]){
            p = &v[0];
            num++;
        }
    }
    cout << "num:" << num << endl;  //容量为100000.扩展了18次

    //而如果一开始就预留充足空间，可减少扩展次数
    vector<int> v1;
    v1.reserve(100000);
    int num1;       //定义计数值
    int *p1 = NULL; //定义空指针
    for (int i = 0; i < 100000; ++i) {
        v.push_back(i);
        if (p1 != &v1[0]){
            p1 = &v1[0];
            num1++;
        }
    }
    cout << "num1:" << num1 << endl;  //扩展了1次

    return 0;
}

3 deque容器

3.1 deque基本概念

功能：可以对头端进行插入删除操作，双端队列，

deque内部工作原理:

deque内部有个中控器，维护每段缓冲区中的内容，缓冲区中存放真实数据

中控器维护的是每个缓冲区的地址，使得使用deque时像一片连续的内存空间

deque容器的迭代器也是支持随机访问的

deque与vector的联系

• 区别：

  • deque相对而言，对头部的插入删除速度会比vector快，因为vector对于头部的插入删除效率低，数据量越大，效率越低
  • 但deque访问元素时的速度会比vector慢，其要先访问缓冲区地址，再访问数据

• 相同点：

  • deque容器的迭代器也是支持随机访问的
  • 很多操作的函数设计模式都相同

3.2 deque构造函数

功能描述：

• deque容器构造

函数原型：

• deque<T> deqT; //默认构造形式
• deque(beg, end); //构造函数将[beg, end)区间中的元素拷贝给本身。
• deque(n, elem); //构造函数将n个elem拷贝给本身。
• deque(const deque &deq); //拷贝构造函数

#include <iostream>
#include <deque>
using namespace std;

// 为了避免函数编写时将迭代器进行写的误操作，一般会将容器加上const限定，保证程序只读，
// 与之对应的是将迭代器iterator改为const_iterator
void printDeque(const deque<int> &d) {
    for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
        //*it = 100; //加上const后这句就会报错
        cout << *it << " ";
    }
    cout << endl;
}

int main() {
    deque<int> d1;  //无参构造函数
    for (int i = 0; i < 10; ++i) {
        d1.push_back(i);
    }
    printDeque(d1);

    deque<int> d2(d1.begin(),d1.end());
    printDeque(d2);

    deque<int>d3(10,100);
    printDeque(d3);

    deque<int>d4(d3);  //拷贝构造函数
    printDeque(d4);
    return 0;
}

0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100

3.3 deque赋值操作

功能描述：

• 给deque容器进行赋值

函数原型：

• deque& operator=(const deque &deq); //重载等号操作符

• assign(beg, end); //将[beg, end)区间中的数据拷贝赋值给本身。

• assign(n, elem); //将n个elem拷贝赋值给本身。

3.4 deque大小操作

功能描述：

• 对deque容器的大小进行操作

函数原型：

• deque.empty(); //判断容器是否为空，为空返回True

• deque.size(); //返回容器中元素的个数

• deque.resize(num); //重新指定容器的长度为num,若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。

• deque.resize(num, elem); //重新指定容器的长度为num,若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。

注意：deque没有容量这一说，它可以无限的向其中添加元素

3.5 deque 插入和删除

功能描述：

• 向deque容器中插入和删除数据

函数原型：

两端插入操作：

• 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位置的数据，返回下一个数据的位置。

普通的函数就不举例了，带返回位置的函数写一些示例

#include <iostream>
#include <deque>
using namespace std;

void printDeque(const deque<int> &d) {
    for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
}

int main() {
    deque<int> d1;  //无参构造函数
    for (int i = 0; i < 10; ++i) {
        d1.push_back(i);
    }

    deque<int>::iterator pos;
    // 返回的是新数据的位置
    pos = d1.insert(d1.begin(),100);
    cout << *pos << endl;
	//返回的删除的数据下一个位置
    pos = d1.erase(d1.begin());
    cout << *pos;
    
    return 0;
}

100

0

3.6 deque 数据存取

功能描述：

• 对deque 中的数据的存取操作

函数原型：

• at(int idx); //返回索引idx所指的数据
• operator[]; //返回索引idx所指的数据
• front(); //返回容器中第一个数据元素
• back(); //返回容器中最后一个数据元素

3.7 deque 排序

功能描述：

• 利用算法实现对deque容器进行排序

算法：

• sort(iterator beg, iterator end) //对beg和end区间内元素进行排序

#include <iostream>
#include <deque>
#include <algorithm>  //注意包含对应头文件
using namespace std;

void printDeque(const deque<int>& d){
    for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
        cout << *it << " ";
    cout << endl;
}

int main() {
    deque<int> d;
    d.push_back(10);
    d.push_back(20);
    d.push_front(100);
    printDeque(d);

    sort(d.begin(), d.end());
    printDeque(d);

    return 0;
}

100 10 20
10 20 100

需要注意的是，只有支持随机访问迭代器的容器，才能使用标准算法，例如上面代码中的 sort(d.begin(), d.end()) 此时sort是标准的全局函数

当容器不支持随机访问迭代器时，内部会提供一些成员函数以供使用，调用的格式就应该是 Name.sort()，在后面的list容器中会碰到

4 stack容器

4.1 stack容器基本概念

概念：stack是一种先进后出(First In Last Out,FILO)的数据结构，又称为堆栈，它只有一个出口

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

栈中进入数据称为 — 入栈 push

栈中弹出数据称为 — 出栈 pop

4.2 stack 常用接口

功能描述：栈容器常用的对外接口，需要记住

构造函数：

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

赋值操作：

• stack& operator=(const stack &stk); //重载等号操作符

数据存取：

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

大小操作：

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

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> s;
    for (int i = 10; i < 5; ++i) {
        s.push(i);
    }
    cout << "栈的大小为：" << s.size() << endl;
    //只要栈不为空，就查看栈顶元素
    while(!s.empty()){
        cout << "栈顶元素为：" << s.top() <<endl;
        //弹出元素
        s.pop();
    }
    
    return 0;
}

栈的大小为：5
栈顶元素为：14
栈顶元素为：13
栈顶元素为：12
栈顶元素为：11
栈顶元素为：10

5 queue容器

5.1 queue基本概念

概念：Queue是一种先进先出(First In First Out,FIFO)的数据结构，称为队列，它有两个出口

队列容器允许从一端新增元素，从另一端移除元素

队列中只有队头和队尾才可以被外界使用，因此队列不允许有遍历行为

队列中进数据称为 — 入队 push

队列中出数据称为 — 出队 pop

5.2 queue 常用接口

功能描述：队列容器常用的对外接口

构造函数：

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

赋值操作：

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

数据存取：

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

大小操作：

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

#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);
    cout << "队列长度:" << q.size() << endl;

    while (!q.empty()) {
        cout << "队头元素：" << q.front() << " " << "队尾元素：" << q.back() << endl;
        q.pop();
    }

    return 0;
}

6 list容器

6.1 list容器基本概念

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

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

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

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

STL中的链表是一个双向循环链表

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

所谓双向，即图中的next指向下一个结点的地址，并且又有prev指向上一个结点的地址。

图中没有表现出的是循环特性，第一个结点的prev应该指向的是最后一个结点的地址，最后一个结点的next指向第一个结点的地址，而不都是指向NULL

STL中List和vector是两个最常被使用的容器，各有优缺点

list的优点：

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

list的缺点：

• 链表灵活，但是空间(指针域) 和 时间（遍历）额外耗费较大

6.2 list构造函数

功能描述：

• 创建list容器

函数原型：

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

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

void printList(const list<int>&l){
    for(list<int>::const_iterator it = l.begin(); it != l.end(); it ++)
        cout << *it << " ";
    cout << endl;
}

int main() {
    list<int> L1;
    for (int i = 0; i < 5; ++i) {
        L1.push_back(i);
    };
    printList(L1);

    return 0;
}

6.3 list赋值和交换

功能描述：

• 给list容器进行赋值，以及交换list容器

函数原型：

• assign(beg, end); //将[beg, end)区间中的数据拷贝赋值给本身。
• assign(n, elem); //将n个elem拷贝赋值给本身。
• list& operator=(const list &lst); //重载等号操作符
• swap(lst); //将lst与本身的元素互换。

6.4 list大小操作

功能描述：

• 对list容器的大小进行操作

函数原型：

• size(); //返回容器中元素的个数

• empty(); //判断容器是否为空

• resize(num); //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。

• resize(num, elem); //重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。

6.5 list插入和删除

功能描述：

• 对list容器进行数据的插入和删除

函数原型：

• push_back(elem); //在容器尾部加入一个元素
• pop_back(); //删除容器中最后一个元素
• push_front(elem); //在容器开头插入一个元素
• 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值匹配的元素。

6.6 list 数据存取

功能描述：

• 对list容器中数据进行存取

函数原型：

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

注意：不支持at和[]方式访问数据

同时，因为list容器的迭代器是双向迭代器，不支持随机访问，所以只能++或者–，而不能+1 -1

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


int main() {
    list<int> l1;
    list<int>::iterator it = l1.begin();
    it++;
    it--;           //既可以++也可以--，双向迭代器
    //it = it + 1;  //会报错，因为其不支持随机访问，没有重载+这个运算符，+1可以的话，+2+3也可以了，所以肯定是不允许的
    
    return 0;
}

6.7 list反转和排序

功能描述：

• 将容器中的元素反转，以及将容器中的数据进行排序

函数原型：

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

这里需要重点强调的时排序算法：

只有支持随机访问迭代器的容器，才能使用标准算法，例如前面的deque容器，可以使用sort(deque1.begin(), deque1.end())，此时sort是标准的全局函数

当容器不支持随机访问迭代器时，内部会提供一些成员函数以供使用，调用的格式就应该是 Name.sort()，如lst.sort()

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

void printList(const list<int>& L) {
    for (list<int>::const_iterator it = L.begin(); it != L.end(); it++)
        cout << *it << " ";
    cout << endl;
}

bool myCompare(int val1 , int val2)
{
    return val1 > val2;
}

int main() {
    list<int> L;
    L.push_back(90);
    L.push_back(30);
    L.push_back(20);
    L.push_back(70);
    printList(L);

    //反转容器的元素
    L.reverse();
    printList(L);

    //排序
    L.sort(); //默认的排序规则 从小到大
    printList(L);

    L.sort(myCompare); //指定规则，从大到小
    printList(L);

    return 0;
}

90 30 20 70
70 20 30 90
20 30 70 90
90 70 30 20

同时对于自定义数据类型，必须要指定排序规则，否则编译器不知道如何进行排序

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

class Person {
public:
    Person(string name, int age , int height) {
        m_Name = name;
        m_Age = age;
        m_Height = height;
    }

public:
    string m_Name;  //姓名
    int m_Age;      //年龄
    int m_Height;   //身高
};

//年龄进行升序，如果年龄相同按照身高进行降序
bool ComparePerson(Person& p1, Person& p2) {
    if (p1.m_Age == p2.m_Age)
        return p1.m_Height  > p2.m_Height;
    else
        return  p1.m_Age < p2.m_Age;
}


int main() {

    list<Person> L;
    Person p1("刘备", 35 , 175);
    Person p2("曹操", 45 , 180);
    Person p3("孙权", 40 , 170);
    Person p4("赵云", 25 , 190);
    Person p5("张飞", 35 , 160);
    Person p6("关羽", 35 , 200);

    L.push_back(p1);
    L.push_back(p2);
    L.push_back(p3);
    L.push_back(p4);
    L.push_back(p5);
    L.push_back(p6);

    L.sort(ComparePerson); //排序

    for (list<Person>::iterator it = L.begin(); it != L.end(); it++) {
        cout << "姓名： " << it->m_Name << " 年龄： " << it->m_Age
        << " 身高： " << it->m_Height << endl;
    }

    return 0;
}

7 set / multiset 容器

7.1 set基本概念

简介：

• 所有元素都会在插入时自动被排序

本质：

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

set和multiset区别：

• set不允许容器中有重复的元素
• multiset允许容器中有重复的元素，因为multiset不会检测数据

7.2 set构造和赋值

功能描述：创建set容器以及赋值

构造：

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

赋值：

• set& operator=(const set &st); //重载等号操作符

#include <iostream>
#include <set>
using namespace std;

void printSet(set<int> & s){
    for (set<int>::iterator it = s.begin(); it != s.end(); it++)
        cout << *it << " ";
    cout << endl;
}


int main() {
    set<int> s1;
    //set容器插入数据时用insert，没有尾插头插
    s1.insert(10);
    s1.insert(20);
    s1.insert(30);
    s1.insert(20);
    s1.insert(40);
    printSet(s1);  //自动排序

    //拷贝构造
    set<int>s2(s1);
    printSet(s2);

    //赋值
    set<int>s3;
    s3 = s2;
    printSet(s3);

    return 0;
}

7.3 set大小和交换

功能描述：

• 统计set容器大小以及交换set容器

函数原型：

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

7.4 set插入和删除

功能描述：

• set容器进行插入数据和删除数据

函数原型：

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

7.5 set查找和统计

功能描述：

• 对set容器进行查找数据以及统计数据

函数原型：

• find(key); //查找key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回set.end();
• count(key); //统计key的元素个数，对于set，结果为0或者1

#include <iostream>
#include <set>
using namespace std;

void printSet(set<int> & s){
    for (set<int>::iterator it = s.begin(); it != s.end(); it++)
        cout << *it << " ";
    cout << endl;
}


int main() {
    set<int> s1;
    //set容器插入数据时用insert
    s1.insert(10);
    s1.insert(20);
    s1.insert(30);
    s1.insert(20);
    s1.insert(40);
    printSet(s1);  //自动排序

    //查找
    set<int>::iterator pos = s1.find(30);
    if (pos != s1.end())
        cout << "找到了元素 ： " << *pos << endl;
    else
        cout << "未找到元素" << endl;

    //统计
    int num = s1.count(30);
    cout << "num = " << num << endl;

    return 0;
}

7.6 pair对组创建

在编写set.insert()时，查看源码会发现，其返回值类型是一个pair<iterator, bool>，这是一个pair对组，可以返回两个数据

功能描述：

• 成对出现的数据，利用对组可以返回两个数据

两种创建方式：

• pair<type, type> p ( value1, value2 );
• pair<type, type> p = make_pair( value1, value2 );

获取方式：

• 访问第一个数据：p.first
• 访问第二个数据：p.second

int main() {
    pair<string,int>p1("jack",18);
    cout << "姓名： " <<  p1.first << " 年龄： " << p1.second << endl;

    pair<string, int> p2 = make_pair("Jerry", 10);
    cout << "姓名： " << p2.first << " 年龄： " << p2.second << endl;
    
    return 0;
}

7.7 set和multiset区别

利用对组查看下set和multiset的区别：

在编写set.insert()时，其会返回一个对组pair<iterator, bool>，第二个值就是用来检测数据的，bool值为真即可以插入，为否则不可以插入

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s1;

    //第一次插入
    pair<set<int>::iterator, bool> ret = s1.insert(10);
    if (ret.second) {
        cout << "第一次插入成功!" << endl;
    }
    else {
        cout << "第一次插入失败!" << endl;
    }

    //尝试第二次插入
    ret = s1.insert(10);
    if (ret.second) {
        cout << "第二次插入成功!" << endl;
    }
    else {
        cout << "第二次插入失败!" << endl;
    }
    
    return 0;
}

第一次插入成功!
第二次插入失败!

而查看multiset.insert()源码时，其只会返回一个迭代器iterator，而不是对组，也就是multiset并不对能否插入进行判断

#include <iostream>
#include <set>
using namespace std;

int main() {
    multiset<int> ms;
    ms.insert(10);
    ms.insert(10);

    for (multiset<int>::iterator it = ms.begin(); it != ms.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;

    return 0;
}

10 10

7.8 set容器排序

学习目标：

• set容器默认排序规则为从小到大，掌握如何改变排序规则

解决方法：

• 利用仿函数（后面的内容会学到），可以改变排序规则

functor（仿函数）, 或者称之为function object(函数对象)， 是STL的四大组件之一。它是让一个函数对象被封装在类中， 从而看起来更像是一个对象。 这个类只有一个成员函数， 即重载了（） (括号)的运算符。 它没有任何数据。 该类被模板化了， 从而可以应付多种数据类型。

#include <iostream>
#include <set>
using namespace std;

void printSet(set<int> & s){
    for (set<int>::iterator it = s.begin(); it != s.end(); it++)
        cout << *it << " ";
    cout << endl;
}

class MyCompare{
public:
    bool operator()(int v1, int v2){
        return v1 > v2;
    }
};

int main() {
    set<int> s1;
    s1.insert(10);
    s1.insert(40);
    s1.insert(20);
    s1.insert(30);
    s1.insert(50);
    //默认从小到大
    printSet(s1);

    //指定排序规则
    set<int,MyCompare> s2;
    s2.insert(10);
    s2.insert(40);
    s2.insert(20);
    s2.insert(30);
    s2.insert(50);
    //printSet(s2);  //原来的打印函数用不了了，类型变了
    for (set<int, MyCompare>::iterator it = s2.begin(); it != s2.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;

    return 0;
}

10 20 30 40 50
50 40 30 20 10

对于自定义的数据类型，set必须指定排序规则才可以插入数据

#include <iostream>
#include <set>
using namespace std;

class Person
{
public:
	Person(string name, int age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}

	string m_Name;
	int m_Age;

};

class comparePerson
{
public:
	bool operator()(const Person& p1, const Person &p2)
	{
		//按照年龄进行排序  降序
		return p1.m_Age > p2.m_Age;
	}
};


int main() {

	set<Person, comparePerson> s;

	Person p1("刘备", 23);
	Person p2("关羽", 27);
	Person p3("张飞", 25);
	Person p4("赵云", 21);

	s.insert(p1);
	s.insert(p2);
	s.insert(p3);
	s.insert(p4);

	for (set<Person, comparePerson>::iterator it = s.begin(); it != s.end(); it++)
	{
		cout << "姓名： " << it->m_Name << " 年龄： " << it->m_Age << endl;
	}

	return 0;
}

8 map/ multimap容器

8.1 map基本概念

简介：

• map中所有元素都是pair
• pair中第一个元素为key（键值），起到索引作用，第二个元素为value（实值）
• 所有元素都会根据元素的键值自动排序
• 当数据以键值对形式存在，可以考虑用map 或 multimap

本质：

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

优点：

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

map和multimap区别：

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

8.2 map构造和赋值

功能描述：

• 对map容器进行构造和赋值操作

构造：

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

赋值：

• map& operator=(const map &mp); //重载等号操作符

#include <iostream>
#include <map>
using namespace std;

void printMap(map<int,int>&m){
    for(map<int,int>::iterator it = m.begin(); it != m.end(); it++)
        cout << "key=" << it->first << " values=" << it->second << endl;
    cout << endl;
}


int main() {
    map<int,int>m;
    m.insert(pair<int,int>(1,10));
    m.insert(pair<int,int>(2,20));
    m.insert(pair<int,int>(3,30));
    printMap(m);

    map<int,int>m2(m);
    //printMap(m2);

    map<int,int>m3;
    m3 = m2;
    //printMap(m3);

    return 0;
}

key=1 values=10
key=2 values=20
key=3 values=30

8.3 map大小和交换

功能描述：

• 统计map容器大小以及交换map容器

函数原型：

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

#include <iostream>
#include <map>
using namespace std;

void printMap(map<int,int>&m){
    for(map<int,int>::iterator it = m.begin(); it != m.end(); it++)
        cout << "key=" << it->first << " values=" << it->second << endl;
    cout << endl;
}


int main() {
    map<int,int>m;
    m.insert(pair<int,int>(1,10));
    m.insert(pair<int,int>(2,20));
    m.insert(pair<int,int>(3,30));

    if (m.empty())
        cout << "m为空" << endl;
    else{
        cout << "m不为空" << endl;
        cout << "m的大小为： " << m.size() << endl;
    }

    map<int, int>m2;
    m2.insert(pair<int, int>(4, 100));
    m2.insert(pair<int, int>(5, 200));
    m2.insert(pair<int, int>(6, 300));
    m2.swap(m);
    printMap(m);
    
    return 0;
}

8.4 map插入和删除

功能描述：

• map容器进行插入数据和删除数据

函数原型：

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

#include <iostream>
#include <map>
using namespace std;

void printMap(map<int,int>&m){
    for(map<int,int>::iterator it = m.begin(); it != m.end(); it++)
        cout << "key=" << it->first << " values=" << it->second << endl;
    cout << endl;
}


int main() {
    map<int,int> m;
    //四种插入方式，
    m.insert(pair<int,int>(1,10));
    m[2] = 20;
    m.insert(make_pair(3,30));
    m.insert(map<int,int>::value_type(4,40));
    printMap(m);

    m.erase(3);  //删除对应键的pair对组，不是对应值
    printMap(m);

    //清空
    m.erase(m.begin(),m.end());
    m.clear();
    printMap(m);

    return 0;
}

key=1 values=10
key=2 values=20
key=3 values=30
key=4 values=40

key=1 values=10
key=2 values=20
key=4 values=40

8.5 map查找和统计

功能描述：

• 对map容器进行查找数据以及统计数据

函数原型：

• find(key); //查找key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回set.end();
• count(key); //统计key的元素个数，对于map，结果为0或者1

int main() {
	map<int, int>m; 
	m.insert(pair<int, int>(1, 10));
	m.insert(pair<int, int>(2, 20));
	m.insert(pair<int, int>(3, 30));

	//查找
	map<int, int>::iterator pos = m.find(3);
    
	if (pos != m.end())
		cout << "找到了元素 key = " << (*pos).first << " value = " << (*pos).second << endl;
	else
		cout << "未找到元素" << endl;

	//统计
	int num = m.count(3);
	cout << "num = " << num << endl;

	return 0;
}

8.6 map容器排序

map容器默认排序规则为 按照key值进行 从小到大排序。

利用仿函数可以指定map容器的排序规则

对于自定义数据类型，map必须要指定排序规则,同set容器

#include <map>

class MyCompare {
public:
	bool operator()(int v1, int v2) {
		return v1 > v2;
	}
};

int main() {
	//默认从小到大排序
	//利用仿函数实现从大到小排序
	map<int, int, MyCompare> m;

	m.insert(make_pair(1, 10));
	m.insert(make_pair(2, 20));
	m.insert(make_pair(3, 30));
	m.insert(make_pair(4, 40));
	m.insert(make_pair(5, 50));

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

	return 0;
}