【手撕】list

系列文章目录

---

---

前言

模拟实现list类

---

STL3.0(SGI版本)

list_node（节点）

//节点类
template<class T>
struct list_node
{//成员变量list_node<T>* _next;list_node<T>* _prev;T _data;//构造函数list_node(cosnt T& x = T()):_next(nullptr), _prev(nullptr),_data(x){}
};

_list_iterator<T, Ref, Ptr>（迭代器）

成员变量

  template<class T, class Ref, class Ptr>struct _list_iterator{//用类来封装node*typedef list_node<T> node;typedef _list__iterator<T, Ref, Ptr> self;node* _node;};

构造函数

//构造函数
_list_iterator(node* n):_node(n)
{}

运算符重载

//Iterator
Ref operator*()
{return _node->_data;
}Ptr operator->()
{//it->_a1 => it->->_a1;return &_node->_data;
}self& operator++()
{_node = _node->_next;return *this;
}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;
}bool operator ==(const self& s)
{return _node == s._node;
}

List（链表）

成员变量

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;private:node* _head;//节点指针
};

构造函数

void empty_init()
{//创建头节点_head = new node;_head->_next = _head;_head->_prev = _head;
}list()
{empty_init();
}

析构函数

//析构函数
~list()
{	clear();//释放头节点delete _head;_head = nullptr;
}

区间构造函数

template <class Iterator>
list(Iterator first, Iterator last)
{empty_init();while (first != last){push_back(*first);++first;}
}

拷贝构造

void swap(list<T>& lt)
{std::swap(_head, lt._head);
}list(const list<T>& lt)
{empty_init();list<T> tmp(lt.begin(), lt.end());swap(tmp);
}

赋值重载

list<T>& operator=(list<T> tmp)
{swap(tmp);return *this;
}

Modifiers（修改器）

void push_back(cosnt T& x)
{insert(end(), x);
}void push_front(const T& x)
{insert(begin(), x);
}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->_prev = prev;new_node->_next = cur;cur->_prev = new_node;
}iterator erase(iterator pos)
{assert(pos != end());//头节点不能删node* prev = pos._node->_prev;node* next = pos._node->_next;prev->_next = next;next->_prev = prev;delete pos._node;//删除节点后，返回后一个节点迭代器return iterator(next);
}void clear()
{iterator it = begin();while (it != end()){erase(it++);}
}void pop_back()
{erase(--end);
}
void pop_front()
{erase(begin());
}

list的迭代器失效

void TestListIterator1()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array + sizeof(array) / sizeof(array[0]));auto it = l.begin();while (it != l.end()){// erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值l.erase(it);++it;}
}
// 改正
void TestListIterator()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array + sizeof(array) / sizeof(array[0]));auto it = l.begin();while (it != l.end()){l.erase(it++); // it = l.erase(it);}
}