C++：模仿实现list
目次节点
迭代器
团体框架
构造函数
empty_init
拷贝构造
赋值重载
析构函数
clear
insert
erase
push_back和push_front
pop_back和push_front
size
empty
Print_Container
节点
对于链表节点，我们须要一个数据、一个前驱指针、一个后继指针来维护，而且将其封装成一个类。
template<class T>
struct list_node
{
T _data;
list_node<T>* _next;
list_node<T>* _prev;
list_node(const T& data = T())
:_data(data)
,_next(nullptr)
,_prev(nullptr)
{}
}; 使用struct的缘故原由是因为，struct默认的域作用限定符是public，方便后续使用，不消走友元的那一套。
迭代器
我们知道迭代器提供访问容器的方法，之前实现vector和string时，迭代器用的就是数据类型的指针，但是list不可以直接用。因为vector和string的数据在内存的存放都是连续的，如果想找下一个数据的指针（迭代器），直接（迭代器）指针++就可以了；但是list的数据存放在内存不是连续的，如果直接把指针当成迭代器，迭代器++是找不到下一个数据的迭代器。
以是综上所述，我们应该用类对链表数据类型的指针封装成迭代器，在类里重载利用符让其达到我们想要的效果。
当然，我们实现的迭代器应该有两个版本，普通版本和const版本。
//普通迭代器
template<class T>
struct list_iterator
{
typedef list_node<T> Node;
typedef list_iterator<T> Self;
Node* _node;
list_iterator(Node* node)
:_node(node)
{}
T& operator*()
{
return _node->_data;
}
T* operator->()
{
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& it) const
{
return _node != it._node;
}
bool operator==(const Self& it) const
{
return _node == it._node;
}
}; //const迭代器
template<class T>
struct list_const_iterator
{
typedef list_node<T> Node;
typedef list_const_iterator<T> Self;
Node* _node;
list_const_iterator(Node* node)
:_node(node)
{}
const T& operator*()
{
return _node->_data;
}
const T* operator->()
{
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;
}
bool operator!=(const Self& it) const
{
return _node != it._node;
}
bool operator==(const Self& it) const
{
return _node == it._node;
}
};
我们发现这两份代码，除了重载*和->有所不同，其余代码都是一样的，以是我们可以增加两个模板参数，将这两份代码合二为一。
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)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
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& it) const
{
return _node != it._node;
}
bool operator==(const Self& it) const
{
return _node == it._node;
}
}; 增加Ref和Ptr模板参数，让T*和T&作为参数传入，这就可以办理将两份代码合二为一。
团体框架
template<class T>
class list
{
typedef list_node<T> Node;
public:
/*typedef list_iterator<T> iterator;
typedef list_const_iterator<T> const_iterator;*/
//将T&和T*作为参数传入
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;
iterator begin()
{
/*iterator it(_head->_next);
return it;*/
//return iterator(_head->_next);
//返回哨兵节点的下一个节点（第一个有效节点）
//隐式类型转换
return _head->_next;
}
iterator end()
{
//最后一个有效节点的下一位置，也就是哨兵节点
return _head;
}
const_iterator begin() const
{
return _head->_next;
}
const_iterator end() const
{
return _head;
}
//实现各种函数......
private:
Node* _head;
size_t _size;
};
构造函数
empty_init
多种构造函数的代码都有重合，以是把重合部分独立成一个函数。
void empty_init()
{
//创造哨兵节点
_head = new Node();
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
普通构造
普通构造就是创造哨兵节点，调用empty_init即可。
//普通构造
list()
{
empty_init();
} 列表构造
C++11的用法，用法例子如下：
list<int> lt1 = { 1,2,3,4,5,6 }; 先创造一个哨兵节点，然后将列表的元素尾插即可。
//列表构造
list(initializer_list<T> il)
{
empty_init();
for (auto& e : il)
{
push_back(e);
}
} 关于列表initializer_list<T>的知识，可以看以下连接。
介绍列表
拷贝构造
创建哨兵节点，将链表元素尾插到待构造的链表就完成拷贝构造了。
//拷贝构造
list(const list<T>& lt)
{
empty_init();
for (auto& e : lt)
{
push_back(e);
}
} 赋值重载
与暂时对象lt互换即可，跟string、vector的实现雷同。
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
} 析构函数
clear
清理除了哨兵节点以外的所有节点。
void clear()
{
auto it = begin();
while (it != end())
{
it = erase(it);
}
} 先将链表clear掉，然后清理哨兵节点。
~list()
{
clear();
delete _head;
_head = nullptr;
} insert
在pos（迭代器）位置前插入元素x，插入后_size++，返回新插入元素的迭代器。
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node; //pos是iterator类的对象，访问里面的成员变量用pos._node，不能用pos->_node
Node* prev = cur->_prev;
Node* newnode = new Node(x);
newnode->_next = cur;
cur->_prev = newnode;
newnode->_prev = prev;
prev->_next = newnode;
++_size;
//隐式类型转换
return newnode;
} erase
删除pos位置的元素，删除后_size--，返回删除元素的下一元素的迭代器。
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;
--_size;
return next;
} push_back和push_front
利用insert函数就可以实现尾插和头插。
void push_back(const T& x)
{
/*Node* newnode = new Node(x);
Node* tail = _head->_prev;
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;
++_size;*/
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
} pop_back和push_front
利用erase函数实现尾删和头删。
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
} size
返回链表有效元素的个数.。
size_t size() const
{
return _size;
} empty
判定链表是否为空。
bool empty() const
{
return _size == 0;
} Print_Container
打印容器的函数。
template<class Container>
void Print_Container(const Container& con)
{
//const对象要用const迭代器，这里没实现的话会报错
/*auto it = con.begin();
while (it != con.end())
{
cout << *it << " ";
++it;
}*/
for (auto e : con)
{
cout << e << " ";
}
cout << endl;
} 拜拜，下期再见
页:
[1]