C++STL标准模板库(容器总结)算法

C++ 标准模板库STL,是一个使用模板技术实现的通用程序库,该库由容器container,算法algorithm,迭代器iterator,容器和算法之间通过迭代器进行无缝连接,其中所包含的数据结构都是目前最优解,该库既能保证软件代码的高可复用性,又能保证代码具有相当高的执行效率,STL库是ANSI/ISO的C++标准的具体实现,任何标准库的实现都是以源码形式释出的.

STL是C++的一部分，STL可分为容器(containers)、迭代器(iterators)、空间配置器(allocator)、配接器(adapters)、算法(algorithms)、仿函数(functors)六个部分，以下案例主要是在学习时对容器的总结笔记，基本上涵盖了关于容器之间，能够想到的任何操作，一次性全部涵盖其中。

String 字串操作容器

String字符串操作容器是C++标准中实现的一个重要容器,其主要用于对字符串的高效处理,它和C风格中的string.h并不是同一个库,两个库有极大的差距,C库中的string.h主要面向过程提供一些处理函数,而C++库中的string则是基于类实现的更高效的一种字符串处理方法集,类中提供了非常方便的成员函数供我们使用.

字符串构造函数: 因为字符串关键字其实是一个类,我们可以通过构造函数完成初始化字符串.

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

int main(int argc, char* argv[])
{
	string str("hello lyshark"); // 定义一个字符串
	string str_1(str);           // 构造函数,将 str中的内容全部复制到str_1
	
	string str_2(str, 2, 5);     // 构造函数,从字符串str的第2个元素开始,复制5个元素,赋值给str_2
	
	string str_3(str.begin(), str.end()); // 复制字符串 str 的所有元素，并赋值给 str_3

	char ch[] = "lyshark";
	string str_4(ch, 3);    // 将字符串ch的前5个元素赋值给str_4

	string str_5(5, 'x');   // 将 5 个 'X' 组成的字符串 "XXXXX" 赋值给 str_5
	
	system("pause");
	return 0;
}

字符串对象赋值: 使用String对象中的assign()函数,可以实现字符串之间的赋值.

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

int main(int argc, char* argv[])
{
	string str,new_str;

	str = "lyshark";     // 基本的对象赋值
	new_str.assign(str); // 把str中的数据赋值给new_str

	string s1, s2, s3;

	s1.assign(str, 1, 4);     // 字符串截取从str中第1位开始向后截取4个字符
	s2.assign(5, 'A');        // 想字符串中填充5个A

	cout << s3 << endl;
	
	system("pause");
	return 0;
}

字符串遍历操作: 通过使用str.size()函数获取到字符的具体个数,最后循环遍历输出这些字符串.

#include <iostream>
#include <string>
#include <stdexcept>
using namespace std;

int main(int argc, char* argv[])
{
	string str = "hello lyshark";

	// 第一种遍历如果字符串越界,会直接挂掉
	for (int x = 0; x < str.size(); x++)
		cout << str[x] << endl;

	// 第二种at遍历,如果越界会抛出异常
	try
	{
		for (int x = 0; x < str.size(); x++)
			cout << str[x] << endl;
	}
	catch (out_of_range &e)
	{
		cout << "异常类型: " << e.what() << endl;
	}
	system("pause");
	return 0;
}

字符串添加与删除: 使用append()添加字符串,使用insert()插入字符串,使用erase()删除指定范围字符串.

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

int main(int argc, char* argv[])
{
	string str1("hello "), str2("lyshark");
	str1.append(str2);        // 将str2的内容追加到str1后面
	str1.append(str2, 1, 3);  // 将str2内容从第1个到第3个字符追加到str1后面
	str1.append(5, 'A');      // 向str1子串里面追加5个A

	string str3 = "this is ok";
	string str4 = str3.substr(1,3);  // 截取子串 => his
	string str5 = str3.substr(1, 5); // 截取子串 => his i

	string str6 = "real steel";
	str6.erase(5);               // 从第5个字符开始向后删除所有
	str6.erase(0, 4);            // 从第0个字符开始向后删除4个

	string str7 = "hello lyshark";
	str7.insert(2, "123");     // 在下标 2 处插入字符串"123"
	str7.insert(3, 4, 'A');    // 在下标 3 处插入 5 个 'A'
	
	system("pause");
	return 0;
}

字符串查找与替换: 使用find()可查找字符串第一次出现的位置,使用compare比较字符串,使用replace()替换字符串.

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

int main(int argc, char* argv[])
{
	string str1("Source Code"),str2("Source Code");
	int x;

	if ((x = str1.find("u")) != string::npos)
		cout << str1.substr(x) << endl;    // 查找字符u第一次出现的位置

	if ((x = str1.find("Source", 3)) != string::npos)
		cout << str1.substr(x) << endl;    // 查找Source字符串,并从下标3位置输出
	
	if ((x = str1.find_first_of("urc")) != string::npos)
		cout << x << endl;                // 查找urc字符串最先出现的位置

	if (str1.compare(str2))               // 比较两个字符串是否相等
		cout << "False" << endl;

	string str3 = "hello lyshark";
	str3.replace(1, 3, "abcde");          // 从第1处开始替换3个字符
	cout << str3 << endl;
	
	system("pause");
	return 0;
}

字符串首尾数据提取: 我们可以通过find()查找指定通配符,然后使用substr()灵活的提取左面或右面的字符串.

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

int main(int argc, char* argv[])
{
	string email = "admin@blib.cn";
	int pos = email.find("@");

	string username = email.substr(0, pos); // 提取出用户名
	cout << username << endl;

	string mail = email.substr(pos+1);      // 提取出mail邮箱
	cout << mail << endl;

	system("pause");
	return 0;
}

字符串与字符互转: 使用str.c_str()将string转换为char,使用string str()将char强转为string.

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

int main(int argc, char* argv[])
{
	string str = "lyshark";

	// string 转换为 -> char *
	const char *ptr = str.c_str();
	cout << ptr << endl;

	// char * 转换为 -> string
	string str1(ptr);
	cout << str1 << endl;

	// int 转换为 -> string
	int Num = 546;
	string str2 = to_string(Num);
	cout << str2 << endl;
	
	system("pause");
	return 0;
}

字符串大小写互转: 使用topper()将小写字符变成大写,使用tolower()将大写字符变为小写.

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

int main(int argc, char* argv[])
{
	string str = "lyshark";
	for (int x = 0; x < str.size(); x++)
		str[x] = toupper(str[x]);   // 全部变大写
		//str[x] = tolower(str[x]); // 全部变小写
		cout << str << endl;
	
	system("pause");
	return 0;
}

Vector 数组向量容器

Vector 容器是一种简单的高效率的数组容器,该容器可以方便、灵活地代替数组,容器可以实现动态对数组阔扩容删除等各种复杂操作,其时间复杂度O(l)常数阶,其他元素的插入和删除为O(n)线性阶,其中n为容器的元素个数,vector具有自动的内存管理机制,对于元素的插入和删除可动态调整所占用的内存空间.

数组向量的基本使用: 首先我们来实现遍历数组向量,向数组向量中放入元素与移出元素.

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

void MyPrint(vector<int>& var)
{
	cout << "empty = " << var.empty() << " --> size = " << var.size()  << endl;
	cout << "capacity = " << var.capacity() << " --> max_size = " << var.max_size() << endl;
	for_each(var.begin(), var.end(), [](int val){ cout << val << endl; });
	cout << "---------------------------------------------------------" << endl;
}

int main(int argc, char* argv[])
{
	vector<int> var{ 1, 2, 3 };

	var.push_back(4);  // 放入元素
	MyPrint(var);
	var.pop_back();    // 弹出一个元素
	MyPrint(var);
	var.resize(10);    // 重新设置最大存储
	var.reserve(30);   // 调整数据空间大小
	MyPrint(var);

	system("pause");
	return 0;
}

数组向量的正/反向遍历: 前两种遍历方式分别是通过下标法和迭代实现正向遍历,最后的第三种方式是实现的反向遍历.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main(int argc, char* argv[])
{
	// 第一种遍历数组的方式,使用数组的下标实现遍历
	vector<string> str_array{ "admin", "guest", "lyshark" };
	cout << "str_array sizeof:" << str_array.capacity() << endl;
	for (int x = 0; x < str_array.size(); x++)
	{
		cout << "str_array --> " << str_array[x] << endl;
	}
	cout << endl;

	// 第二种遍历数组的方式,使用迭代器实现的正向遍历
	vector<int> int_array{ 1, 2, 3, 4, 5 };
	vector<int>::const_iterator item;
	int each = 0;
	for (item = int_array.begin(), each = 0; item != int_array.end(); ++item, ++each)
	{
		cout << "int_array[" << each << "] --> " << (*item) << endl;
	}
	cout << endl;

	// 第三种遍历数组的方式,使用迭代器实现的反向遍历
	vector<int> rint_array{ 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	vector<int>::reverse_iterator start, end; // 定义向量迭代器
	end = int_array.rend();
	for (start = int_array.rbegin(); start != end; start++)
	{
		cout << "int_array --> " << *start << endl;
	}

	system("pause");
	return 0;
}

数组向量的正/反向排序: 首先生成10个随机数,然后分别对这些数字进行正向排序,与反向排序.

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

// 实现的一个排序回调函数,反向排序需要使用该回调
bool MyCompare(int value1, int value2){ return value1 > value2; }

int main(int argc, char* argv[])
{
	vector<int> *int_array = new vector<int>;

	// 生成10个随机数用于测试
	for (int x = 0; x < 10; x++)
		int_array->push_back(rand() % 100);

	// 遍历的方式实现 正向排序
	std::sort(int_array->begin(), int_array->end());
	vector<int>::const_iterator item = int_array->cbegin();
	while (item != int_array->cend())
	{
		cout << (*item) << " ";
		item++;
	}
	cout << endl;

	// 遍历的方式实现 反向排序
	std::sort(int_array->begin(), int_array->end(), MyCompare);
	vector<int>::const_iterator item_1 = int_array->cbegin();
	while (item_1 != int_array->cend())
	{
		cout << (*item_1) << " ";
		item_1++;
	}

	system("pause");
	return 0;
}

向数组向量中插入元素: 向数组中插入元素可以使用push_back()方法,当需要插入到指定位置时可使用insert()方法.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main(int argc, char* argv[])
{
	// 定义数组容器,并赋予初始值
	vector<string> str_array{ "admin", "guest", "lyshark" };

	str_array.push_back("django");     // 插入元素
	str_array.push_back("python");     // 插入元素
	str_array.pop_back()               // 弹出元素
	// cout << str_array[3] << endl;                   // 通过元素下标遍历数据
	str_array.insert(str_array.begin() + 2, "ruby");   // 在数组索引2的位置插入元素
	str_array.insert(str_array.end(), "C++");          // 在数组最后插入元素

	for (int x = 0; x < str_array.size(); x++)
		cout << "str_array[" << x << "] --->" << str_array[x] << endl;

	system("pause");
	return 0;
}

向数组向量中插入结构指针: 首先我们定义一个数组向量,然后向指定的数组中插入结构的首地址.

#include <iostream>
#include <vector>

using namespace std;

typedef struct
{
	int ID;
	char szName[20];
}Person, *Ptr;

int main(int argc, char* argv[])
{
	vector<Person> ary[10];

	Person p1 = { 1, "admin" };
	Person p2 = { 2, "lyshark" };
	Person p3 = { 3, "guest" };

	ary[0].push_back(p1);
	ary[1].push_back(p2);
	ary[2].push_back(p3);

	for (int x = 0; x < 3; x++)
	{
		vector<Person>::iterator item = ary[x].begin();
		cout << "ID: " << (*item).ID <<" ---> Name: " << (*item).szName << endl;
	}
	system("pause");
	return 0;
}

向数组向量中插入类指针: 此处插入类指针与上方的结构指针是类似的,此处不在说明了.

#include <iostream>
#include <vector>

using namespace std;

class MyAnimal{
public:
	char *name;
	int id;
public:
	MyAnimal(char* name, int id)
	{
		this->name = name;
		this->id = id;
	}
};

int main(int argc, char* argv[])
{
	MyAnimal* pDog = new MyAnimal("dog", 1);
	MyAnimal* pMonkey = new MyAnimal("monkey", 2);
	MyAnimal* pSnake = new MyAnimal("psnake", 3);

	vector<MyAnimal *> var;     // 定义模板
	var.push_back(pDog);        // 将指针放入列表
	var.push_back(pMonkey);
	var.push_back(pSnake);
	// 指针列表的遍历器
	vector<MyAnimal*>::iterator start, end;
	end = var.end();
	for (start = var.begin(); start != end; start++)
	{
		cout <<"ID: "<<(*start)->id << " ---> " << "Name: " << (*start)->name << endl;
	}
	system("pause");
	return 0;
}

在数组容器中嵌套容器: 首先声明var容器,该容器的内部定义为容器类型,然后初始化v1,v2,将其放入var容器中.

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

int main(int argc, char* argv[])
{
	// 容器中内嵌容器
	vector< vector<int> > var;
	vector<int> v1;
	vector<int> v2;

	for (int x = 0; x < 5; x++)
	{ // 放入小容器中的数据
		v1.push_back(x);
		v2.push_back(x + 10);
	}
	// 将小容器放入大容器中
	var.push_back(v1);
	var.push_back(v2);
	
	// 遍历所有容器中的数据, 由于是嵌套容器,所以我们要先来遍历第一层,在第一层中遍历第二层.
	for (vector<vector<int>>::iterator item = var.begin(); item != var.end(); item++)
	{
		for (vector<int>::iterator vitem = (*item).begin(); vitem != (*item).end(); vitem++)
		{
			cout << (*vitem) << " ";
		}
		cout << endl;
	}
	system("pause");
	return 0;
}

函数参数定义为容器类型: 这里我们定义了函数MyPrintVector()其形参可接受vector<int>类型的容器.

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


void MyPrintVector(vector<int> &var)
{
	for (vector<int>::iterator item = var.begin(); item != var.end(); item++)
	{
		cout << (*item) << " ";
	}
	cout << endl;
}

int main(int argc, char* argv[])
{
	vector <int> var;
	int arry[] = { 1, 2, 3, 4, 5 };

	// 两种不同的容器构造方式
	vector<int> v1 (arry, arry + sizeof(arry) / sizeof(int));
	vector<int> v2(v1.begin(), v1.end());

	MyPrintVector(v2);       // 打印v2容器中的内容

	vector<int> v3(10, 20);  // 生成容器,里面包含10个20
	MyPrintVector(v3);

	vector<int> v4;          // 赋值的使用,里面包含10个20
	v4.assign(v3.begin(), v3.end());
	MyPrintVector(v4);

	v4.swap(v2);             // v2与v4容器内容互换
	MyPrintVector(v4);

	system("pause");
	return 0;
}

数组向量元素的删除: 数组向量并没有直接删除元素的方法,需要使用find()方法找到元素,迭代并使用erase()删除元素.

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

int main(int argc, char* argv[])
{
	vector<int> int_array {1,2,3,4,5,6,7,8,9,10};

	// find 找到元素7并删除
	vector<int>::iterator item = find(int_array.begin(), int_array.end(), 7);
	if (item != int_array.cend())
		int_array.erase(item);  // 删除指定元素

	// 删除后对数组进行遍历
	vector<int>::iterator start, end;
	end = int_array.end();
	for (start = int_array.begin(); start != end; start++)
	{
		cout << (*start) << endl;
	}
	system("pause");
	return 0;
}

Deque 双向队列容器

Deque双向队列容器与Vector非常相似,它不但可以在数组尾部插入和删除元素,还可以在头部进行插入和删除,队列算法的时间复杂度也是常数阶O(1),队列内部的数据机制和性能与Vector不同,一般来说当考虑到容器元素的内存分配策略和操作的性能时,Deque相对于Vector较有优势.

单向队列的基本操作: 单向队列容器遵循先进先出FIFO的原则,最先从队列尾部插入的容器会最先被弹出队列.

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

int main(int argc, char* argv[])
{
	queue<int> que;

	que.push(1); // 入队列
	que.push(2);

	while (!que.empty())
	{
		cout << "Head: " << que.front() << endl; // 队头
		cout << "End: " << que.back() << endl;   // 队尾
		que.pop(); // 出队列
	}
	cout << "Size: " << que.size() << endl;
	system("pause");
	return 0;
}

双向队列的基本操作: 双向队列相比于单项来说,它的前面后面都可以插入和取出数据,但同样遵循FIFO原则.

#include <iostream>
#include <deque>

using namespace std;

int main(int argc, char* argv[])
{
	deque<int> deq{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

	deq.push_back(11);  // 向队尾放入元素
	deq.push_front(12); // 向队头放入元素

	deq.pop_back();     // 从队尾弹出一个元素
	deq.pop_front();    // 从队头弹出一个元素

	cout << "是否为空: " << deq.empty() << endl;
	cout << "首个元素: " << deq.front() << endl;
	cout << "末尾元素: " << deq.back() << endl;
	cout << "元素个数: " << deq.size() << endl;
	cout << "最大元素数: " << deq.max_size() << endl;

	system("pause");
	return 0;
}

双向队列正/反向遍历: 通过使用下标法和迭代器都可以实现对队列的数据遍历,这里先演示正向遍历,然后反向遍历.

#include <iostream>
#include <deque>

using namespace std;

int main(int argc, char* argv[])
{
	deque<int> deq{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

	// 双向队列的正向遍历: 此处有两种遍历方法
	for (int x = 0; x < deq.size(); x++)    // 第一种,通过下标遍历数据
		cout << deq[x] << " " ;
	cout << endl;

	deque<int>::iterator start, end;        // 第二种,通过迭代器遍历数据
	end = deq.end();
	for (start = deq.begin(); start != end; start++)
		cout << (*start) << " " ;
	cout << endl;

	// 双向队列的反向遍历: 此处我们使用迭代器遍历
	deque<int>::reverse_iterator rstart, rend;
	rend = deq.rend();
	for (rstart = deq.rbegin(); rstart != rend; rstart++)
	{
		cout << (*rstart) << " " ;
	}

	system("pause");
	return 0;
}

双向队列插入/弹出元素: 通过使用insert()向队列中插入元素,使用erase()可以弹出指定位置的元素.

#include <iostream>
#include <deque>

using namespace std;

int main(int argc, char* argv[])
{
	deque<int> deq{ 1, 2, 3, 4, 5 };

	deq.push_back(6);               // 从队列末尾追加元素
	deq.push_front(0);              // 从队列首部追加元素
	deq.insert(deq.begin() + 1, 9); // 在第二个元素前插入9

	deq.pop_front();                // 从队列首部弹出元素
	deq.pop_back();                 // 从队列尾部弹出元素
	deq.erase(deq.begin() + 1);     // 弹出第二个(下标索引)元素


	for (int x = 0; x < deq.size(); x++)
		cout << deq[x] << " ";
	cout << endl;

	system("pause");
	return 0;
}

函数参数传递双向队列: 将我们定义的deque<int> deq的指针传递给PrintDeque这个函数进行迭代遍历.

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

// 定义只读deque双端队列
void PrintDeque(const deque<int> &deq)
{
	for (deque<int>::const_iterator item = deq.begin(); item != deq.end(); item++)
	{
		// 迭代器类型: iterator=>普通迭代器 reverse_iterator=>逆序迭代器 const_iterator=>只读迭代器
		cout << (*item) << endl;
	}
}

int main(int argc, char* argv[])
{
	deque<int> deq = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	PrintDeque(deq);
	system("pause");
	return 0;
}

List/Slist 动态链表容器

List双向链表是一种序列容器,它的数据元素可以通过链表指针串接成逻辑意义上的线性表,不同于采用线性表顺序存储结构的Vector和Deque容器,双向链表中任一位置的元素,查找,插入和删除,都具有高效的常数阶算法时间复杂度O(1).

List的缺点是无法通过位置来直接访问序列中的元素,也就是说,不能动态跨段索引元素.为了访问 list 内部的一个元素,必须一个一个地遍历元素,通常从第一个元素或最后一个元素开始遍历.

双向链表遍历整数: 首先动态生成一个链表,里面存储1-10之间的数,然后通过链表指针开始遍历这个数值链表.

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

int main(int argc, char* argv[])
{
	list<int> MyList;
	// 生成10个测试数据,并链入链表中.
	for (int x = 0; x < 10; x++)
		MyList.push_back(x);

	// 将node节点初始化为第一个节点的下一个节点,第一个节点是链表头,无数据.
	list<int>::_Nodeptr node = MyList._Myhead->_Next;

	for (int x = 0; x < MyList._Mysize; x++)
	{
		cout << "Node: " << node->_Myval << endl;
		node = node->_Next;         // 每次输出,将node指向下一个链表
		if (node == MyList._Myhead) // 如果到头了,直接指向头结点的第二个节点
		{
			node = node->_Next;     // 由于是双向链表,所以到头了会回到起始位置
		}                               // 此时我们执行 node->_Next 继续指向开头
	}
	system("pause");
	return 0;
}

双向链表遍历结构体: 上方遍历的是一个整数链表,接下来实现的是遍历Student这个结构体中的所有数据.

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

struct Student{
	char * name;
	int age;
	char * city;
};

bool MyCompare(Student &s1, Student &s2)
{   // 实现从大到小排序
	if (s1.age > s2.age)
		return true;
	return false;
}

int main(int argc, char* argv[])
{
	Student stu[] = {
		{ "admin", 22, "beijing" },
		{ "lisi", 32, "shanghai" },
		{ "wangwu", 26, "shandong" },
		{"wangermazi",8,"jinan"}
	};

	list<Student> MyList;
	MyList.push_back(stu[0]);  // 装入链表数据
	MyList.push_back(stu[1]);
	MyList.push_back(stu[2]);
	MyList.push_back(stu[3]);

	// 根据Student结构中的age从大到小排序
	MyList.sort(MyCompare);

	// 遍历链表
	list<Student>::iterator start, end;
	for (start = MyList.begin(); start != MyList.end(); start++)
	{
		cout << (*start).name << " ";
		cout << (*start).age << " ";
		cout << (*start).city << endl;
	}
	system("pause");
	return 0;
}

实现正反向遍历链表: 链表容器不支持随机访问只能遍历,使用begin()/end()正向遍历,使用rbegin()/rend()反向遍历.

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

int main(int argc, char* argv[])
{
	list<int> MyList{ 1, 2, 3, 4, 5, 6, 7, 8, 9 };

	// 正向打印链表元素
	for (list<int>::iterator item = MyList.begin(); item != MyList.end(); item++)
		cout << *item << endl;
	// 反向打印链表元素
	for (list<int>::reverse_iterator item = MyList.rbegin(); item != MyList.rend(); item++)
		cout << *item << endl;
	system("pause");
	return 0;
}

遍历链表中指定元素: 通过使用结构体存储人物数据,然后使用迭代器查找id=3的人物结构,找到后输出它的Name属性.

#include <iostream>
#include <list>
#include <string>
using namespace std;

struct Student{
	int id;
	string name;
};

int main(int argc, char* argv[])
{
	list<Student> MyList;
	// 定义列表中的元素集合
	Student stu[] = {
		{ 1,"aaddm"},
		{ 2,"admin"},
		{ 3,"waann" },
		{ 4,"ruiii" }
	};

	for (int x = 0; x < 4; x++)
	{ // 循环插入测试结构 stu[0] - stu[4]
		MyList.push_back(stu[x]);
	}

	// 遍历链表中ID=3的元素
	list<Student>::iterator start, end;
	for (start = MyList.begin(); start != MyList.end(); start++)
	{
		if ((*start).id == 3) // 寻找ID是3的结构体,找到后输出其name属性
		{
			cout << "UName: " << (*start).name << endl;
		}
	}
	system("pause");
	return 0;
}

实现插入/删除链表元素: 定义list<int>链表,通过insert()向链表中插入元素,通过remove()移除指定的元素.

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

void MyPrint(list<int> &MyList)
{
	list<int>::iterator start, end;
	for (start = MyList.begin(); start != MyList.end(); start++)
		cout << *start << " ";
	cout << endl;
}

int main(int argc, char* argv[])
{
	list<int> MyList{ 1, 2, 3, 4, 5, 6, 7, 8, 9 };

	MyList.push_back(10);  // 尾部插入数据
	MyList.push_front(0);  // 头部插入数据

	MyList.pop_front();    // 头删数据
	MyList.pop_back();     // 尾删除数据

	MyList.insert(MyList.begin(), 500); // 从开头插入500
	MyList.insert(MyList.end(), 1000);  // 从结尾插入1000

	MyList.remove(7);    // 移除7这个元素
	MyPrint(MyList);
	system("pause");
	return 0;
}

实现整数链表正反向排序: 定义list<int>链表,并通过sort()实现正反向排序,通过reverse()实现链表翻转.

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

void MyPrint(list<int> &MyList)
{
	list<int>::iterator start, end;
	for (start = MyList.begin(); start != MyList.end(); start++)
		cout << *start << " ";
	cout << endl;
}

// 实现的从大到小排序的回调函数
bool MyCompare(int value1, int value2) { return value1 > value2; }

int main(int argc, char* argv[])
{
	list<int> MyList{ 12,56,33,78,9,43,2,1,7,89 };

	MyList.reverse();        // 对链表进行翻转
	MyPrint(MyList);

	MyList.sort();           // 从小到大排序
	MyPrint(MyList);

	MyList.sort(MyCompare);  // 从大到小排序
	MyPrint(MyList);

	system("pause");
	return 0;
}

实现类链表正反向排序: 定义Person类存储数据,使用sort()函数设置自定义回调函数MyCompare()实现对类中数据排序.

#include <iostream>
#include <list>
#include <string>
using namespace std;

class Person
{
public:
	string m_name;
	int m_age;
	int m_height;

public: Person(string name, int age, int height){
		this->m_name = name;
		this->m_age = age;
		this->m_height = height;
	}
};
// 排序规则为: 如果年龄相同,则按照身高由低到高排列
bool MyCompare(Person &x,Person &y)
{
	if (x.m_age == y.m_age)
		return x.m_height < y.m_height; // 身高升序排列
	else
		return x.m_age > y.m_age;       // 年龄降序排列
}

int main(int argc, char* argv[])
{
	list<Person> MyList;

	Person p1("a", 20, 169);  // 定义元素数据
	Person p2("b", 14, 155);
	Person p3("c", 14, 165);

	MyList.push_back(p1);     // 加到链表里
	MyList.push_back(p2);
	MyList.push_back(p3);

	MyList.sort(MyCompare);  // 排序代码

	// 排序后进行打印
	for (list<Person>::iterator it = MyList.begin(); it != MyList.end(); it++)
		cout << "Name: " << it->m_name << " Age: " << it->m_age << " Height: " << it->m_height << endl;
	system("pause");
	return 0;
}

实现类链表成员的删除: 自定义Person结构来存储人物的信息,然后重载等于号,实现让remove可以删除Person中的数据.

#include <iostream>
#include <list>
#include <string>
using namespace std;

class Person
{
public:
	string m_name;
	int m_age;
	int m_height;

public: Person(string name, int age, int height){
		this->m_name = name;
		this->m_age = age;
		this->m_height = height;
}
// 重载等于号 == 让 remove() 函数,可以删除自定义的Person类型的结构
public: bool operator==(const Person &p) {
		if (this->m_name == p.m_name && this->m_age == p.m_age && this->m_height == p.m_height)
			return true;
		return false;
	}
};

int main(int argc, char* argv[])
{
	list<Person> MyList;

	Person p1("a", 20, 169);
	Person p2("b", 14, 155);
	Person p3("c", 34, 165); // 初始化并给Person赋值

	MyList.push_back(p1);    // 将参数放入链表中
	MyList.push_back(p2);
	MyList.push_back(p3);

	MyList.remove(p3);   // 删除这个类中的p3成员

	// 删除p3数据后,通过使用迭代器遍历这个链表,查看情况.
	for (list<Person>::iterator it = MyList.begin(); it != MyList.end(); it++)
		cout << "Name: " << it->m_name << " Age: " << it->m_age << " Height: " << it->m_height << endl;
	system("pause");
	return 0;
}

Set/Multiset 集合容器

Set集合使用的是红黑树的平衡二叉检索树的数据结构,来组织泛化的元素数据,通常来说红黑树根节点每次只能衍生出两个子节点,左面的节点是小于根节点的数据集合,右面的节点是大于根节点的集合,通过这样的方式将数据组织成一颗看似像树一样的结构,而平衡一词的含义则是两边的子节点数量必须在小于等1的区间以内.

需要注意的是,Set集合天生去重,所有元素都会根据元素的键值自动的排序,并且Set元素在确定后无法进行更改,换句话说Set的Iterator是一种Const_iterator,而Multiset则允许出现重复的数据,如需使用只需要将set<int>改为multiset<int>即可,Multiset操作方式与API函数与Set集合保持相同.

正反向遍历集合元素: 通过迭代器实现对集合容器的正反向遍历,注意Set集合只能使用insert方法向集合插值.

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

void PrintSet(set<int>& s ,int flag)
{
	if (flag == 1)
	{ // 正向遍历元素
		for (set<int>::iterator it = s.begin(); it != s.end(); it++)
			cout << (*it) << " ";
	}
	else if (flag == 0)
	{ // 反向遍历元素
		for (set<int>::reverse_iterator it = s.rbegin(); it != s.rend(); it++)
			cout << (*it) << " ";
	}
}

int main(int argc, char* argv[])
{
	set<int> var { };

	var.insert(56);
	var.insert(67);  // 插入元素
	var.insert(99);
	PrintSet(var,0); // 打印并从大到小排列

	if (var.empty()) // 判断是否为空
		cout << "None" << endl;
	else
		cout << "size: " << var.size() << endl;

	var.erase(var.begin());   // 删除第一个元素
	var.erase(99);            // 删除99这个元素
	PrintSet(var, 0);         // 打印并从大到小排列
	system("pause");
	return 0;
}

查找集合中指定元素: 通过find可实现查找集合指定元素,lower/upper/equal bound则实现对元素区间的遍历.

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

int main(int argc, char* argv[])
{
	set<int> var { 23,44,56,78,90,0,90,12,54,67,85,3,4,7};

	// 寻找set集合中数值是90的
	set<int>::iterator pos = var.find(90);
	if (pos != var.end())  // 寻找90是否存在
		cout << "找到了: " << *pos << endl;
	
	// count(key) 查找90存在几个,对于set而言返回结果是 1或者0
	int number = var.count(90);
	cout << "90是否存在: " << number << endl;

	// lower_bound(keyElem); 返回第一个 key>=keyElem 元素的迭代器
	set<int>::iterator it = var.lower_bound(4); // 寻找4是否存在
	if (it != var.end())
		cout << "找到了 lower_bound(4) 的值:" << *it << endl;

	// upper_bound(keyElem); 返回第一个 key>keyElem 元素的迭代器
	set<int>::iterator it2 = var.upper_bound(4); // 寻找4相邻值
	if (it2 != var.end())
		cout << "找到了 upper_bound(4) 的值:" << *it2 << endl;

	// equal_range(keyElem) 返回容器中key与keyElem相等的上下限的两个迭代器.
	// 下限就是 lower_bound 上限就是 upper_bound 需要分别迭代输出
	pair<set<int>::iterator, set<int>::iterator> ret = var.equal_range(4);
	if (ret.first != var.end())
		cout << "找到 lower_bound(4): " << *(ret.first) << endl;
	if (ret.second != var.end())
		cout << "找到 upper_bound(4): " << *(ret.second) << endl;

	system("pause");
	return 0;
}

设置默认集合排序方式: 集合默认情况下会从小到大的将数据排列整齐,我们可以自定义仿函数让其从大到小排序.

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

class MyCompare
{ // 通过仿函数,重载小括号,实现默认从大到小排列
public: bool operator()(int v1, int v2) {
		return v1 > v2;    // 从大到小
		// return v1 < v2; 从小到大
	}
};

int main(int argc, char* argv[])
{
	set<int, MyCompare> var;

	var.insert(6);
	var.insert(3);
	var.insert(9);

	for (set<int, MyCompare>::iterator it = var.begin(); it != var.end(); it++)
		cout << *it << endl;

	system("pause");
	return 0;
}

向集合插入自定义类型: 此处使用类做数据存储,插入自定义数据类型时,必须在一开始就指定好排序规则,否则会报错.

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

class Person {
public:
	string m_name;
	int m_age;

public: Person(string name, int age) {
	this->m_name = name;
	this->m_age = age;
	}
};

class MyCompare{
	// 通过仿函数,重载,实现默认降序排列
public: bool operator()(const Person & p1, const Person & p2){
		if (p1.m_age > p2.m_age) // 指定为降序排列
			return true;
		return false;
	}
};

int main(int argc, char* argv[])
{
	set<Person,MyCompare> var;

	Person p1("dawa", 22);   // 初始化
	Person p2("xiwa", 44);
	var.insert(p1);          // 插入自定义数据类型
	var.insert(p2);

	// 显示出自定义类型
	for (set<Person, MyCompare>::iterator it = var.begin(); it != var.end();it ++)
	{
		cout << "Name: " << (*it).m_name << "Age: " << (*it).m_age << endl;
	}
	system("pause");
	return 0;
}

Map/Multimap 序列容器

Map映射容器属于关联容器,它的每个键对应着每个值,容器的数据结构同样采用红黑树进行管理,插入的键不允许重复,但值是可以重复的,如果使用Multimap声明映射容器,则同样可以插入相同的键值.

Map中的所有元素都会根据元素的键值自动排序,所有的元素都是一个Pair同时拥有实值和键值,Pair的第一个元素被视为键值,第二个元素则被视为实值,Map 容器中不允许两个元素有相同的键出现.

通过对组实现键值对: 对组pair<>是一个键值对的组合,类似于一个字典,每个对组中,包含1个key和1个value.

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

int main(int argc, char* argv[])
{   // 创建的对组字符串
	pair<string, int> p(string("lyshark"), 100);
	pair<string, int> p2 = make_pair("jerry", 200);
	cout << "Name: " << p.first << endl;
	cout << "Age: " << p.second << endl;

	// 检测集合元素是存在重复的,如果出现重复的则报错
	set<int> var;
	var.insert(10);  // 由于插入过10这个元素,所以在此插入则会报错
	pair<set<int>::iterator, bool> ret = var.insert(10);
	if (!ret.second)
		cout << "insert error" << endl;

	system("pause");
	return 0;
}

正反向遍历映射容器: 通过使用begin/rbegin,end/rend等迭代器,实现对MAP映射容器元素的正反向遍历.

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main(int argc, char* argv[])
{
	map<string, int> mp;
	// 三种方式实现map容器插入操作
	mp.insert(pair<string, int>("admin0", 100));
	mp.insert(make_pair("admin1", 200));
	mp["admin2"] = 300;

	mp.erase("admin2");    // 删除第3个数据

	// 正向遍历键值对
	for (map<string, int>::iterator it = mp.begin(); it != mp.end(); it++)
		cout << "key = " << it->first << " --> value = " << it->second << endl;

	cout << endl;
	// 反向遍历键值对
	for (map<string, int>::reverse_iterator it = mp.rbegin(); it != mp.rend();it ++)
		cout << "key = " << it->first << " --> value = " << it->second << endl;
	system("pause");
	return 0;
}

查找映射容器中的元素: 首先创建一个映射容器,然后通过迭代器mp.find("admin0");遍历查找特定的映射元素.

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main(int argc, char* argv[])
{
	map<string, int> mp;

	mp["admin0"] = 100;
	mp["admin1"] = 200;
	mp["admin2"] = 300;
	
	// 寻找admin0是否存在于键值对中
	map<string, int>::iterator pos = mp.find("admin0");
	if (pos != mp.end())
		cout << "key = " << pos->first << " --> value = " << pos->second << endl;

	// lower_bound(keyElem) 返回第一个key=keyElem元素的迭代器
	map<string, int>::iterator ret = mp.lower_bound("admin0");
	if (ret != mp.end())
		cout << "lower_bound key = " << ret->first << " --> lower_bound value = " << ret->second << endl;
	
	// upper_bound(keyElem) 返回第一个key>keyElem元素的迭代器
	map<string, int>::iterator ret1 = mp.upper_bound("admin0");
	cout << "upper_bound key = " << ret1->first << " --> upper_bound value = " << ret1->second << endl;
	system("pause");
	return 0;
}

遍历映射容器中的结构: 上方代码是查找一个映射元素,本案例将查找一个映射结构,找到后打印出该结构的详细数据.

#include <iostream>
#include <map>
#include <string>
using namespace std;

struct StudentInfo{
	char *name;
	int year;
	char *addr;
};

struct StudentRecord{
	int id;
	StudentInfo stu;
};

int main(int argc, char* argv[])
{
	StudentRecord szArray[] = {
		{ 1, "admin0", 22, "beijing" },
		{ 2, "admin1", 33, "shanghai" },
		{ 3, "admin2", 24, "jinan" },
	};
	// 创建Map映射
	map<int, StudentInfo> mp;

	// 初始化,将学生数组装入映射
	for (int x = 0; x < 3; x++)
	{
		mp[szArray[x].id] = szArray[x].stu;
	}
	// 迭代遍历Map中所有的数据
	map<int, StudentInfo>::iterator start, end;
	end = mp.end();
	for (start = mp.begin(); start != end; start++)
		cout << "ID: " << (*start).first << " --> Name: " << (*start).second.name << endl;

	// 迭代寻找mp.find(1) 元素,并打印出其内部成员
	map<int, StudentInfo>::iterator i = mp.find(1);
	cout << "First: " << (*i).first << endl;
	cout << "Name: " << (*i).second.name << endl;
	system("pause");
	return 0;
}

通过映射容器实现分组: 定义三个不同的部门,然后通过映射容器对其进行分组,并实现遍历并打印出每个分组.

#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;

enum {RENLI,YANFA,MEISHU};  // 定义三个部门 RENLI=0
class Worker
{
public:
	string m_name;
	int m_money;
};
// 随机生成5个员工成员
void CreateWorker(vector<Worker> &v)
{
	string nameSeed = "ABCDE";
	Worker w;
	for (int x = 0; x < 5; x++)
	{
		string name;
		name += nameSeed[x];
		int money = rand() % 10000+10000;
		w.m_name = name;
		w.m_money = money;
		v.push_back(w);
	}
}
// 打印出指定的部门信息,查其他分组只需修改RENLI为其他即可
void ShowGroup(multimap<int, Worker> &m)
{
	cout << "Group:" << endl;
	multimap<int,Worker>::iterator pos = m.find(RENLI);
	int index = 0;            // 计数器每次递增,直到等于num
	int num = m.count(RENLI); // 人力部门有多少调数据
	for (; pos != m.end(), index < num; pos++, index++)
	{
		cout << "Name: " << pos->second.m_name << endl;
	}
}
// 实现员工分组
void SetGroup(vector<Worker> &v,multimap<int,Worker> & m)
{
	for (vector<Worker>::iterator it = v.begin(); it != v.end(); it++)
	{
		// 随机的产生一个部门编号
		int departmentId = rand() % 3;
		// 将员工分到multimap容器中, 1=mp
		m.insert(make_pair(departmentId, *(it)));
	}
}
int main(int argc, char* argv[])
{
	vector<Worker> v;
	CreateWorker(v);
	// 实现员工分组,分组的multimap容器
	multimap<int, Worker> mp;
	SetGroup(v,mp);   	// 实现员工分组
	ShowGroup(mp);      // 显示分组信息

	system("pause");
	return 0;
}