一 初识STL list
STL list 容器，又称双向链表容器，即该容器的底层是以双向链表的形式(或者说是一种环状结构)实现的。这意味着，list 容器中的元素可以分散存储在内存空间里，而不是必须存储在一整块连续的内存空间中。
每一个节点都拥有数据域和指针域，只不过实在指针域中有俩个指针罢了，一个指前指针(prev)，一个指后指针(next)。
本片内容主要是使用C++实现自己的list的容器，很简易，一些东西没有做，比如emplace系列函数，又或者是rbegin,rend指针的实现。
二 前置C++知识
1.类和对象：构造函数，析构函数，拷贝构造（深拷贝/浅拷贝），拷贝赋值
2.模板 :使用模板来实现泛性编程，支持存储各种类型
3.STL迭代器的思想:STL容器使用迭代器来进行封装统一接口，忽略底层复杂的实现逻辑
4.operator重载:使用operator重载常用的操作符,如[],++,–,*,->
5.C++基本语法与关键词:引用，初始化列表，缺省值，auto,nullptr
函数重载
三 实现部分
总的来说，实现一个list容器，分为三部分：节点，迭代器和链表
1 节点(node)
要包括数据域(data_)，一个指前指针(prev_)和一个指后指针(next_)，以及相应的构造函数，析构函数
template <class T>
// list存储的节点
// 可以根据你的需要添加适当的成员函数与成员变量
struct node
{
node<T> *prev_;
node<T> *next_;
T data_;
// 构造函数
node(const T &data)
: data_(data), prev_(nullptr), next_(nullptr)
{
}
node()
: prev_(nullptr), next_(nullptr)
{
}
// 析构函数
~node()
{
}
};
2 迭代器(iterator)
要包括节点(node),指针(iterator)，构造函数和析构函数，以及各种符号的重载
template <class T>
// 迭代器类,(类比指针)
struct iterator
{
typedef node<T> node_;
typedef iterator<T> iterator_;
node_ *data_;
iterator(node_ *data)
: data_(data)
{
}
~iterator()
{
}
// 迭代到下一个节点
//++it
iterator_ &operator++()
{
// node *next = node * data_;
// this->data_ = next;
data_ = data_->next_;
return *this;
}
// 迭代到前一个节点
//--it
iterator_ &operator--()
{
// node *prev = data_->prev_;
// this->data_ = prev;
data_ = data_->prev_;
return *this;
}
// it++
iterator operator++(int)
{
iterator it(data_);
data_ = data_->next_;
return it;
}
// it--
iterator operator--(int)
{
iterator it(data_);
data_ = data_->prev_;
return it;
}
// 获得迭代器的值
T &operator*()
{
return data_->data_;
}
// 获得迭代器的值所对应的指针
T *operator->()
{
return &(data_->data_);
}
// 重载==
bool operator==(const iterator_ &t)
{
if (data_ == t.data_)
return true;
else
return false;
}
// 重载!=
bool operator!=(const iterator_ &t)
{
if (data_ == t.data_)
return false;
else
return true;
}
//**可以添加需要的成员变量与成员函数**
};
3.链表
众所周知，创建一个list容器大致可以分为俩类，一类是指定各自元素的初始值(比如容量)，一类是通过已经存在的list容器来拷贝构造出一个新list容器。所以说在该部分中有俩构造函数。这个部分下基本就是些简单逻辑的实现，慢慢捋就行。
别和我一样把尾插和头插，尾删和头删搞混就行
template <class T>
class list
{
public:
typedef node<T> node_;
typedef iterator<T> Iterator;
private:
// 可以添加你需要的成员变量
node_ *head_; // 头节点,哨兵（不存储有效数据）
public:
// 构造函数
list()
{
head_ = new node<T>();
head_->next_ = head_;
head_->prev_ = head_;
}
// 拷贝构造，要求实现深拷贝
list(const list<T> <)
{
head_ = new node<T>();
head_->next_ = head_;
head_->prev_ = head_;
for (auto Lt = lt.begin(); Lt != lt.end(); ++Lt)
{
push_back(*Lt);
}
}
template <class inputIterator>
// 迭代器构造
list(inputIterator begin, inputIterator end)
{
head_ = new node<T>();
head_->prev_ = head_;
head_->next_ = head_;
for (inputIterator it = begin; it != end; ++it)
{
push_back(*it);
}
}
~list()
{
clear();
delete head_;
head_ = NULL;
}
// 拷贝赋值
list<T> &operator=(const list<T> <)
{
if (this != <)
{
clear();
for (auto it = lt.begin(); it != lt.end(); ++it)
{
push_back(*it);
}
}
return *this;
}
// 清空list中的数据
void clear()
{
while (!empty())
{
pop_front();
}
}
// 返回容器中存储的有效节点个数
size_t size() const
{
size_t num = 0;
for (auto lt = begin(); lt != end(); ++lt)
{
++num;
}
return num;
}
// 判断是否为空
bool empty() const
{
return head_->next_ == head_;
}
// 尾插
bool push_back(const T &data)
{
node_ *pNewNode = new node<T>(data);
pNewNode->prev_ = head_->prev_;
pNewNode->next_ = head_;
head_->prev_->next_ = pNewNode;
head_->prev_ = pNewNode;
return true;
}
// 头插
bool push_front(const T &data)
{
node_ *pNewNode = new node<T>(data);
pNewNode->next_ = head_->next_;
pNewNode->prev_ = head_;
head_->next_->prev_ = pNewNode;
head_->next_ = pNewNode;
return true;
}
// 尾删
bool pop_back()
{
node_ *prev = this->head_->prev_->prev_;
node_ *cur = this->head_->prev_;
prev->next_ = this->head_;
head_->prev_ = prev;
cur->next_ = NULL;
cur->prev_ = NULL;
delete cur;
return true;
}
// 头删
bool pop_front()
{
node_ *next = this->head_->next_->next_;
node_ *cur = this->head_->next_;
next->prev_ = this->head_;
head_->next_ = next;
cur->next_ = NULL;
cur->prev_ = NULL;
delete cur;
return true;
}
// 默认新数据添加到pos迭代器的后面,根据back的方向决定插入在pos的前面还是后面
// back是false->插在前 back是true->插在后
bool insert(Iterator pos, const T &data, bool back = true)
{
node_ *AddNode = new node<T>(data);
node_ *next = pos.data_->next_;
node_ *prev = pos.data_->prev_;
node_ *cur = pos.data_;
if (!back) // 前插
{
AddNode->next_ = cur;
AddNode->prev_ = prev;
prev->next_ = AddNode;
cur->prev_ = AddNode;
return true;
}
else // 后插
{
AddNode->prev_ = cur;
AddNode->next_ = prev;
next->prev_ = AddNode;
cur->next_ = AddNode;
return true;
}
}
// 删除pos位置的元素
bool erase(Iterator pos)
{
if (pos.data_ == head_)
{
return true;
}
node_ *cur = pos.data_;
node_ *next = cur->next_;
node_ *prev = cur->prev_;
prev->next_ = next;
next->prev_ = prev;
cur->next_ = nullptr;
cur->prev_ = nullptr;
delete cur;
return true;
}
// 获得list第一个有效节点的迭代器
Iterator begin() const
{
return Iterator(head_->next_);
}
// 获得list最后一个节点的下一个位置，可以理解为nullptr
Iterator end() const
{
return Iterator(head_);
}
// 查找data对应的迭代器
Iterator find(const T &data) const
{
for (auto It = begin(); It != end(); ++It)
{
if (It.data_->data_ == data)
{
return It;
}
}
return nullptr;
}
// 获得第一个有效节点
node_ front() const
{
Iterator It(head_->next_);
return It.data_->data_;
}
// 获得最后一个有效节点
node_ back() const
{
Iterator It(head_);
return It.data_->data_;
}
private:
// 可以添加你需要的成员函数
};