11、C++进阶编程STL

• 一、STL简介
• 二、容器
• • 1 - 容器分类
  • 2 - 序列容器
  • 3 - 关联容器
• 三、仿函数（functor）
• 四、算法（algorithm）
• 五、迭代器
• 六、容器适配器（adapter）
• 七、空间配置器（allocator）
• 扩展1：关于Boost库
• 扩展2、C++多线程
• • 1 - 多线程基本使用
  • 2 - 案例：多线程存取款
  • 3 - 线程交换
  • 4 - 线程移动

• STL概念
  • STL算法是泛型的（generic），不与任何特定数据结构和对象绑定，不必在环境类似的情况下重写代码
  • STL算法可以量身定做，并且具有很高的效率
  • STL可以进行扩充，可以编写自己的组件并且能与STL标准的组件进行很好的配合
• STL六大组件
  
• STL六大组件关系
  

• 容器用于存放数据，STL容器分为两大类
  • 序列式容器（Sequence Containers）：其中的元素都是可排序的（ordered），STL提供了vector、list、deque等序列式容器，而stack、queue、priority_queue则是容器适配器
  • 关联式容器（Associative Containers）：每个数据元素都是由一个键（key）和值（value）组成，当元素被插入到容器时，按其键以某种特定规则放入适当位置；常见的STL关联容器如：set、multiset、map、multimap

#include 
#include 
#include 
#include 
#include 
using namespace std;

//仿函数
struct Display
{
	void operator()(int i)
	{
		cout << i << " ";
	}
};

int main()
{
	int iArr[] = { 1, 2,3,4,5 };

	vector iVector(iArr, iArr + 4);
	list iList(iArr, iArr + 4);
	deque iDeque(iArr, iArr + 4);

	for_each(iVector.begin(), iVector.end(), Display());
	cout << endl;
	for_each(iList.begin(), iList.end(), Display());
	cout << endl;
	for_each(iDeque.begin(), iDeque.end(), Display());
	cout << endl;

	queue iQueue(iDeque);     // 队列 先进先出
	stack iStack(iDeque);         // 栈 先进后出
	priority_queue iPQueue(iArr, iArr + 4);  // 优先队列，按优先权

	while (!iQueue.empty())
	{
		cout << iQueue.front() << " ";  // 1 2 3 4
		iQueue.pop();
	}
	cout << endl;

	while (!iStack.empty())
	{
		cout << iStack.top() << " ";    // 4 3 2 1
		iStack.pop();
	}
	cout << endl;

	while (!iPQueue.empty())
	{
		cout << iPQueue.top() << " "; // 4 3 2 1
		iPQueue.pop();
	}
	cout << endl;

	return 0;
}

• map的基本使用

#include 
#include 
#include

• 仿函数作用：仿函数一般不会单独使用，主要是为了搭配STL算法使用
• 为什么不使用函数指针：函数指针不能满足STL对抽象性的要求，不能满足软件积木的要求，无法和STL其他组件搭配
• 仿函数本质：本质就是类重载了一operator()，创建一个行为类似函数的对象
• 1、仿函数实现：C++方式

#include 
#include 
using namespace std;

bool MySort(int a, int b)
{
	return a < b;
}
void Display(int a)
{
	cout << a << " ";
}

int main()
{
	// C++方式
	int arr[] = { 4, 3, 2, 1, 7 };
	sort(arr, arr + 5, MySort);
	for_each(arr, arr + 5, Display);
	cout << endl;

	return 0;
}

• 2、仿函数实现：C++泛型

#include 
#include 
using namespace std;

template
inline bool MySortT(T const& a, T const& b)
{
	return a < b;
}

template
inline void DisplayT(T const& a)
{
	cout << a << " ";
}

int main()
{
	// C++泛型
	int arr2[] = { 4, 3, 2, 1, 7 };
	sort(arr2, arr2 + 5, MySortT);
	for_each(arr2, arr2 + 5, DisplayT);
	cout << endl;

	return 0;
}

• 3、仿函数实现：C++仿函数

#include 
#include 
using namespace std;

struct SortF
{
	bool operator() (int a, int b)
	{
		return a < b;
	}
};
struct DisplayF
{
	void operator() (int a)
	{
		cout << a << " ";
	}
};

int main()
{
	// C++仿函数
	int arr3[] = { 4, 3, 2, 1, 7 };
	sort(arr3, arr3 + 5, SortF());
	for_each(arr3, arr3 + 5, DisplayF());
	cout << endl;

	return 0;
}

• 4、仿函数实现：C++仿函数模板

#include 
#include 
using namespace std;

// C++仿函数模板
template
struct SortTF
{
	inline bool operator() (T const& a, T const& b) const
	{
		return a < b;
	}
};
template
struct DisplayTF
{
	inline void operator() (T const& a) const
	{
		cout << a << " ";
	}
};

int main()
{
	// C++仿函数模板
	int arr4[] = { 4, 3, 2, 1, 7 };
	sort(arr4, arr4 + 5, SortTF());
	for_each(arr4, arr4 + 5, DisplayTF());
	cout << endl;

	return 0;
}

• STL种算法头文件：包含于、、
• STL种算法分类大致分为四类
  • ①.非可变序列算法：指不直接修改其所操作的容器内容的算法
  • ②.可变序列算法：指可以修改他们所操作的容器内容的算法
  • ③.排序算法：包括对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作
  • ④.数值算法：对容器内容进行数值计算
• 最常见的算法包括：查找、排序和通用算法、排列组合算法、数值算法、集合算法等算法
• transform与lambda表达式

#include 
#include 
using namespace std;

int main()
{
	// transform和lambda表达式
	int ones[] = { 1, 2, 3, 4, 5 };
	int twos[] = { 10, 20, 30, 40, 50 };
	int results[5];
	transform(ones, ones + 5, twos, results, std::plus()); // 数组元素依次相加并返回
	for_each(results, results + 5,
		[](int a)->void {
			cout << a << endl;
		}); // lambda表达式（匿名函数）
	cout << endl;

	return 0;
}

• 统计与二分查找

#include 
#include 
#include 
#include 

using namespace std;

int main()
{
	// find
	int arr[] = { 0, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 7, 7, 8 };
	int len = sizeof(arr) / sizeof(arr[0]);

	cout << count(arr, arr + len, 6) << endl; // 统计6的个数

	// bind1st(const _Fn& _Func, const _Ty& _Left)  -> 可以理解为参数在left
	// bind2nd(const _Fn& _Func, const _Ty& _Right) -> 可以理解为参数在right
	cout << count_if(arr, arr + len, bind1st(less(), 7)) << endl; // 统计>7的个数
	cout << count_if(arr, arr + len, bind2nd(less(), 7)) << endl; // 统计<7的个数

	// 二分查找，前置要求必须是有序的序列，否则要先排序，arr是已经排序好了的
	cout << binary_search(arr, arr + len, 9) << endl;   // 返回0=找不到


	vector iA(arr + 2, arr + 6);   // {2,3,3,4}
	//vector iA;
	//iA.push_back(1);
	//iA.push_back(9); // {1, 9}

	// 注意search返回的是地址值
	cout << *search(arr, arr + len, iA.begin(), iA.end()) << endl; // 查找子序列

	cout << endl;

	return 0;
}

• 案例：全排列：输入一个不存在重复字符的字符串，打印出字符串中字符的全排列
  • 比如输入: “123”，输出“123 213 231 321 312”
  • 思路：f(123) = 1+f(23), f(23) = 2+f(3), f(3) = 3 递归

#include 
#include 

using namespace std;

// 输入一个不存在重复字符的字符串，打印出字符串中字符的全排列。
//比如：
//输入: "123"   3*2*1 = 3!
//输出:  123
//          132
//          213
//          231
//          321
//          312
//f(123) = 1+f(23), f(23) = 2+f(3), f(3)  = 3  递归
void swap(char* a, char* b)
{
	char temp = *a;
	*a = *b;
	*b = temp;
}
void Permutation(char* pStr, char* pPostion)
{
	// 基准点
	if (*pPostion == '')
	{
		cout << pStr << endl;
	}
	else
	{
		for (char* pChar = pPostion; *pChar != ''; pChar++)
		{
			// 依次和后面的字符交换
			swap(*pChar, *pPostion);
			Permutation(pStr, pPostion + 1);

			// 换回来
			swap(*pChar, *pPostion);
		}
	}
}


int main()
{
	//C++原始的方法实现
	char test[] = "123";
	Permutation(test, test);
	cout << endl;

	// 用STL输出全排列
	// 注意：必须要保证数组顺序是从小到大
	do
	{
		cout << test[0] << test[1] << test[2] << endl;
	} while (next_permutation(test, test + 3));
	cout << endl;

	char test2[] = "321";
	// 注意：必须要保证数组顺序是从大到小
	do
	{
		cout << test2[0] << test2[1] << test2[2] << endl;
	} while (prev_permutation(test2, test2 + 3));

	return 0;
}

• 迭代器概念：迭代器是一种smart pointer，用于访问顺序容器和关联容器中的元素，相当于容器和操纵容器的算法之间的中介
• 迭代器按照定义方式分成以下四种：“const”是因为我们很多时候在遍历的时候不需要修改迭代器的值
  • ①.正向迭代器：iterator
  • ②.常量正向迭代器：const_iterator
  • ③.反向迭代器：reverse_iterator
  • ④.常量反向迭代器：const_reverse_iterator
• 迭代器功能

• stack堆栈：一种“先进后出”的容器，底层数据结构是使用deque
• queue队列：一种“先进先出”的容器，底层数据结构是使用deque
• prioruty_queue优先队列：一种特殊的队列，它能够在队列中进行排序(堆排序)，底层实现结构是vector或者deque

#include 
#include 

using namespace std;

int main()
{
	priority_queue pq;  // 默认是最大值优先
	priority_queue, less > pq2; //   最大值优先
	priority_queue, greater > pq3; // 最小值优先

	pq.push(2);
	pq.push(1);
	pq.push(3);
	pq.push(0);
	while (!pq.empty())
	{
		int top = pq.top();
		cout << " top is: " << top << endl;
		pq.pop();
	}
	cout << endl;

	pq2.push(2);
	pq2.push(1);
	pq2.push(3);
	pq2.push(0);
	while (!pq2.empty())
	{
		int top = pq2.top();
		cout << " top is: " << top << endl;
		pq2.pop();
	}
	cout << endl;

	pq3.push(2);
	pq3.push(1);
	pq3.push(3);
	pq3.push(0);
	while (!pq3.empty())
	{
		int top = pq3.top();
		cout << " top is: " << top << endl;
		pq3.pop();
	}
	cout << endl;

	return 0;
}

• 概念：从使用的角度来看，allocator隐藏在其他组件中默默工作，不需要关心，但是从理解STL实现角度来看，它是需要首先分析的组件；allocator的分析可以体现C++在性能和资源管理上的优化思想
• 自定义空间配置器：一般来说我们不需要自定义空间配置器，但是对性能要求更高，觉得底层实现的空间配置性能不够的时候可以选择自定义空间配置器
• 引用：候捷版本的空间配置器源码：这个目前还是不完善的，仅仅参考实现思路的大体流程

#pragma once
#ifndef _JJALLOC
#define _JJALLOC
#include //for placement new
#include //for ptrdiff_t ,size_t
#include //for exit()
#include //for UINX_MAX
#include //for cerr

namespace  JJ
{
	template
	inline T* _allocate(ptrdiff_t size, T*)
	{
		set_new_handler(0);
		T* tmp = (T*)(::operator new((size_t)(size * sizeof(T))));
		if (tmp == 0)
		{
			cerr << "out of memory" << endl;
			exit(1);
		}
		return tmp;
	}
	template
	inline void _deallocate(T* buffer)
	{
		::operator delete(buffer);
	}

	template
	inline void _construct(T1* p, const T2& value)
	{
		new(p) T1(value);//placement new,invoke constuctor of T1
	}

	template
	inline void _destroy(T* ptr)
	{
		ptr->~T();
	}

	template
	class allocator {
	public:
		typedef T value_type;
		typedef T* pointer;
		typedef const T* const_pointer;
		typedef T& reference;
		typedef const T& const_reference;
		typedef size_t size_type;
		typedef ptrdiff_t difference_type;

		//rebind allocator of type U
		template
		struct rebind {
			typedef allocator other;
		};
		//需要加上以下2个函数，windows的编译器用到了allocator不同类型的拷贝， 
		allocator()
		{
			return;
		}

		template 
		allocator(const allocator& c)
		{
		}

		//hint user for locality,第2个参数是个提示，实现上可能会利用它来增进区域性（locality），或完全忽略之
		pointer allocate(size_type n, const void* hint = 0)
		{
			return _allocate((difference_type)n, (pointer)0);
		}

		void deallocate(pointer p, size_type n)
		{
			_deallocate(p);
		}

		void construct(pointer p, const T& value)
		{
			_construct(p, value);
		}
		void destroy(pointer p)
		{
			_destroy(p);
		}
		pointer address(reference x) { return (pointer)&x; }
		const_pointer const_address(const_reference x) { return (const_pointer)&x; }

		size_type max_size() const {
			return size_type(UINT_MAX / sizeof(T));
		}
	};
}//#end of namespace JJ
#endif

#include 
#include "jjalloc.h"
#include 

using namespace std;

int main()
{
	int ia[5] = { 0, 1, 2, 3, 4 };
	unsigned int i;
	vector > iv(ia, ia + 5);
	for (i = 0; i < iv.size(); i++)
	{
		cout << iv[i] << " ";
	}
	cout << endl;


	return 0;
}

#include 
#include 
using namespace std;

void T1()
{
	cout << "T1 Hello" << endl;
}

void T2(const char* str)
{
	cout << "T2 " << str << endl;
}

int main()
{
	thread t1(T1);
	t1.join(); // 主线程等待t1线程执行完毕再继续执行

	thread t2(T2, "Hello World");
	t2.join();

	cout << "Main Hi" << endl;

	return 0;
}

#include 
#include 
#include 
using namespace std;

mutex g_mutex;
void T1()
{
	g_mutex.lock();
	cout << "T1 Hello" << endl;
	g_mutex.unlock();
}
void T2(const char* str)
{
	g_mutex.lock();
	cout << "T2 " << str << endl;
	g_mutex.unlock();
}

int main()
{
	thread t1(T1);
	t1.join(); // 主线程等待t1线程执行完毕再继续执行

	thread t2(T2, "Hello World");
	t2.join();

	cout << "Main Hi" << endl;

	return 0;
}

#include 
#include 
#include 
using namespace std;

// 存钱
void Deposit(mutex& m, int& money)
{
	// 锁的粒度尽可能的最小化
	for (int index = 0; index < 100; index++)
	{
		m.lock();
		money += 1;
		m.unlock();
	}
}
// 取钱
void Withdraw(mutex& m, int& money)
{
	// 锁的粒度尽可能的最小化
	for (int index = 0; index < 100; index++)
	{
		m.lock();
		money -= 2;
		m.unlock();
	}
}

int main()
{
	// 银行存取款
	int money = 2000;
	mutex m;
	cout << "Current money is: " << money << endl;
	thread t1(Deposit, ref(m), ref(money));
	thread t2(Withdraw, ref(m), ref(money));
	t1.join();
	t2.join();
	cout << "Finally money is: " << money << endl;

	return 0;
}

#include 
#include 
using namespace std;

int main()
{
	//线程交换 
	thread tW1([]()
		{
			cout << "ThreadSwap1 " << endl;
		});
	thread tW2([]()
		{
			cout << "ThreadSwap2 " << endl;
		});
	cout << "ThreadSwap1' id is " << tW1.get_id() << endl;
	cout << "ThreadSwap2' id is " << tW2.get_id() << endl;

	cout << "Swap after:" << endl;
	swap(tW1, tW2);
	cout << "ThreadSwap1' id is " << tW1.get_id() << endl;
	cout << "ThreadSwap2' id is " << tW2.get_id() << endl;
	tW1.join();
	tW2.join();

	return 0;
}

#include 
#include 
using namespace std;

int main()
{
	 线程移动
	thread tM1([]() {; });
	//tM1.join();
	cout << "ThreadMove1' id is " << tM1.get_id() << endl;
	cout << "Move after:" << endl;
	thread tM2 = move(tM1);
	cout << "ThreadMove2' id is " << tM2.get_id() << endl;
	cout << "ThreadMove1' id is " << tM1.get_id() << endl;
	tM2.join();

	return 0;
}