C++_23_STL容器

STL容器

概念

			STL(Standard Template Library,标 准 模 板 库 ),是 惠 普 实 验 室 开 发 的 一 系 列 软 件 的 统称 。

STL 6大 组 件
容 器 :
        作 用 :容 纳 存 储 数 据
        分 类 :
            序 列 式 容 器 ：
                强 调 值 的 排 序 ， 每 个 元 素 均 有 固 定 的 位 置 ，  除 非 用 删 除 或 插 入 的 操
作 改 变 这 个 位 置 ，
     如  vector, deque/queue, list;
            关 联 式 容 器 :
                非 线 性 ， 更 准 确 的 说 是 二 叉 树 结 构 ， 各 元 素 之 间 没 有 严 格 的 物 理 上
的 顺 序 关 系 ; 
                在 数 据 中 选 择 一 个 关 键 字 key， 这 个 key对 数 据 起 到 索 引 的 作 用 ， 方
便 查 找 。

                如 ：  set/multiset ，  Map/multimap 容 器
        注 意 :容 器 可 以 嵌 套 容 器

    算 法 :
        作 用 :操 作 数 据 ,如 插 入 数 据 、 删 除 数 据 、 修 改 数 据 、 排 序 等
        分 类 :
            质 变 算 法 ： 是 指 运 算 过 程 中 会 更 改 区 间 内 的 元 素 的 内 容 。 例 如 拷 贝 ， 替
换 ， 删 除 等 等

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

    迭 代 器
        作 用 :容 器 与 算 法 之 间 的 粘 合 剂
        注 意 :每 个 容 器 都 有 自 己 的 迭 代 器
        分 类 :
            输 入 迭 代 器  提 供 对 数 据 的 只 读 访 问  只 读 ， 支 持 ++、 ==、 ！ = 
            输 出 迭 代 器  提 供 对 数 据 的 只 写 访 问  只 写 ， 支 持 ++
            前 向 迭 代 器  提 供 读 写 操 作 ， 并 能 向 前 推 进 迭 代 器  读 写 ， 支 持 ++、
==、 ！ = 
            双 向 迭 代 器  提 供 读 写 操 作 ， 并 能 向 前 和 向 后 操 作  读 写 ， 支 持 ++、 --，
            随 机 访 问 迭 代 器  提 供 读 写 操 作 ， 并 能 以 跳 跃 的 方 式 访 问 容 器 的 任 意 数
据 ， 是 功 能 最 强 的 迭 代 器 读 写 ， 支 持 ++、 -- [n]、 - n、 <、 <=、 >、 >=

    仿 函 数
        作 用 :为 算 法 提 供 策 略

    适 配 器
        作 用 :为 算 法 提 供 更 多 的 参 数 接 口
           空 间 配 置 器
        作 用 :为 容 器 和 算 法 管 理 空 间

常用容器

A string

作用

存储字符的容器(字符串)

构造函数

语法

string();//创 建 一 个 空 的 字 符 串  例 如 : string str;

string(const string& str);//使 用 一 个  string 对 象 初 始 化 另 一 个  string 对 象

string(const char* s);//使 用 字 符 串  s 初 始 化

string(int n, char c);//使 用  n 个 字 符  c 初 始 化  v

示例:

void fun01()
{
    string str01;
    cout << "str01 = " << str01 << endl;
    string str02("hello");
    cout << "str02 = " << str02 << endl;
    string str03 = str02;
    cout << "str03 = " << str03 << endl;
    string str04(3,'a');
    cout << "str04 = " << str04 << endl;
}

基本赋值操作

语法

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赋 给 当 前 字 符 串

string& assign(const string &s, int start, int n);//将 s从  start开 始 n个字 符 赋 值 给 字 符 串

示例1

void fun02()
{
    string str01;
    cout << "str01 = " << str01 << endl;
    str01 = "张 十 一";
    cout << "str01 = " << str01 << endl;
    string str02;
    str02 = str01;
    cout << "str02 = " << str02 << endl;
    string str03;
    str03 = 'A';
    cout << "str03 = " << str03 << endl;
}

示例2

void fun03()
{
    // 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赋 给 当 前 字 符 串
   // string& assign(const string &s, int start, int n);//将 s从  start开 始 n个 字 符 赋 值 给 字 符 串
     string str01 = "hello";
     cout << "str01 = " << str01 << endl;
   // str01.assign("world123");
   // str01.assign("world123",5);
   // str01.assign(3,'A');
   // cout << "str01 = " << str01 << endl;
      string str02;
      str02.assign(str01, 0, 2);
      cout << "str02 = " << str02 << endl;
}

获取字符串长度

语法

int size();
int length();
注 意 :不 包 含 \0

示例

void fun04()
{
      string str = "hello";
      int size = str.size();
      cout << "size = " << size << endl;
      int len = str.length();
      cout << "len = " << len << endl;
}

存取字符操作

语法

char& operator[](int n);//通 过 []方 式 取 字 符 ,下 标 越 界 不 会 抛 出 异 常

char& at(int n);//通 过 at方 法 获 取 字 符 ,下 标 越 界 会 抛 出 异 常

示例

void fun05()
{
    string str = "hello";
    cout << str[2] << endl;
    cout << str.at(1) << endl;
}

拼接操作

string& operator+=(const string& str);//重 载 +=操 作 符

string& operator+=(const char* str);//重 载 +=操 作 符

string& operator+=(const char c);//重 载 +=操 作 符

string& append(const char *s);//把 字 符 串 s连 接 到 当 前 字 符 串 结 尾

string& append(const char *s, int n);//把 字 符 串 s的 前 n个 字 符 连 接 到 当 前 字 符串 结 尾

string& append(const string &s);//同 operator+=()

string& append(const string &s, int pos, int n);//把 字 符 串 s中 从 pos开 始 的n个 字 符 连 接 到 当 前 字 符 串 结 尾

string& append(int n, char c);//在 当 前 字 符 串 结 尾 添 加 n个 字 符 c

示例

void fun06()
{
    string str01 = "Hi";
    str01+="C++";
    cout << "str01 = " << str01 << endl;
    string str02 = " STL";
    str01+=str02;
    cout << "str01 = " << str01 << endl;
    str01+='A';
    cout << "str01 = " << str01 << endl;
}
void fun07()
{
    // string& append(const char *s);
    //把 字 符 串 s连 接 到 当 前 字 符 串 结 尾
    string str01;
    str01.append("hi");
    cout << "str01 = " << str01 << endl;
    str01.append(" c++");
    cout << "str01 = " << str01 << endl;
    // string& append(const char *s, int n);
    //把 字 符 串 s的 前 n个 字 符 连 接 到 当 前 字 符 串 结 尾
    string str02;
    str02.append("abcdefg",5);
    cout << "str02 = " << str02 << endl;
    // string& append(const string &s);
    //同 operator+=()
    // string& append(const string &s, int pos, int n);
    //把 字 符 串 s中 从 pos开 始 的 n个 字 符 连 接 到 当 前 字 符 串 结 尾
    string str03 = "1234567890";
    string str04;
    str04.append(str03,3,2);
    cout << "str04 = " << str04 << endl;
    // string& append(int n, char c);
    //在 当 前 字 符 串 结 尾 添 加 n个 字 符 c
    str04.append(2,'W');
    cout << "str04 = " << str04 << endl;
}

查找和替换

语法

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第一次出现位置
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最后一次出现位置
string& replace(int pos, int n, const string& str); //替换从pos开始n个字符为字符串str
string& replace(int pos, int n, const char* s); //替换从pos开始的n个字符为字符串s

注意:查找是不存在返回-1

示例

void fun08()
{
    string str = "123abc123";
    int i01 = str.find('2');
    cout << "i01 = " << i01 << endl;
    int i02 = str.find("3a");
    cout << "i02 = " << i02 << endl;
    int i03 = str.rfind('2');
    cout << "i03 = " << i03 << endl;
    str.replace(3, 3, "147258369");
    cout << "str = " << str << endl;
}

比较操作

/**
*compare函数在>时返回1，<时返回-1，==时返回0。
*比较区分大小写，比较时参考字典顺序，排越前面的越小。大写的A比小写的a小。
**/
int compare(const string &s) const; //与字符串s比较
int compare(const char *s) const;   //与字符串s比较

截取操作

语法

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

示例

void fun09()
{
	string str01 = "a.txt";
	string str02 = str01.substr(1,4);
	cout << str02 << endl;
}

插入与删除

语法

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个字符

示例

void fun10()
{
    // 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 str01 = "11";
    // 开始位置不要超出字符串下标范围
    //  str01.insert(1,"abc");
    str01.insert(1, 3, 'A');
    cout << "str01 = " << str01 << endl;
    // string& erase(int pos, int n = npos);//删除从Pos开始的n个字符
    str01.erase(1, 3);
    cout << "str01 = " << str01 << endl;
}

string与char * 转换

语法

//string转char*
string str = "itcast";
const char* cstr = str.c_str();
//char*转string
char* s = "itcast";
string str(s);

示例

void fun11()
{
    string str01 = "abc";
    string str02("abc");
    char *str03 = (char *)str01.c_str();
}

B vector

概述

• 连 续 开 辟 ,单 向 开 口 ,随 机 访 问 迭 代 器 ,有 容 量 ,每 次 扩 容 是 原 来 的 2倍

• 底 层 数 据 结 构 :数 组

与数组区别

>
 vector的 结 构 类 同 于 数 组 ， 数 组 是 静 态 的 ， 在 定 义 时 确 定 的 数 组 的 大 小 ；
 而 vector是 动 态 的 ， 添 加 元 素 时 如 果 空 间 不 足 时 ， 则 会 自 动 扩 容 器 （ 2^n);这 被 称 为
 vector的 未 雨 绸 缪 机 制
 整 体 来 说 ， vector比 较 灵 活 的 ， 而 且 vector是 类 模 板 ， 可 以 存 放 任 意 类 型 的 元 素

迭代器

构造函数

语法

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

示例

void fun01()
{
    vector<int> v01;
    v01.push_back(1); // 尾部添加
    v01.push_back(5);
    v01.push_back(3);
    vector<int>::iterator it = v01.begin(); // 获取开始位置的迭代器
    while (it != v01.end())                 // end():结束位置
    {
        cout << *it << endl; //*it获取当前迭代器指向的位置的值
        it++;                // 迭代器后移1位
    }
}
// =======================================
void fun02()
{
    vector<int> v01;
    v01.push_back(1); // 尾部添加
    v01.push_back(5);
    v01.push_back(3);
    vector<int> v02(v01.begin() + 1, v01.begin() + 2); // 包含开始位置,不包含结束位置(前闭后开)
    // vector<int>::iterator it = v02.begin();
    auto it = v02.begin(); // c++11及以上版本,编译时需加-std=c++11
    while (it != v02.end())
    {
        cout << *it << endl;
        it++;
    }
}
// =======================================
void fun03()
{
    vector<int> v(10, 5);
    auto it = v.begin();
    while (it != v.end())
    {
        cout << *it << endl;
        it++;
    }
}

赋值操作

语法

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

示例

void fun04()
{
    // assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
    // assign(n, elem);//将 n 个 elem 拷贝赋值给本身。
    // vector& operator=(const vector &vec);//重载等号操作符
    // swap(vec);// 将 vec 与本身的元素互换
    vector<int> v01;
    v01.push_back(1);
    v01.push_back(5);
    v01.push_back(3);
    v01.push_back(9);
    v01.push_back(7);
    vector<int> v02;
    // v02.assign(v01.begin(),v01.begin()+3);
    // v02.assign(5,3);
    // v02 = v01;
    v02.push_back(2);
    v02.push_back(4);
    v02.swap(v01);
    auto it = v02.begin();
    while (it != v02.end())
    {
        cout << *it << endl;
        it++;
    }
    cout << "---------------" << endl;
    auto it01 = v01.begin();
    while (it01 != v01.end())
    {
        cout << *it01 << endl;
        it01++;
    }
}

插入与删除

语法

push_back(ele); 
//尾部插入元素 ele

insert(const_iterator pos, int count, T ele);
//迭代器指向位置 pos 插入count个元素ele.

pop_back();
//删除最后一个元素

erase(const_iterator start, const_iterator end); 
//删除迭代器从 start到 end 之间的元素,删除[start, end)区间的所有元素

erase(const_iterator pos); 
//删除迭代器指向的元素

clear(); 
//删除容器中所有元素

示例

void fun05()
{
    vector<int> v;
    // push_back(ele); //尾部插入元素 ele
    v.push_back(1);
    v.push_back(3);
    v.push_back(5);
    v.push_back(7);
    // insert(const_iterator pos, int count, T ele); //迭代器指向位置pos 插入 count个元素ele.v.insert(v.begin(), 1, 0);
    // pop_back();//删除最后一个元素
    v.pop_back();
    // v.pop_back();
    //  erase(const_iterator start, const_iterator end); //删除迭代器从start 到 end 之间的元素,删除[start, end)区间的所有元素
    v.erase(v.begin() + 1, v.begin() + 3);
    // erase(const_iterator pos); //删除迭代器指向的元素
    v.erase(v.begin());
    // clear(); //删除容器中所有元素
    v.clear();
    auto it = v.begin();
    while (it != v.end())
    {
        cout << *it << endl;
        it++;
    }
}

取值操作

语法

at(int idx); //返回索引 idx 所指的数据，如果 idx 越界，抛出 out_of_range异常。
operator[](int idx); //返回索引 idx 所指的数据，越界时,不会直接报错
front(); //返回容器中第一个数据元素
back(); //返回容器中最后一个数据元素

示例

void fun06()
{
    vector<int> v;
    v.push_back(1);
    v.push_back(3);
    v.push_back(5);
    v.push_back(7);
    // at(int idx); //返回索引 idx 所指的数据，如果 idx 越界，抛出
    out_of_range 异常。
            cout
        << "v.at(3) = " << v.at(3) << endl;
    // operator[](int idx); //返回索引 idx 所指的数据，越界时，不会报错
    cout << "v[2] = " << v[100] << endl;
    // front(); //返回容器中第一个数据元素
    cout << v.front() << endl;
    // back(); //返回容器中最后一个数据元素
    cout << v.back() << endl;
}

大小相关

语法

int size(); // 返回容器中元素的个数
bool empty(); //判断容器是否为空， 返回bool值（0， 1）
void resize(int num); //重新指定容器的长度为 num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
void resize(int num, elem); //重新指定容器的长度为 num，若容器变长，则以elem 值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
int capacity(); //容器的容量
void reserve(int len); //容器预留 len 个元素长度

示例

void fun07()
{
    vector<int> v;
    v.push_back(1);
    v.push_back(3);
    v.push_back(5);
    v.push_back(7);
    v.push_back(9);
    // int size(); // 返回容器中元素的个数
    // cout << v.size() << endl;
    // bool empty(); //判断容器是否为空， 返回bool值（0， 1）
    // cout << v.empty() << endl;
    // void resize(int num); //重新指定容器的长度为 num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
    // v.resize(2);
    // void resize(int num, elem); //重新指定容器的长度为 num，若容器变长，则以 elem 值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
    // v.resize(10,10);
    // int capacity(); //容器的容量
    cout
        << v.capacity() << endl;
    // void reserve(int len); //容器预留 len 个元素长度
    v.reserve(10);
    cout << v.capacity() << endl;
    // auto it = v.begin();
    // while(it != v.end())
    // {
    // cout << *it << endl;
    // it++;
    // }
}
void fun08()
{
    vector<int> v;
    v.push_back(1);
    v.push_back(3);
    v.push_back(5);
    v.push_back(7);
    v.push_back(9);
    cout << "v的大小 = " << v.size() << endl;
    cout << "v的容量 = " << v.capacity() << endl;
    vector<int>(v).swap(v);
    cout << "v的大小 = " << v.size() << endl;
    cout << "v的容量 = " << v.capacity() << endl;
}

存储自定义类型

示例

class Per
{
public:
    char *name;
    Per(char *name)
    {
        this->name = name;
    }
};
void fun09()
{
    vector<Per> ps;
    ps.push_back(Per("张三"));
    ps.push_back(Per("李四"));
    ps.push_back(Per("王五"));
    for (auto it = ps.begin(); it != ps.end(); it++)
    {
        cout << (*it).name << endl;
    }
}

容器嵌套

void fun10()
{
    vector<int> v1;
    v1.push_back(10);
    v1.push_back(20);
    v1.push_back(30);
    v1.push_back(40);
    v1.push_back(50);
    vector<int> v2;
    v2.push_back(100);
    v2.push_back(200);
    v2.push_back(300);
    v2.push_back(400);
    v2.push_back(500);
    vector<int> v3;
    v3.push_back(1000);
    v3.push_back(2000);
    v3.push_back(3000);
    v3.push_back(4000);
    v3.push_back(5000);
    vector<vector<int>> v;
    v.push_back(v1);
    v.push_back(v2);
    v.push_back(v3);
    vector<vector<int>>::iterator it = v.begin();
    for (; it != v.end(); it++)
    {
        //*it == vector<int>
        vector<int>::iterator mit = (*it).begin();
        for (; mit != (*it).end(); mit++)
        {
            //*mit==int
            cout << *mit << " ";
        }
        cout << endl;
    }
}

C deque

概述

>deque 则是一种双向开口的连续线性空间。所谓的双向开口，意思是可以在头尾两端分
别做元素的插入和删除操作
	数据结构:数组

与vector的区别

• 一 在 于 deque 允 许 使 用 常 数 项 时 间 对 头 端 进 行 元 素 的 插 入 和 删 除 操 作 。

• 二 在 于 deque 没 有 容 量 的 概 念 ， 因 为 它 是 动 态 的 以 分 段 连 续 空 间 组 合 而 成 ， 随 时 可 以

  增 加 一 段 新 的 空 间 并 链 接 起 来

api

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

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

//大 小 操 作
deque.size();//返 回 容 器 中 元 素 的 个 数
deque.empty();//判 断 容 器 是 否 为 空


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

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

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

//数 据 存 取
at(idx);//返 回 索 引  idx 所 指 的 数 据 ， 如 果  idx 越 界 ， 抛 出  out_of_range。
operator[];//返 回 索 引  idx 所 指 的 数 据 ， 如 果  idx 越 界 ， 不 抛 出 异 常 ， 直 接 出错 。

front();//返 回 第 一 个 数 据 。
back();//返 回 最 后 一 个 数 据

//插 入 操 作
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 位 置 的 数 据 ， 返 回 下 一 个 数 据 的 位 置 。

D stack

概念

栈 (先 进 后 出 ,又 名 水 桶 ),单 向 开 口 ,没 有 迭 代 器

api

构 造 函 数
stack<T> stkT;//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(int argc, char const *argv[])
{
    stack<int> s;
    s.push(1);
    s.push(5);
    s.push(3);
    s.push(7);
    // while(s.size() != 0)
    // {
    // cout << s.top() << endl;
    // s.pop();
    // }
    while (!s.empty())
    {
        cout << s.top() << endl;
        s.pop();
    }
    return 0;
}

E queue

概念

• 队 列 (先 进 先 出 ),又 名 水 管 ,双 向 开 口 ,没 有 迭 代 器
  • 队 头 :出 数 据
  • 队 尾 :入 数 据

api

构 造 函 数

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

存 取 、 插 入 和 删 除 操 作

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

赋 值 操 作

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

大 小 操 作

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

示例

#include <iostream>
#include <queue>
using namespace std;
int main(int argc, char const *argv[])
{
    queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);
    while (!q.empty())
    {
        cout << q.front() << endl;
        q.pop();
    }
    return 0;
}

E List

概念

• 基 于 双 向 链 表 的 ,离 散 存 储 的 ,双 向 迭 代 器 ,元 素 可 重 复
  • 数 据 结 构 :链 表

双 向 迭 代 器 :可 以 ++,–,但 是 不 能 +,-

api

构 造 函 数

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

数 据 元 素 插 入 和 删 除 操 作

   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 值 匹 配 的 元 素 。

大 小 操 作

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

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

赋 值 操 作

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

数 据 的 存 取

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

反 转 排 序

   reverse();//反 转 链 表 ， 比 如  lst 包 含  1,3,5 元 素 ， 运 行 此 方 法 后 ， lst 就 包含  5,3,1元 素 
   sort(); //list 排 序

示例

#include <iostream>
#include <list>
#include <string>
using namespace std;
void showList(list<int> nums)
{
    list<int>::iterator it = nums.begin();
    for (; it != nums.end(); it++)
    {
        cout << *it << endl;
    }
}
void fun01()
{
    list<int> nums;
    nums.push_back(1);
    nums.push_back(5);
    nums.push_back(3);
    nums.push_back(7);
    nums.reverse();
    showList(nums);
}
void fun02()
{
    list<int> nums;
    nums.push_back(1);
    nums.push_back(5);
    nums.push_back(3);
    nums.push_back(7);
    nums.sort();
    showList(nums);
}
void fun03()
{
    list<int> nums;
    nums.push_back(1);
    nums.push_back(5);
    nums.push_back(3);
    nums.push_back(7);
    nums.sort();
    nums.reverse();
    showList(nums);
}
class Person
{
private:
    string name;

public:
    Person()
    {
        name = "";
    }
    Person(char *name)
    {
        this->name = name;
    }
    Person(const Person &p)
    {
        this->name = p.name;
    }
    string &getName()
    {
        return name;
    }
};
int main(int argc, char const *argv[])
{
    list<Person> ps;
    ps.push_back(Person("张三"));
    ps.push_back(Person("李四"));
    ps.push_back(Person("王五"));
    list<Person>::iterator it;
    for (it = ps.begin(); it != ps.end(); it++)
    {
        cout << (*it).getName() << endl;
    }
    return 0;
}

F set/multiset

set特点

• Set 的 特 性 是 。 所 有 元 素 都 会 根 据 元 素 的 键 值 自 动 被 排 序 。
• Set 容 器 的 键 值 和 实 值 是 同 一 个 值 。
• Set 不 允 许 两 个 元 素 有 相 同 的 键 值 。
• Set容 器 的 迭 代 器 是 只 读 迭 代 器 。 插 入 数 据 后 不 允 许 修 改 set的 键 值 。
  • 数 据 结 构 :红 黑 树

注 意 :

如 果 存 入 的 值 大 于 原 有 的 值 ,此 时 x > y 为 真 ,存 入 的 值 在 原 有 值 左 边

如 果 存 储 的 值 小 于 原 有 的 值 ,此 时 x > y 为 假 ,交 换 在 比 较

如 果 交 换 后 ,存 储 的 值 为 y,原有值的为 x,此 时 x > y 为真 ,存入的值不应该在原有值 左 边

如 果 交 换 后 ,存 储 的 值 为 y,原 有 值 的 为 x,此 时 x > y 为 假 ,此时证明不符合其存储 原 则

multiset特点

• multiset 特 性 及 用 法 和 set 完 全 相 同 ， 唯 一 的 差 别 在 于 它 允 许 键 值 重 复 。
  • 数 据 结 构 :红 黑 树

api

构 造 函 数

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

赋 值 操 作

set& operator=(const set &st);//重 载 等 号 操 作 符
swap(st);//交 换 两 个 集 合 容 器

大 小 操 作

size();//返 回 容 器 中 元 素 的 数 目
empty();//判 断 容 器 是 否 为 空

插 入 和 删 除 操 作

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

查 找 操 作

find(key);//查 找 键  key 是 否 存 在 ,若 存 在 ， 返回该键的元素的迭代器；若不存在返回set.end();
count(key);//查 找 键  key 的 元 素 个 数
lower_bound(keyElem);//下 限 返 回 第 一 个  key>=keyElem 元 素 的 迭 代 器 。
upper_bound(keyElem);//上 限 返 回 第 一 个  key>keyElem 元 素 的 迭 代 器 。
equal_range(keyElem);//返 回 容 器 中  key 与  keyElem 相 等 的 上 下 限 的 两 个 迭 代器 。

示例

#include <iostream>
#include <set>
using namespace std;
void fun01()
{
    set<int> s;
    s.insert(3);
    s.insert(2);
    s.insert(6);
    s.insert(5);
    s.insert(1);
    s.insert(1); // 存储的元素不允许重复
    set<int>::const_iterator it = s.begin();
    while (it != s.end())
    {
        cout << *it << endl;
        it++;
    }
}
void fun02()
{
    multiset<int> s;
    s.insert(3);
    s.insert(2);
    s.insert(6);
    s.insert(5);
    s.insert(1);
    s.insert(1); // 存储的元素允许重复
    multiset<int>::const_iterator it = s.begin();
    while (it != s.end())
    {
        cout << *it << endl;
        it++;
    }
}
class MyCompare
{
public:
    bool operator()(int x, int y)
    {
        return x > y;
    }
};
void fun03()
{
    // 自定义比较器
    set<int, MyCompare> s;
    s.insert(3);
    s.insert(4);
    // s.insert(2);
    // s.insert(5);
    set<int>::const_iterator it = s.begin();
    while (it != s.end())
    {
        cout << *it << endl;
        it++;
    }
}

class MyCompareP;
class Person
{
    friend class MyCompareP;
    friend void fun04();

private:
    string name;
    int age;

public:
    Person()
    {
        name = "";
    }
    Person(char *name, int age)
    {
        this->name = name;
        this->age = age;
    }
    Person(const Person &p)
    {
        this->name = p.name;
        this->age = p.age;
    }
    string &getName()
    {
        return name;
    }
};
class MyCompareP
{
public:
    bool operator()(Person p1, Person p2)
    {
        return p1.age <= p2.age;
    }
};
void fun04()
{
    set<Person, MyCompareP> s;
    s.insert(Person("张三", 18));
    s.insert(Person("李四", 16));
    s.insert(Person("王五", 19));
    s.insert(Person("赵六", 18));
    cout << "size = " << s.size() << endl;
    set<Person>::const_iterator it;
    for (it = s.begin(); it != s.end(); it++)
    {
        cout << (*it).name << endl;
    }
}
int main(int argc, char const *argv[])
{
    fun04();
    return 0;
}

#include <iostream>
#include <set>
#include <map>
using namespace std;
int main(int argc, char const *argv[])
{
    set<int> ns;
    ns.insert(10);
    ns.insert(20);
    ns.insert(30);
    ns.insert(40);
    // lower_bound(keyElem);//下限返回第一个 key>=keyElem 元素的迭代器。
    auto it01 = ns.lower_bound(30);
    cout << *it01 << endl;
    // upper_bound(keyElem);//上限返回第一个 key>keyElem 元素的迭代器
    auto it02 = ns.upper_bound(30);
    cout << *it02 << endl;
    pair<set<int>::iterator, set<int>::iterator> p = ns.equal_range(30);
    cout << *(p.first) << endl;  // 键是下限
    cout << *(p.second) << endl; // 值是上限
    return 0;
}

G map/multimap

map概述

• 键 值 对 的 形 式 存 储 数 据 ,一 个 键 值 对 称 为 一 个 对 组

• 这 一 对 值 可 以 具 有 不 同 的 数 据 类 型 ， 两 个 值 可 以 分 别 用 pair(对 组 ) 的 两 个 公 共 的 成 员

  变 量 first(键 ) 和 second(值 )访 问 。

不 允 许 键 重 复

multimap概述

允 许 键 重 复

api

map 构 造 函 数
map<T1, T2> mapTT;//map 默 认 构 造 函 数 : 
    T1:键 的 数 据 类 型 ,要 有 可 比 较 性 ,基 本 数 据 类 型 都 有 可 比 性
    T2:值 的 数 据 类 型
map(const map &mp);//拷 贝 构 造 函 数

map 赋 值 操 作
map& operator=(const map &mp);//重 载 等 号 操 作 符
swap(mp);//交 换 两 个 集 合 容 器

map 大 小 操 作
size();//返 回 容 器 中 元 素 的 数 目
empty();//判 断 容 器 是 否 为 空

map 插 入 数 据 元 素 操 作
map.insert(...); //往 容 器 插 入 元 素 ， 返 回  pair<iterator,bool>

map 删 除 操 作
clear();//删 除 所 有 元 素
erase(pos);//删 除  pos 迭 代 器 所 指 的 元 素 ， 返 回 下 一 个 元 素 的 迭 代 器 。
erase(beg,end);//删 除 区 间 [beg,end)的 所 有 元 素  ， 返 回 下 一 个 元 素 的 迭 代 器 。
erase(keyElem);//删 除 容 器 中  key 为  keyElem 的 对 组 。

map 查 找 操 作
find(key);//查找键 key 是否存在,若存在返回该键的元素的迭代器；若不存在，返回  map.end();
count(keyElem);//返回容器中key为keyElem的对组个数。对map来说,要么是 0，要么是1,对multimap 来说,值可能大于1。
lower_bound(keyElem);//返 回 第 一 个  key>=keyElem 元 素 的 迭 代 器 。
upper_bound(keyElem);//返 回 第 一 个  key>keyElem 元 素 的 迭 代 器 。
equal_range(keyElem);//返 回 容 器 中  key 与  keyElem 相 等 的 上 下 限 的 两 个 迭 代
器 。

总结

vector 单 端 动 态 数 组 随 机 访 问 迭 代 器 (重 点 )
比 如 软 件 历 史 操 作 记 录 的 存 储 ， 我 们 经 常 要 查 看 历 史 记 录 ， 比 如 上 一 次 的 记 录 ， 上 上 次

的 记 录 ， 但 却 不 会 去 删 除 记 录 ， 因 为 记 录 是 事 实 的 描 述 。

数 据 结 构 :数 组

deque： 双 端 动 态 数 组 随 机 访 问 迭 代 器

deque 的 使 用 场 景 ： 比 如 排 队 购 票 系 统 ， 对 排 队 者 的 存 储 可 以 采 用 deque， 支 持 头 端
的 快 速 移 除 ， 尾 端 的 快 速 添 加

stack栈 容 器 没 有 迭 代 器 先 进 后 出
queue队 列 容 器 没 有 迭 代 器 先 进 先 出

list 链 表 容 器 双 向 迭 代 器 (重 点 )
比 如 公 交 车 乘 客 的 存 储 ， 随 时 可 能 有 乘 客 下 车 ， 支 持 频 繁 的 不 确 实 位 置 元 素 的 移 除 插 入

数 据 结 构 :双 链 表

set 容 器 只 有 键 值 键 值 不 能 重 复 自 动 排 序 只 读 迭 代 器
比 如 对 手 机 游 戏 的 个 人 得 分 记 录 的 存 储 ， 存 储 要 求 从 高 分 到 低 分 的 顺 序 排 列 。
数 据 结 构 :红 黑 树

map容 器 ： 键 值 -实 值 成 对 出 现 键 值 不 能 重 复 自 动 排 序 只 读 迭 代 器 (重 点 )
比 如 按 ID 号 存 储 十 万 个 用 户 ， 想 要 快 速 要 通 过 ID 查 找 对 应 的 用 户 。
数 据 结 构 :红 黑 树