【C++】STL容器：list的模拟实现-创新互联
一、list的结构
1. list的节点
二、list的迭代器
2. 反向迭代器
三、构造和析构
四、insert和erase
五、其他元素操作
分享文章：【C++】STL容器：list的模拟实现-创新互联
分享网址：http://scjbc.cn/article/ddisch.html
list的底层是一个带头双向循环链表，但list本身和list的节点是不同的结构，需要分开实现。
list节点的结构：
templatestruct list_node
{list_node* _next;
list_node* _prev;
T _data;
//构造：使用x初始化节点的数据
list_node(const T& x)
:_next(nullptr)
, _prev(nullptr)
, _data(x)
{}
}; class list
{typedef list_nodenode;
//……
private:
node* _head;
size_t _size;
}; 二、list的迭代器
list的迭代器不能再像vector一样用普通指针作为迭代器，因为存储节点的空间不保证连续。
list迭代器必须有能力指向list的节点，并能够正确的进行++、--、*、->等操作，所谓正确是指：++时指向下一个节点，--时指向上一个节点，*取的是节点的数据值，->取的是节点数据成员的地址。
list的迭代器使用封装 + 操作符重载，以达到在使用方式上如同指针一样的目的。
list是一个双向链表，迭代器必须具有前移++、后移- -，所以list的迭代器是一个双向迭代器。
1. 正向迭代器templatestruct __list_iterator
{typedef list_nodenode;
typedef __list_iteratorSelf;
node* _pnode;//迭代器内部要有一个指针，指向list的节点
//constructor
__list_iterator(node* p)
:_pnode(p)
{}
Ptr operator->()
{//return &_pnode->_data;
return &(operator*());//标准做法
}
// iterator it
// *it
// ++it;
// 解引用取到的是节点的数据值
Ref operator*()
{return _pnode->_data;
}
const T& operator*() const
{return _pnode->_data;
}
// ++it
Self& operator++()
{_pnode = _pnode->_next;
return *this;
}
// it++
Self operator++(int)//返回类型为迭代器自己
{//拷贝构造，这里只需要浅拷贝，使用系统生成的即可满足需求
Self tmp(*this);
_pnode = _pnode->_next;
return tmp;
}
//--it
Self& operator--()
{_pnode = _pnode->_prev;
return *this;
}
//it--
Self operator--(int)
{Self tmp(*this);
_pnode = _pnode->_prev;
return tmp;
}
//比较指向节点的指针即节点的地址
bool operator!=(const Self& it) const
{return _pnode != it._pnode;
}
bool operator==(const Self& it) const
{return _pnode == it._pnode;
}
}; 2. 反向迭代器
反向迭代器的实现体现了泛型思维。反向迭代器是正向迭代器的封装，内部有一个正向迭代器成员
模板参数Iterator：给我不同容器的正向迭代器，适配出对应的这个容器需要的反向迭代器。比如要实现vector的反向迭代器只需将其正向迭代器作为参数传入即可。
// 适配器 -- 复用
templateclass ReverseIterator
{typedef ReverseIteratorSelf;
private:
Iterator _it;
public:
ReverseIterator(Iterator it)
:_it(it)
{}
Ref operator* ()
{Iterator tmp = _it;
return *(--tmp);//先--再解引用原因是用正向迭代器的end构造了rbegin
}
Ptr operator->()
{return &(operator*());//显示调解引用再取地址
}
//前置++
Self& operator++ ()
{--_it;//反向迭代器的++是正向迭代器的--
return *this;
}
//后置++
Self operator++ (int)
{ReverseIterator tmp(_it);
--_it;
return tmp;
}
//前置--
Self& operator-- ()
{++_it;
return *this;
}
//后置--
Self operator-- (int)
{ReverseIterator tmp(_it);
++_it;
return tmp;
}
bool operator!= (const Self& s)
{return _it != s._it;
}
}; list的一个性质：插入操作不会造成原迭代器失效。删除操作也只有”指向“被删除元素的迭代器失效，其他不受影响。
4. 具体实现templateclass list
{typedef list_nodenode;
private:
node* _head;
size_t _size;
//……
public:
//前面使用模板参数是为了根据传入参数不同实现不同迭代器
typedef __list_iteratoriterator;
typedef __list_iteratorconst_iterator;
typedef ReverseIteratorreverse_iterator;
typedef ReverseIteratorconst_reverse_iterator;
//反向迭代器
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());
}
const_iterator begin() const
{return const_iterator(_head->_next);
}
const_iterator end() const
{return const_iterator(_head);
}
iterator begin()
{return iterator(_head->_next);
}
iterator end()
{//iterator it(_head);
//return it;
return iterator(_head);
}
}; 
可以发现正向迭代器和反向迭代器是对称的，这也是为什么在反向迭代器实现中会有如下代码：
Ref operator* ()
{Iterator tmp = _it;
return *(--tmp);//先--再解引用原因是用正向迭代器的end构造了rbegin
}三、构造和析构
- 构造一个空链表
void empty_initialize()
{_head = new node(T());
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list() {empty_initialize(); }//生成一个空链表- 区间构造
templatelist(InputIterator first, InputIterator last)
{empty_initialize();
while (first != last)
{push_back(*first);
++first;
}
} - 拷贝构造和赋值运算符重载
//传统写法
// lt2(lt1)
//list(const list& lt)
//{// empty_initialize();
// for (const auto& e : lt)
// {// push_back(e);
// }
//}
lt1 = lt3
//list& operator=(const list& lt)
//{// if (this != <)
// {// clear();
// for (const auto& e : lt)
// {// push_back(e);
// }
// }
// return *this;
//}
void swap(list& lt)
{std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
// lt2(lt1)
list(const list& lt)
//list(const list& lt) //虽然C++语法支持类名作为类型，但是不建议
{empty_initialize();
listtmp(lt.begin(), lt.end());
swap(tmp);
}
// lt3 = lt1
list& operator=(listlt)
//list& operator=(list lt) // 不建议
{swap(lt);
return *this;
} - 析构
void clear()
{iterator it = begin();
while (it != end())
{it = erase(it);
}
}
~list()
{clear();//clear完成除头节点外其他节点的销毁工作
delete _head;
_head = nullptr;
}四、insert和erase
//在pos前插入
iterator insert(iterator pos, const T& x)
{node* newnode = new node(x);
node* cur = pos._pnode;
node* prev = cur->_prev;
// prev newnode cur
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
++_size;
return iterator(newnode);
}
iterator erase(iterator pos)
{assert(pos != end());
node* prev = pos._pnode->_prev;
node* next = pos._pnode->_next;
prev->_next = next;
next->_prev = prev;
delete pos._pnode;
--_size;
return iterator(next);
}五、其他元素操作
void push_back(const T& x)
{//node* newnode = new node(x);
//node* tail = _head->_prev;
_head tail newnode
//tail->_next = newnode;
//newnode->_prev = tail;
//newnode->_next = _head;
//_head->_prev = newnode;
insert(end(), x);
}
void push_front(const T& x)
{insert(begin(), x);
}
void pop_front()
{erase(begin());
}
void pop_back()
{erase(--end());
}你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
分享文章：【C++】STL容器：list的模拟实现-创新互联
分享网址：http://scjbc.cn/article/ddisch.html
