【C/C++学院】0828-STL入门与简介/STL容器概念/容器迭代器仿函数算法STL概念例子/栈队列双端队列优先队列/数据结构堆的概念/红黑树容器

  1. 云栖社区>
  2. 博客>
  3. 正文

【C/C++学院】0828-STL入门与简介/STL容器概念/容器迭代器仿函数算法STL概念例子/栈队列双端队列优先队列/数据结构堆的概念/红黑树容器

吴英强 2015-12-02 12:21:00 浏览1231
展开阅读全文

STL入门与简介

#include<iostream>
#include <vector>//容器
#include<array>//数组
#include <algorithm>//算法

using namespace std;

//实现一个类模板,专门实现打印的功能
template<class T> //类模板实现了方法
class myvectorprint
{
public:
	void operator ()(const T &t)//重载,使用(),打印
	{
		std::cout << t << std::endl;
	}
};

void main()
{
	vector<int>  myvector;
	myvector.push_back(11);
	myvector.push_back(21);
	myvector.push_back(31);
	myvector.push_back(81);
	myvector.push_back(51);

	array<int, 10> myarray = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };

	myvectorprint<int >print;//对于打印进行实例化

	          //begin,endl迭代器,是一个指针
	for_each (myvector.begin(), myvector.end(),print);
	for_each(myarray.begin(), myarray.end(), print);
	cin.get();

	//算法可以适用于任何容器,for_each是一个算法
}

STL容器概念

数组线性容器

#include<iostream>
#include<vector>
#include <array>
#include <tuple>
using namespace std;

void main1()
{
	array<int, 5>myarray = { 1, 2, 3, 4, 5 };
	//数组,静态数组,栈上

	vector <int >myvetor;
	myvetor.push_back(1);
	//动态数组,堆上,

	//不需要变长,容量较小,array
	//需要变长,容量较大,vetor	
}	

链式容器

#include<iostream>
#include <hash_set>
#include <list>
#include<stdio.h>


//list适用于经常插入,经常删除
using namespace std;
void main()
{
	list<int> mylist;
	
	mylist.push_back(1);
	mylist.push_back(2);
	mylist.push_back(3);
	mylist.push_back(4);
	//mylist[1];
	auto ibegin = mylist.begin();//指针,指向一个迭代器,迭代器存储了位置
	auto iend = mylist.end();
	//list用迭代器进行遍历
	for (;ibegin!=iend;ibegin++)
	{
		cout << *ibegin << endl;
		printf("%p,%p\n",  ibegin._Ptr,ibegin);//重载
	}

	cin.get();
}

//list删除
void main3()
{
	list<int> mylist;
	mylist.push_back(1);
	mylist.push_back(2);
	mylist.push_back(3);
	mylist.push_back(4);	
	mylist.push_back(5);
	//auto i = mylist.begin();//删除元素,依赖于迭代器,
	//++i;
	//++i;
	//++i;
	auto i = mylist.end();//end最后一个没有实体,
	//
	i--;
	mylist.erase(i);//链式存储,不允许下标访问
	//只能用迭代器,链表迭代器只能用++,--
	//mylist.clear();清空
	auto ibegin = mylist.begin();//指针,指向一个迭代器,迭代器存储了位置
	auto iend = mylist.end();

	for (; ibegin != iend; ibegin++)
	{
		if ((*ibegin) == 3)
		{
			mylist.erase(ibegin);//删除,删除的时候迭代器会发生
			break;
		}
		//cout << *ibegin << endl;
	}
	{
		auto ibegin = mylist.begin();//指针,指向一个迭代器,迭代器存储了位置
		auto iend = mylist.end();

		for (; ibegin != iend; ibegin++)
		{
			cout << *ibegin << endl;
		}
	}
	cin.get();
}

void main4()
{
	int a[5] = { 1, 2, 3, 4, 5 };
	list<int > mylist(a, a + 5);//根据数组初始化,
	//传递开始地址,传递结束地址
   //	mylist(0);
	//mylist[1];只能用迭代器访问
	mylist.push_back(10);
	mylist.push_front(12);
	auto ibegin = mylist.begin();//指针,指向一个迭代器,迭代器存储了位置
	auto iend = mylist.end();

	for (; ibegin != iend; ibegin++)
	{
		if (*ibegin==3)
		{
			mylist.insert(ibegin ,30);
			break;//删除或者插入,迭代器都会发生变化
		}
	}

	mylist.remove(30);//直接一个函数,根据元素来删除

	{
		auto ibegin = mylist.begin();//指针,指向一个迭代器,迭代器存储了位置
		auto iend = mylist.end();

		for (; ibegin != iend; ibegin++)
		{
			cout << *ibegin << endl;
		}
	}

	cin.get();
}

void main5()
{
	int a[5] = { 1, 2, 3, 4, 5 };
	list<int > mylist(a, a + 5);//根据数组初始化,
	auto rb = mylist.rbegin();
	auto re = mylist.rend();
	//同时正向与方向查找
	for (;rb != re; rb++)
	{
		cout << *rb << endl;
	}

	cin.get();
}

void  main6()
{
	int a[5] = { 1, 2, 3, 104, 5 };
	list<int > mylist1(a, a + 5);//根据数组初始化,
	int b[5] = { 11, 122,33, 44, 55 };
	list<int > mylist2(b, b + 5);//根据数组初始化,
	mylist1.sort();
	mylist2.sort();//排序


	mylist1.merge(mylist2);//合并之前必须有序

	{
		auto ibegin = mylist1.begin();//指针,指向一个迭代器,迭代器存储了位置
		auto iend = mylist1.end();

		for (; ibegin != iend; ibegin++)
		{
			cout << *ibegin << endl;
		}
	}
	cout << "\n\n\n";
	{
		auto ibegin = mylist2.begin();//指针,指向一个迭代器,迭代器存储了位置
		auto iend = mylist2.end();

		for (; ibegin != iend; ibegin++)
		{
			cout << *ibegin << endl;
		}
	}
	cin.get();
}

void main7()
{
		int a[6] = { 1, 2,98, 2, 5, 98 };
		list<int > mylist1(a, a + 6);//根据数组初始化,
		{
			auto ibegin = mylist1.begin();//指针,指向一个迭代器,迭代器存储了位置
			auto iend = mylist1.end();

			for (; ibegin != iend; ibegin++)
			{
				cout << *ibegin << endl;
			}
		}
		mylist1.sort();
		mylist1.unique();//唯一依赖于排序
		cout << "\n\n\n";
		{
			auto ibegin = mylist1.begin();//指针,指向一个迭代器,迭代器存储了位置
			auto iend = mylist1.end();

			for (; ibegin != iend; ibegin++)
			{
				cout << *ibegin << endl;
			}
		}

		cin.get();
}

红黑树容器

#include<iostream>
#include <set>
using namespace std;

void main1231()
{
	set<int>myset;
	myset.insert(10);
	myset.insert(9);
	myset.insert(8);
	myset.insert(7);
	myset.insert(5);
	myset.insert(6);
	myset.insert(7);
	//myset.insert(7);重复会被舍弃
	auto findpos = myset.find(10);
	cout << "  find ->" << *findpos << "  \n";

	auto ib = myset.begin();
	auto ie = myset.end();
	for (;ib!=ie;ib++)
	{
		cout << *ib << "  ";
		
	}
	std::cout << "\n"<<myset.size() << endl;
	cin.get();
}

容器迭代器仿函数算法STL概念例子

算法的概念

#include <algorithm>
#include <iostream>
using namespace std;

struct print
{
	void operator ()(int x)//重载了()符号,之际调用()
	{
		std::cout << x << endl;
	}
};

void printA(int x)
{
	std::cout << x << endl;
}

void main1()
{
	int a[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	int *p = find(a, a + 10, 8);
	std::cout << (void*)a << (void*)(a + 10) << std::endl;
	std::cout << *p << endl;
	std::cout << p << endl;
	if (p==(a+10))
	{
		std::cout << "没有找到\n";
	}
	for_each(a, a + 4, print());//遍历每一个元素,
	//printA是一个函数指针,必须是函数类型

	cin.get();
}

容器与迭代器

#include<iostream>
#include <set>
#include <stdio.h>
#include <list>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

void main12()
{
	multiset <int>myset;
	myset.insert(11);
	myset.insert(12);
	myset.insert(13);
	myset.insert(10);
	myset.insert(10);
	myset.insert(100);
	auto ib = myset.begin();
	auto ie = myset.end();

	for (;ib!=ie;ib++)
	{
		std::cout << *ib << std::endl;
		printf("%p,%p\n", ib, ib._Ptr);//智能指针
	}

	cin.get();
}


void main()
{
	list<int> mylist;
	mylist.push_back(11);
	mylist.push_back(1);
	mylist.push_back(16);
	mylist.push_back(1);
	mylist.push_back(18);

	auto ib = mylist.begin();
	auto ie = mylist.end();
	for (;ib!=ie;ib++)
	{
		std::cout << *ib << std::endl;
		printf("%p\n", ib);
		
		printf("%p\n", ib._Ptr);

		//智能指针  STL  bug ,分行打印,先访问内部,再访问外部

		printf("%p,%p\n", ib._Ptr,ib );//智能指针.
	}

	cin.get();
}


void mainx()
{
	list<int> mylist;

	mylist.push_back(1);
	mylist.push_back(2);
	mylist.push_back(3);
	mylist.push_back(4);
	//mylist[1];
	auto ibegin = mylist.begin();//指针,指向一个迭代器,迭代器存储了位置
	auto iend = mylist.end();
	//list用迭代器进行遍历
	for (; ibegin != iend; ibegin++)
	{
		cout << *ibegin << endl;
		printf("%p,%p\n", ibegin._Ptr, ibegin);//重载
	}

	cin.get();
}

bool less3(int x)
{
	return x < 3;

}

void mainu()
{
	vector<int> mylist;
	mylist.push_back(1);
	mylist.push_back(2);
	mylist.push_back(16);
	mylist.push_back(1);
	mylist.push_back(18);

	using namespace std;

	auto ib = mylist.begin();
	auto ie = mylist.end();
	for (; ib != ie; ib++)
	{
		std::cout << *ib << std::endl;		
	}

	//仿函数可以实现一定的算法策略

	//auto ifind = find_if(++mylist.begin(), mylist.end(), bind1st( greater<int>(), 3));
	auto ifind = find_if(mylist.begin(), mylist.end(), less3);
	// bind1st( greater<int>(), 3)
     //绑定一个函数, greater<int>(),3

	std::cout <<"\n\n\n\n"<< *ifind << endl;

	cin.get();
}

栈队列双端队列优先队列

#include <stack>
#include <iostream>

using namespace std;

void mainB()
{
	int a[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

	stack<int> mystack;
	for (int i = 0; i < 10;i++)
	{
		mystack.push(a[i]);
	}

	while (!mystack.empty())
	{
		int num = mystack.top();
		std::cout << num << " ";
		mystack.pop();
	}

	cin.get();
}

void mainA()
{
	int num;
	cin >> num;
	stack<int> mystack;
	for ( ;num;num/=2)
	{
		mystack.push(num % 2);
		std::cout << "当前元素个数" << mystack.size() << endl;
	}

	while (!mystack.empty())
	{
		int num=mystack.top();
		std::cout << num << " ";
		mystack.pop();
	}

	cin.get();
	cin.get();
}

队列

#include <queue>
#include <iostream>
#include <string>
#include <stdlib.h>
#include <list>
#include<deque>//双端队列

//提供了二维动态数组的功能,头部,尾部,任意操作
using namespace std;

void mainX()
{
	queue<char *>myq;
	myq.push("calc");
	myq.push("notepad");
	myq.push("tasklist");
	myq.push("mspaint");

	while (!myq.empty())
	{
	  char *p=	myq.front();//获取
	  system(p);
	  myq.pop();
	}
}


void mainY()
{
	deque<int> mydq;
	mydq.push_back(1);
	mydq.push_back(11);
	mydq.push_back(111);
	mydq.push_back(1111);
	mydq.push_back(11111);
	mydq.push_front(123);
	mydq.insert(mydq.begin() + 3, 100);//插入

	for (int i = 0; i < mydq.size();i++)
	{
		std::cout << mydq[i] << std::endl;
	}
	auto ib = mydq.begin();
	auto ie = mydq.end();
	for (; ib != ie; ib++)
	{
		std::cout << *ib<< std::endl;
	}

	cin.get();
}

void main11()
{
	deque<int> mydq;
	mydq.push_back(1);
	mydq.push_back(11);
	mydq.push_back(111);
	mydq.push_back(1111);
	mydq.push_back(11111);
	mydq.push_front(123);
	//mydq.erase(mydq.begin());
	//mydq.erase(mydq.end() - 1);
	mydq.pop_front();//头部弹出
	mydq.pop_back();//尾部
	//mydq.clear();
	
	auto ib = mydq.begin();
	auto ie = mydq.end();
	for (; ib != ie; ib++)
	{
		std::cout << *ib << std::endl;
	}

	cin.get();
}

void main1234()
{
	deque<int> mydq1;
	mydq1.push_back(1);
	mydq1.push_back(11);
	mydq1.push_back(111);
	mydq1.push_back(1111);
	mydq1.push_back(11111);

	deque<int> mydq2;
	mydq2.push_back(2);
	mydq2.push_back(21);
	mydq2.push_back(211);
	mydq2.push_back(2111);
	
	mydq1.swap(mydq2);
	//块语句
	{
		auto ib = mydq1.begin();
		auto ie = mydq1.end();
		for (; ib != ie; ib++)
		{
			std::cout << *ib << std::endl;
		}
	}

	{
		auto ib = mydq2.begin();
		auto ie = mydq2.end();
		for (; ib != ie; ib++)
		{
			std::cout << *ib << std::endl;
		}
	}

	cin.get();
}

void mainXF()
{
	deque<int> mydq1;
	mydq1.push_back(1);
	mydq1.push_back(11);
	mydq1.push_back(111);
	mydq1.push_back(1111);
	mydq1.push_back(11111);
	std::cout << mydq1.front() << std::endl;
	std::cout << mydq1.back() << std::endl;
	std::cout << mydq1.max_size() << std::endl;
	std::cout << mydq1.size() << std::endl;


	cin.get();
}

void  mainRT()
{
	priority_queue<int > myq;
	myq.push(10);
	myq.push(12);
	myq.push(11);
	myq.push(110);
	myq.push(101);//自动排序

	while (!myq.empty())
	{
		std::cout << myq.top() << endl;
		myq.pop();
	}

	cin.get();
}


struct student
{
	int age;
	string name;
};
//strcmp==0; 字符串比较, c风格
struct stuless
{
	//仿函数
	bool operator()(const student &s1,  const student &s2)
	{
		return s1.age < s2.age;
	}
};

void main()
{                  //类名,   //存储         //比大小
	priority_queue<student, deque<student>, stuless> myq;
	student s1;
	s1.age = 10;
	s1.name = "谭胜";
	student s2;
	s2.age = 9;
	s2.name = "熊飞";
	student s3;
	s3.age = 19;
	s3.name = "熊peng飞";
	myq.push(s1);
	myq.push(s2);
	myq.push(s3);
	while (!myq.empty())
	{
		std::cout << myq.top().age << myq.top().name << endl;
		myq.pop();
	}

	cin.get();
}

数据结构堆的概念

堆数据结构是一种数组对象,它可以被视为一科完全二叉树结构。它的特点是父节点的值大于(小于)两个子节点的值(分别称为大顶堆和小顶堆)。它常用于管理算法执行过程中的信息,应用场景包括堆排序,优先队列等。 

数组的形式,采用顺序存储,构成树的结构。

红黑树容器

Set 每一个节点就是一个基本的节点数据

#include<iostream>
#include <set>
#include <string>
#include <bitset>

using namespace std;

struct strless
{
	bool operator()(const char *str1, const char *str2) //二分查找法依赖于有序,字符串有序
	{
		return strcmp(str1, str2)  <  0;
	}
};

//红黑树,处理纯数字非常少,处理类对象以及字符串
void main1()
{
	//set<char *, strless> myset(strless());//默认构造
	const char *cmd[] = { "abc", "calc", "notepad", "const","xyz","ghj" };

	set< const char *, strless> myset(cmd, cmd + 6, strless());//构造
	myset.insert("1234");
	myset.insert("4567");

	//pair起到获取插入返回值,第一个类型,类型比大小的方式
	pair<set<const char *>::iterator, bool> p = myset.insert("9876");
	cout << "pair start" << endl;
	cout << *(p.first) <<"   "<< p.second << endl;
	cout << "pair over" << endl;

	auto ib = myset.begin();
	auto ie = myset.end();
	for (;ib!=ie;ib++)
	{
		cout << *ib << endl;
	}
	auto rb = myset.rbegin();
	auto re = myset.rend();
	for (; rb != re; rb++)
	{
		cout << *rb << endl;
	}
	set<const char *, strless>::iterator pfind = myset.find("xyz");//查找
	std::cout <<"\n\n\n"<< *pfind << endl;

//	std::cout << "\n\n\n" << *p << endl;
	cin.get();
}

Multiset 内部机制:红黑树的每一个节点是链表

#define _CRT_SECURE_NO_WARNINGS
#include <set>
#include <iostream>
#include <string>

//mutiset每一个节点都是一个链表,set每个节点就是一个节点
using namespace std;

struct student
{
	int id;
	char name[30];
};
//排序
struct stuless
{
	bool operator()(const student &s1, const student &s2)
	{
		return s1.id < s2.id;
	}
};

void main2()
{
	student sarray[3] = { { 10, "tansheng" }, { 3, "liguilong" }, { 4, "xiongfei" } };
	multiset<student, stuless> myset (sarray, sarray + 3, stuless());
	student stu1;
	stu1.id = 20;
	strcpy(stu1.name, "mouzhiwei");
	myset.insert(stu1);
	strcpy(stu1.name, "mouzhiwei1");
	myset.insert(stu1);
	strcpy(stu1.name, "mouzhiwei2");
	myset.insert(stu1);
	auto ib = myset.begin();
	auto ie = myset.end();
	for (;ib!=ie;ib++)
	{
		cout << (*ib).id << "  " << (*ib).name << endl;
	}

	cin.get();
}

映射map 本质也是红黑树,可以同时存储很多数据。

#include <map>//也是红黑树
#include <iostream>

using namespace std;

void main1111()
{
	map<const char * , int> mymap;
	mymap["司令"] = 10;//映射 ,对等的映射查找
	mymap["军长"] = 9;
	mymap["师长"] = 8;
	mymap["旅长"] = 7;

	cout << mymap["司令"] << endl;
	cout << mymap["军长"] << endl;
	cout << mymap["师长"] << endl;
	cout << mymap["旅长"] << endl;
	
	std::cin.get();
}

struct  student
{
	char * name;
	int  year;
};

struct stuinfo
{
	int id;
	student stu;
};

void main3213()
{
	stuinfo infoarrary[] = { { 10, { "yincheng1", 21 }  },
	                         { 5, { "yincheng2", 22 } } ,
							 { 25, { "yincheng3", 30 } } };

	map<int, student> m;//编号映射 结构体
	for (int i = 0; i < 3;i++)
	{
		m[ infoarrary[i].id ] = infoarrary[i].stu;//编号映射一个学生的信息	
	}
	stuinfo infoarrarys = { 101, { "china", 99 } };
	m[25] = infoarrarys.stu;//映射

	map<int,student>::iterator ib = m.begin();
	auto ie = m.end();
	for (;ib!=ie;ib++)
	{
		cout << (*ib).first << endl;
		cout << (*ib).second.name <<"  " <<(*ib).second.year << endl;
	}
	
	cin.get();
}

Multimap  每一个节点又是一个链表

#include <map>
#include <iostream>

using namespace std;

//map,mutlimap区别是map每一个节点是一个映射
//multimap每一个一个节点是映射的链表的开头
void main121321()
{
	map<const char *, int> m;
	m.insert(pair<const char *, int>("司令1",101));
	m.insert(pair<const char *, int>("司令2", 102));
	m.insert(pair<const char *, int>("司令3", 103));
	m.insert(pair<const char *, int>("司令1", 104));

	map<const char *, int>::iterator ib = m.begin();
	auto ie = m.end();
	for (; ib != ie; ib++)
	{
		cout << (*ib).first << "   " << (*ib).second << "\n";
	}
	
	cin.get();
}

void main2123123()
{
	multimap<const char *, int> m;
	m.insert(pair<const char *, int>("司令1", 101));
	m.insert(pair<const char *, int>("司令2", 102));
	m.insert(pair<const char *, int>("司令3", 103));
	m.insert(pair<const char *, int>("司令1", 104));

	auto ib = m.begin();
	auto ie = m.end();
	for (; ib != ie; ib++)
	{
		cout << (*ib).first << "   " << (*ib).second << "\n";
	}
	
	cin.get();
}

Hash_set  hash不需要排序,能够做到快速查找。秒查,比二分查找法还快。


#include <hash_set>
#include <iostream>
#include<algorithm>
#include <string>

using namespace std;

void main123123123()
{
	const char *cmd[] = { "abc", "calc", "notepad", "const", "xyz", "ghj" };
	hash_set<const char*> hs;//C++11自带了字符串的哈希
	
	hs.insert("chian");
	hs.insert("chi123an");
	hs.insert("chi23an");
	hs.insert("chzcian");
	hs.insert("1chzcian");

	auto pfind = hs.find("chi1213an");

	if (pfind == hs.end())
	{
		std::cout << "没有";
	}
	else
	{
		std::cout << *pfind;
	}

	cin.get();
}


void main1asdasdsad()
{
	hash_set<int> hs;
	hs.insert(91);
	hs.insert(21);
	hs.insert(41);
	
	auto ib = hs.begin();
	auto ie = hs.end();
	for (;ib!=ie;ib++)
	{
		cout << *ib << endl;
	}
	auto pfind = hs.find(211);
	if (pfind==ie)
	{
		std::cout << "没有";
	} 
	else
	{
		std::cout << *pfind;
	}

	cin.get();
}

Hash_map

#include <hash_map>//也是红黑树
#include <iostream>
#include<map>

using namespace std;

void main()
{
	map< int,const char *> m;
	m.insert(pair< int, const char *>(201, "司令1" ));
	m.insert(pair< int, const char *>(101, "司" ));
	m.insert(pair< int, const char *>(401, "司令11111" ));
	m.insert(pair< int, const char *>(301, "司令"));

	auto ib = m.begin();
	auto ie = m.end();
	for (; ib != ie; ib++)
	{
		cout << (*ib).first << "   " << (*ib).second << "\n";
	}
	{
		hash_map< int, const char *> m;
		m.insert(pair< int, const char *>(201, "司令1"));
		m.insert(pair< int, const char *>(101, "司"));
		m.insert(pair< int, const char *>(401, "司令11111"));
		m.insert(pair< int, const char *>(301, "司令"));

		auto ib = m.begin();
		auto ie = m.end();
		for (; ib != ie; ib++)
		{
			cout << (*ib).first << "   " << (*ib).second << "\n";
		}
		auto tofind = m.find(1101);
		if (tofind == ie)
		{
			cout << "没有找到";
		}
		else
		{
			cout << "\n\n\n"<<(*tofind).first<<"  "<<(*tofind).second;
		}
	}

	std::cin.get();
}


网友评论

登录后评论
0/500
评论
吴英强
+ 关注