【C++】STL 容器类型和API函数实现

STL 库

1. STL 库概述

STL 是 C++ 提供的面向【容器，迭代器，算法】相关的一个工具库/标准库。

容器包括: string, vector, deque, queue, list, map, set, stack...

迭代器: 输出，前向，双向，随机

算法: 查询，替换，排序，翻转，转换

学习 STL 要求

熟练掌握 STL 中相关容器使用和配套函数

针对于算法使用，熟练掌握可以利用文档形式进行函数调用和算法使用。

高阶情况可以实现 STL 中核心容器的相关代码实现，建议完成 string vector list

2. string 容器【重点】

2.1 string 概述

C++ 中的字符串数据，提供了大量操作函数，使用便捷程度相较于 C 语言字符串有较大的提升。C++ 字符串底层核心结构是一个【可变长字符数组结构】

2.2 string 构造函数

string();//创建一个空的字符串 例如: string str; 
string(const string& str);//使用一个 string 对象初始化另一个 string 对象
string(const char* s);//使用字符串 s 初始化
string(int n, char c);//使用 n 个字符 c 初始化 v

#include <iostream>

using namespace std;

int main(int argc, char const *argv[])
{
    string str1;
    string str2("注意交通安全!!!");
    string str3(str2);
    string str5(10, 'A');

    cout << "str1 : " << str1 << endl;
    cout << "str2 : " << str2 << endl;
    cout << "str3 : " << str3 << endl;
    cout << "str5 : " << str5 << endl;

    cout << "---------------------------------------" << endl;

    string *p_str1 = new string;
    string *p_str2 = new string("道路千万条，安全第一条，行车不规范，亲人两行泪");
    string *p_str3 = new string(*p_str2);
    string *p_str5 = new string(10, 'B');

    cout << "*p_str1 : " << *p_str1 << endl;
    cout << "*p_str2 : " << *p_str2 << endl;
    cout << "*p_str3 : " << *p_str3 << endl;
    cout << "*p_str5 : " << *p_str5 << endl;

    delete p_str1;
    delete p_str2;
    delete p_str3;
    delete p_str5;

    return 0;
}

2.3 string 基本赋值操作

string &operator=(const char* s);//char*类型字符串 赋值给当前的字符串
string &operator=(const string &s);//把C++字符串 s 赋给当前的字符串
string &operator=(char c);//字符赋值给当前的字符串
string &assign(const string &s);//把C++字符串 s 赋给当前的字符串
string &assign(const char *s);//把C字符串 s 赋给当前的字符串
string &assign(const char *s, int n);//把字符串 s 的前 n 个字符赋给当前的字符串
string &assign(size_t n, char c);//将 n 个字符 c 赋值给当前字符串
string& assign(const string &s);//把字符串 s 赋给当前字符串
string& assign(const string &s, int start, int n);//将 s 从 start 开始 n 个

#include <iostream>

using namespace std;

int main(int argc, char const *argv[])
{
    string str1;
    str1 = "下周一 30 度!!!";
    cout << "str1 : " << str1 << endl;

    string str2;
    str2 = str1;
    cout << "str2 : " << str2 << endl;

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

    cout << "--------------------------------" << endl;

    string str3;
    str3.assign(str2);
    cout << "str3 : " << str3 << endl;
    str3.assign("明天 13 ~ 25 度");
    cout << "str3 : " << str3 << endl;

    str3.assign("ABC", 1);
    cout << "str3 : " << str3 << endl;

    return 0;
}

2.4 string 存取字符操作

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

#include <iostream>

using namespace std;

int main(int argc, char const *argv[])
{

    string str("0123456789");
    cout << "str : " << str << endl;
  
    cout << "str[3] : " << str[3] << endl;
    cout << "str.at(3) : " << str.at(3) << endl;

    /*
    char& operator[](int n);//通过[]方式取字符
        当前操作是 string 类型重载运算符 [] 之后实现的内容
        返回值类型是 char & 引用，如果在调用过程中，例如
        str[3] 可以认为是得到了当前字符串底层下标为 3 的元素本身

        可以完成赋值和取值操作，当前案例代码中，是直接赋值字符串
        中下标为 3 的元素，可以发现字符串数据发生了改变。
    */
    str[3] = 'A';
    cout << "str : " << str << endl;

    return 0;
}

2.5 string 拼接操作

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

#include <iostream>

using namespace std;

int main(int argc, char const *argv[])
{
    string str("ABC");
    str += "123";

    string str2("中");
    str += str2;  
    cout << "str : " << str << endl;

    str += 'G';
    cout << "str : " << str << endl;

    str.append("我想吃羊肉泡馍");
    cout << "str : " << str << endl;

    str.append("中中中", 6);
    cout << "str : " << str << endl;

    string str3("012345678");
    str.append(str3, 2, 5);
    cout << "str : " << str << endl;

    str.append(10, '?');
    cout << "str : " << str << endl;

    return 0;
}

2.6 string 查找和替换

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

#include <iostream>

using namespace std;

int main(int argc, char const *argv[])
{
    string str("0123456789");

    size_t index = str.find("567");
    cout << "index : " << index << endl;

    string str2("666");

    index = str.find(str2);
    cout << "index : " << index << endl;

    index = str.find("012", 2);
    cout << "index : " << index << endl;

    index = str.find("122", 0, 2);
    cout << "index : " << index << endl;

    cout << "------------------------------------------" << endl;

    string str3("ABCDEFG");
    string str5("798");

    str3.replace(1, 2, "0123");
    cout << "str2 : " << str3 << endl;

    str3.replace(1, 2, str5);
    cout << "str2 : " << str3 << endl;

    return 0;
}

2.7 string 比较

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


#include <iostream>

using namespace std;

/*
compare 函数在>时返回 1，<时返回 -1，==时返回 0。
比较区分大小写，比较时参考字典顺序，排越前面的越小。
大写的 A 比小写的 a 小。

memset(void *p, int b, size_t count);
memmove(void * dst, void * src, size_t n);
memcpy(void * dst, void * src, size_t n);
memcmp(void * p1, void * p2, size_t n);
memchr(void * p1, int ch);

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

int main(int argc, char const *argv[])
{
    string str("ABCDEFG");

    /*
    compare
    Comparetor
    */
    cout << "compare : " << str.compare("ABCdEFG") << endl;

    string str2("abcdefg");
    cout << "compare : " << str2.compare(str) << endl;

    return 0;
}

2.8 string 子串，插入和删除操作

/*
substr 函数返回值类型是一个 string 对象，因为在函数内部需要根据调用函数 string 对象，以及限制的截取下标和字符个数范围，得到一个新的 string 对象，返回值就是实例化得到的新对象。
【当前函数返回值不是引用】
*/
string substr(int pos = 0, int n = npos) const;//返回由 pos 开始的 n 个字符

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>

using namespace std;

int main(int argc, char const *argv[])
{
    string str("0123456789");

    string sub_str = str.substr(2, 5);
    cout << "sub_str : " << sub_str << endl;
  
    str.insert(2, "你好!");
    cout << "str : " << str << endl;

    string str2("朋友!阿达西!");
    str.insert(2, str2);
    cout << "str : " << str << endl;

    str.insert(2, 10, '0');
    cout << "str : " << str << endl;

    str.erase(2, 5);
    cout << "str : " << str << endl;

    return 0;
}

2.9 string 和 C 语言字符串转换

const char* c_str(); // C++ string 类型转换为 C 语言字符串常量
// C语言字符串转换 C++ string 类型，可以使用构造函数，assign 赋值函数，append 转换函数

#include <iostream>

using namespace std;

int main(int argc, char const *argv[])
{
    string str(10, 'A');

    const char * c_str = str.c_str();

    printf("%s\n", c_str);
    return 0;
}

3. vector 单向可变长数组【重点】

3.1 vector 结构概述

vector 是一个可变长单向操作数组，存储数据类型为模版类型，需要用户在实例化 vector 对象时，进行明确的数据类型告知。

vector 支持数组的下标操作方式，整体访问数据效率较高。同时支持迭代器 Iterator 外部操作形式。另外 vector 底层数组的扩容形式十分重要！！！

3.2 迭代器引入

vector 使用了模版，限制当前底层存储的数据类型。目前使用的函数有
vector(); // 构造 vector 对象
push_back(E element); // 将指定数据类型对象，存储到 Vector 容器中。

#include <iostream>
// 如果需要使用 vector 容器，必须导入对应的头文件
#include <vector>

using namespace std;

int main(int argc, char const *argv[])
{
    vector<string> v1;

    v1.push_back("胡辣汤");
    v1.push_back("羊肉汤");
    v1.push_back("羊杂汤");
    v1.push_back("丸子汤");
    v1.push_back("驴肉汤");
    v1.push_back("牛肉汤");
    v1.push_back("牛杂汤");
    v1.push_back("豆腐汤");
    v1.push_back("白菜汤");

    /*
    迭代器相关内容
        1. 迭代器数据类型
            vector<T>::iterator
        2. 相关函数，利用 vector 对象调用
            vector<T>::iterator begin();
                获取当前容器中指向下标为 0 的元素迭代器对象。
            vector<T>::iterator end();
                获取当前容器中指向下标为 size 的元素迭代器对象。超出
                当前有效数据范围，类似于 EOF(-1) 结束标记
        3. 迭代器是一个操作当前数据的外部指针。
    */
    vector<string>::iterator it1 = v1.begin();
    cout << "当前迭代器指向的数据内容 : " << *it1 << endl;

    it1 += 1;
    cout << "当前迭代器指向的数据内容 : " << *it1 << endl;

    it1 += 1;
    cout << "当前迭代器指向的数据内容 : " << *it1 << endl;

    cout << "-------------------------------------" << endl;

    vector<string>::iterator it_end = v1.end();
    cout << "end() 迭代器获取到的数据 : " << *it_end << endl;

    it_end -= 1;
    cout << "end() 迭代器获取到的数据 : " << *it_end << endl;

    cout << "-------------------------------------" << endl;

    // 遍历操作
    vector<string>::iterator it_loop = v1.begin();

    while (it_loop != v1.end())
    {
        cout << "value : " << *it_loop << endl;
        it_loop += 1;
    }

    cout << "-------------------------------------" << endl;

    // 可以根据将迭代器认为是一个指针直接访问目标元素
    vector<string>::iterator it_pointer = v1.begin();

    it_pointer += 5;

    cout << "it_pointer += 5 : " << *it_pointer << endl;

    return 0;
}

3.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;

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

void show_vector(vector<string>::iterator begin, vector<string>::iterator end);

int main(int argc, char const *argv[])
{
    vector<string> v1;

    v1.push_back("胡辣汤");
    v1.push_back("羊肉汤");
    v1.push_back("羊杂汤");
    v1.push_back("丸子汤");
    v1.push_back("驴肉汤");
    v1.push_back("牛肉汤");
    v1.push_back("牛杂汤");
    v1.push_back("豆腐汤");
    v1.push_back("白菜汤");

    vector<string> v2(v1.begin() + 3, v1.end() - 2);

    show_vector(v2.begin(), v2.end());

    cout << "-------------------------------------" << endl;

    vector<string> v3(10, "羊肉冲汤");

    show_vector(v3.begin(), v3.end());

    cout << "-------------------------------------" << endl;

    vector<string> v5(v1);

    show_vector(v5.begin(), v5.end());
  
    cout << "-------------------------------------" << endl;
    return 0;
}

void show_vector(vector<string>::iterator begin, vector<string>::iterator end)
{
    while (begin != end)
    {
        cout << "value : " << *begin << endl;
        begin += 1;
    }
}

3.3 vector 常用赋值操作

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

#include <iostream>
#include <vector>

using namespace std;

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

void show_vector(vector<string>::iterator begin, vector<string>::iterator end);

int main(int argc, char const *argv[])
{
    vector<string> v1;

    v1.push_back("胡辣汤");
    v1.push_back("羊肉汤");
    v1.push_back("羊杂汤");
    v1.push_back("丸子汤");
    v1.push_back("驴肉汤");
    v1.push_back("牛肉汤");
    v1.push_back("牛杂汤");
    v1.push_back("豆腐汤");
    v1.push_back("白菜汤");

    vector<string> v2;
    cout << "v2.size() : " << v2.size() << endl;
    cout << "v2.capacity() : " << v2.capacity() << endl;

    v2.assign(v1.begin() + 2, v1.end());

    cout << "v2.size() : " << v2.size() << endl;
    cout << "v2.capacity() : " << v2.capacity() << endl;

    show_vector(v2.begin(), v2.end());

    v2.push_back("滚蛋汤");
    cout << "v2.size() : " << v2.size() << endl;
    cout << "v2.capacity() : " << v2.capacity() << endl;

    cout << "------------------------------------" << endl;

    vector<string> v3;

    v3.assign(10, "方便面");
    cout << "v3.size() : " << v3.size() << endl;
    cout << "v3.capacity() : " << v3.capacity() << endl;
    show_vector(v3.begin(), v3.end());

    cout << "------------------------------------" << endl;

    vector<string> v5(5, "炒饼丝");
    vector<string> v6(10, "烩饼");

    cout << "v5.size() : " << v5.size() << endl;            // 5
    cout << "v5.capacity() : " << v5.capacity() << endl;    // 5
    cout << "v6.size() : " << v6.size() << endl;            // 10
    cout << "v6.capacity() : " << v6.capacity() << endl;    // 10

    /*
    swap 函数是交换两个 vector 容器中存储的数据，同时考虑容量和有效元素个数
    改变问题
    较大容量 vector 会进行缩容操作，降低内存占用
    */
    v5.swap(v6);

    cout << "v5.size() : " << v5.size() << endl;            // 10
    cout << "v5.capacity() : " << v5.capacity() << endl;    // 10
    cout << "v6.size() : " << v6.size() << endl;            // 5
    cout << "v6.capacity() : " << v6.capacity() << endl;    // 5
    return 0;
}

void show_vector(vector<string>::iterator begin, vector<string>::iterator end)
{
    while (begin != end)
    {
        cout << "value : " << *begin << endl;
        begin += 1;
    }
}

3.4 vector 大小操作

size();//返回容器中元素的个数
empty();//判断容器是否为空 { return 0 == size; }
capacity();//容器的容量

reserve(int len);//容器预留 len 个元素长度，预留位置不初始化，元素不可访问。
resize(int num);//重新指定容器的长度为 num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
resize(int num, elem);//重新指定容器的长度为 num，若容器变长，则以 elem 值填充新位置。如果容器变短，则末尾超出容器长>度的元素被删除。

#include <iostream>
#include <vector>

using namespace std;

/*
size();//返回容器中元素的个数
empty();//判断容器是否为空 { return 0 == size; }
capacity();//容器的容量

reserve(int len);//容器预留 len 个元素长度，预留位置不初始化，元素不可访问。
resize(int num);//重新指定容器的长度为 num，若容器变长，
    则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
resize(int num, elem);//重新指定容器的长度为 num，若容器变长，
    则以 elem 值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
*/

void show_vector(vector<string>::iterator begin, vector<string>::iterator end);

int main(int argc, char const *argv[])
{
    /*
    vector 容量在不满足当前有效元素所需，默认扩容是原本容量的 2 倍
        new_capacity = old_capacity << 1;
    在不同的 C++ 版本中，存在扩容大约 1.5 倍情况
        new_capacity = old_capacity + (old_capacity >> 1);
    */

    vector<string> v1;

    cout << "v1.size() : " << v1.size() << endl;
    cout << "v1.capacity() : " << v1.capacity() << endl;

    v1.push_back("扁粉菜 BFC");
    cout << "v1.size() : " << v1.size() << endl;
    cout << "v1.capacity() : " << v1.capacity() << endl;

    v1.push_back("胡辣汤");
    cout << "v1.size() : " << v1.size() << endl;
    cout << "v1.capacity() : " << v1.capacity() << endl;

    v1.push_back("饸饹面");
    v1.push_back("河北邯郸正宗安徽太和板面");
    cout << "v1.size() : " << v1.size() << endl;
    cout << "v1.capacity() : " << v1.capacity() << endl;

    v1.push_back("重庆鸡公煲");
    cout << "v1.size() : " << v1.size() << endl;
    cout << "v1.capacity() : " << v1.capacity() << endl;

    bool ret = v1.empty();
    cout << "ret : " << ret << endl;

    v1.erase(v1.begin(), v1.end());
    ret = v1.empty();
    cout << "ret : " << ret << endl;

    cout << "-----------------------------" << endl;

    v1.push_back("God Use VPN");
    v1.push_back("道口烧鸡");
    v1.push_back("臧营桥牛肉");
    v1.push_back("裹凉皮");
    v1.push_back("洗碗凉皮");
    v1.push_back("擀面皮");
    cout << "v1.size() : " << v1.size() << endl;
    cout << "v1.capacity() : " << v1.capacity() << endl;

    v1.resize(10);
    cout << "v1.size() : " << v1.size() << endl;
    cout << "v1.capacity() : " << v1.capacity() << endl;

    show_vector(v1.begin(), v1.end());

    cout << "-----------------------------" << endl;

    v1.resize(15, "清丰大烧饼");
    cout << "v1.size() : " << v1.size() << endl;
    cout << "v1.capacity() : " << v1.capacity() << endl;

    show_vector(v1.begin(), v1.end());
    cout << "-----------------------------" << endl;

    v1.resize(3);
    cout << "v1.size() : " << v1.size() << endl;
    cout << "v1.capacity() : " << v1.capacity() << endl;

    show_vector(v1.begin(), v1.end());

    cout << "-----------------------------" << endl;

    vector<string> v2;
    cout << "v2.size() : " << v2.size() << endl;
    cout << "v2.capacity() : " << v2.capacity() << endl;

    /*
    如果知晓之后的数据个数，可以利用 reserve 函数进行空间预留。
    */
    v2.reserve(10);
    cout << "v2.size() : " << v2.size() << endl;
    cout << "v2.capacity() : " << v2.capacity() << endl;

    cout << "-----------------------------" << endl;
    return 0;
}

void show_vector(vector<string>::iterator begin, vector<string>::iterator end)
{
    while (begin != end)
    {
        cout << "value : " << *begin << endl;
        begin += 1;
    }
}

3.5 vector 数据存取操作

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

#include <iostream>
#include <vector>

using namespace std;

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

void show_vector(vector<string>::iterator begin, vector<string>::iterator end);

int main(int argc, char const *argv[])
{
    vector<string> v1;

    v1.push_back("胡辣汤");
    v1.push_back("羊肉汤");
    v1.push_back("羊杂汤");
    v1.push_back("丸子汤");
    v1.push_back("驴肉汤");
    v1.push_back("牛肉汤");
    v1.push_back("牛杂汤");
    v1.push_back("豆腐汤");
    v1.push_back("白菜汤");

    /*
    当前函数的声明可以认为是
        string &at(size_t pos);
    */
    string &ref = v1.at(5);
    cout << "ref : " << ref << endl;

    ref = "汤";

    show_vector(v1.begin(), v1.end());

    cout << "------------------------" << endl;
    cout << "v1[2] : " << v1[2] << endl;
    v1[2] = "sha汤";
    show_vector(v1.begin(), v1.end());

    cout << "------------------------" << endl;

    /*
    string &front()
    */
    cout << "v1.front() : " << v1.front() << endl;
    v1.front() = "牛排胡辣汤";

    /*
    string &back()
    */
    cout << "v1.back() : " << v1.back() << endl;


    v1.back() = "玉米排骨汤";
    cout << "------------------------" << endl;

    show_vector(v1.begin(), v1.end());


    return 0;
}

void show_vector(vector<string>::iterator begin, vector<string>::iterator end)
{
    while (begin != end)
    {
        cout << "value : " << *begin << endl;
        begin += 1;
    }
}

3.6 vector 插入和删除操作

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

4. deque 双向可变长数组

4.1 底层数据存储分析

底层结构可以认为是一个数组 + 链表。链表作为数据的中控结点，数组作为数据的连续存储空间。

03-deque底层结构

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

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

void show_deque(deque<string>::iterator begin, deque<string>::iterator end);

int main(int argc, char const *argv[])
{
    deque<string> d1;

    d1.push_back("于东来");
    d1.push_back("雷军");
    d1.push_back("崔培军");

    d1.push_front("活力28");

    show_deque(d1.begin(), d1.end());

    deque<string> d2(d1.begin() + 1, d1.end() - 1);
    cout << "------------------------------------" << endl;
    show_deque(d2.begin(), d2.end());

    cout << "------------------------------------" << endl;

    deque<string> d3(5, "雷军");
    show_deque(d3.begin(), d3.end());
    cout << "------------------------------------" << endl;

    deque<string> d5(d3);
    show_deque(d5.begin(), d5.end());
  
    return 0;
}

void show_deque(deque<string>::iterator begin, deque<string>::iterator end)
{
    while (begin != end)
    {
        cout << "value : " << *begin << endl;
        begin += 1;
    }
}

4.3 deque 赋值操作

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

4.4 deque 大小操作

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

4.5 deque 双端插入和删除操作

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

4.6 deque 数据存取

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

4.7 deque 删除操作

clear();//移除容器的所有数据
erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置。erase(pos);//删除 pos 位置

5. stack 栈

5.1 结构概述

stack 结构是以栈结构，遵从规则是 Frist In Last Out (FILO)，所有操作都从栈顶进行操作。stack 结构不支持迭代器！！！

5.2 相关函数

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

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

// stack 数据存取操作
push(elem);//向栈顶添加元素
pop();//从栈顶移除第一个元素
top();//返回栈顶元素

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

#include <iostream>
#include <stack>

using namespace std;

int main(int argc, char const *argv[])
{
    stack<string> s1;

    s1.push("丝绒拿铁");
    s1.push("精粹熬瑞白");
    s1.push("橙C美式");
    s1.push("生椰拿铁");

    while (!s1.empty())
    {
        cout << "value : " << s1.top() << endl;
        s1.pop();
    }

    stack<string> s2;

    s2.push("冰鲜柠檬水");
    s2.push("珍珠奶茶");
    s2.push("棒打鲜橙");
    s2.push("杨枝甘露");

    stack<string> s3(s2);

    while (!s3.empty())
    {
        cout << "value : " << s3.top() << endl;
        s3.pop();
    }


    return 0;
}

6. queue 队列

6.1 结构概述

队列结构是 First In First Out(FIFO)，有且只允许在队尾插入数据，从队头获取数据。不支持迭代器。可以用于后续的消息队列，任务队列，线程队列/线程池

6.2 相关函数

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

// queue 存取、插入和删除操作
push(elem);//往队尾添加元素
pop();//从队头移除第一个元素
back();//返回最后一个元素
front();//返回第一个元素

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

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

7. list 双向链表结构【重点】

7.1 list 结构概述

list 结构底层是一个双向链表结构，每一个结点都是存储 data ，next 和 prev 相关数据内容，同时支持头尾进行操作。链表效率主要体现于头尾结构操作，效率极高，中间元素内容操作，因为内存空间非连续存储，遍历搜索效率较低。

list 支持迭代器，但是迭代器功能比较少！

7.1 list 构造函数

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

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

7.3 list 大小操作

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

7.4 list 赋值操作

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

7.5 list 数据的存取

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

7.6 list 反转排序

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

8. pair 对组

8.1 案例代码

#include <iostream>

using namespace std;

int main(int argc, char const *argv[])
{
    pair<const char *, int> p1("蘑菇炒肉", 16);

    cout << "p1.first : " << p1.first << endl;
    cout << "p1.second : " << p1.second << endl;

    cout << "------------------" << endl;

    pair<string, int> p2 = make_pair("鱼香肉丝", 15);
    cout << "p2.first : " << p2.first << endl;
    cout << "p2.second : " << p2.second << endl;

    cout << "------------------" << endl;

    pair<string, int> p3 = p2;
    cout << "p3.first : " << p3.first << endl;
    cout << "p3.second : " << p3.second << endl;

    return 0;
}

8.2 底层结构分析

简要分析底层结构

template <typename T1, typename T2>
struct pair
{
	T1 first;
    T2 second;
}

可以利用模版类型的自由度，完成当前 pair 键值对模型结构，后续开发中会在 map 容器中使用。

9. set/multiset

9.1 树形结构

9.2 set 构造函数

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

9.3 set 赋值操作

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

9.4 set 大小操作

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

9.5 set 插入和删除操作

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

9.6 set 查找操作

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

10. map/multimap

10.1 存储数据形式

map 存储存储的类型都是 pair 对组，可以认为是键值对象。pair 中 first 对应的数据是键值，second 对应数据为实值/值。map 存储 pair 要求键值不得重复，存在唯一性，同时要求提供键值必须有自然顺序或者提供对应的比较方式。

10.2 map 构造函数

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

10.3 map 赋值操作

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

10.4 map 大小操作

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

10.5 map 插入数据操作

map.insert(...); //往容器插入元素，返回 pair<iterator,bool>
map<int, string> mapStu;
// 第一种 通过 pair 的方式插入对象
mapStu.insert(pair<int, string>(3, "小张"));
// 第二种 通过 pair 的方式插入对象
mapStu.inset(make_pair(-1, "校长"));
// 第三种 通过 value_type 的方式插入对象
mapStu.insert(map<int, string>::value_type(1, "小李"));
// 第四种 通过数组的方式插入值
mapStu[3] = "小刘";
mapStu[5] = "小王";

10.6 map 删除操作

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

10.7 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 相等的上下限的两个迭代器。

STL 库

1. STL 库概述

2. string 容器【重点】

2.1 string 概述

2.2 string 构造函数

2.3 string 基本赋值操作

2.4 string 存取字符操作

2.5 string 拼接操作

2.6 string 查找和替换

2.7 string 比较

2.8 string 子串， 插入和删除操作

2.9 string 和 C 语言字符串转换

3. vector 单向可变长数组【重点】

3.1 vector 结构概述

3.2 迭代器引入

3.2 vector 构造函数

3.3 vector 常用赋值操作

3.4 vector 大小操作

3.5 vector 数据存取操作

3.6 vector 插入和删除操作

4. deque 双向可变长数组

4.1 底层数据存储分析

4.2 deque 构造函数

4.3 deque 赋值操作

4.4 deque 大小操作

4.5 deque 双端插入和删除操作

4.6 deque 数据存取

4.7 deque 删除操作

5. stack 栈

5.1 结构概述

5.2 相关函数

6. queue 队列

6.1 结构概述

6.2 相关函数

7. list 双向链表结构【重点】

7.1 list 结构概述

7.1 list 构造函数

7.2 list 数据元素插入和删除操作

7.3 list 大小操作

7.4 list 赋值操作

7.5 list 数据的存取

7.6 list 反转排序

8. pair 对组

8.1 案例代码

8.2 底层结构分析

9. set/multiset

9.1 树形结构

9.2 set 构造函数

9.3 set 赋值操作

9.4 set 大小操作

9.5 set 插入和删除操作

9.6 set 查找操作

10. map/multimap

10.1 存储数据形式

10.2 map 构造函数

10.3 map 赋值操作

10.4 map 大小操作

10.5 map 插入数据操作

10.6 map 删除操作

10.7 map 查找操作

2.8 string 子串，插入和删除操作