【C++之容器篇】造轮子：list的模拟实现与使用

前言

前面我们已经学习了string和vector的模拟实现和使用，相信对于容器的模拟实现和使用的能力已经上升一定的水平，今天我们要学习的是list的模拟实现，List的模拟实现和string和vector其实没有本质的区别，只是在list的模拟实现过程中，list的迭代器和string和vector有所不同，这是我们实现List的模拟实现中需要重点掌握的，今天学习的List本质就是一个带头双向循环链表。

一、关于list

1. 简介

list本质就是一个带头双向循环链表，支持在任何位置以O(1)的时间进行插入和删除。

2. 成员类型

看到上图，我们一定要知道迭代器的类型：list中的迭代器的类型是双向迭代器，其他的迭代器类型好还有：单向迭代器，随机迭代器。

• 单向迭代器：只支持单向遍历访问的迭代器，只支持++，不支持–
• 双向迭代器：支持双向访问容器的迭代器，同时支持++和–
• 随机迭代器：支持随机访问容器的迭代器，同时支持++，–，+，-

二、默认成员函数

1. 构造函数

1. list()

• 使用代码

void test_list1()
{// 无参构造函数list<int> lt1;// 创建一个存储int的list对象list<char> lt2;// 创建一个存储char的list对象list<double> lt3;// 创建一个存储double的list对象list<string> lt4;// 创建一个存储string的list对象
}

2. list(size_t n,const T& val = T())和list(InputIterator first,InputIterator last)

• 使用代码：

void test_list2()
{// 用n个值来构造Listlist<int> lt1(3, 6);// 用3个6来构造一个list对象// 使用一段迭代器区间来构造string s2("hello list::list(InputIterator first,InputIterator last)");vector<char> v2(s2.begin(), s2.end());list<char> lt2(v2.begin(), v2.end());// 遍历// 使用迭代器进行遍历// 遍历lt1cout << "lt1:" << endl;list<int>::iterator lit1 = lt1.begin();while (lit1 != lt1.end()){cout << *lit1 << " ";lit1++;}cout << endl;// 遍历lt2cout << "lt2:" << endl;list<char>::iterator lit2 = lt2.begin();while (lit2 != lt2.end()){cout << *lit2 << " ";lit2++;}cout << endl;// 使用范围for进行遍历cout << "lt1:" << endl;for (auto& e : lt1){cout << e << " ";}cout << endl;cout << "lt2:" << endl;for (auto& e : lt2){cout << e << " ";}cout << endl;}

运行结果：

2. 拷贝构造函数

拷贝构造函数和前面的容器样子还是差不多

void test_list3()
{string s("hello list(const list<char>& lt)");list<char> lt1(s.begin(), s.end());list<char> lt2(lt1);cout << "lt1:" << endl;for (auto& e : lt1){cout << e << " ";}cout << endl;cout << "lt2" << endl;for (auto& e : lt2){cout << e << " ";}cout << endl;
}

运行结果：

3. 析构函数

4. 赋值运算符重载函数

• 使用代码：

void test_list4()
{string s("hello list<char>& operator=(const list<char>& lt)");list<char> lt(s.begin(), s.end());list<char> lt1;lt1 = lt;// 调用赋值运算符重载函数cout << "lt:" << endl;for (auto& e : lt){cout << e << " ";}cout << endl;cout << "lt1:" << endl;for (auto& e : lt1){cout << e << " ";}cout << endl;}

运行结果：

三、迭代器

1. 普通对象的正向迭代器

• 使用代码：

void test_list5()
{string s("hello list<char>::iterator begin() and end()");list<char> lt(s.begin(), s.end());list<char>::iterator lit = lt.begin();while (lit != lt.end()){cout << *lit << " ";lit++;}cout << endl;
}

运行结果：

2. const对象的正向迭代器

• 使用代码：

void test_list6()
{string s("hello list<char>::const_iterator begin() and end()");const list<char> lt(s.begin(), s.end());list<char>::const_iterator lit = lt.begin();while (lit != lt.end()){cout << *lit << " ";lit++;}cout << endl;
}

运行结果：

3. 普通对象的反向迭代器

使用代码：

void test_list7()
{string s("hello list<char>::reverse_iterator begin() and end()");list<char> lt(s.begin(), s.end());list<char>::reverse_iterator lit = lt.rbegin();while (lit != lt.rend()){cout << *lit << " ";lit++;}cout << endl;
}

4. const对象的反向迭代器

四、容量接口

1. empty()

2. size()

五、元素访问接口

1. front()

2. back()

六、修改接口

1. push_front()

2. pop_front()

3. push_back()

4. pop_back()

5. insert()

6.erase()