目录
关于list
list常见接口实现
STL的精华之迭代器
关于list
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常见接口实现（参考部分g++版本下stl底层源码）
namespace dw
{
template<class T>
struct list_node //链表节点
{
list_node<T>* _prev;
list_node<T>* _next;
T _data;
};
//迭代器实现
template<class T>
class list
{
typedef list_node<T> node;
public:
//代码实现
private:
node* _head;
};
//------------------------------------------------
void list_test()
{
;
}
}1.注意：类名不是类型，建议声明类型的时候都加上模板参数
举例来说这里 list_node 是类名， list_node<T> 是类型
如果不加上模板参数运行程序会报错
typedef list_node<T> node;typedef list_node node;
2.注意：这里使用的 struct 定义类，struct 定义的类默认访问权限是公开。
构造函数
无参
void empty_init() //初始化头节点
{
_head = new node;
_head->_next = _head;
_head->_prev = _head;
}
list()
{
empty_init();
}push_back
void push_back(const T& x)
{
node* tail = _head->_prev;
node* newnode = new node(x);
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;
}注意，这里测试运行会发现：
原因出在：
node* newnode = new node(x);所以关于链表节点 list_node 的这个类也需要实现构造函数
list_node(const T& x = T()) //这里是匿名对象调用构造函数
:_prev(nullptr)
,_next(nullptr)
,_data(x)
{}
STL的精华之迭代器
这样就完成了需要的准备工作，接下来就可以进行神奇的迭代器部分了，看完大呼 - 还可以这样玩。
上面的代码可以通过测试以及调试观看到具体状态，那么怎么进行成员访问？
我们知道，vector 迭代器使用的是原生指针(g++版本) vector相关迭代器的实现，因为 vector 可以看作是一块连续的物理空间，我们通过下标就可以访问到下一个元素
但是链表可以这样玩吗？肯定是不可以的！所以，这里 list 迭代器的实现不能使用原生指针，而是需要一个类去进行封装。
iterator
//迭代器实现
template<class T>
struct __list_iterator
{
public:
typedef list_node<T> node;
typedef __list_iterator self;
node* _node;
__list_iterator(node* x)
:_node(x)
{}
T& operator*()
{
return _node->_data;
}
self& operator++()
{
_node = _node->_next;
return *this;
}
bool operator!=(const self& s)
{
return _node != s._node;
}
};注意：c++一般不喜欢内部类，所以一般都使用自定义类型
继而我们需要在 list 类进行 typedef
typedef __list_iterator<T> iterator;begin()
begin（）是第一个节点的位置
iterator begin()
{
iterator tmp(_head->_next);
return tmp;
}
end()
end（）是头节点的位置
iterator end()
{
return iterator(_head);
}注：这里和 begin( ) 的写法其实没什么不同，本质上是运用了匿名对象。
- 其实这里可以看到，虽然vector，list 表面上都是 iterator，但是底层却千差万别，这些都源自于底层的封装
- 并且，可以明显的感觉到迭代器很好体现了类的设计价值。如果一个内置类型无法满足我们的需求，那么我们可以使用一个自定义类型去封装，然后重载运算符，继而改变它的行为
- 比如说这里的 iterator 是一个节点的指针，++， * 不满足我们的需求，我们可以去进行封装, 用类去封装一个node* 重载++， * 运算符的函数
- 重载运算符函数的具体实现以及行为完全由我们自己来定义，这是自定义类型＋运算符重载＋类的定义等等的价值
其次，关于下面这句代码，我们并没有实现拷贝构造，编译器会默认生成，默认生成的拷贝构造是浅拷贝，那么，这里可以使用浅拷贝嘛？为什么没报错?
list<int>::iterator it = lt.begin();//首先:这里是需要浅拷贝的，因为这里拷贝的是指向节点的指针
//其次，为什么没报错 ? 是因为迭代器没有写析构函数，那么为什么没写 ?
//是因为迭代器不需要释放节点。更深层次一些，为什么不需要释放节点 ?
//虽然这里迭代器有指向节点的指针，但是并不支持释放节点，因为释放节点是链表的行为
//链表会有析构函数释放节点，也可以简单把这里迭代器理解为工具，可以支持读或者写
//但是只有使用权限，并没有归属权限，所以这里浅拷贝也就没有问题了。
然后现在就可以丰富一些 迭代器 __list_iterator 这个类，后置 ++ ，--，等等
template<class T>
struct __list_iterator
{
public:
typedef list_node<T> node;
typedef __list_iterator<T> self;
node* _node;
__list_iterator(node* x)
:_node(x)
{}
T& operator*()
{
return _node->_data;
}
self& operator++()
{
_node = _node->_next;
return *this;
}
bool operator!=(const self& s)
{
return _node != s._node;
}
self& operator++(int) //编译器会默认传一个整型，进行占位，更前置进行区分
{
self tmp(*this);
_node = _node->_next;
return tmp;
}
self& operator--()
{
_node = _node->_prev;
return *this;
}
self& operator--(int)
{
self tmp(*this);
_node = _node->_prev;
return tmp;
}
bool operator==(const self& s)
{
return _node == s._node;
}
};const_iterator
接下来是关于 const 修饰的迭代器，如果是下面这样环境，该怎么办？
这里的迭代器就需要使用const 进行修饰了，那么请问这样写法可不可以？
iterator begin() const
{
iterator tmp(_head->_next);
return tmp;
}
iterator end() const
{
return iterator(_head);
}这里运行编译通过，但是存在一个问题，明明是const修饰，为什么还能构造迭代器?
因为这里的const修饰的是*this 也就是指向的内容，*this 是这个节点的指针，const修饰的是这个指针的本身不能被改变，也就是_head不能被改变，但是可以拷贝。
结果发现并不符合我们的预期，因为这里我们期望迭代器被 const 修饰之后内容不可修改。这里不仅可读，并且可写，显然程序是有些不正确的。
所以这里的写法是我们需要再完成一个类，也就是 __list_const_iterator
template<class T>
struct __list_const_iterator
{
public:
typedef list_node<T> node;
typedef __list_const_iterator<T> self;
node* _node;
__list_const_iterator(node* x)
:_node(x)
{}
const T& operator*()
{
return _node->_data;
}
self& operator++()
{
_node = _node->_next;
return *this;
}
bool operator!=(const self& s)
{
return _node != s._node;
}
self& operator++(int)
{
self tmp(*this);
_node = _node->_next;
return tmp;
}
self& operator--()
{
_node = _node->_prev;
return *this;
}
self& operator--(int)
{
self tmp(*this);
_node = _node->_prev;
return tmp;
}
bool operator==(const self& s)
{
return _node == s._node;
}
};注意：c++一般不喜欢内部类，所以一般都使用自定义类型
继而我们需要在 list 类进行 typedef
typedef __list_const_iterator<T> const_iterator;begin()
const_iterator begin() const
{
const_iterator tmp(_head->_next);
return tmp;
}end()
const_iterator end() const
{
return const_iterator(_head);
}代码程序正常运行
但是观察上面这两个类我们会发现，__list_iterator 与 __list_const_iterator
他们的区别只在于重载运算符解引用的实现不同，更细节一点只是解引用的返回值不同
__list_iterator
__list_const_iterator
但是却写了两个类，这样会显得代码很臃肿，会让人觉得一模一样的代码为什么要写两遍，所以这里提出了一个新的语法知识 - - - 添加模板参数
代码如下：
template<class T, class Ref>
struct __list_iterator
{
public:
typedef list_node<T> node;
typedef __list_iterator<T, Ref> self;
node* _node;
__list_iterator(node* x)
:_node(x)
{}
Ref operator*()
{
return _node->_data;
}
self& operator++()
{
_node = _node->_next;
return *this;
}
bool operator!=(const self& s)
{
return _node != s._node;
}
self& operator++(int) //编译器会默认传一个整型，进行占位，更前置进行区分
{
self tmp(*this);
_node = _node->_next;
return tmp;
}
self& operator--()
{
_node = _node->_prev;
return *this;
}
self& operator--(int)
{
self tmp(*this);
_node = _node->_prev;
return tmp;
}
bool operator==(const self& s)
{
return _node == s._node;
}
};这样 __list_iterator 与 __list_const_iterator 就可以合并为一个类
再修改一些 list ，模板参数不同，调用逻辑也不同
typedef __list_iterator<T, T&> iterator;
typedef __list_iterator<T, const T&> const_iterator;
//typedef __list_const_iterator<T> const_iterator; //注释掉例：
如果你认为到这里就结束了，那么不好意思，还差一点。因为观察库里 list 的实现，我们会发现迭代器的模板参数是三个。
附上stl部分底层源码：
template<class T, class Ref, class Ptr>
struct __list_iterator {
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
typedef __list_iterator<T, Ref, Ptr> self;
typedef bidirectional_iterator_tag iterator_category;
typedef T value_type;
typedef Ptr pointer;
typedef Ref reference;
typedef __list_node<T>* link_type;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
link_type node;
__list_iterator(link_type x) : node(x) {}
__list_iterator() {}
__list_iterator(const iterator& x) : node(x.node) {}
bool operator==(const self& x) const { return node == x.node; }
bool operator!=(const self& x) const { return node != x.node; }
reference operator*() const { return (*node).data; }
#ifndef __SGI_STL_NO_ARROW_OPERATOR
pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */
self& operator++() {
node = (link_type)((*node).next);
return *this;
}
self operator++(int) {
self tmp = *this;
++*this;
return tmp;
}
self& operator--() {
node = (link_type)((*node).prev);
return *this;
}
self operator--(int) {
self tmp = *this;
--*this;
return tmp;
}
};源码的 Ptr 是什么？因为这里不仅重载了*，还重载了 ->，那么什么时候要去调用->呢?
1.迭代器要么就是原生指针
⒉.迭代器要么就是自定义类型对原生指针的封装，模拟指针的行为
解释这个原因的话，先看一个测试用例：
这时候我们会发现，之所以会报错是因为AA这个类没有自己实现一个流插入
所以要是想让代码跑起来，有很多的解决办法
方法一便是根据AA这个类型重载一个流插入
所以回过头来也能发现，c++新增运算符重载，而不是继续使用printf函数，是因为printf函数有局限性，printf只能打印内置类型，%d，%lf等等。
但是打印也不是没有其他办法，比如说上面这种，但是看到似乎是有点怪，解引用之后﹒去访问成员
所以这样为了看起来更顺畅一些，我们需要去实现 ->
这里返回值是T*，但是如果是const迭代器呢?
所以这里就不能使用T*，而是需要新增加函数模板参数 Ptr
template<class T, class Ref, class Ptr>
struct __list_iterator
{
public:
typedef list_node<T> node;
typedef __list_iterator<T, Ref, Ptr> self;
node* _node;
__list_iterator(node* x)
:_node(x)
{}
Ptr operator->()
{
return &_node->_data;
}
Ref operator*()
{
return _node->_data;
}
self& operator++()
{
_node = _node->_next;
return *this;
}
bool operator!=(const self& s)
{
return _node != s._node;
}
self& operator++(int)
{
self tmp(*this);
_node = _node->_next;
return tmp;
}
self& operator--()
{
_node = _node->_prev;
return *this;
}
self& operator--(int)
{
self tmp(*this);
_node = _node->_prev;
return tmp;
}
bool operator==(const self& s)
{
return _node == s._node;
}
};
以上就是list底层源码的实现逻辑，补充一点：
这里看着是有些怪异的，因为
it-> _a1
it-> ->_a1
本来这里应该是两个 ->
一个是运算符重载的调用
一个是有了结构体的指针再使用 -> 去访问
这里为了增加代码的可读性，省略了一个-> ，可以理解为是一个特殊处理
看似是：
cout << it->_a1 << ":" << it->_a2 << endl;实际上：
cout << it.operator->()->_a1 << ":" << it.operator->()->_a2 << endl;另外需要说明的点是：
迭代器用原生指针只是一个偶然，用类去封装才是一个常态
但是底层的本质都可以认为是指针，只说是嵌入了一个自定义类型去封装指针，在编译器看来是自定义类型而不是指针
并且自定义类型使用运算符只能去重载运算符，至于重载运算符函数的行为，完全是由我们自己来控制的
包括vector的迭代器， 在g++版本下（linux系统）是原生指针，但是vs下也不是原生指针，因为vs需要重载运算符函数，比如 * 用来判断迭代器是否失效。
要注意，不同编译器底层实现不同。以上就是 stl 的精华部分，关于迭代器。
swap
void swap(list<T>& tmp)
{
std::swap(_head, tmp._head);
}迭代器区间构造
template<class Iterator>
list(Iterator first, Iterator last)
{
empty_init();
while (first != last)
{
push_back(*first);
first++;
}
}拷贝构造
//现代写法
list(const list<T>& lt)
{
empty_init();
list<T> tmp(lt.begin(), lt.end());
swap(tmp);
}
//传统写法
list(const list<T>& lt)
{
empty_init();
for (auto e : lt)
{
push_back(e);
}
}赋值
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}insert
void insert(iterator pos, const T& x)
{
node* cur = pos._node;
node* prev = cur->_prev;
node* new_node = new node(x);
prev->_next = new_node;
new_node->_next = cur;
new_node->_prev = prev;
cur->_prev = new_node;
}erase
void erase(iterator pos)
{
assert(pos != end());
node* next = pos._node->_next;
node* prev = pos._node->_prev;
next->_prev = prev;
prev->_next = next;
delete pos._node;
}
//看需求
iterator erase(iterator pos)
{
assert(pos != end());
node* next = pos._node->_next;
node* prev = pos._node->_prev;
next->_prev = prev;
prev->_next = next;
delete pos._node;
return iterator(next);
}push_front
void push_front(const T& x)
{
insert(begin(), x);
}
pop_back
void pop_back()
{
erase(--end());
}
pop_front
void pop_front()
{
erase(begin());
}clear
void clear()
{
iterator it = begin();
while (it != end())
{
erase(it++);
//it = erase(it); //两种方法都可以，这中 erase 需要有返回值
}
}析构函数
~list()
{
clear();
delete _head;
_head = nullptr;
}
最后附上全部代码以及测试用例：
list.h
namespace dw
{
template<class T>
struct list_node //链表节点
{
list_node<T>* _prev;
list_node<T>* _next;
T _data;
list_node(const T& x = T())
:_prev(nullptr)
,_next(nullptr)
,_data(x)
{}
};
//迭代器实现
template<class T, class Ref, class Ptr>
struct __list_iterator
{
public:
typedef list_node<T> node;
typedef __list_iterator<T, Ref, Ptr> self;
node* _node;
__list_iterator(node* x)
:_node(x)
{}
Ptr operator->()
{
return &_node->_data;
}
Ref operator*()
{
return _node->_data;
}
self& operator++()
{
_node = _node->_next;
return *this;
}
bool operator!=(const self& s)
{
return _node != s._node;
}
self& operator++(int) //编译器会默认传一个整型，进行占位，更前置进行区分
{
self tmp(*this);
_node = _node->_next;
return tmp;
}
self& operator--()
{
_node = _node->_prev;
return *this;
}
self& operator--(int)
{
self tmp(*this);
_node = _node->_prev;
return tmp;
}
bool operator==(const self& s)
{
return _node == s._node;
}
};
/*
template<class T>
struct __list_const_iterator
{
public:
typedef list_node<T> node;
typedef __list_const_iterator<T> self;
node* _node;
__list_const_iterator(node* x)
:_node(x)
{}
const T& operator*()
{
return _node->_data;
}
self& operator++()
{
_node = _node->_next;
return *this;
}
bool operator!=(const self& s)
{
return _node != s._node;
}
self& operator++(int)
{
self tmp(*this);
_node = _node->_next;
return tmp;
}
self& operator--()
{
_node = _node->_prev;
return *this;
}
self& operator--(int)
{
self tmp(*this);
_node = _node->_prev;
return tmp;
}
bool operator==(const self& s)
{
return _node == s._node;
}
};
*/
template<class T>
class list
{
typedef list_node<T> node;
public:
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
//typedef __list_const_iterator<T> const_iterator;
void empty_init() //初始化头节点
{
_head = new node;
_head->_next = _head;
_head->_prev = _head;
}
list()
{
empty_init();
}
void swap(list<T>& tmp)
{
std::swap(_head, tmp._head);
}
//现代写法
list(const list<T>& lt)
{
empty_init();
list<T> tmp(lt.begin(), lt.end());
swap(tmp);
}
//传统写法
//list(const list<T>& lt)
//{
// empty_init();
// for (auto e : lt)
// {
// push_back(e);
// }
//}
template<class Iterator>
list(Iterator first, Iterator last)
{
empty_init();
while (first != last)
{
push_back(*first);
first++;
}
}
//lt2 = lt1
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
iterator begin()
{
iterator tmp(_head->_next);
return tmp;
}
iterator end()
{
return iterator(_head);
}
const_iterator begin() const
{
const_iterator tmp(_head->_next);
return tmp;
}
const_iterator end() const
{
return const_iterator(_head);
}
void push_back(const T& x)
{
node* tail = _head->_prev;
node* newnode = new node(x);
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}
iterator erase(iterator pos)
{
assert(pos != end());
node* next = pos._node->_next;
node* prev = pos._node->_prev;
next->_prev = prev;
prev->_next = next;
delete pos._node;
return iterator(next);
}
void insert(iterator pos, const T& x)
{
node* cur = pos._node;
node* prev = cur->_prev;
node* new_node = new node(x);
prev->_next = new_node;
new_node->_next = cur;
new_node->_prev = prev;
cur->_prev = new_node;
}
void clear()
{
iterator it = begin();
while (it != end())
{
erase(it++);
//it = erase(it); //两种方法都可以，这中 erase 需要有返回值
}
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
private:
node* _head;
};
//------------------------------------------------
void print_list(const list<int>& lt)
{
list<int>::const_iterator it = lt.begin();
while (it != lt.end())
{
//(*it) *= 2;
cout << *it << " ";
++it;
}
cout << endl;
}
void list_test1()
{
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>::iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
print_list(lt);
list<int> lt2(lt);
for (auto e : lt2)
{
cout << e << " ";
}
cout << endl;
list<int> lt3 = lt2;
for (auto e : lt3)
{
cout << e << " ";
}
cout << endl;
}
void list_test2()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
lt.push_back(1000); //测试尾插
lt.push_front(100); // 测试头插
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
lt.pop_back(); // 测试尾删
lt.pop_front(); //测试头删
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
auto pos = lt.begin();
++pos;
lt.insert(pos, 9); //测试任意位置插入
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
pos = lt.begin();
++pos;
lt.erase(pos); // 测试任意位置删除
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
}
}
