`STL` 的基本概念

什么是 `STL`

STL ( standard template libaray - 标准模板库)：是 C++ 标准库的重要组成部分，不仅是一个可复用的组件库，而且是一个包罗数据结构与算法的软件框架。

`STL` 的六大组件

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gvE1R4s2-1661693871023)(D:/picture/image-20220710004902208.png)]

空间配置器

容器

`string`

标准库中的 `string`

链接 https://cplusplus.com/reference/string/

编码

编码：

ASCII：第一个用来表示英文的表, 计算器底层存的值和映射之间的关系, 英文
int main()
{char ch1 = 'A';char ch2 = 65;   // 在内存中存的都是65return 0;}
unicode：utf-8、utf-16 、utf-32 针对全世界的文字设计

gbk：针对中国的编码表 gb 国标

ASCII表

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zkpvLEGz-1661693871024)(D:/picture/image-20220710010914544.png)]

string 类

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Lba0d7Tt-1661693871025)(D:/picture/image-20220710011842375.png)]

string 被设计为模板 – 管理的是char 能很好兼容char

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nbLnwtL0-1661693871026)(D:/picture/image-20220710012024833.png)]

因为有不同的编码，所以把string 设计为模板

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Z9OU72Xs-1661693871027)(D:/picture/image-20220710012547010.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2BHd4dus-1661693871027)(D:/picture/image-20220710012625639.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JNSSVNg6-1661693871028)(D:/picture/image-20220710012657358.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-h0iqVXGo-1661693871028)(D:/picture/image-20220710012718440.png)]

#include <iostream>
using namespace std;int main()
{string s; // string 属于std 命名空间return 0;
}

字符串是表示字符序列的类
标准的字符串类提供了对此类对象的支持，其接口类似于标准字符容器的接口，但添加了专门用于操作单字节字符字符串的设计特性
string 类是使用char 。即作为它的字符类型，使用它的默认char_traits 和分配器类型(关于模板的更多信息，请参阅basic_string )
string 类是basic_string 模板类的一个实例，它使用char 来实例化basic_string 模板类，并用char_traits 和 allocator 作为 basic_string 的默认参数
注意，这个类独立于所使用的编码来处理字节：如果用来处理多字节或变长字符(如UTF-8 )的序列，这个
类的所有成员(如长度或大小)以及它的迭代器，将仍然按照字节(而不是实际编码的字符)来操作

常用的接口

string类对象的[常见构造](string::string - C++ Reference (cplusplus.com))

函数名称	功能说明
`string()`	构造空的`string`类对象，即空字符串
`string(const char* s)`	用`C-string` 来构造 `string` 类对象
`string(size_t n, char c)`	`string` 类对象中包含 `n` 个字符 `c`
`string(const string& s)`	拷贝构造函数

void test_string1()
{// 管理动态增长字符数组 // 字符串以 /0 结尾string s1;                // 无参构造函数        string()string s2("hello world"); // 用常量字符串来构造   string(const char* s)string s3(s2);            // 拷贝构造           string(const string& s)string s4 = s2;           // 拷贝构造           string(const string& s)string s5("https://cplusplus.com/reference/string/", 4); // 使用第一个字符串的前n个初始化 // string(const char* s, size_t n)string s6(10, 'A');       // 用10个A来初始化     string(size_t n, char c)string s7(s2, 6, 3);      // 用a的第6个位置开始 共三个 // string(const string& str, size_t pos, size_t len = npos) npos = -1 -- 正的最大string s8(s2, 6);         // 有多少取多少// template<class InputIterator>//     string (InputIterator first, InputIterator last);
}

string 类对象的容量操作

函数名称	功能说明
[size](string::size - C++ Reference (cplusplus.com))	返回字符串有效字符长度
[length](string::length - C++ Reference (cplusplus.com))	返回字符串有效字符长度
[capacity](string::capacity - C++ Reference (cplusplus.com))	返回空间总大小
[empty](string::empty - C++ Reference (cplusplus.com))	检测字符串释放为空串，是返回`true`，否则返回`false`
[clear](string::clear - C++ Reference (cplusplus.com))	清空有效字符
[reverse](string::reserve - C++ Reference (cplusplus.com))	为字符串预留空间
[resize](string::resize - C++ Reference (cplusplus.com))	将有效字符的个数该成n个，多出的空间用字符c填充

void string_test1() {string s("hello world");cout << s.length() << endl;    // 输出有效字符的长度cout << s.size() << endl;      // 输出有效字符的长度cout << s.max_size() << endl;  // 字符串最大的大小cout << s.capacity() << endl;  // 容量的大小(总空间的大小)
}

// 扩容的演示 
void string_test2() {string s;size_t sz = s.capacity();cout << "making s grow:" << endl;           // 输出标题cout << "capacity changed: " << sz << endl; // 显示当前的大小// 连续插入数据  当容量变换时 打印出最新的数据   并及时更新for (int i = 0; i < 100; ++i) {s.push_back('c');if (sz != s.capacity()) {sz = s.capacity();cout << "capacity changed: " << sz << endl;}}
}

// 提前开辟空间  
void string_test3() {string s;s.reverse(1000);           // 会最少开辟1000个空间  不需要再次扩容size_t sz = s.capacity();cout << "making s grow:" << endl;cout << "capacity changed: " << sz << endl;for (int i = 0; i < 100; ++i) {s.push_back('c');if (sz != s.capacity()) {sz = s.capacity();cout << "capacity changed: " << sz << endl;}}
}

// vs         下他们都不会缩容量
// reserve()  开空间
// resize()   开空间 + 初始化   reseize(10, 'a'); 不给初始字符时  默认是 '\0'
void string_test4() {string s1("hello");string s2("hello");s1.resize(100, 'a');s1.reverse(100);cout << "s1.size(): " << s1.size() << endl;cout << "s2.size(): " << s2.size() << endl;cout << "s1.capacity(): " << s1.capacity() << endl;cout << "s2.capacity(): " << s2.capacity() << endl;
}

// clear 只将字符串清空  不改变容量的大小 
void string_test5() {string s("hello");cout << s.size() << endl;cout << s.capacity() << endl;s.clear();cout << s.size() << endl;cout << s.capacity() << endl;
}

size() 与 length() 方法底层实现原理完全相同

引入 size() 的原因是为了与其他容器的接口保持一致，一般情况下基本都是用 size()

clear() 只是将 string 中有效字符清空，不改变底层空间大小

resize(size_t n) 与 resize(size_t n, char c) 都是将字符串中有效字符个数改变到 n 个，不同的是当字符个数增多时：

resize(n) 用0 来填充多出的元素空间

resize(size_t n, char c) 用字符c 来填充多出的元素空间

注意：resize 在改变元素个数时，如果是将元素个数增多，可能会改变底层容量的大小，如果是将元素个数减少，底层空间总大小不变

reserve(size_t res_arg = 0) ：为 string 预留空间，不改变有效元素个数，当 reserve 的参数小于 string 的底层空间总大小时，reserver 不会改变容量大小

string 类对象的访问及遍历操作

函数名称	功能说明
operator[]	返回 `pos` 位置的字符，`const string` 类对象调用
begin + end	`begin` 获取一个字符的迭代器 `end` 获取最后一个字符下一个位置的迭代器
rbegin + rend	`begin` 获取一个字符的迭代器 `end` 获取最后一个字符下一个位置的迭代器
范围 `for`	`C++11` 支持更简洁的范围 `for` 的新遍历方式(底层基于迭代器实现)

// 字符串的 遍历
void test_string1(){string s1("hello world");// 第一种方式， 下标加方括号// operator[] 的实现  for (size_t i = 0; i < s1.size(); i++) cout << s1[i] << " ";cout << endl;  // 第二种方式 迭代器// begin() 指向第一个位置// end()   指向最后一个数据的下一个位置 [begin(), end())string::iterator it = s1.begin();while (it != s1.end()) {cout << *it << " "; ++it;}cout << endl;// 第三种方式 范围forfor (auto ch: s1) cout << ch << " ";cout << endl;    // 反向迭代器string::reverse_iterator rit = s1.rbegin();while (rit != s1.rend()) {cout << *it << " ";++it;}cout << endl;// 只读迭代器Func(s1);// 反向只读迭代器// string::const_revese_iterator rit = s1.rbegin();auto rit = s1.rbegin();while (rit != s1.rend()) {cout << *it << " ";++it;}cout << endl;
}
void Func(const string& s) {string::const_iterator it = s.begin();while (it != r.end()) {cout << *it << " ";++it;}cout << endl;
}

operatpr[] 和 at 的区别，功能相同，不同之处在于operator 会断言 at 会抛出异常

back front 访问最后一个字符和访问第一个字符

迭代器：像指针一样的东西

template <class T>
class basic_string {
public:// 重新开辟 是为了可以动态的增减basic_string(const T* str) {size_t len = strlen(str);_str = new T[len + 1];strcpy(_str, str);}// 返回引用 可以修改T& operator[](size_t pos) {return _str[pos];}
private:const T* _str;size_t _size;size_t _capacity;
}

string类对象的修改操作

函数名称	功能说明
push_back	在字符串后尾插字符`c`
append	在字符串后追加一个字符串
operator+=	在字符串后追加字符串 `str`
c str	返回 `C` 格式字符串
find + npos	从字符串 `pos` 位置开始往后找字符 `c` ，返回该字符在字符串中的位置
rfind	从字符串 `pos` 位置开始往前找字符 `c` ，返回该字符在字符串中的位置
substr	在 `str` 中从 `pos` 位置开始，截取 `n` 个字符，然后将其返回

void string_test1() {string s;s.push_back('x');   // 尾插一个字符s.append("hello");  // 尾插一个字符串string str("world");s.append(str);  // 也可以通过 += 尾插s += 'x';s += "hello";s += "world";// 插入s.insert(0, 1, 's'); // 开头位置插入一个 ss.insert(s.begin(), 'r'); // 往s.begin() 迭代器位置插入一个rs.insert(0, "nihao ");// 删除s.erase(s.begin());     // 将第一个位置的字符删除s.erase(s.begin() + 3); // 删除第三个位置s.erase(3, 2);          // 第三个位置删除两个s.erase(3);             // 不给删除的个数  默认全部删除 size_t npos = -1// 交换string s1("hello");string s2("world");s1.swap(s2);               // 效率高  交换指针swap(s1, s2);              // 效率低  深拷贝// 取出文件的后缀string file("string.cpp");size_t pos = file.find('.');if (pos != string::npos) {string suffix = file.substr(pos, file.size() - pos);// string suffix = file.substr(pos);  将.及后面全部取出来cout << "后缀为: " << suffix << endl;} else {cout << "没有后缀" << endl;}string file("string.c.tar.zip");size_t pos = file.rfind('.');if (pos != string::npos) {string suffix = file.substr(pos, file.size() - pos);// string suffix = file.substr(pos);  将.及后面全部取出来cout << "后缀为: " << suffix << endl;} else {cout << "没有后缀" << endl;}// 取出 url 的域名string url("http://www.cplusplus.com/reference/string/string/find/");// 将协议 域名 uri(资源名)// 找协议string protocol;size_t pos1 = url.find("://");if (pos1 != string::npos) {protocol = url.substr(0, pos1);cout << "protocol: " << protocol << endl;} else {cout << "非法url" << endl;}// 找域名string domain;size_t pos2 = url.find('/', pos1 + 3);if (pos2 != string::npos) {domain = url.substr(pos1 + 3, pos2 - (pos1 + 3));cout << "domain: " << domain << endl;} else {cout << "非法url" << endl;}// uristring uri = url.substr(pos2 + 1);cout << "uri: " << uri << endl;// 字符串转整型// stoistring s("12321312");int val = stoi(s);
}

在string 尾部追加字符时，s.push_back(c) / s.append(1, c) / s += 'c' 三种的实现方式差不多，一般情况下string 类的 += 操作用的比较多，+= 操作不仅可以连接单个字符，还可以连接字符串
对 string 操作时，如果能够大概预估到放多少字符，可以先通过 reserve 把空间预留好

string 类非成员函数

函数名称	功能说明
operator+	尽量少用，因为传值返回，导致深拷贝效率低
operator>>	输入运算符重载
operator<<	输出运算符重载
getline	获取一行字符串
relational opeartors	大小比较

void string_test() {string s1("hello");string s2("world");// 比较大小s1 < s2;          // string 和 string 比s1 < "hello";     // string 和 字符串  比"hello" < s1;     // 字符串  和 string 比// + 传值返回 // getline 读取一行字符串// cin 读取到空格或换行间隔string str;getlin(cin, str);
}

string 的模拟实现

模拟实现

namespace ToodlesFate {// 实现一个简单的string, 只考虑资源管理深浅拷贝问题class string {public:typedef char* iterator;        typedef const char* const_iterator;iterator begin() { return _str; }const_iterator begin() const { return _str; }iterator end() { return _str + _size; }        const_iterator end() const { return _str + _size; }//  "\0"         ""      '\0' //  常量字符串   隐式     字符string(const char* str = ""):_size(strlen(str)),_capacity(_size) { _str = new char[_capacity + 1];strcpy(_str, str);}/** string():_size(0),_capacity(0) {_str = new char[1];_str[0] = '\0';}string(const char* str) :_size(strlen(str)),_capacity(_size) {_str = new char[_capacity + 1];strcpy(_str, str);}*/ // 传统写法/* string(const string& s) :_size(strlen(s._str)),_capacity(_size) {_str = new char[_capacity + 1];strcpy(_str, s._str);} */   void swap(string& s) {std::swap(_str, s._str);std::swap(_size, s._size);std::swap(_capacity, s._capacity);}// 现代写法string(const string& s) :_str(nullptr),_size(0),_capacity(0) {string tmp(s._str);swap(tmp);}        /** string& operator=(const string& s) {if (this != &s) {string tmp(s._str);swap(tmp);}return *this;}*/ string& operator=(string s) {swap(s);return *this;}~string() {if (_str) { delete[] _str;_str = nullptr;_size = _capacity = 0;}}const char* c_str() const { return _str; }char& operator[](size_t pos) {assert(pos < _size);return _str[pos];}const char& operator[](size_t pos) const {assert(pos < _size);return _str[pos];}/*string& operator=(const string& s) {if (size() < strlen(s._str)) _str = new char[strlen(s._str) + 1];strcpy(_str, s._str);return *this;}*/ string& operator=(const string& s) {if (this != &s) {char* tmp = new char[s._capacity + 1];strcpy(_str, s._str);delete[] _str;_str = tmp;_size = s._size;_capacity = s._capacity;} return *this;}string& operator+=(char ch) {push_back(ch);return *this;}string& operator+=(const char* str) {append(str);return *this;}size_t capacity() const { return _capacity; }size_t size() const { return _size; }void reserve(size_t n) {if (n > _capacity) {char* tmp = new char[n + 1];strcpy(tmp, _str);delete[] _str;_str = tmp;_capacity = n;}}void resize(size_t n, char ch = '\0') {if (n > _capacity) reserve(n);for (size_t i = _size; i < n; i++) _str[i] = ch;_size = n;_str[_size] = '\0';}void push_back(char ch) {/* if (_size == _capacity) {    //     char* tmp = new char[_capacity * 2 + 1];//     strcpy(tmp, _str);//     delete[] _str;//     _str = tmp;//     _capacity *= 2;   reserve(_capacity == 0? 4 : _capacity * 2);}_str[_size++] = ch;_str[_size] = '\0';*/      insert(_size, ch);}  void append(const char* str) {size_t len = _size + strlen(str);if (len > _capacity) reserve(len);strcpy(_str + _size, str);_size = len;}string& insert(size_t pos, const char ch) {assert(pos <= _size);if(_size == _capacity) reserve(_capacity == 0? 4: _capacity * 2);size_t end = _size + 1;while (end > pos) {_str[end] = _str[end - 1];--end;}_str[pos] = ch;++_size;return *this;}    string& insert(size_t pos, const char* str) {assert(pos <= _size);size_t len = strlen(str);if (len == 0) return *this;if (_size + len > _capacity) reserve(_size + len);/** size_t help = pos;while (help <= _size) {_str[help + len] = _str[help];help++;}for (size_t i = pos; i < pos + len; i++) {_str[i] = str[i - pos];}*/ size_t end = _size + len;while (end > pos + len - 1) {_str[end] = _str[end - len];end--;}strncpy(_str + pos, str, len);_size += len;return *this;}string& earse(size_t pos, size_t len = npos) {assert(pos < _size);if (len == npos || pos + len >= _size) {_str[pos] = '\0';_size = pos;} else {size_t begin = pos + len;while (begin <= _size) {_str[begin - len] = _str[begin];++begin;}_size -= len;}return *this;}size_t find(char ch, size_t pos = 0) {for (; pos < _size; pos++) if (_str[pos] == ch) return pos;return npos;}size_t find(const char* str, size_t pos) {const char* p = strstr(_str + pos, str);if (p == nullptr) return npos;return p - _str;}void clear() {_str[0] = '\0';_size = 0;}private:char* _str;size_t _size;          // 有效字符的个数size_t _capacity;      // 实际存储有效字符的空间const static size_t npos;};const size_t string::npos = -1;bool operator<(const string& s1, const string& s2) {return strcmp(s1.c_str(), s2.c_str()) < 0;}bool operator==(const string& s1, const string& s2) {return strcmp(s1.c_str(), s2.c_str()) == 0;}bool operator<=(const string& s1, const string& s2) {return s1 < s2 || s1 == s2;}bool operator>(const string& s1, const string& s2) { return !(s1 <= s2); }bool operator>=(const string& s1, const string& s2) { return !(s1 < s2); }bool operator!=(const string& s1, const string& s2) { return !(s1 == s2); }std::ostream& operator<<(std::ostream& out, const string& s) {//  out << s.c_str();for (auto ch: s)  out << ch;return out;}std::istream& operator>>(std::istream& in, string& s) {/** char ch;ch = in.get();while (ch != ' ' && ch != '\n') {s += ch;ch = in.get();}*/ s.clear();char ch;ch = in.get();char buffer[128] = {'\0'};size_t i = 0;while (ch != ' ' && ch != '\n') {buffer[i++] = ch;if (i == 127) {s += buffer;memset(buffer, '\0', 128);i = 0;}ch = in.get();}s += buffer;return in;}
}

测试

void test_string1() {ToodlesFate::string s1("hello world");cout << s1.c_str() << endl;s1[0] = 'x';cout << s1.c_str() << endl;for (size_t i = 0; i < s1.size(); i++) {cout << s1[i] << " ";}cout << endl;
}

void test_string2() {ToodlesFate::string s1("hello world");// 浅拷贝: //   1. 析构两次//   2. 改变其中一个会对另一个修改ToodlesFate::string s2(s1);cout << s1.c_str() << endl;cout << s2.c_str() << endl;
}

void test_string3() {string s1("hello");string s2("world");string s3("1111111111111");s1 = s3;cout << s1.c_str() << endl;cout << s2.c_str() << endl;cout << s3.c_str() << endl;
}

void test_string4() {string s1("hello");string s2;cout << s1.c_str() << endl;cout << s2.c_str() << endl;
}

void test_string5() {string s1("hello world");ToodlesFate::string::iterator it = s1.begin();while (it != s1.end()) {*it -= 1;cout << *it << " ";*it += 1;it++;}cout << endl;cout << s1.c_str() << endl;
}

void Func(const ToodlesFate::string& s);
void test_string6() {ToodlesFate::string s1("hello world");// 范围 for 底层用 迭代器实现 // 不可以被修改for (auto ch: s1) cout << ch << " ";cout << endl;// 可以被修改for (auto& ch: s1) cout << ch << " ";cout << endl;Func(s1);
}
void Func(const ToodlesFate::string& s) {// 使用 const 修饰 无法修改for (size_t i = 0; i < s.size(); i++) cout << s[i] << " ";cout << endl;// auto 自动推for (auto ch: s) cout << ch << " ";cout << endl;for (auto& ch: s) cout << ch << " ";cout << endl;
}

void test_string7() {ToodlesFate::string s1("hello world");s1.insert(6, '*');cout << s1.c_str() << endl;
}

void test_string8() {ToodlesFate::string s1("hello world");cout << s1 << endl;
}

void test_string9() {ToodlesFate::string s("hello world");cin >> s;cout << s << endl;
}

练习

仅仅反转字符串
字符串中的第一个唯一字符
字符串最后一个单词的长度
验证一个字符串是否回文
字符串相加
反转字符串II
反转字符串中的单词III
字符串相乘
找出字符串中第一个只出现一次的字符
把字符串转换成整数
字符串相加

vector

标准库中 `vector`

`vector` 的介绍

vector 是表示可变大小数组的序列容器
像数组一样，vector 也采用的连续存储空间来存储元素。

也就是意味着可以采用下标对vector 的元素进行访问，和数组一样高效。

但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
vector 使用动态分配数组来存储它的元素。

当新元素插入时候，这个数组需要被重新分配大小, 为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。

就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector 并不会每次都重新分配大小。
vector 分配空间策略：

vector 会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。

不同的库采用不同的策略权衡空间的使用和重新分配。

但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
vector 占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
与其它动态序列容器相比（deques , lists and forward_lists ), vector 在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起lists 和forward_lists 统一的迭代器和引用更好。

常用的接口

常见构造函数

构造函数的声明	接口说明
`vector()`	无参构造
`vector（size_type n, const value_type& val = value_type())`	构造并初始化`n` 个`val`
`vector (const vector& x);`	拷贝构造
`vector (InputIterator first, InputIterator last);`	使用迭代器进行初始化构造

void test_vector1() {vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);vector<double> v2;v2.push_back(1.1);v2.push_back(1.2);v2.push_back(1.3);v2.push_back(1.4);vector<string> v3;v3.push_back("李白");v3.push_back("张三");v3.push_back("李四");v3.push_back("王五");vector<int> v3(10, 5);                       // 构造 10个 5vector<string> v5(v3.begin(), v3.end());     // 使用迭代器初始化 vector<string> v6(++v3.begin(), --v3.end()); // 使用迭代器初始化  迭代器 解引用是stringstring s = "hello world";vector<char> v7(s.begin(), s.end());         // 使用迭代器初始化 迭代器解引用是char
}

void test_vector2() {vector<int> first; vector<int> second (4, 100);                       // 4个100vector<int> third (second.begin(), second.end());  // 使用迭代器vector<int> fourth (third);                        // 拷贝构造int myints[] = { 16, 2, 77, 29 };             vector<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );cout << "The contents of fifth are:";for (vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it)cout << ' ' << *it;cout << '\n';
}

迭代器

iterator 的使用	接口说明
begin + end	获取第一个数据位置的`iterator` / `const_iterator` ，获取最后一个数据的下一个位置的`iterator` / `const_iterator`
rbegin + rend	获取最后一个数据位置的`reverse_iterator` ，获取第一个数据前一个位置的`reverse_iterator`

// 遍历vector 的方法
void test_vector1() {vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);    // 1. 下表  + []for (size_t i = 0; i < v.size(); i++) {v[i] += 1;cout << v[i] << " ";}cout << endl;    // 2. 迭代器vector<int>::iterator it = v.begin();while (it != v.end()) {cout << *it << " ";++it;}cout << endl;    // 3. 范围forfor (auto e: v) {cout << e << " " ;}cout << endl;    // 使用反向迭代器进行遍历再打印vector<int>::reverse_iterator rit = v.rbegin();while (rit != v.rend()) {cout << *rit << " ";++rit;}cout << endl;   // 使用迭代器进行修改it = v.begin();while (it != v.end()) {*it *= 2;++it;}
}

空间增长问题

容量空间	接口说明
size	获取数据个数
capacity	获取容量大小
empty	判断是否为空
resize	改变`vector` 的 `size`
reserve	改变 `vector` 放入 `capacity`

void test_vector1() {vector<int> v;cout << v.max_size() << endl; // 整型的最大值 除以单个对象的大小vector<char> v1;cout << v1.max_size() << endl;
}

void test_vector2() {// 观察增容 是如何增的 // vs    1.5倍// linux 2倍  size_t sz;vector<int> foo;foo.reserve(100); // 只开空间  不初始化foo.resize(100);  // 开空间 + 初始化sz = foo.capacity();cout << "making foo grow:\n";for (int i = 0; i < 100; i++) {foo.push_back(i);if (sz != foo.capacity()) {sz = foo.capacity();cout << "capacity changed: " << sz << '\n';}}
}

void test_vector3() {// 删除数据 一般不会主动缩容的vector<int> countv;countv.resize(100, 1);   // 开100个空间  并初始化为1countv.shrink_to_fit();  // 调整容量和有效个数一样 再申请size个大小空间，将原来的释放掉
}

void test_vector4() {vector<int> V;for (int i=1;i<10;i++) V.push_back(i);V.resize(5);V.resize(8,100);V.resize(12);cout << "V contains: ";for (int i=0;i<V.size();i++) cout << " " << V[i];cout << endl;
}

增删查改

`vector` 增删查改	接口说明
push_back	尾插
pop_back	尾删
find	查找
insert	在`position` 之前插入 `val`
erase	删除 `position` 位置的数据
swap	交换两个 `vector` 的数据空间
operator[]	像数组一样访问

void test_vector1() {vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.insert(v.begin(), -1); // 头插  不支持下标v.insert(v.begin(), -2); v.insert(v.begin(), -3); v.insert(v.begin(), -4);v.insert(v.begin() + 3, -5)for (auto e: v) cout << e << " ";cout << endl;v.erase(v.begin());    // 头删v.erase(v.begin());    // 头删
}

void test_vector2() {int a[] = { 1, 2, 3, 4 };vector<int> v(a, a + sizeof(a) / sizeof(int));vector<int>::iterator it = v.begin();while (it != v.end()) {cout << *it << " ";++it;}cout << endl;v.pop_back();v.pop_back();it = v.begin();while (it != v.end()) {cout << *it << " ";++it;}cout << endl;
}

void test_vector3() {vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);// vector<int>::iterator pos = find(v.begin(), v.end(), 3);// find() 传迭代器区间 左闭右开auto pos = find(v.begin(), v.end(), 3);if (pos != v.end()) cout << "找到了" << endl;else cout << "没有找到" << endl;
}

void test_vector4() {vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(9);v.push_back(8);v.push_back(7);v.push_back(6);// 默认是升序sort(v.begin(), v.end());for (auto e: v) cout << e << " ";cout << endl;// 派降序 仿函数 sort(v.begin(), v.end(), greater<int>()); // > 
}

`vector` 模拟实现

模拟

namespace ToodlesFate {template <class Iterator, class Ref, class Ptr>struct Reverse_iterator{Iterator _it;typedef Reverse_iterator<Iterator, Ref, Ptr> Self;Reverse_iterator(Iterator it):_it(it){}Ref operator*(){Iterator tmp = _it;return *(--tmp);}    Ptr operator->(){return &(operator*());}Self& operator++(){--_it;return *this;}Self& operator--(){++_it;return *this;}bool operator(const Self& s){return _it != s.it;}}template<class T>class vector {public:typedef T* iterator;typedef const T* const_iterator;typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;  vector():_start(nullptr),_finish(nullptr),_endofstoage(nullptr){  }   vector(const vector<T>& v) :_start(nullptr),_finish(nullptr),_endofstoage(nullptr) {vector<T> tmp(v.begin(), v.end());swap(tmp);}template <class InputIterator>vector(InputIterator first, InputIterator last) :_start(nullptr),_finish(nullptr),_endofstoage(nullptr) {while (first != last){push_back(*first);++first;}}vector(size_t n, const T& val = T()) :_start(nullptr),_finish(nullptr),_endofstoage(nullptr) {reserve(n);for (size_t i = 0; i < n; i++) push_back(val);}vector(int n, const T& val = T()) :_start(nullptr),_finish(nullptr),_endofstoage(nullptr) {reserve(n);for (size_t i = 0; i < n; i++) push_back(val);}~vector() {if (_start) {delete[] _start;_start = _finish = _endofstoage = nullptr;}}void swap(vector<T>& v) {std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstoage, v._endofstoage);}vector<T>& operator=(vector<T> v) {swap(v);return *this;}iterator begin() { return _start; }const_iterator begin() const { return _start; }iterator end() { return _finish; }const_iterator end() const { return _finish; }size_t size() const { return _finish - _start; }size_t capacity() const { return _endofstoage - _start; }void reserve(size_t n) {size_t sz = size();if (n > capacity()) {T* tmp = new T[n];if (_start) {//     memcpy(tmp, _start, size() * sizeof(T));for (size_t i = 0; i < size(); i++) tmp[i] = _start[i];delete[] _start;}_start = tmp;} _finish = _start + sz;_endofstoage = _start + n;}void push_back(const T& x) {/** if (_finish == _endofstoage) {size_t newCapacity = capacity() == 0? 4 : capacity() * 2;reserve(newCapacity);}*_finish = x;++_finish; */ insert(end(), x);}void pop_back() {/* if (_finish > _start)  --_finish; */ erase(end() - 1);}T& operator[](size_t pos) {assert(pos < size());return _start[pos]; }const T& operator[](size_t pos) const {assert(pos < size());return _start[pos];} // cpp 有了模板之后  内置类型也可以认为有构造函数 和 析构函数 这样才可以更好的支持模板void resize(size_t n, const T& val = T()) {if (n > capacity()) reserve(n);if (n > size()) {while (_finish < _start + n) {*_finish = val;++_finish;}} else {_finish = _start + n;}}iterator insert(iterator pos, const T& x) {assert(pos >= _start && pos <= _finish);if (_finish == _endofstoage) {size_t n = pos - _start;size_t newCapacity = capacity() == 0? 4: capacity() * 2;reserve(newCapacity);pos = _start + n;}iterator end = _finish - 1;while (end >= pos) {*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;}/** * 一般不考虑缩容方案 * 缩容方案: size() < capacity() / 2 时, 可以考虑开一个size() 大小的空间, 拷贝数据，释放旧空间* 缩容方案 本质是时间换空间 一般设计不会考虑缩容 因为实际比较关注时间效率 不关注空间效率 */ iterator erase(iterator pos) {assert(pos >= _start && pos < _finish);iterator it = pos + 1; while (it != _finish) {*(it - 1) = *it;++it;}--_finish;return pos;}reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}const_reverse_iterator rbegin() const{return const_reverse_iterator(end());}const_reverse_iterator rend() const{return const_reverse_iterator(begin());}void clear() { _finish = _start; }private:iterator _start;iterator _finish;iterator _endofstoage;};
}

测试

void test_vector1() {ToodlesFate::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);ToodlesFate::vector<int>::iterator it = v.begin();while (it != v.end()) {cout << *it << " ";it++;}cout << endl;v.pop_back();v.pop_back();v.pop_back();it = v.begin();while (it != v.end()) {cout << *it << " ";it++;}cout << endl;
}

void test_vector2() {ToodlesFate::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);ToodlesFate::vector<int>::iterator it = v.begin(); // 得到一个起始位置的迭代器// 在偶数的前面插入一个15while (it != v.end()) {if (*it % 2 == 0) {it = v.insert(it, 15);it++;}++it;}for (auto e: v) cout << e << " ";cout << endl;
}

void test_vector3() {ToodlesFate::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);v.push_back(7);for (auto e: v) cout << e << " ";cout << endl;v.push_back(100);for (auto e: v) cout << e << " ";cout << endl;v.pop_back();for (auto e: v) cout << e << " "; cout << endl;
}

void test_vector4() {ToodlesFate::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);std::string s("hello world");// 使用迭代器区间进行构造  [)ToodlesFate::vector<int> v2(v.begin(), v.end());// 使用迭代器区间进行构造  [)ToodlesFate::vector<char> v3(s.begin(), s.end());// 打印出来  观察结果for (auto e: v2) cout << e << " ";cout << endl;for (auto e: v3) cout << e << " ";cout << endl;
}

void test_vector5() {// int类型的vector 进行尾插ToodlesFate::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);for (auto e: v) cout << e << " ";cout << endl;// char类型的vector 拷贝构造ToodlesFate::vector<char> v1;v1.push_back('a');v1.push_back('a');v1.push_back('a');v1.push_back('a');v1.push_back('a');v1.push_back('a');ToodlesFate::vector<char> v3(v1);for (auto e: v3) cout << e << " ";cout << endl;  // int 类型的vector  进行赋值ToodlesFate::vector<int> v2;v2.push_back(99);v2.push_back(99);v2.push_back(99);v2.push_back(99);v2.push_back(99);v2.push_back(99);v2.push_back(99);v = v2;for (auto e: v) cout << e << " ";cout << endl; 
}

练习

只出现一次的数字
杨辉三角形
删除排序数组中的重复项
只出现一次的数ii
只出现一次的数iii
数组中出现次数超过一半的数字
电话号码的字母组合
连续子数组的最大和

list

标准库中 `list`

`list` 的介绍

list 是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
list 的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向
其前一个元素和后一个元素。
list 与forward_list 非常相似。

最主要的不同在于forward_list 是单链表，只能朝前迭代，已让其更简单高效。
与其他的序列式容器相比(array ，vector ，deque )，list 通常在任意位置进行插入、移除元素的执行效率更好。
与其他序列式容器相比，list 和forward_list 最大的缺陷是不支持任意位置的随机访问，

比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；

list 还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list 来说这可能是一个重要的因素

常用的接口

list 的构造函数

构造函数	接口说明
`list()`	构造空的`list`
`list(size_type n, const value_type& val = value_type())`	构造的 `list` 中包含`n` 个值为 `val` 的元素
`list(const list& x)`	拷贝构造函数
`list(InputIterator first, InputIterator last)`	用`[first, last)` 区间中的元素构造`list`

list 迭代器的使用

函数声明	接口说明
begin + end	返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin + rend	返回第一个元素的`reverse_iterator` ,即 `end` 位置，返回最后一个元素下一个位置的`reverse_iterator` ,即 `begin` 位置

void test_list1() {list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);// 使用迭代器遍历list<int>::iterator it = lt.begin();while (it != lt.end()) {cout << *it << " ";++it;}cout << endl;// 使用范围for遍历for (auto e: lt) cout << e << " ";  cout << endl;   // 反向遍历list<int>::reverse_iterator rit = lt.rbegin();while (rit != lt.rend()) {cout << *rit << " ";                                                               rit++;         }                  cout << endl; 
}

list capacity

函数声明接口说明
empty 检测list 是否为空，是返回true ，否则返回false
size 返回list 中有效节点的个数
list element access

函数声明接口说明
front 返回 list 的第一个节点中值的引用
back 返回 list 的最后一个节点中值的引用
list modifiers

函数声明	接口说明
empty	检测`list` 是否为空，是返回`true` ，否则返回`false`
size	返回`list` 中有效节点的个数

函数声明	接口说明
front	返回 `list` 的第一个节点中值的引用
back	返回 `list` 的最后一个节点中值的引用

 | 函数声明                                                     | 接口说明                                    || ------------------------------------------------------------ | ------------------------------------------- || [push_front](https://cplusplus.com/reference/list/list/push_front/) | 在`list` 首元素前插入值为 `val` 的元素      || [pop_front](https://cplusplus.com/reference/list/list/pop_front/) | 删除`list` 中第一个元素                     || [push_back](https://cplusplus.com/reference/list/list/push_back/) | 在`list` 尾部插入值为`val` 的元素           || [pop_back](https://cplusplus.com/reference/list/list/pop_back/) | 删除`list` 中最后一个元素                   || [insert](https://cplusplus.com/reference/list/list/insert/)  | 在`list position`位置中插入值为`val` 的元素 || [erase](https://cplusplus.com/reference/list/list/erase/)    | 删除`list position` 位置的元素              || [swap](https://cplusplus.com/reference/list/list/swap/)      | 交换两个`list` 中的元素                     || [clear](https://cplusplus.com/reference/list/list/clear/)    | 清空`list` 中的有效元素                     |```cppvoid test_list1() {list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for (auto e: lt) cout << e << " ";cout << endl;  lt.push_front(100);lt.push_front(200);lt.push_front(300);lt.push_front(400);lt.push_front(500);lt.push_front(600);lt.push_front(700);for (auto e: lt) cout << e << " ";cout << endl;  lt.pop_front();lt.pop_front();lt.pop_front();for (auto e: lt) cout << e << " ";cout << endl;}``````cppvoid test_list2() {srand(time(0));const int N = 10000;vector<int> v;list<int> lt;for (int i = 0; i < N; i++) {v.push_back(rand());lt.push_back(v[i]);}// 计算vecror 排序需要的时间int begin1 = clock();sort(v.begin(), v.end());int end1 = clock();// 计算list 排序需要的时间int begin2 = clock();lt.sort();int end2 = clock();cout << "vector sort: " << end1 - begin1 << endl;cout << "list sort: " << end2 - begin2 << endl;   }``````cppvoid test_list3() {srand(time(0));const int N = 10000000;vector<int> v; v.reserve(N);    // 事先开辟好N个空间list<int> lt1;list<int> lt2;for (int i = 0; i < N; ++i) {auto e = rand();lt1.push_back(e);lt2.push_back(e);}// 拷贝到vector排序，排完以后再拷贝回来int begin1 = clock();for (auto e : lt1) v.push_back(e);  // 拷贝在vector中sort(v.begin(), v.end());           // 进行排序size_t i = 0;        for (auto& e : lt1) e = v[i++];     // 将排好序的返回int end1 = clock();// 列表排序int begin2 = clock();lt2.sort();int end2 = clock();   cout << "将list中的数据拷贝在vector中，排完序后在拷贝回去:" << end1 - begin1 << endl;cout << "list 排序: " << end2 - begin2 << endl;}``````cppunique(); // 去重  需要连续split();  // 结点转移```

`list` 模拟实现

namespace ToodlesFate {template<class T>struct list_node {list_node<T>* _next;list_node<T>* _prev;T _data;list_node(const T& val = T()) :_next(nullptr),_prev(nullptr),_data(val){}};template <class Iterator, class Ref, class Ptr>struct Reverse_iterator{Iterator _it;typedef Reverse_iterator<Iterator, Ref, Ptr> Self;Reverse_iterator(Iterator it):_it(it){}Ref operator*() {Iterator tmp = _it;return *(--tmp);}    Ptr operator->() {return &(operator*());}Self& operator++() {--_it;return *this;}Self& operator--() {++_it;return *this;}bool operator(const Self& s) {return _it != s.it;}}template<class T, class Ref, class Ptr>struct __list_iterator {typedef list_node<T> Node;typedef __list_iterator<T, Ref, Ptr> self;Node* _node;__list_iterator(Node* node):_node(node){}Ref operator*() { return _node->_data; } Ptr operator->() { return &_node->_data; }Ref operator++() {_node = _node->_next;return *this;}Ref operator++(int) {self tmp(*this);_node = _node->_next;return tmp;}Ref operator--() {_node = _node->_prev;return *this;}Ref operator--(int) {self tmp(*this);_node = _node->_prev;return tmp;}bool operator==(const self& it) { return _node == it._node; }bool operator!=(const self& it) { return _node != it._node; }};template<class T>class list {typedef list_node<T> Node;       public:/** *   关于const迭代器模板中第一个参数不用const 的原因*     对于模板而言, 不同的参数代表的不同的类型, list_node<int> 和 list_node<const int> 是不同的类型 不能赋值*     return const_iterator(_head->_next);     传递的类型是 list_node<int>  接受是 list_node<const int> 不是同一类型 不能传过去*/  typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;typedef Reverse_iterator<const_iterator, const T&, const T*> 			                     const_reverse_iterator;    list() {_head = new Node;_head->_next = _head;_head->_prev = _head;}~list() {clear();delete _head;_head = nullptr;}/* list(const list<T>& lt){_head = new Node();_head->_next = _head;_head->_prev = _head;for (auto e: lt) push_back(e);}*/ template <class InputIteratpr>list(InputIteratpr first, InputIteratpr last) {_head = new Node();_head->_prev = _head;_head->_next = _head;while (first != last) {push_back(first);++first;}}list(const list<T>& lt) {_head = new Node();_head->_prev = _head;_head->_next = _head;list<T> tmp(lt.begin(), lt.end());swap(tmp);}void swap(list<T>& lt) { std::swap(_head, lt.head); }void clear() {iterator it = begin();while (it != end()) it = erase(it); } void push_back(const T& x) {/** Node* tail = _head->_prev;Node* newNode = new Node(x);_head->_prev = newNode;newNode->_next = _head;newNode->_prev = tail;tail->_next = newNode;*/ insert(end(), x);       }void push_front(const T& x) { insert(begin(), x);}/* *   会存在迭代器失效*   返回删除位置的下一个位置**/ iterator erase(iterator pos) {assert(pos != end());Node* cur = pos._node;Node* next = pos->_next;Node* prev = pos->_prev;prev->_next = next;next->_prev = prev;delete cur;return iterator(next);}void pop_back() { erase(--end()); }void pop_front() { erase(begin()); }iterator begin() { return iterator(_head->_next); } const_iterator begin() const { return const_iterator(_head->_next); }iterator end() { return iterator(_head); }const_iterator end() const { return const_iterator(_head); }reverse_iterator rbegin() {return reverse_iterator(end());}reverse_iterator rend() {return reverse_iterator(begin());}const_reverse_iterator rbegin() const {return const_reverse_iterator(end());}const_reverse_iterator rend() const {return const_reverse_iterator(begin());}void insert(iterator pos, const T x) {Node* newNode = new Node(x);Node* cur = pos._node;Node* prev = cur->_prev;prev->_next = newNode;newNode->_prev = prev;newNode->_next = cur;cur->_prev = newNode;}list<T>& operator=(list<T> lt) {swap(lt);return *this;}private:Node* _head;};
}

练习

LRU缓存
扁平化多级双向链表
设计浏览器历史记录
二叉搜索树与双向链表
展平多级双向链表
最近最少使用缓存

`deque`

vector

优点：

适合尾插，尾删，随机访问
cpu高速缓存命中高

缺点：

不适合头部或者中部的删除，效率低，需要挪动数据
扩容有一定性能消耗，还可能存在一定程度的空间浪费

list

优点：

任意位置的插入删除效率高。O(1)
按需申请释放空间

缺点：

不支持随机访问
cpu高速缓存命中低

deque

一段一段的，满了之后在后面加，小段小段加。

有一个中控数组，里面存放的是指针数组。满了之后扩容，拷贝代价低。只有第一个和最后一个可能不会满，中间肯定会满。

优点：

头部和尾部插入删除数据效率不错
支持随机访问
扩容代价小
cpu 高速缓存命中高

缺点：

中部的插入效率不行
虽然支持随机访问，但是效率相比vector而言还是有差距，频繁随机访问要小心
不够极致

适合使用的场景：大量的头尾插入、删除，偶尔随机访问。(stack 和 queue 用 deque 作为默认的构造器)

`map`

`set`

`multimap`

`multilset`

配接器

适配器

`stack`

标准库

介绍

stack 是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行
元素的插入与提取操作.
stack 是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定
的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。
stack 的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下
操作
- empty ：判空操作
- back ：获取尾部元素操作
- push_back ：尾部插入元素操作
- pop_back ：尾部删除元素操作
标准容器vector 、deque 、list 均符合这些需求，默认情况下，如果没有为stack 指定特定的底层容器，默认情况下使用deque

常用接口

函数说明	接口说明
stack()	构造空的栈
empty()	检测`stack` 是否为空
size()	返回`stack` 中元素的个数
top()	返回栈顶元素的引用
push()	将元素`val` 压入`stack` 中
pop()	将`stack` 中尾部的元素弹出

void test_stack1() {stack<int> s;s.push(1);s.push(2);s.push(3);s.push(4);s.push(5);s.push(6);while (!s.empty()) {cout << s.top() << " ";s.pop();}cout << endl;
}

模拟实现

namespace ToodlesFate {template<class T, class Container = deque<T> >class stack {public:void push(const T& x) { _con.push_back(x); }void pop() { _con.pop_back(); }const T& top() { return _con.back(); }size_t size() { return _con.size(); }bool empty() { return _con.empty(); }private:Container _con;    };
}

练习

最小栈
栈的压入、弹出序列
逆波兰表达式求值
用栈实现队列

`queue`

标准库

介绍

队列是一种容器适配器，专门用于在FIFO 上下文(先进先出)中操作，其中从容器一端插入元素，另一端
提取元素。
队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue 提供一组特定的
成员函数来访问其元素。元素从队尾入队列，从队头出队列。
底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操
作：

 *   `empty` ：检测队列是否为空*   `size` ：返回队列中有效元素的个数*   `front` ：返回队头元素的引用*   `back` ：返回队尾元素的引用*   `push_back` ：在队列尾部入队列*   `pop_front` ：在队列头部出队列

标准容器类deque 和list 满足了这些要求。

默认情况下，如果没有为queue 实例化指定容器类，则使用标
准容器deque 。

常用接口

函数声明	接口说明
queue()	构造空的队列
empty()	检测队列是否为空，是返回`true` ，否则返回`false`
size()	返回队列中有效元素的个数
front()	返回队头元素的引用
back()	返回队尾元素的引用
push()	在队尾将元素`val` 入队列
pop()	将队头元素出队列

void test_queue() {queue<int> q;q.push(1);q.push(2);q.push(3);q.push(4);q.push(5);q.push(6);q.push(7);while (!q.empty())  {cout << q.front() << " ";q.pop();}cout << endl;
}

模拟实现

namespace ToodlesFate 
{template<class T, class Container = deque<T> >class queue {public:void push(const T& x) {_con.push_back(x);}void pop() {_con.pop_front(); }const T& front() { return _con.front(); }const T& back() {return _con.back(); }size_t size() {return _con.size(); }bool empty() { return _con.empty(); }private:Container _con;};
}

练习

用队列实现栈

`priority_queue`

标准库

介绍

优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue 提供一组特
定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭
代器访问，并支持以下操作
- empty() ：检测容器是否为空
- size() ：返回容器中有效元素个数
- front() ：返回容器中第一个元素的引用
- push_back() ：在容器尾部插入元素
- pop_back() ：删除容器尾部元素
标准容器类vector 和deque 满足这些需求。

默认情况下，如果没有为特定的priority_queue 类实例化指定容器类，则使用vector 。
需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap 、push_heap 和pop_heap 来自动完成此操作。

常用接口

函数声明	接口说明
priority_queue() / priority_queue(first,last)	构造一个空的优先级队列
empty()	检测优先级队列是否为空，是返回`true` ，否则返回`false`
top()	返回优先级队列中最大(最小元素)，即堆顶元素
push(x)	在优先级队列中插入元素`x`
pop()	删除优先级队列中最大(最小)元素，即堆顶元素

void test_priority_queue() {// 大的优先级高// 优先级队列默认传的时less仿函数 底层是一个大堆// 想控制小的优先级高, 底层是一个小堆priority_queue<int> pq;pq.push(1);pq.push(3);pq.push(2);pq.push(6);pq.push(5);pq.push(4);while (!pq.empty()) {cout << pq.top() << " ";pq.pop();}cout << endl;
}

void test_priority_queue() {// greater<int> 仿函数 从小到达排序 头文件functionalpriority_queue<int, vector<int>, greater<int> > pq;pq.push(1);pq.push(3);pq.push(2);pq.push(6);pq.push(5);pq.push(4);while (!pq.empty()) {cout << pq.top() << " ";pq.pop();}cout << endl;
}

模拟实现

namespace ToodlesFate 
{template<class T, class Container = vector<T>, class Compare = less<T> >class priority_queue {Compare _comFunc;public:priority_queue(const Compare* comFunc = Compare()) :_comFunc(comFunc) {}template <class InputIterator>priority_queue(InputIterator first, InputIterator last, const Compare* comFunc = Compare()) :_comFunc(comFunc) {while (first != last) {_con.push_back(*first);++first;}for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i) {AdjustDown(i);}}void push(const T& x) {_con.push_bacl(x);AdjusyUp(_con.size() - 1);}void pop() {assert(!_con.empty());swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}void AdjusyUp(int child) {Compare comFunc;int parent = (child - 1) / 2;while (child > 0) {if (comFunc(_con[parent], _con[child])) {swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;} else {break;}}}void AdjustDown(int parent) {Compare comFunc;int child = parent * 2 + 1;while (child < _con.size()) {if (child + 1 < _con.size() && comFunc(_con[child], _con[child + 1]){++child;}if (comFunc(_con[child], _con[parent])) {swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;} else {break;}}}const T& top() {return _con[0]; }size_t size() { return _con.size(); }bool empty() {return _con.empty();}private:Container _con;      };template<class T>struct less {bool operator()(const T& x, const T& y) const  { return x < y; }};template<class T>struct greater {bool operator()(const T& x, const T& y) const { return x > y;}};}

迭代器

从实现结构的角度，迭代器再实际中分为三类：

单向。++ ：forward_list unordered_map unordered_set
双向。++ – ：list map set
随机。++ – + - : vector string deque InputIterator

可以认为随机是单向和双向

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fSPEDqOc-1661693871030)(D:/picture/image-20220712140433941.png)]

反向迭代器

对正向迭代器封装适配一下，生成对应的反向迭代器.

template <class Iterator, class Ref, class Ptr>
struct reverse_iterator
{Iterator _it;typedef reverse_iterator<Iterator, Ref, Ptr> Self;reverse_iterator(Iterator it):_it(it){}Ref operator*(){iterator tmp = it;return *(--tmp);}    Ptr operator->(){return &(operator*());}Self& operator++(){--_it;return *this;}Self& operator--(){++_it;return *this;}bool operator(const Self& s){return _it != s.it;}
}

算法

仿函数

void test_functional()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);print_vector(v);// 默认小于升序sort(v.begin(), v.end());print_vector(v);// 升序 传一个匿名对象sort(v.begin(), v.end(), greater<int>());print_vector(v);}
void print_vector(vector<int> v) 
{for (auto e: v) cout << e << " ";cout << endl;
}

struct Goods
{string _name;double _price;size_t _saleNum;bool operator<(const Goods& g) const {return _price < g._price;}
};struct LessPrice
{bool operator()(const Goods& g1, const Goods& g2) const {return g1._price < g2._price;}
};struct GreaterPrice
{bool operator()(const Goods& g1, const Goods& g2) const {return g1._price > g2._price;}
};struct LessSaleNum
{bool operator()(const Goods& g1, const Goods& g2) const {return g1._saleNum < g2._saleNum;}
};struct GreaterSaleNum
{bool operator()(const Goods& g1, const Goods& g2) const {return g1._saleNum > g2._saleNum;}
};void test_functional()
{// 指向数组的原生指针 本身就是天然的迭代器int a[6] = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };sort(a, a + 6);print(a, 6);sort(a, a + 6, greater<int>());print(a, 6);Goods gds[4] = {{"苹果", 2.1, 1000}, {"香蕉", 2.1, 200}, {"梨", 2.1, 300}, {"西瓜", 2.1, 50}};sort(gds, a + 4, LessPrice());print(gds, 4)sort(gds, a + 4, GreaterPrice());sort(gds, a + 4, LessSaleNum());sort(gds, a + 4, GreaterSaleNum());
}void print(int a[], size_t sz)
{for (int i = 0; i < sz; i++) cout << a[i] << " ";cout << endl;
}void print(Goods gds[], size_t sz)
{for (int i = 0; i < sz; ++i) cout << gds[i]._name << " " << gds[i]._price << " " << gds._saleNum << endl;
}

erator<Iterator, Ref, Ptr> Self;

reverse_iterator(Iterator it):_it(it)
{}Ref operator*()
{iterator tmp = it;return *(--tmp);
}    Ptr operator->()
{return &(operator*());
}Self& operator++()
{--_it;return *this;
}Self& operator--()
{++_it;return *this;
}bool operator(const Self& s)
{return _it != s.it;
}

}

# 算法# 仿函数```cpp
void test_functional()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);print_vector(v);// 默认小于升序sort(v.begin(), v.end());print_vector(v);// 升序 传一个匿名对象sort(v.begin(), v.end(), greater<int>());print_vector(v);}
void print_vector(vector<int> v) 
{for (auto e: v) cout << e << " ";cout << endl;
}

struct Goods
{string _name;double _price;size_t _saleNum;bool operator<(const Goods& g) const {return _price < g._price;}
};struct LessPrice
{bool operator()(const Goods& g1, const Goods& g2) const {return g1._price < g2._price;}
};struct GreaterPrice
{bool operator()(const Goods& g1, const Goods& g2) const {return g1._price > g2._price;}
};struct LessSaleNum
{bool operator()(const Goods& g1, const Goods& g2) const {return g1._saleNum < g2._saleNum;}
};struct GreaterSaleNum
{bool operator()(const Goods& g1, const Goods& g2) const {return g1._saleNum > g2._saleNum;}
};void test_functional()
{// 指向数组的原生指针 本身就是天然的迭代器int a[6] = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };sort(a, a + 6);print(a, 6);sort(a, a + 6, greater<int>());print(a, 6);Goods gds[4] = {{"苹果", 2.1, 1000}, {"香蕉", 2.1, 200}, {"梨", 2.1, 300}, {"西瓜", 2.1, 50}};sort(gds, a + 4, LessPrice());print(gds, 4)sort(gds, a + 4, GreaterPrice());sort(gds, a + 4, LessSaleNum());sort(gds, a + 4, GreaterSaleNum());
}void print(int a[], size_t sz)
{for (int i = 0; i < sz; i++) cout << a[i] << " ";cout << endl;
}void print(Goods gds[], size_t sz)
{for (int i = 0; i < sz; ++i) cout << gds[i]._name << " " << gds[i]._price << " " << gds._saleNum << endl;
}

5.STL

STL 的基本概念

什么是 STL

STL 的六大组件

空间配置器

容器

string

标准库中的 string

编码

string 类

常用的接口

string 的模拟实现

练习

vector

标准库中 vector

vector 的介绍

常用的接口

vector 模拟实现

练习

list

标准库中 list

list 的介绍

常用的接口

list 模拟实现

练习

deque

map

set

multimap

multilset

配接器

适配器

stack

标准库

常用接口

模拟实现

练习

queue

标准库

常用接口

模拟实现

练习

priority_queue

标准库

常用接口

模拟实现

迭代器

算法

仿函数

相关文章

`STL` 的基本概念

什么是 `STL`

`STL` 的六大组件

`string`

标准库中的 `string`

标准库中 `vector`

`vector` 的介绍

`vector` 模拟实现

标准库中 `list`

`list` 的介绍

`list` 模拟实现

`deque`

`map`

`set`

`multimap`

`multilset`

`stack`

`queue`

`priority_queue`