一、模拟实现源码
#pragma once
namespace sjx
{
template <typename T>
struct __list_node
{
__list_node<T>* _next;
__list_node<T>* _prev;
T _data;
__list_node(const T& val = T()) :_data(val), _next(nullptr), _prev(nullptr)
{
}
};
template <typename T, typename Ref, typename Ptr>
struct __list_iterator
{
typedef __list_node<T> node;
typedef __list_node<T>* node_pointer;
typedef __list_iterator<T, Ref, Ptr> self;
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
node_pointer _pnode;
__list_iterator(const node_pointer& val = nullptr) :_pnode(val) {}
__list_iterator(const iterator& it) :_pnode(it._pnode) {}
Ref operator*()
{
return _pnode->_data;
}
Ptr operator->()
{
return &(_pnode->_data);
}
bool operator!=(const self& val) const
{
return _pnode != val._pnode;
}
bool operator==(const self& val) const
{
return _pnode == val._pnode;
}
self& operator++()
{
_pnode = _pnode->_next;
return *this;
}
self operator++(int)
{
self tmp(_pnode);
_pnode = _pnode->_next;
return tmp;
}
self& operator--()
{
_pnode = _pnode->_prev;
return *this;
}
self operator--(int)
{
self tmp(_pnode);
_pnode = _pnode->_prev;
return tmp;
}
};
template <typename T>
class list
{
public:
typedef __list_node<T> node;
typedef __list_node<T>* node_pointer;
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
list()
{
empty_initialize();
}
template <typename InputIterator>
list(InputIterator first, InputIterator last)
{
empty_initialize();
while (first != last)
{
push_back(*first);
++first;
}
}
list(const list& other)
{
empty_initialize();
list<T> tmp(other.begin(), other.end());
swap(tmp);
}
~list()
{
clear();
delete _head;
}
list<T>& operator=(list<T> other)
{
empty_initialize();
swap(other);
return *this;
}
// Element access
T& front()
{
assert(!empty());
return _head->_next->_data;
}
const T& front() const
{
assert(!empty());
return _head->_next->_data;
}
T& back()
{
assert(!empty());
return _head->_prev->_data;
}
const T& back() const
{
assert(!empty());
return _head->_prev->_data;
}
// Iterators
iterator begin()
{
return _head->_next;
}
const_iterator begin() const
{
return _head->_next;
}
iterator end()
{
return _head;
}
const_iterator end() const
{
return _head;
}
// Capacity
bool empty() const
{
return _head->_next == _head;
}
size_t size() const
{
size_t i = 0;
node_pointer cur = _head->_next;
while (cur != _head)
{
++i;
cur = cur->_next;
}
return i;
}
// Modifiers
void clear()
{
node_pointer cur = _head->_next;
while (cur != _head)
{
node_pointer tmp = cur->_next;
delete cur;
cur = tmp;
}
_head->_next = _head;
_head->_prev = _head;
}
iterator insert(const_iterator pos, const T& val)
{
node_pointer cur = new node(val);
node_pointer tail = pos._pnode;
node_pointer head = tail->_prev;
head->_next = cur;
cur->_next = tail;
tail->_prev = cur;
cur->_prev = head;
return cur;
}
iterator insert(const_iterator pos, size_t count, const T& val)
{
for (size_t i = 0; i < count; ++i)
{
pos = insert(pos, val);
}
return pos._pnode;
}
template <typename InputIterator>
iterator insert(const_iterator pos, InputIterator first, InputIterator last)
{
node_pointer head = pos._pnode;
if (first != last)
{
head = insert(pos, *first)._pnode;
++first;
}
while (first != last)
{
insert(pos, *first);
++first;
}
return head;
}
iterator erase(const_iterator pos)
{
node_pointer tmp = pos._pnode;
if (pos != end())
{
node_pointer del = tmp;
tmp = tmp->_next;
del->_prev->_next = del->_next;
del->_next->_prev = del->_prev;
delete del;
}
return tmp;
}
iterator erase(const_iterator first, const_iterator last)
{
while (first != last)
{
first = erase(first);
}
return last._pnode;
}
void push_back(const T& val)
{
node_pointer tmp = new node(val);
node_pointer tail = _head->_prev;
tail->_next = tmp;
tmp->_next = _head;
_head->_prev = tmp;
tmp->_prev = tail;
}
void pop_back()
{
erase(--end());
}
void push_front(const T& val)
{
insert(begin(), val);
}
void pop_front()
{
erase(begin());
}
void swap(list<T>& val)
{
std::swap(_head, val._head);
}
protected:
void empty_initialize()
{
_head = new node;
_head->_next = _head;
_head->_prev = _head;
}
private:
node_pointer _head;
};
}二、重难点——迭代器实现
list的迭代器不同于vector，vector的迭代器用指针就可以实现大部分功能，但是list的迭代器要实现++，不再是单纯数值上的加减，而是要让迭代器指向当前结点的next。
因此，需要将list的迭代器封装成一个类__list_iterator。通过运算符重载，来改变迭代器运算的效果。
需要注意的是__list_iterator还有另外两个模板参数，Ref和Ptr。
对于const_iterator，它与普通的iterator的区别就是它里面的内容不允许被修改，但是本身依旧可以进行++或者--等操作，其区别之一就在于对迭代器的解引用，一个的返回值可以被修改，一个不可以，因此我们引入了一个模板参数Ref，对于普通的迭代器，它被设置为T&，而对于const迭代器，它被设置为const T&。
对于模板参数Ptr，需要应对以下情况：
#include <iostream>
#include <assert.h>
#include "my_list.h"
struct Data
{
int _year;
int _month;
int _day;
Data(int year = 2000, int month = 1, int day = 1)
:_year(year)
, _month(month)
, _day(day)
{
}
};
int main()
{
// 如果存储的对象是自定义类型，且要访问其中的数据
sjx::list<Data> l1;
l1.push_back(Data());
sjx::list<Data>::iterator it = l1.begin();
// 使用 * 访问
std::cout << (*it)._year << " " << (*it)._month << " " << (*it)._day << std::endl;
// 使用 operator->
std::cout << it.operator->()->_year << " " << it.operator->()->_month << " " << it.operator->()->_day << std::endl;
// 为了可读性，一般我们省略了一个 ->
std::cout << it->_year << " " << it->_month << " " << it->_day << std::endl;
return 0;
}
以上三种输出方式实际上是等价的。
