C++list模拟实现

list接口总结

namespace bite
{
    // List的节点类
    template<class T>
    struct ListNode
    {
        ListNode(const T& val = T());
        ListNode<T>* _pre;
        ListNode<T>* _next;
        T _date;
    };

    //List的迭代器类
    template<class T, class Ref, class Ptr>
    class Listiterator
    {
        typedef ListNode<T>* Node;
        typedef Listiterator<T, Ref, Ptr> Self;
    public:
        Listiterator(Node* Node);
        Ref operator*();
        Ptr operator->();
        Self& operator++();d
        Self operator++(int);
        Self& operator--();
        Self& operator--(int);
        bool operator!=(const Self& l);
        bool operator==(const Self& l);
    private:
        Node _node;
    };

    //list类
    template<class T>
    class list
    {
        typedef ListNode<T> Node;
    public:
        typedef Listiterator<T, T&, T*> iterator;
        typedef Listiterator<T, const T&, const T&> const_iterator;
    public:
        ///
        // List的构造
        void init();
        list();
        list(const list<T>& val)
        list<T>& operator==(list<T> val)
        ~list();
        ///
        // List Iterator
        iterator begin();
        iterator end();
        const_iterator begin();
        const_iterator end();

        ///
        // List Capacity
        size_t size()const;
        bool empty()const;

        
        // List Modify
        void push_back(const T& val) { insert(end(), val); }
        void pop_back() { erase(--end()); }
        void push_front(const T& val) { insert(begin(), val); }
        void pop_front() { erase(begin()); }
        // 在pos位置前插入值为val的节点
        iterator insert(iterator pos, const T& val);
        // 删除pos位置的节点，返回该节点的下一个位置
        iterator erase(iterator pos);
        void clear();
        void swap(list<T>& lt);
    private:
        Node* _head;
        size_t _size;
    };
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

结点类的模拟实现

STL中的list为带头双向循环链表。
如图：

所以我们要实现list链表之前还要实现结点类。 结点中要存储前一个结点的地址和后一个结点的地址、还有数据。因此我们只需要设定成员变量和构造函数就行。

template <class T>  //设定模板结点中的数据类型可以是不同的
struct ListNode
{
	typedef ListNode<T> Node;
	ListNode(const T& val = T())//构造函数
		:_prev(nullptr)
		,_next(nullptr)
		,_date(val)
	{}
	Node* _prev;//前驱指针
	Node* _next;//后驱指针
	T _date;//数据

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

迭代器的模拟实现

我们在string和vector中迭代器模拟都是直接给定模板指针。但是到了list中我们就需要实现一个迭代器类型。why？
这是因为我们在string和vector中数据的存储都是存放在一块连续的空间。我们可以同过指针进行对数据的增删查改。

list并不是存放一块连续的空间，而是通过结点存放下一个结点的地址一个一个连结起来的。 所以我们不能通过指针来实现链表的增删查改。
迭代器是一种用于遍历集合或容器中元素的接口，它可以隔离对容器的访问方式和底层实现，从而实现解耦。迭代器可以依次访问容器中的每一个元素，而无需了解容器的内部细节。
既然我们的指针不能满足迭代器的行为，那我们就将指针封装成类，使其能够满足迭代器的需要。

迭代器模板参数

迭代器我们给处三个模板参数。

 template<class T, class Ref, class Ptr>
1

实现两个迭代器，一个iterator 和另一个 const_iterator。

  typedef Listiterator<T, T&, T*> iterator;
  typedef Listiterator<T, const T&, const T&> const_iterator;
1
2

从这里我们可以看出，Ref 代表的是引用类型和指针类型。

迭代器类中的构造函数

我们迭代器的底层就是对指针进行的封装，因此成员变量就一个就是结点指针。

Listiterator(Node* node)
	:_node(node)
{}
1
2
3

迭代器类中的运算符重载

operator++和operator - -

list的迭代器没必要实现operator+，只需要实现自增和和自减
自增：

//前置++
self& operator++()
{
	_node = _node->_next;
	return *this;
}
//后置++
self operator++(int)
{
	self tmp = *this;
	_node = _node->_next;
	return tmp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

自减：

//前置--
self& operator--()
{
	_node = _node->_prev;
	return *this;
}
//后置--
self operator--(int)
{
	self tmp = *this;
	_node = _node->_prev;
	return tmp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

operator！= 和operator==

实现两个迭代器之间的比较。

bool operator!=(const self& val)
{
	return _node != val._node;
}

bool operator==(const self& val)
{
	return _node == val._node;
}
1
2
3
4
5
6
7
8
9

operator*

当我们使用解引用操作符，想要得到的是这个地址所指向的数据。所以我们operator* 返回该地址所指向的数据就行。

Ref operator*()
{
	return _node->_date;
}
1
2
3
4

operator->

我们在使用list时，如果list内结点存储的数据不是内置类型，而是自定义类型，例如Date日期类。我们访问Date类中的成员，就需要用到operator->。
例如：

struct A //自定义类型
{
	A(int x=0 ,int y =0)
		:_aa1(x)
		,_aa2(y)
	{}
	int _aa1;
	int _aa2;
};
void test()
{
	A aa1(0,0);
	list<A> lt;
	lt.push_back(aa1);
	lt.push_back(A(1, 1));
	lt.push_back({ 2,2 });
	lt.push_back({3,3});

	list<A>::iterator it = lt.begin();
	while (it != lt.end())
	{
		cout << it->_aa1 << " " << it->_aa2 << endl;;
		it++;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

operator->只需要返回结点数据的地址就行。

Ptr operator->()
{
	return &_node->_date;
}
1
2
3
4

这里有人就可能发现，这种方式访问自定义类型成员需要用到两个->。

这里其实是忽略了一个->，两个->第一个运算符重载的调用是指向A* ，另一个是原生指针的调用。为了让代码有良好的可读性，编译器做了特殊处理，忽略了一个->。

总览

template <class T , class Ref , class Ptr>
struct Listiterator
{
	typedef ListNode<T> Node;
	typedef Listiterator<T , Ref , Ptr> self;

	Node* _node;

	Listiterator(Node* node)
		:_node(node)
	{}

	Ref operator*()
	{
		return _node->_date;
	}

	Ptr operator->()
	{
		return &_node->_date;
	}

	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& val)
	{
		return _node != val._node;
	}

	bool operator==(const self& val)
	{
		return _node == val._node;
	}

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

list 类

构造函数

list是一个双向带头循环链表，list初始化需要设置一个哨兵位，并使其的前驱指针和后驱指针都指向自己。

void init()
{
	_head = new Node;
	_head->_prev = _head;
	_head->_next = _head;

	_size = 0;
}
list()
{
	init();
}
1
2
3
4
5
6
7
8
9
10
11
12

拷贝构造函数

list的拷贝构造就是根据所给的对象，拷贝处一个新的对象。拷贝构造函数我们先给一个头结点使其前驱指针和后驱指针都指向自己，然后再遍历对象，让对象中的结点一个一个尾插入到新的list中去。

list(const list<T>& val)
{
	init();
	for (auto& e : val)
	{
		push_back(e);
	}
}
1
2
3
4
5
6
7
8

赋值运算符重载operator=

我们这里直接使用现代写法。利用传入的参数通过编译器自动调用list构造函数构造出一个list对象，
再使用swap使其与原来的容器进行交换。

	list<T>& operator==(list<T> val)
	{
		swap(val);
		return *this;
	}
1
2
3
4
5

clear（）

clear函数只需要将链表中的结点和数据清理即可，给一个迭代器使其指向头结点，然后遍历链表将结点一个一个删除，除了哨兵位以外。

void clear()
{
	iterator it = begin();
	while (it != end())
	{
		it = erase(it);
	}
}
1
2
3
4
5
6
7
8

析构函数

析构函数首先我们先将list容器中的数据清除，让后在释放哨兵位和让_size归零。

~list()
{
	clear();
	delete _head;
	_head = nullptr;
	_size = 0;
}
1
2
3
4
5
6
7

迭代器相关函数

begin和end

在这里我们需要清楚的是begin为哨兵位的下一个结点，而end就是哨兵位。

iterator begin()
{
	return _head->_next;
}

iterator end()
{
	return _head;
}
1
2
3
4
5
6
7
8
9

还有const begin 和end

const_iterator begin() const
{
	return _head->_next;
}

const_iterator end() const 
{
	return _head;
}
1
2
3
4
5
6
7
8
9

与容器修改有关函数

insert 插入

insert函数作用是在pos位置插入一个新的结点。
如图：

我们要在pos位置插入一个新的结点（newnode）就得让新结点前驱指针指向pos结点前一个结点（prev），让prev的后驱指针指向newnode。newnode后驱指针指向pos结点，pos前驱指针指向newnode。

void insert(iterator pos , const T& val)
{
	Node* newnode = new Node(val);
	Node* cur = pos._node;
	Node* prev = cur->_prev;
	
	newnode->_next = cur;
	cur->_prev = newnode;
	newnode->_prev = prev;
	prev->_next = newnode;

	_size++;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

erase 删除

erase就是删除pos位置的结点。
如图：

iterator erase(iterator pos)
{
	assert(pos != _head);
	Node* del = pos._node;
	Node* prev = del->_prev;
	Node* next = del->_next;
	
	prev->_next = next;
	next->_prev = prev;

	delete del;
	--_size;

	return iterator(next);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

注意： erase还要注意迭代器失效的问题因此我们的返回值指向的是下一个结点。

push_back（）尾插

双向带头循环链表的尾插比较容易理解。新建一个结点使其的前驱指针指向尾结点，尾结点的后驱结点指向新的结点。新结点的后驱指针指向哨兵位，哨兵位的前驱指针指向新结点，再++_size。

void push_back(const T& val)
{
	Node* newnode = new Node(val);
	Node* tail = _head->_prev;

	newnode->_prev = tail;
	tail->_next = newnode;

	newnode->_next = _head;
	_head->_prev = newnode;
	_size++;
}
1
2
3
4
5
6
7
8
9
10
11
12

还可以复用insert函数，是push_back函数变得简单。

 void push_back(const T& val) 
 { 
    insert(end(), val); 
 }   
1
2
3
4

pop_back 尾删

我们这里直接复用erase函数。

void pop_back()
 {
    erase(--end()); 
 }   
1
2
3
4

push_front 头插

头插也是复用insert函数。

void push_front(const T& val) 
{ 
    insert(begin(), val); 
}
1
2
3
4

pop_front 头删

void pop_front()
 { 
   erase(begin()); 
 }
1
2
3
4

size

返回结点个数。

size_t size()
{
	return _size;
}
1
2
3
4