C++之9|容器与迭代器

• 九、容器与迭代器
• • 1、容器
  • • 例40、链表实现（C++的方式）
  • 2、迭代器
  • • 例41、iterator_1
  • 3、STL容器
  • • 例42、iterator_2
    • 例43、vector_1
    • 例44、vector_2
    • 例45、list
    • 例46、map
  • 4、STL算法
  • • 例47、排序算法sort
    • 例48、遍历算法for_each
    • 例49、除重复算法unique
    • 例50、查找内容算法find_if及获取内容个数算法count_if

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

vector		list	  deque		适配器		statck		 queue		priority_queue

map			set//tree		multimap		multiet

#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;

}

运行结果

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

实现指针p指向某个节点然后p+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 < 
运行结果
 
@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$ 
 
3、STL容器 
template 	//类型模板化
 
例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$
 
官方已经提供了很多容器，直接包含头文件就可以使用
 
 
例43、vector_1 
#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 < 
运行结果：
 
@ubuntu:/mnt/hgfs/ub2$ g++ vector_list1.cpp 
@ubuntu:/mnt/hgfs/ub2$ ./a.out
1
2
3
4
5
@ubuntu:/mnt/hgfs/ub2$
 
除了整形int，还可以实现浮点，比如double
 
例44、vector_2 
#include 
#include 

using namespace std;

int main()
{
#if 0
	vector arr;

	arr.push_back(1);
	arr.push_back(2);
	arr.push_back(3);
	arr.push_back(4);
	arr.push_back(5);
#endif
	vector arr;

	arr.push_back(1.2);
	arr.push_back(1.2);
	arr.push_back(1.2);
	arr.push_back(1.2);
	arr.push_back(1.2);

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

	while(i != arr.end() )
	{
		cout<< *i < 
运行结果：
 
@ubuntu:/mnt/hgfs/ub2$ g++ vector_list2.cpp 
@ubuntu:/mnt/hgfs/ub2$ ./a.out
1.2
1.2
1.2
1.2
1.2
@ubuntu:/mnt/hgfs/ub2$
 
下面的是容器list链式存储
 
例45、list 
#include 
//#include 
#include 

using namespace std;

int main()
{
#if 0
	vector arr;

	arr.push_back(1);
	arr.push_back(2);
	arr.push_back(3);
	arr.push_back(4);
	arr.push_back(5);
#endif
//	vector arr;
	list arr;
	arr.push_back(1.2);
	arr.push_back(1.2);
	arr.push_back(1.2);
	arr.push_back(1.2);
	arr.push_back(1.2);

//	vector::iterator i = arr.begin();
//	vector::iterator i = arr.begin();
	list::iterator i = arr.begin();
	while(i != arr.end() )
	{
		cout<< *i < 
运行结果：
 
@ubuntu:/mnt/hgfs/ub2$ g++ vector_list3.cpp 
@ubuntu:/mnt/hgfs/ub2$ ./a.out
1.2
1.2
1.2
1.2
1.2
@ubuntu:/mnt/hgfs/ub2$
 
例46、map 
#include 
#include