目录
一.list的介绍
二.list的接口实现
1.结点
template<class T>
struct list_node
{
list_node* _prev;
list_node* _next;
T _data;
// 由于数据类型由模板参数决定，所以缺省值给匿名对象
list_node(const T& x = T())
:_prev(nullptr)
,_next(nullptr)
,_data(x)
{}
};用一个结构体来封装结点，我们手动写默认构造函数以便在申请结点时调用。
2.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;
// 有效数据个数
size_t _size = 0;
};
3.迭代器
list的迭代器与之前的string和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)
{}
// 比较指向的结点是否相同
bool operator!=(const Self& s)
{
return _node != s._node;
}
bool operator==(const Self& s)
{
return _node == s._node;
}
// Ref来控制iterator与const_iterator
// Ref->T& -- iterator;
// Ref->const T& -- const_iterator;
// 获取结点存储的数据
Ref 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;
}
// 为了可读性进行特殊处理 it->->_a1 被优化为 it->_a1
// Ptr来控制iterator与const_iterator
// Ptr->T* -- iterator
// Ptr->const T* -- const_iterator
Ptr operator->()
{
return &_node->_data;
}
};（1）begin
iterator begin()
{
return iterator(_head->_next);
}const_iterator begin() const
{
return const_iterator(_head->_next);
}（2）end
iterator end()
{
// 返回尾结点的下一个结点，也就是哨兵位
return iterator(_head);
}const_iterator begin() const
{
return const_iterator(_head->_next);
}4.修改
（1）insert
void insert(iterator pos, const T& x)
{
// 申请新结点的空间，调用构造
Node* newnode = new Node(x);
// 断开旧连接，连接新结点
Node* cur = pos._node;
Node* prev = cur->_prev;
// prev newnode cur
newnode->_prev = prev;
newnode->_next = cur;
prev->_next = newnode;
cur->_prev = newnode;
++_size;
}（2）push_back
void push_back(const T& x)
{
//Node* newnode = new Node(x);
//Node* tail = _head->_prev;
tail newnode _head
//newnode->_prev = tail;
//newnode->_next = _head;
//tail->_next = newnode;
//_head->_prev = newnode;
insert(end(), x);
}（3）push_front
void push_front(const T& x)
{
insert(begin(), x);
}（4）erase
iterator erase(iterator pos)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
--_size;
//return iterator(next);
// 为防止迭代器失效，返回删除后的下一个结点的迭代器
// 单参数构造函数支持隐式转换
return next;
}为防止erase后，pos依然指向被delete的结点从而导致迭代器失效，erase返回指向下一个结点的迭代器。
（5）pop_back
void pop_back()
{
erase(--end());
}（6）pop_front
void pop_front()
{
erase(begin());
}（7）swap
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}交换哨兵位即可交换两个list。
（8）clear
void clear()
{
auto it = begin();
while (it != end())
{
it = erase(it);
}
}
除了哨兵位，其他结点逐个erase。
5.默认成员函数
（1）构造函数
空list申请哨兵位：empty_init
// 空list申请哨兵位
void empty_init()
{
_head = new Node;
_head->_prev = _head;
_head->_next = _head;
}
// 无参数构造
list()
{
//_head = new Node;
//_head->_prev = _head;
//_head->_next = _head;
empty_init();
}
// initializer_list构造
list(std::initializer_list<T> il)
{
empty_init();
for (auto& e : il)
{
push_back(e);
}
}（2）拷贝构造函数
list(const list<T>& lt)
{
empty_init();
for (auto& e : lt)
{
push_back(e);
}
}先申请哨兵位，再逐个尾插即可。
（3）赋值重载
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
（4）析构函数
~list()
{
clear();
delete _head;
_head = nullptr;
}三.代码总览
list.h
#include<iostream>
#include<initializer_list>
namespace my_list
{
template<class T>
struct list_node
{
list_node* _prev;
list_node* _next;
T _data;
// 由于数据类型由模板参数决定，所以缺省值给匿名对象
list_node(const T& x = T())
:_prev(nullptr)
,_next(nullptr)
,_data(x)
{}
};
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)
{}
// 比较指向的结点是否相同
bool operator!=(const Self& s)
{
return _node != s._node;
}
bool operator==(const Self& s)
{
return _node == s._node;
}
// Ref来控制iterator与const_iterator
// Ref->T& -- iterator;
// Ref->const T& -- const_iterator;
// 获取结点存储的数据
Ref 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;
}
// 为了可读性进行特殊处理 it->->_a1 被优化为 it->_a1
// Ptr来控制iterator与const_iterator
// Ptr->T* -- iterator
// Ptr->const T* -- const_iterator
Ptr operator->()
{
return &_node->_data;
}
};
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申请哨兵位
void empty_init()
{
_head = new Node;
_head->_prev = _head;
_head->_next = _head;
}
// 无参数构造
list()
{
//_head = new Node;
//_head->_prev = _head;
//_head->_next = _head;
empty_init();
}
// initializer_list构造
list(std::initializer_list<T> il)
{
empty_init();
for (auto& e : il)
{
push_back(e);
}
}
list(const list<T>& lt)
{
empty_init();
for (auto& e : lt)
{
push_back(e);
}
}
// lt2 = lt1
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
void clear()
{
auto it = begin();
while (it != end())
{
it = erase(it);
}
}
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
size_t size()
{
return _size;
}
iterator begin()
{
return iterator(_head->_next);
}
iterator end()
{
// 返回尾结点的下一个结点，也就是哨兵位
return iterator(_head);
}
const_iterator begin() const
{
return const_iterator(_head->_next);
}
const_iterator end() const
{
return const_iterator(_head);
}
void push_back(const T& x)
{
//Node* newnode = new Node(x);
//Node* tail = _head->_prev;
tail newnode _head
//newnode->_prev = tail;
//newnode->_next = _head;
//tail->_next = newnode;
//_head->_prev = newnode;
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}
void insert(iterator pos, const T& x)
{
// 申请新结点的空间，调用构造
Node* newnode = new Node(x);
// 断开旧连接，连接新结点
Node* cur = pos._node;
Node* prev = cur->_prev;
// prev newnode cur
newnode->_prev = prev;
newnode->_next = cur;
prev->_next = newnode;
cur->_prev = newnode;
++_size;
}
iterator erase(iterator pos)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
--_size;
//return iterator(next);
// 为防止迭代器失效，返回删除后的下一个结点的迭代器
// 单参数构造函数支持隐式转换
return next;
}
private:
// 哨兵位
Node* _head;
// 有效数据个数
size_t _size = 0;
};
}test.cpp
#include"list.h"
using namespace std;
namespace my_list
{
void test_list1()
{
list<int> lt1;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(3);
lt1.push_back(4);
list<int>::iterator it = lt1.begin();
while (it != lt1.end())
{
*it += 10;
cout << *it << " ";
++it;
}
cout << endl;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_front(3);
lt1.push_front(4);
for (auto& e : lt1)
{
cout << e << " ";
}
cout << endl;
lt1.pop_back();
lt1.pop_front();
for (auto& e : lt1)
{
cout << e << " ";
}
cout << endl;
cout << lt1.size() << endl;
}
void test_list2()
{
list<int> lt1;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_front(3);
lt1.push_front(4);
for (auto& e : lt1)
{
cout << e << " ";
}
cout << endl;
list<int> lt2(lt1);
for (auto& e : lt1)
{
cout << e << " ";
}
cout << endl;
list<int> lt3;
lt3 = lt1;
for (auto& e : lt1)
{
cout << e << " ";
}
}
struct AA
{
int _a1;
int _a2;
AA(int a1 = 1, int a2 = 1)
:_a1(a1)
, _a2(a2)
{}
};
void test_list3()
{
list<int> lt1 = { 1,2,3,4 };
for (auto& e : lt1)
{
cout << e << " ";
}
cout << endl;
list<AA> lt2 = { {1,1},{2,2},{3,3},{4,4} };
list<AA>::iterator it = lt2.begin();
while (it != lt2.end())
{
//cout << (*it)._a1 << ":" << (*it)._a2 << endl;
//cout << it->->_a1 << ":" << it->->_a2 << endl;
cout << it->_a1 << ":" << it->_a2 << endl;
++it;
}
list<AA>::iterator lit = lt2.begin();
while (lit != lt2.end())
{
cout << lit.operator->()->_a1 << ":" << lit.operator->()->_a2 << endl;
++lit;
}
}
}
int main()
{
my_list::test_list3();
return 0;
}