泛型编程学习，编写一个类似STL库中的简易list的迭代器（iterator）
前言
近期在研究stl源代码及stl里各种实现的细节，初学入门免不了模仿，以下便写一次自己的简单的list容器的迭代器。
首先，在开始编写List的迭代器的时候我们首先应该了解我们要写的List和其迭代器要做出什么样的功能。（学习书籍《C++STL基础应用》《STL源代码剖析》《泛型思维》）
list
list相较于vector，list的好处是每次插入/删除一个数据，他就重新申请/释放一个空间，对内存的把握绝对的精准（vector是申请一片区域，超过此容量便进行“重新配置两倍区域，元素移动，释放原空间”）；另外 对于元素的移动，list永远是常数的时间。
迭代器
每一个容器都应有对应的迭代器（iterator），容器通过迭代器共享某一具体算法（之后使用display()函数举例）。迭代器是算法和容器之间起媒介作用（display(iterator it1,iterator it2)），迭代器思维的产生是编制泛型算法发展的必然结果。
简单的display()函数
1
2
3
4
5
6
7
8
| template<class T>
void display(T start, T end) {
cout << endl;
for (T i = start; i != end; i++) {
cout << *i << endl;
}
cout << endl;
}
|
我的目的就是为了使我编写的list容器可以使用此display()函数。
编写
list
我们想要的基础的list需要：基本的结点struct Node（含head 和 prev分别指向下一位和前一位结点）
1
2
3
4
5
6
7
8
9
10
11
12
|
template<class T>
struct Node
{
Node* next;
Node* prev;
T data;
Node(T s = 0, Node* n = NULL, Node* p = NULL) :data(s), next(n), prev(p) {};
};
|
确定好了Node开始编写class list
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
| template<class T>
class list {
public:
struct Node
{
};
class iterator
{
};
private:
Node * head,*tail;
int _size;
void createlist() {
_size = 0;
head = new Node();
tail = new Node();
head->next = tail;
tail->prev = head;
}
public:
list() {
createlist();
}
~list() {
while (!empty()) {
pop_front();
}
delete head;
delete tail;
}
bool empty()const { return _size == 0; };
iterator begin() {
return iterator(head->next);
}
iterator end() {
return iterator(tail);
}
iterator insert(iterator pos, const T& value) {
Node* p = new Node(value, pos.cur, pos.cur->prev);
_size++;
p->prev->next = p;
pos.cur->prev = p;
return iterator(p);
}
iterator erase(iterator pos) {
Node* p = pos.cur;
iterator newite(p->next);
p->prev->next = p->next;
p->next->prev = p->prev;
delete p;
_size--;
return newite;
}
void push_back(const T& value) {
insert(end(), value);
}
void push_front(const T& value) {
insert(begin(), value);
}
void pop_front() {
erase(begin());
}
void pop_back() {
erase(end());
}
};
|
这样，我们的list就含有基础的push_back,push_front,pop_back,pop_front,insert,erase功能，和构造、析构函数了。
list 的iterator的编写
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
| template<class T>
class list {
public:
struct Node
{
};
class iterator {
private:
Node* cur;
public:
friend class list;
explicit iterator(Node* p=0) {cur = p; }
bool operator ==(iterator& x) { return (*this).cur == x.cur; }
bool operator !=(iterator& x) { return (*this).cur != x.cur; }
iterator& operator++() {
cur = cur->next;
return *this;
}
iterator operator++(int) {
iterator temp = *this;
++(*this);
return temp;
}
iterator& operator--() {
cur = cur->prev;
return *this;
}
iterator operator--(int) {
iterator temp = *this;
--(*this);
return temp;
}
Node* operator->() {
return cur;
}
T operator*() { return cur->data; }
};
};
|
因为display()函数中使用了++，！=，->,因此需要写迭代器的符号重载。
1
| T operator*() { return cur->data; }
|
如果不写这一个，我们可以使用编写重载全局
ostream operator<<(ostream& os,const iterator& it){ //实现细节 }
来实现display()中的“
cout<<*iterator;
main()函数及运行结果
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
| #include"_list.h"
#include<iostream>
using namespace std;
int main() {
list<int>a;
for (int i = 0; i < 5; i++) {
a.push_back(i);
}
list<int>::iterator itb = a.begin();
list<int>::iterator ite = a.end();
display(itb, ite);
a.insert(ite, 5);
display(itb, ite);
cout << *itb<<endl;
cout<<*(++itb)<<endl;
cout << *(--ite) << endl<<endl;
a.pop_back();
display(a.begin(), a.end());
system("pause");
return 0;
}
|
至此简历list及其迭代器就编写完了。
STL中list容器类的clear,remove,unique,splice,merge,reverse,sort等元素操作留着之后实现。
