C++List容器
Rookiep 人气:0一、基本结构
由源代码可知，list容器是有一个带头双向循环链表实现，所以我们模拟实现也需要实现一个带头双向循环链表的数据结构。
template<class T>
struct list_node
{
list_node<T>* _next;
list_node<T>* _prev;
T _data;
list_node(const T& val = T())//用一个匿名对象来做缺省参数
:_next(nullptr)
, _prev(nullptr)
, _data(val)
{}
};
template<class T>
class list
{
public:
typedef list_node<T> Node;
private:
Node* _head;
};二、list的迭代器的构造
list的迭代器与vector的迭代器不一样，list的迭代器是一个自定义类型的对象，成员变量包含一个指向节点的指针。
template<class T, class Ref, class Ptr>
struct __list_iterator
{
typedef list_node<T> Node;
typedef __list_iterator<T, Ref, Ptr> self;
Node* _node;
__list_iterator(Node* node)
:_node(node)
{}
// 析构函数 -- 节点不属于迭代器，不需要迭代器释放
// 拷贝构造和赋值重载 -- 默认生成的浅拷贝就可以
// *it
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
//return &(operator*());
return &_node->_data;
}
self& operator++()
{
_node = _node->_next;
return *this;
}
self operator++(int)
{
self tmp(*this);//拷贝构造
_node = _node->_next;
return tmp;//因为tmp出了作用域就不在了，所以不可以引用返回
}
self& operator--()
{
_node = _node->_prev;
return *this;
}
self operator--(int)
{
self tmp(*this);
_node = _node->_prev;
return tmp;
}⭐️⭐️⭐️即用一个自定义类型封装，通过运算符的重载使迭代器实现像指针一样的操作行为。
三、迭代器的实现
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;
//仅仅是为了改名，如果不是为了改名，不用写。
__list_iterator<T, const T&, const T*> begin() const
{
// list_node<int>*
return __list_iterator<T, const T&, const T*>(_head->_next);
//构造一个匿名对象
}
const_iterator end() const
{
return const_iterator(_head);
}
iterator begin()
{
return iterator(_head->_next);//构造一个匿名对象来返回
//return _head->_next;//也可以，因为单参数构造函数支持隐式类型转换。
//iterator it = _head->_next 隐式调用
}
iterator end()
{
return iterator(_head);
}
}四、insert,erase
// 插入在pos位置之前
iterator insert(iterator pos, const T& x)//pos是一个迭代器对象
{
Node* newNode = new Node(x);
Node* cur = pos._node;
Node* prev = cur->_prev;
// prev newnode cur
prev->_next = newNode;
newNode->_prev = prev;
newNode->_next = cur;
cur->_prev = newNode;
return iterator(newNode);
}
iterator erase(iterator pos)
{
assert(pos != end());
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
// prev next
prev->_next = next;
next->_prev = prev;
delete cur;
return iterator(next);
}五、push_back,push_front,pop_back,pop_front
void push_back(const T& x)
{
//Node* tail = _head->_prev;
//Node* newnode = new Node(x);
_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_back()
{
erase(--end());
//这里不可以用end()-1吧，因为尾部迭代器在尾删后是需要变得
}
void pop_front()
{
erase(begin());
}⭐️这里均复用了insert和erase函数。
六、构造函数与赋值重载
list()//带头双向循环链表，初始化要先把头弄出来
{
_head = new Node();
//自定义类型去调用对应类的构造函数,带不带这个括号都可
_head->_next = _head;
_head->_prev = _head;
}
// lt2(lt1)————传统写法
/*list(const list<T>& lt)
{
_head = new Node();
_head->_next = _head;
_head->_prev = _head;
for (auto e : lt)
{
push_back(e);//push_back中复用insert，insert中完成深拷贝
}
}*/
void empty_init()
{
_head = new Node();
_head->_next = _head;
_head->_prev = _head;
}
//如果我们写现代写法，那么必须提供相应的带参构造
template <class InputIterator>
list(InputIterator first, InputIterator last)
{
empty_init();
while (first != last)
{
push_back(*first);//push_back中调用insert时会完成相应深拷贝
++first;
}
}
void swap(list<T>& lt)
{
std::swap(_head, lt._head);//交换头节点
}
// lt2(lt1) -- 现代写法
list(const list<T>& lt)
{
empty_init();//总不能把一个野指针换给别人呀！
list<T> tmp(lt.begin(), lt.end());
swap(tmp);
}
// lt2 = lt1
list<T>& operator=(list<T> lt)
//list<T> lt = lt1，传值传参这一步就调用了拷贝构造完成深拷贝
{
swap(lt);
return *this;
}⭐️⭐️⭐️注意现代写法的方法
七、析构与清空
~list()
{
clear();
delete _head;
_head = nullptr;
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);//用返回值更新，防止迭代器失效
}
}加载全部内容