九、容器与迭代器

代码界的高手们写出了很多有价值的库、容器、算法等并且开源，所以我们在后续的项目以及大工程方面的开发基本都是站在这些巨人的肩膀上进行的。相信很多人都是把前人的库或者代码架构作为基础，然后运用此前我们所学知识进行浅层的修改（换汤不换药），进行功能的整合，最终满足自身的需求。有些啰嗦，总之，使用别人的库是提高效率很好的方式。

1、容器

/********顺序容器********/
vector		list	  deque		适配器		statck		 queue		priority_queue
/********关联容器********/
map			set//tree		multimap		multiet
1
2
3
4

例40、链表实现（C++的方式）

#include 
#include 

using namespace std;

class myList{	
	struct Node{//struct声明的所有类都是public
		Node(int x, Node *ptr=NULL):data(x), next(ptr) { }
		int data;
		Node *next;
	};
public:
	myList():head(NULL) { }//初始化表，见例9
	~myList() {
		while(head)//遍历
		{
			Node *tem = head;
			head = head->next;
			delete tem;
		}
	}

	void insert_head(int data)
	{
		Node *node = new Node(data);//数据传给节点
		node->next = head;          
		head = node;
	}

    //声明成友元，见例11
	friend ostream &operator<<(ostream &out, const myList &list);
private:
	Node *head;
};

//运算符<<重载，见例21
ostream &operator<<(ostream &out, const myList &list)//&list是常引用
{
	myList::Node *tem = list.head;//Node是内部类所以要名字限定在myList
	while(tem)
	{
		out<< tem->data <<',';
		tem = tem->next;
	}
	out << endl;//输出流的out所以不是cout，ostream是标准输出流

	return out;
}

int main()
{
	myList list;

	list.insert_head(1);
	list.insert_head(2);
	list.insert_head(4);
	list.insert_head(3);

	cout << 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

运行结果

@ubuntu:/mnt/hgfs/ub2$ g++ list1.cpp 
@ubuntu:/mnt/hgfs/ub2$ ./a.out
3,4,2,1,
@ubuntu:/mnt/hgfs/ub2$ 
1
2
3
4

2、迭代器

实现指针p指向某个节点然后p+1就指向下一个节点

例41、iterator_1

#include 
#include 

using namespace std;

class myList{	
   struct Node{
   	Node(int x, Node *ptr=NULL):data(x), next(ptr) { }
   	int data;
   	Node *next;
   };
public:
   class iterator{//迭代器类，要申请为public，否则默认成私有会报错
   public:
   	iterator(Node *ptr=NULL):pos(ptr) {  }//初始化表
   	iterator &operator++(int)//重载运算符++
   	{
   		if(NULL != pos)
   			pos = pos->next;
   		return *this;
   	}

   	int &operator*()
   	{
   		return pos->data;
   	}

   	bool operator!=(iterator x)
   	{
   		return pos != x.pos;
   	}
   private:
   	Node *pos;
   };
public:
   myList():head(NULL) { }
   ~myList() {
   	while(head)
   	{
   		Node *tem = head;
   		head = head->next;
   		delete tem;
   	}
   }

   void insert_head(int data)
   {
   	Node *node = new Node(data);
   	node->next = head;
   	head = node;
   }

   iterator begin()//起始迭代器
   {
   	return iterator(head);
   }
   iterator end()//尾巴迭代器
   {
   	return iterator(NULL);
   }


   friend ostream &operator<<(ostream &out, const myList &list);
private:
   Node *head;
};

ostream &operator<<(ostream &out, const myList &list)
{
   myList::Node *tem = list.head;
   while(tem)
   {
   	out<< tem->data <<',';
   	tem = tem->next;
   }
   out << endl;

   return out;
}

int main()
{
   myList list;

   list.insert_head(1);
   list.insert_head(2);
   list.insert_head(4);
   list.insert_head(3);

   cout << list;

   myList::iterator i = list.begin();//开始时获取起始迭代器
   while(i != list.end() )//判定尾巴迭代器
   {
       //重载运算符 *号和 ++号 以及 !=号
   	cout << *i <<endl;
   	i++;//遍历链表
   }

}
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

运行结果

@ubuntu:/mnt/hgfs/ub2$ g++ list_iterator1.cpp 
@ubuntu:/mnt/hgfs/ub2$ ./a.out
3,4,2,1,
3
4
2
1
@ubuntu:/mnt/hgfs/ub2$ 
1
2
3
4
5
6
7
8

3、STL容器

template <typename T>	//类型模板化
1

例42、iterator_2

#include 
#include 

using namespace std;

template 
class myList{	
	struct Node{
		Node(T x, Node *ptr=NULL):data(x), next(ptr) { }
		T data;
		Node *next;
	};
public:
	class iterator{
	public:
		iterator(Node *ptr=NULL):pos(ptr) {  }
		iterator &operator++(int)
		{
			if(NULL != pos)
				pos = pos->next;
			return *this;
		}

		int &operator*()
		{
			return pos->data;
		}

		bool operator!=(iterator x)
		{
			return pos != x.pos;
		}
	private:
		Node *pos;
	};
public:
	myList():head(NULL) { }
	~myList() {
		while(head)
		{
			Node *tem = head;
			head = head->next;
			delete tem;
		}
	}

	void insert_head(T data)
	{
		Node *node = new Node(data);
		node->next = head;
		head = node;
	}

	iterator begin()
	{
		return iterator(head);
	}
	iterator end()
	{
		return iterator(NULL);
	}


	template 
	friend ostream &operator<<(ostream &out, const myList &list);
private:
	Node *head;
};

template 
ostream &operator<<(ostream &out, const myList &list)
{
	typename myList::Node *tem = list.head;
	//myList::Node *tem = list.head;会报错，需要typename修饰
	while(tem)
	{
		out<< tem->data <<',';
		tem = tem->next;
	}
	out << endl;

	return out;
}

int main()
{
	myList list;

	list.insert_head(1);
	list.insert_head(2);
	list.insert_head(4);
	list.insert_head(3);

	cout << list;

	myList::iterator i = list.begin();
	while(i != list.end() )
	{
		cout << *i <

@ubuntu:/mnt/hgfs/ub2$ g++ list_iterator_template.cpp 
@ubuntu:/mnt/hgfs/ub2$ ./a.out
3,4,2,1,
3
4
2
1
@ubuntu:/mnt/hgfs/ub2$
1
2
3
4
5
6
7
8

#include 
#include 

using namespace std;

int main()
{

	vector arr;

	arr.push_back(1);
	arr.push_back(2);
	arr.push_back(3);
	arr.push_back(4);
	arr.push_back(5);


	vector::iterator i = arr.begin();

	while(i != arr.end() )
	{
		cout<< *i <