目录
STL简介
STL版本
STL的六大组件：
STL的缺陷：（了解）
string类
介绍
string类的常用结构说明
1、常见构造类
2、容量操作类
3、string类对象的访问及遍历操作
4、string类对象的修改操作
5、string类非成员函数
string类的模拟实现
vector的使用
vector常用结构说明
1、vector定义(构造)类
2、vector与string相类似的部分
3、vector 迭代器失效问题。
vector的模拟实现
list类
list 的用法简介
list的构造函数
list的迭代器
其他成员函数
list的模拟实现（重头戏）
在介绍之前，我们可以先来了解一下，何为STL?它有多少个版本？以及它的优势和缺陷。
STL简介
STL版本
截至今天，目前认为：STL有四大版本：
原始版本（HP版本）
Alexander Stepanov、Meng Lee 在惠普实验室完成的原始版本，本着开源精神，他们声明允许任何人任意运用、拷贝、修改、传播、商业使用这些代码，无需付费。唯一的条件就是也需要向原始版本一样做开源使用。 HP 版本--所有STL实现版本的始祖。
P. J. 版本
由P. J. Plauger开发，继承自HP版本，被Windows Visual C++采用，不能公开或修改，缺陷：可读性比较低，符号命名比较怪异。
RW版本
由Rouge Wage公司开发，继承自HP版本，被C+ + Builder 采用，不能公开或修改，可读性一般。
SGI版本
由Silicon Graphics Computer Systems，Inc公司开发，继承自HP版本。被GCC(Linux)采用，可移植性好，可公开、修改甚至贩卖，从命名风格和编程 风格上看，阅读性非常高。我们后面学习STL要阅读部分源代码，主要参考的就是这个版本。
STL的六大组件：
仿函数；算法；迭代器；空间配置器；容器；配接器。
STL的缺陷：（了解）
1. STL库的更新太慢了。这个得严重吐槽，上一版靠谱是C++98，中间的C++03基本一些修订。C++11出来已经相隔了13年，STL才进一步更新。
2. STL现在都没有支持线程安全。并发环境下需要我们自己加锁。且锁的粒度是比较大的。
3. STL极度的追求效率，导致内部比较复杂。比如类型萃取，迭代器萃取。
4. STL的使用会有代码膨胀的问题，比如使用vector/vector/vector这样会生成多份代码，当然这是模板语法本身导致的
今天，我们将学习其中的三个类——string类、vector类、list类。
string类
介绍
我们先来说一说它的用法，然后再来讲解其模拟实现。
首先我们来简单地介绍一下string类：（了解）
1. 字符串是表示字符序列的类
2. 标准的字符串类提供了对此类对象的支持，其接口类似于标准字符容器的接口，但添加了专门用于操作单字节字符字符串的设计特性。
3. string类是使用char(即作为它的字符类型，使用它的默认char_traits和分配器类型(关于模板的更多信息，请参阅basic_string)。
4. string类是basic_string模板类的一个实例，它使用char来实例化basic_string模板类，并用char_traits和allocator作为basic_string的默认参数(根于更多的模板信息请参basic_string)。
5. 注意，这个类独立于所使用的编码来处理字节:如果用来处理多字节或变长字符(如UTF-8)的序列，这个类的所有成员(如长度或大小)以及它的迭代器，将仍然按照字节(而不是实际编码的字符)来操作。
string类的常用结构说明
1、常见构造类
我们可以访问相关的网站来看一下：
框~~可以看到，有这么多函数都可以作为构造函数。
我们介绍几个常用的：
重点来看这么几个：
像上面几种写法，都是可以的。
注意，其隐藏了'\0'，用户即便在调式的时候也是看不见的。
实际上，还可以直接用赋值操作，编译器底层会将其优化为先调用一次构造函数，再调用一次拷贝构造。
2、容量操作类
可以看到，又有不少。
我们介绍一下下面这几个，并举出例子（一块说了）
注意：
1. size()与length()方法底层实现原理完全相同，引入size()的原因是为了与其他容器的接口保持一致，一般情况下基本都是用size()。
2. clear()只是将string中有效字符清空，不改变底层空间大小。
3. resize(size_t n) 与 resize(size_t n, char c)都是将字符串中有效字符个数改变到n个，不同的是当字符个数增多时：resize(n)用0来填充多出的元素空间，resize(size_t n, char c)用字符c来填充多出的元素空间。注意：resize在改变元素个数时，如果是将元素个数增多，可能会改变底层容量的大小，如果是将元素个数减少，底层空间总大小不变。
4. reserve(size_t res_arg=0)：为string预留空间，不改变有效元素个数，当reserve的参数小于
string的底层空间总大小时，reserver不会改变容量大小。
3、string类对象的访问及遍历操作
我们主要来介绍上面这么几个：
上面8个分别是返回正向、逆向、常量的迭代器。
下面的是运用的操作符重载函数完成的。
说到这个访问，于是我们就引出了三种常见的遍历访问方式：
#include<iostream> #include<string> using namespace std; int main() { string s = "hello jxwd"; //其会转换成temp("hello jxwd"),然后拷贝构造到s中. //1、迭代器 string::iterator it = s.begin();//也可以去定义反向迭代器，反向遍历。 while (it != s.end()) { cout << *it; it++; } cout << endl; //2、for+operator[] for (size_t i = 0; i < s.size(); i++) { cout << s[i]; } cout << endl; //3、范围for for (char e : s) { cout << e; } cout << endl; return 0; }
4、string类对象的修改操作
至于功能是什么，上面已经写得很清楚了。
我们现在用这些函数来举几个例子：
#include<iostream> #include<string> using namespace std; int main() { string s1 = "hello "; cout << s1 << endl; s1 += "jxwd";//其相当于s1.append("jxwd"); cout << s1 << endl; s1.push_back(' '); s1.push_back('i'); s1.push_back(' '); s1.push_back('l'); s1.push_back('o'); s1.push_back('v'); s1.push_back('e'); s1.push_back(' '); s1.push_back('y'); s1.push_back('o'); s1.push_back('u'); cout << s1 << endl; cout << s1.c_str() << endl; return 0; }
我们接着来说一下substr接口：
通过上述文献的索引，我们可以直到，substr是从pos的为止开始，向后len个字符为止，返回值为这中间的字符串。
注意到这里的npos是size_t类型的-1，就是说，其是最大的那个数。
我们再来说一下find接口：
可以看到，其有4种重载形式，每一种也分别代表了不同的含义。
而rfind和find的意思差不多，其主要是从后面去找。
我们把substr和find接口联系在一块来举个例子：
#include<iostream> #include<string> using namespace std; int main() { //获得file的后缀 string file("string.cpp"); size_t pos = file.rfind('.'); cout << pos << endl; string suffix(file.substr(pos, file.size() - pos));//这里就相当于是suffix(file.substr(6,4)); cout << suffix << endl; return 0; }
我们再来举一个find 和substr结合的例子：
注意到这样一个接口，和上面的find的四种重载形式，
就是说，我们这里的find可以指定从某一位置开始找，也可以指定在某一范围开始找。（注：如果找不到，则返回-1）
可以找string，可以找C类型的字符串，还可找单个字符。
#include<iostream> #include<string> using namespace std; int main() { //打印出下面链接的域名 string url("http://www.cplusplus.com/reference/string/string/find/"); cout << url << endl; size_t start = url.find("://"); //先找 :// ，找到，返回:位置的下标，找不到，返回npos if (start == string::npos) { cout << "invalid url" << endl; return -1; } start += 3; //让其向后偏移三个位置 size_t finish = url.find('/', start); //从start的位置开始向后找，找'/' string address = url.substr(start, finish - start); //截取finish到start位置中间的字串 cout << address << endl; return 0; }
删除和插入：
5、string类非成员函数
实际上，这些我们已经不需要再举过多的例子了，相信各位已经或多或少地会用了。我们在后面的模拟实现中会具体地说到其原理。
string类的模拟实现
实际上，用博客的形式来介绍还是比较生硬的，但是不妨碍能够将其说清楚。
好长一大段。
下面，笔者将耐心地为大家一点一点解释。
#include<iostream> #include<string.h> #include<assert.h> namespace jxwd { class string { /*string(const string& s) :_str(new char[strlen(s._str+1)]) { strcpy(_str, s._str); }*///传统写法 //string& operator=(const string& s) //{ /*if (this != &s) { delete[] _str; _str = new char[strlen(s._str) + 1]; strcpy(_str, s._str); } return *this;*///传统写法 //} public: typedef char* iterator; typedef const char* const_iterator; iterator begin() //定义迭代器 { return _str; //可读可写 } iterator end() //同理，定义end()函数返回的迭代器，这里，我们用指针来去实现 { //注意其返回的是最后一个元素的下一个位置 return _str + _size; } const_iterator begin() const { return _str; //仅可读版本 } const_iterator end() const { return _str + _size; } string(const char* str = "", size_t capacity = 1,size_t size = 0) //构造函数 { _str = new char[strlen(str) + 1]; //先创建这么大的空间 if (capacity > strlen(str))_capacity = capacity; //如果现有容量比其小，则现有容量扩大至新的容量大小 else _capacity = strlen(str); //(这取决于你传过来的capacity有多大) _size = _capacity; strcpy(_str, str); //在自己开辟的_str里，将str的内容拷贝过来。 } ~string() //析构函数 { delete[] _str; _str = nullptr; _size = _capacity = 0; } void swap(string& s) //自己创建的swap函数 { std::swap(_str, s._str); std::swap(_size,s._size); std::swap(_capacity, s._capacity); } string(const string& s) //拷贝构造函数 在创建类的时候调用 :_str(nullptr) //初始化三个成员变量 即this指针指向的对象 ,_size(0) ,_capacity(0) { string tmp(s._str); //调用其构造函数 std::swap(_str, tmp._str); //可以直接swap(tmp); std::swap(_size,tmp._size); //将其三个量全部交换 std::swap(_capacity,tmp._capacity); } string& operator=(string s) { std::swap(_str, s._str); //直接调用库中的swap 函数，将变量的内容交换 return *this; //可以直接swap(s)，这样的 话调用的是jxwd::swap }//现代写法 地址会变 //返回*this char& operator[](size_t i) //操作符重载，重载[]操作符//可读可写 { assert(i < _size); return _str[i]; } const char& operator[](size_t i) const //操作符重载，重载[]操作符//仅读 { assert(i < _size); return _str[i]; } const char* c_str() const //c_str函数，用于返回其数组 { return _str; } size_t size() const //返回数组元素的大小 { return _size; } void reserve(size_t n) //reserve函数，用于重置空间 { if (n > _capacity) //开空间，扩展capacity，如果传过来的n>_capacity才开辟，否则就当视而不见 { char* tmp = new char[n + 1]; //动态开辟n+1个(最后一个用于存放'\0') strncpy(tmp, _str,_size); //拷贝，将原先_str里面的_size个数据全部拷贝到tmp里面。 delete[] _str; //销毁原有的_str _str = tmp; //让_str指向tmp _capacity = n; //_capacity赋值成n } } void resize(size_t n , char val = '\0') { //开空间+初始化，并且可能拓展capacity if (n < _size) { _size = n; _str[_size] = '\0'; //要注意需要在最后位置放上'\0' } else { if (n > _capacity) { reserve(n); } for (size_t i = _size; i < n; i++) { _str[i] = val; } _str[n] = '\0'; _size = n; } } void push_back(char ch) //尾插 { if (_size == _capacity) //如果空间不够，则自动扩容 { reserve(_capacity == 0 ? 4 : _capacity*2); } _str[_size] = ch; //将最后原先最后一个位置赋值成ch _str[_size + 1] = '\0'; //然后将下一个位置赋值成'\0' _size++; //让_size自增。因为push_back后元素多了一个 } void append(const char* str) //这就是在后面增加了一个字符串 { size_t len = _size + strlen(str); if (len > _capacity) //先计算是否需要扩容 { reserve(len); } strcpy(_str + _size, str); //再将str拷贝至_str+_size的位置 _size = len; //重新赋值_size的值 } string& insert(size_t pos, char ch) //在pos的位置插入ch 很像顺序表的插入 { assert(pos <= _size); //先断言，判断能否去插入 if (_size == _capacity) { reserve(_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 (_size + len > _capacity) { reserve(_size + len); //和上面一样，该断言断言，该开空间就开空间 } char* end = _str + _size + len; //标注出尾部的地址 while (end >= _str + pos) //同样地道理向后移动，腾出来len个空间 { *(end + 1) = *end; end--; } strncpy(_str + pos, str, len); //同样道理去拷贝 _size += len; //_size重新计算 } string& erase(size_t pos,size_t len = npos) //同理，相当于顺序表的尾删 { size_t leftLen = _size - pos; //如果len缺省，就是从pos的位置，向后全删了 if (len > leftLen) //如果len > leftLen还要大，那就全删了 { _str[pos] = '\0'; //注意'\0' _size = pos; } else { //否则 strcpy(_str + pos, _str + pos + len); //直接将后面的元素连着'\0'一块，拷到前面的位置 _size -= len; //重新计算_size } } string& operator+=(char ch) //重载+= ，如果是加等一个字符，主要是调用push_back { push_back(ch); return *this; } string& operator+=(const char* str) //如果是+=一个字串，就调用append { append(str); return *this; } size_t find(char ch, size_t pos = 0) //find函数，主要就是一个一个去遍历寻找，找到了就返回下标，否则，返回npos { //这是找字符 for (size_t i = pos; i < _size; i++) { if (_str[i] == ch) { return i; } } return npos; } size_t find(const char* str, size_t pos = 0) { const char* ret = strstr(_str, str); //这是找字串，直接调用strstr函数 if (ret) { return ret - _str; } else { return npos; } } void clear() //清除所有数据 { _size = 0; _str[_size] = '\0'; } std::istream& getline(std::istream& cin, string& s) //getline函数，主要获取一行的信息 { s.clear(); //首先是清楚所有数据， char ch; ch = cin.get(); while (ch != '\n') //然后一个一个字符获取，直到获取到'\n'为止 { s += ch; ch = cin.get(); } return cin; //定义要求返回输入流 } private: //这里定义其私有类 char* _str; //由于是字串，我们定义一个数组 size_t _size; //并且定义出其容量和元素个数的大小 size_t _capacity; static const size_t npos; //定义一个静态变量npos,我们等会会看到在外部去定义，定义其为-1. }; //接下来的都是运算符重载 inline bool operator<(const string& s1, const string& s2) //关系运算符的重载 { return strcmp(s1.c_str(), s2.c_str()) < 0; //直接调用strcmp函数 } inline bool operator>(const string& s1, const string& s2) //下面的直接复用上面的 { return !(s1 <= s2); } inline bool operator==(const string& s1, const string& s2) //同上 { return strcmp(s1.c_str(), s2.c_str()) == 0; } inline bool operator<=(const string& s1, const string& s2) { return s1 < s2 || s1 == s2; } inline bool operator>=(const string& s1, const string& s2) { return!(s1 < s2); } inline bool operator!=(const string& s1, const string& s2) { return !(s1 == s2); } std::ostream& operator<<(std::ostream& cout, string& s) //输出一个字串 { for (auto ch : s) //一个一个输出直到将s内容全部输出（遇到空格 Tab和回车都会停止输出） { cout << ch; } return cout; } std::istream& operator>>(std::istream& cin, string& s) //输入一个字串 { s.clear(); char ch; ch = cin.get(); //调用cin.get()函数 while (ch != ' ' && ch != '\n') //一个一个输入，直到遇到空格、换行符或者Tab { s += ch; ch = cin.get(); } return cin; } const size_t string::npos = -1; //定义静态变量为-1(由于其是size_t，所以其为很大很大的数) } 各位可以复制到本地的ide中去看。 我们可以测试测试。 比如：(测试用例：) #define _CRT_SECURE_NO_WARNINGS 1 #include<iostream> #include<string.h> #include<assert.h> namespace jxwd { void test_string1() { string s1("hello world"); string s2(s1); std::cout << s1.c_str() << std::endl; std::cout << s2.c_str() << std::endl; string s3("hello bit"); s1 = s3; std::swap(s1, s3);//效率低 } void test_string2() { string s1("hello world"); s1[0] = 'x'; std::cout << s1[0] << std::endl; std::cout << s1.c_str() << std::endl; } void test_string3() { string s1("hello bit"); string::iterator it = s1.begin(); while (it != s1.end()) { std::cout << *it << " "; it++; } for (auto ch : s1)//会被替代成迭代器，是有迭代器支持的 { std::cout << ch << " "; } std::cout << std::endl; } void test_string4() { string s1("hello"); s1 += '!'; s1.resize(8, 'z'); std::cout << s1.c_str() << std::endl; s1.resize(1, 's'); std::cout << s1.c_str() << std::endl; s1.resize(3); std::cout << s1.c_str() << std::endl; } void test_string5() { string s1("hello ljx"); std::cout << s1.find("hel") << std::endl; } } using namespace std; int main() { jxwd::test_string1(); jxwd::test_string2(); jxwd::test_string3(); jxwd::test_string4(); jxwd::test_string5(); return 0; }
我们得出：
我们下面来看vector.
vector的使用
与string同理，vector实际上与string有许许多多的地方都是一样的。
有关vector的一些说明：
1. vector是表示可变大小数组的序列容器。
2. 就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
3. 本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。
4. vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。 因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
5. 与其它动态序列容器相比（deques, lists and forward_lists）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起lists和forward_lists统一的迭代器和引用更好
相比于string而言，vector甚至更简单。因为其不需要再末尾考虑'\0'的问题了。
对于vector的学习，我们同样的道理，还是借助于文档来完成。
vector常用结构说明
1、vector定义(构造)类
可以看出，密密麻麻的，我们根据具体的用法简化一下：
我们可以这样构造
第一个：无参构造；
第二个：构造并初始化n个val；
第三个：拷贝构造 //也就是文档中的copy
第四个：用迭代器进行构造。
还需要注意的是：
我们可以看到，其定义出来的时候，需要一个模板参数，所以，我们在定义vector类的时候就需要加上这么个模板参数，形成显式模板转换，要不然就会出错。
我们来举几个例子：
如上图所示。各种方法已经标出。
2、vector与string相类似的部分
我们之前说过，vector和string有许许多多类似的地方。
接下来，我们将对比学习。
首先，是二者的迭代器。一样的用法：
再次，是vector的增删查改。
看不出来什么不一样。
并且，vector的空间增容等问题与string基本也是一样的。
这些东西，笔者就不再赘述了，如果以后遇到了问题，可以先于string类进行比较，然后如果有具体问题我们再做补充。
3、vector 迭代器失效问题。
迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装。
比如：vector的迭代器就是原生态指针T*。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃
(即如果继续使用已经失效的迭代器，程序可能会崩溃)
对于vector可能会导致其迭代器失效的操作有：
1. 会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、push_back等。
它们实际上都是由于底层可能会增容导致。我们在string类的模拟实现中就提到过，如果增容用的是calloc，也就是说vector底层原理旧空间被释放掉，而在打印时，it还使用的是释放之间的旧空间，在对it迭代器操作时，实际操作的是一块已经被释放的空间，而引起代码运行时崩溃那么其迭代器所指向的那部分空间，就很有可能失效了。
那有什么解决办法呢？
解决方式：在以上操作完成之后，如果想要继续通过迭代器操作vector中的元素，只需给it重新
赋值即可。
2、指定位置删除元素——erase
#include <iostream> using namespace std; #include <vector> int main() { int a[] = { 1, 2, 3, 4 }; vector<int> v(a, a + sizeof(a) / sizeof(int)); // 使用find查找3所在位置的iterator vector<int>::iterator pos = find(v.begin(), v.end(), 3); // 删除pos位置的数据，导致pos迭代器失效。 v.erase(pos); cout << *pos << endl; // 此处会导致非法访问 return 0; }
erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是：如果pos刚好是最后一个元素，删完之后pos刚好是end的位置，而end位置是没有元素的，那么pos就失效了。
因此删除vector中任意位置上元素时，vs就认为该位置迭代器失效了。
迭代器失效解决办法：在使用前，对迭代器重新赋值即可
关于底层：
我们给个图来理解一下：
注意：其不一定直接在原位置上开辟新空间。其可能是另外开辟，然后其拷贝，再释放旧空间的过程。
vector的模拟实现
#include<iostream> #include<assert.h> using namespace std; namespace ljx { template <class T> class vector { public: typedef T* iterator; //定义出迭代器，可以看出，这里底层是用指针来实现的 typedef const T* const_iterator; vector() //构造函数，实际上，构造函数应当有重载的形式 :_start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) {} vector(int a, int b) //构造函数的重载形式 fill 的形式 :_start(nullptr) ,_finish(nullptr) ,_endofstorage(nullptr) { for (int i = 0; i < a; i++) this->push_back(b); } vector(const vector<T>& v) //拷贝构造 也可以用交换的方法 { _start = new T[v.capacity()]; //首先开辟空间，首地址返回给_start _finish = _start; //_finish 给_start _endofstorage = _start + v.capacity(); //计算尾部的容量 for (size_t i = 0; i < v.size(); i++) { *_finish = v[i]; ++_finish; } } /* vector(const vector<T>& v) :_start(nullptr) ,_finish(nullptr) ,_endofstorage(nullptr) { reserve(v.capacity()); for(const auto e : v) push_back(e);//可以直接调？！ } */ vector<T>& operator=(const vector<T>& v) //赋值构造 { if (this != &v) { delete[] _start; _start = new T[v.capacity()]; memcpy(_start, v._start, sizeof(T) * v.size); } return *this; } //还可以这样写： /*vector<T>& operator=(vector<T> v) { ::swap(_start, v._start); ::swap(_finish, v._finish); ::swap(_endofstorage, v._endofstorage);//可以把它们合成一个Swap函数 return *this; }*/ //如果要交换，不建议直接swap.因为会有三个深拷贝 //可以用v1.swap(v2),这样只是三个指针的拷贝 void print_vector() const //打印 { vector v = *this; vector<int>::const_iterator it = v.begin(); while (it != v.end()) { cout << *it << " "; it++; } cout << endl; } size_t size() const //返回size，即元素个数 { return _finish - _start; } size_t capacity() const //返回capacity，即容量大小 { return _endofstorage - _start; } void reserve(size_t n) //重新定义空间大小 { if (n > capacity()) { size_t sz = size(); T* tmp = new T[n]; //重新在新的为止上开辟空间 if (_start) { //memcpy(tmp, _start, sizeof(T) * sz); for (size_t i = 0; i < sz; i++) { tmp[i] = _start[i];//如果T是string等自定义类型，那么这样就会按照string的深拷贝来进行 } //注意，这里不能用memcpy.因为memcpy所对应的是浅拷贝，只是按照二进制，将对应的地址拷贝过去 delete[] _start; } _start = tmp; _finish = tmp + sz; _endofstorage = tmp + n; } } const_iterator begin() const //定义返回头部第一个元素的迭代器 { return _start; //仅可读 } const_iterator end() const //定义返回尾部的迭代器 { return _finish; //仅可读 } iterator begin() { return _start; } iterator end() { return _finish; } //略 void push_back(const T& x) //尾插 { if (_finish == _endofstorage) //问：是否要增容？ { size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(newcapacity); } *_finish = x; _finish++; } T& operator[](size_t i) //重载[]运算符 { assert(i < size()); return _start[i]; } T& operator[](size_t i) const //第二个版本 { assert(i < size()); return _start[i]; } void pop_back() //尾删 { assert(_start < _finish); --_finish; } void insert(iterator pos, const T& x) //插入 { assert(pos <= _finish); if (_finish == _endofstorage) //判断是否要增容 { 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; //在pos位置插入 ++_finish; } iterator erase(iterator pos) //删除 { assert(pos < _finish); iterator it = pos; //把后面的位置往前移动 while (it < _finish) { *it = *(it + 1); ++it; } --_finish; //减减最后元素的门神 return pos; } void resize(size_t n,const T& val = T()) //重新开辟元素空间大小 { if (n < this->size()) { _finish = _start + n; //问：是否比我原有的size要大？ } else { if (n > capacity()) //问：是否要增容 { reserve(n); } while (_finish < _start + n) //接下来，就将剩下的新增元素初始化为val { *_finish = val; ++_finish; } } } private: iterator _start; //左指针 iterator _finish; //左闭右开，右指针 iterator _endofstorage; //容量的尾部 }; } 我们可以来测试一下： （让主函数去调用这两个函数） 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); vector<int>::iterator it = v.begin(); while (it != v.end()) { cout << *it << " "; ++it; } cout << endl; } void test_vector2() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); vector<int>::iterator it = v.begin(); while (it != v.end()) { if (*it % 2 == 0) { it = v.erase(it); } else { it++; } } v.print_vector(); }
我们得到：
ok。有关vector的内容暂且介绍到这里，后期我们刷题时还会重新见面的。
list类
对于list类，我们重点说其迭代器的模拟实现。
如果说vector是一个数组，是一个顺序表，那么list就是一个链表。
1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息
如果要更准确地说，我们的list 是双向循环带头链表。
list 的用法简介
关于list的用法，实际上，我们通过查看文档就是可以理解的。因为我们已经有了上面string和vector的基础了。
list的构造函数
我们可以看到，其构造的方式有4种。
简而言之，我们可以用迭代器区间去进行构造，可以直接去填充，也可以进行拷贝。
举几个例子：
int main(){ std::list<int> l1; // 构造空的l1 std::list<int> l2 (4,100); // l2中放4个值为100的元素 std::list<int> l3 (l2.begin(), l2.end()); // 用l2的[begin(), end()）左闭右开的区间构 造l3 std::list<int> l4 (l3); // 用l3拷贝构造l4 // 以数组为迭代器区间构造l5 int array[] = {16,2,77,29}; std::list<int> l5 (array, array + sizeof(array) / sizeof(int) ); // 用迭代器方式打印l5中的元素 for(std::list<int>::iterator it = l5.begin(); it != l5.end(); it++) std::cout << *it << " "; std::cout<<endl; // C++11范围for的方式遍历 for(auto& e : l5) std::cout<< e << " "; std::cout<<endl; return 0; }
那么链表有两种遍历方式。
一种是用显示的迭代器去遍历；
还有一种是用范围for（本质上还是迭代器）（如上述代码）
list的迭代器
1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动
这些东西和string、vector几乎都是一样的，就是要注意的是其是循环的。这个链表的思路我们在数据结构的时候就曾说过。
其他成员函数
我们这里就说一个：assign(其余的我们将在模拟实现的时候一笔带过)
它的意思就是说，先把原有的链表内容清空，然后将n个val的值拷贝入新的链表中。
我们再说一个：
用于拼接，就是说，我能将list& x拼接到list中（就是调用该函数的类）
后面的二者是迭代器，即拼接的范围。
注意：在list中，使用insert后，原本的迭代器不会失效。但是在使用erase时，使用完的迭代器便会失效。
list的模拟实现（重头戏）
在此之前，我们需要将一个思想：
由于list的底层在存储的时候地址不是连续的，但是我们有需要实现++;--;*等运算操作，我们需要自己构建一个迭代器类，将其封装起来然后使用。这也是我们模拟实现list的重点。
我们接下来进行模拟实现：
#include<iostream> #include<assert.h> namespace jxwd { template<class T> struct _list_node //该结构体是为了要构建结点（即链表的结点） { T val; _list_node<T>* _next; _list_node<T>* _prev; _list_node(const T& x = T()) :val(x) ,_next(nullptr) ,_prev(nullptr) {} }; template <class T ,class Ref ,class Cal> //封装着迭代器的类 struct _list_iterator { typedef _list_node<T> node; //而在这里，我就是想要进行一个浅拷贝 typedef _list_iterator<T,Ref,Cal> self; //所以这里拷贝构造、operator、析构我们不写，编译器默认生成的就可以用 node* _pnode; //定义一个_pnode结点，即用于迭代器的底层实现——实际上就是一个链表结点的指针 _list_iterator(node* pnode) //迭代器类的构造函数 :_pnode(pnode) { } Ref operator*() //解引用，返回T&类型 { return _pnode->val; } Cal operator->() //重载->操作符,返回T* { return &_pnode->val; } bool operator!=(const self& s) const //操作符重载，并且提供const与否的两种类型 { return _pnode != s._pnode; } bool operator==(const self& s) const { return _pnode == s._pnode; } self& operator++() //重载前置++，返回一个迭代器类型 { _pnode = _pnode->_next; return *this; } //it++ -> it.operator++(&it,0) //++it ->it.operator++(&it) self operator++(int) //重载后置++，返回未++的迭代器，并将迭代器++ { self tmp(*this); _pnode = _pnode->_next; return tmp; } self& operator--() //同++理 { _pnode = _pnode->_prev; return *this; } self operator--(int) { self tmp(*this); _pnode = _pnode->_prev; return tmp; } }; template<class T> class list { typedef _list_node<T> node; public: typedef _list_iterator<T , T&, T*> iterator; //将封装的迭代器类重命名未iterator typedef _list_iterator<T, const T&,const T*> const_iterator;//同上，只不过定义要求了另外一种const 类型 iterator begin() //返回第一个结点的迭代器 { return iterator(_head->_next); } iterator end() //返回最后一个结点的下一个位置的迭代器（即头节点） { return iterator(_head); } const_iterator begin() const //第二种类型 { return const_iterator(_head->_next); } const_iterator end() const { return const_iterator(_head); } list() //构造函数 { _head = new node; _head-> _next = _head; _head-> _prev = _head; } ~list() //析构函数 { clear(); delete _head; _head = nullptr; } list(const list<T>& x) //拷贝构造 { _head = new node; _head->_next = _head; _head->_prev = _head; for (const auto& e : x) { push_back(e); } } //list<int>& operator=(const list<T>& lt) //{ // if (this != <) // { // clear(); // for (const auto& e : lt) // { // push_back(e); // } // } // return *this; //}//传统写法 list<T>& operator=(list<T>& lt) //赋值运算符重载 { ::swap(_head, lt._head); return *this; } void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } } void push_back(const T& x) { node* newnode = new node(x); node* tail = _head->_prev; tail->_next = newnode; newnode->_prev = tail; newnode->_next = _head; _head->_prev = newnode; //insert(end(),x); //尾插，一种思路时复用insert() } void push_front(const T& x) { insert(begin(), x); } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } void insert(iterator pos, const T& x) //在pos前面插入 { assert(pos._pnode); node* cur = pos._pnode; //三结点之间的关系 node* prev = cur->_prev; node* newnode = new node(x); prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; } iterator erase(iterator pos) //删除pos结点 { assert(pos._pnode); assert(pos != end()); node* prev = pos._pnode->_prev; node* next = pos._pnode->_next; delete pos._pnode; prev->_next = next; next->_prev = prev; return iterator(next); } bool empty() //判断是否为空 { return begin() == end(); } size_t size() //计算结点数 { size_t sz = 0; iterator it = begin(); while (it != end()) { sz++; it++; } return sz; } private: node* _head; //定义一个哨兵位——头节点 }; }
我们这里的模拟实现，主要是针对迭代器封装的模拟，其他的链表成员我们都简略或者省略了。
我们可以测试看看：
namespace jxwd{ void func() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); list<int> llt(lt); list<int>::iterator it = llt.begin(); //这里是将返回的迭代器 进行拷贝构造 while (it != llt.end()) { std::cout << *it << " "; ++it; } std::cout << std::endl; } void test_list2() { list<int> lt; lt.push_back(10); lt.push_back(20); list<int> lt2(lt); list<int>::iterator it = lt2.begin(); while (it!=lt2.end()) { std::cout << *it << " "; it++; } } }
我们将上面的函数放在main函数中测试一下看看，发现程序成功运行了起来。下面是运行截图：
这就说明我们模拟成功了。
对于迭代器的封装模拟使用也是正确的。
好耶！！！
至于vector和list 的对比，实际上就是链表和顺序表的对比，如果想看的话，我们下节再啰嗦一遍吧
好啦，我们本节的内容就先到这里吧，我们下节再见。
