C++标准库笔记一：STL基本组件和STL算法

下面的代码用gcc version 3.4.5 (mingw-vista special r3)测试

来源于sgi STL的官方手册以及《泛型编程与STL》（Generic Programming and the STL）

 

 

// 编译命令行：
// g++ -Wno-deprecated test001.cpp

// 演示STL基本组件
//construct
//destroy
//uninitialized_copy/uninitialized_copy_n
//uninitialized_fill/uninitialized_fill_n
//get_temporary_buffer/return_temporary_buffer

#include <iostream>
#include <string>
#include <memory>
// algo.h的construct和destroy不属于标准，尽量不要使用
// 因为algo.h会导致名字空间std被using
#include <algo.h> 

class Int 
{
public:
	Int(int x):val(x) {}
	int get() { return val; }
private:
	int val;
};

int main(int argc, const char *argv[])
{
	std::cout << "Test STL basic functions" << std::endl;
	
	// 底层函数construct，不需要std::
	// 用于使用malloc构造类对象
	std::string *sptr = (std::string *)malloc(sizeof(std::string));
	construct(sptr, "test");
	assert(strcmp(sptr->c_str(), "test") == 0);
	std::cout << "sptr->c_str() == \"test\"" << std::endl;
	
	// 底层函数destroy，不需要std::
	// 用于调用数组的某指针到某指针之间的所有对象的析构函数
	//（但内存并没有真正释放）
	Int A[] = { Int(1), Int(2), Int(3), Int(4) };
	destroy(A, A + 4);
	construct(A, Int(10));
	construct(A + 1, Int(11));
	construct(A + 2, Int(12));
	construct(A + 3,  Int(13));
	for(int i1 = 0; i1 < 4; i1++)
	{
		std::cout << "A[" << i1 << "] = " << A[i1].get() << std::endl;
	}
	
	// 底层函数uninitialized_copy/uninitialized_copy_n
	// 用于对一个数组批量执行construct
	// 相当于执行N次construct(&*(result + (i - first)), *i) 
	int A1[] = {1, 2, 3, 4, 5, 6, 7};
	const int N = sizeof(A1) / sizeof(int);
	Int* A2 = (Int*) malloc(N * sizeof(Int));
	std::uninitialized_copy(A1, A1 + N, A2);
	//or
	//uninitialized_copy_n(A1, N, A2);
	for(int i2 = 0; i2 < N; i2++)
	{
		std::cout << "A2[" << i2 << "] = " << A2[i2].get() << std::endl;
	}
	
	
	// 底层函数uninitialized_fill/uninitialized_fill_n
	// 用于对一个数组批量执行相同的construct
	// 相当于执行N次construct(&*i, x)
	const int N3 = 7;
	Int val(46);
	Int* A3 = (Int*) malloc(N3 * sizeof(Int));
	std::uninitialized_fill(A3, A3 + N3, val);
	//or
	//uninitialized_fill_n(A3, N3, val);
	for(int i3 = 0; i3 < N3; i3++)
	{
		std::cout << "A3[" << i3 << "] = " << A3[i3].get() << std::endl;
	}
	
	// 底层函数get_temporary_buffer/return_temporary_buffer
	// 用于开辟临时内存区，供:
	// uninitialized_copy/uninitialized_copy_n/uninitialized_fill/uninitialized_fill_n
	// 这些底层函数使用
	// sgi的文档例子在mingw测试时有问题：
	// 如果你不指明模板参数<int>，g++会报以下编译错误
	// test001.cpp:75: error: no matching function for call to `get_temporary_buffer(int)'
	// see http://www.cplusplus.com/reference/std/memory/get_temporary_buffer/
	// 另外，新版本的get_temporary_buffer可以多接一个初始化参数
	// pair<int*, ptrdiff_t> P = get_temporary_buffer<int>(10000, (int*) 0);
	std::pair<int*, ptrdiff_t> P = std::get_temporary_buffer<int>(10000);
	//拿到刚开辟的临时内存区和大小
	int* buf = P.first;
	ptrdiff_t N4 = P.second;
	//全部填充42
	std::uninitialized_fill_n(buf, N4, 42);
	//寻找不等于42的位置
	int* result = std::find_if(buf, buf + N4, std::bind2nd(std::not_equal_to<int>(), 42));
	//毫无疑问，指向内存区最后的下一个位置
	assert(result == buf + N4);
	std::cout << "result == buf + N4" << std::endl;
	//归还临时内存
	std::return_temporary_buffer(buf);
	
	return 0;
}

 

 

 

 

// 编译命令行：
// g++ test002.cpp

// 演示STL algorithm functions（无修改算法）
//

#include <iostream>
#include <iterator>
#include <list>
#include <vector>
#include <ext/slist>
#include <functional>
//#include <ext/functional>
// for iota
#include <ext/numeric>
//有时用function.h更方便
//因为mingw的compose1和select1st并不在std内
//而是在__gnu_cxx内
//不过这样做会引入std名字空间
//#include <function.h>

bool IsOdd (int i) 
{
	return ((i%2)==1);
}

//非模板的congruent
bool congruent1(int& a, int& b)
{
	return (a - b) % 10 == 0;
}

//模板化的congruent1
template<class Integer>
struct congruent
{
	congruent(Integer mod):N(mod){}
	//小心这里有两个括号，别漏了，否则会出现
	//error: no match for call to `(congruent) (int&, int&)'
	//参数可以写成引用（更快）
	bool operator()(Integer a, Integer b) const 
	{
		return (a - b) % N == 0;
	}
	Integer N;
};

bool eq_nosign(int x, int y) 
{ 
	return abs(x) == abs(y); 
}

void lookup(int* first, int* last, size_t count, int val) 
{
	std::cout << "Searching for a sequence of "
		<< count
		<< " '" << val << "'"
		<< (count != 1 ? "s: " : ":  ");
	int* result = std::search_n(first, last, count, val);
	if (result == last)
		std::cout << "Not found" << std::endl;
	else
		std::cout << "Index = " << result - first << std::endl;
}

void lookup_nosign(int* first, int* last, size_t count, int val) 
{
	std::cout << "Searching for a (sign-insensitive) sequence of "
		<< count
		<< " '" << val << "'"
		<< (count != 1 ? "s: " : ":  ");
	int* result = std::search_n(first, last, count, val, eq_nosign);
	if (result == last)
		std::cout << "Not found" << std::endl;
	else
		std::cout << "Index = " << result - first << std::endl;
}

// 模拟std::ostream_iterator
template<class T> 
struct print : public std::unary_function<T, void>
{
	print(std::ostream& out) : os(out), count(0) {}
	void operator() (T x) 
	{ 
		os << x << ' '; ++count; 
	}
	std::ostream& os;
	int count;
};

int main(int argc, const char *argv[])
{
	std::cout << "Test STL algorithm functions (no motifications)" << std::endl;
	
	//find，用于得到[first, last)范围内第一个满足*i == value的位置
	{
		std::list<int> L;
		L.push_back(3);
		L.push_back(1);
		L.push_back(7);
		std::list<int>::iterator result = std::find(L.begin(), L.end(), 7);
		assert(result == L.end() || *result == 7);
		std::cout << "result == L.end() || *result == 7" << std::endl;
		std::cout << "*result == " << *result << std::endl;
	}
	
	{
		//find_if，用于得到[first, last)范围内第一个满足pred(*i) == true的位置
		int A[] = {-3, 0, 3, -2};
		const int N = sizeof(A) / sizeof(int);
		int *result2 = std::find_if(A, A+N,
			std::bind2nd(std::greater<int>(), 0));
		// 或者干脆用一个C函数作为条件
		//int *result2 = std::find_if(A, A+N, IsOdd);    
		assert(result2 == A + N || *result2 > 0);
		std::cout << "result2 == A + N || *result2 > 0" << std::endl;
		std::cout << "*result2 == " << *result2 << std::endl;	
		
		//更复杂的find_if：
		typedef std::pair<int, char*> Pair;
		std::vector<Pair> V;
		V.push_back(Pair(3, "A"));
		V.push_back(Pair(2, "B"));
		std::vector<Pair>::iterator p = 
			std::find_if(V.begin(), V.end(), 
			__gnu_cxx::compose1(std::bind2nd(std::equal_to<int>(), 2), 
				__gnu_cxx::select1st<Pair>()));
		std::cout << p->first << " , " << p->second << std::endl;
	}
	
	{
		//adjacent_find，用于相邻重复查找，即第一个出现重复的位置
		int A2[] = {1, 2, 3, 3, 4, 5};
		const int N2 = sizeof(A2) / sizeof(int);
		const int* p2 = std::adjacent_find(A2, A2 + N2);
		std::cout << "*p2 == " << *p2 << std::endl; 
		std::cout << "*(p2 + 1) == " << *(p2 + 1) << std::endl;
		
		//adjacent_find，还可用于判断递增性
		int A3[] = {1, 2, 3, 4, 6, 5, 7, 8};
		const int N3 = sizeof(A3) / sizeof(int);
		const int* p3 = std::adjacent_find(A3, A3 + N3, std::greater<int>());
		std::cout << "Element " << p3 - A3 << " is out of order: "
			 << *p3 << " > " << *(p3 + 1) << "." << std::endl;
	}
	
	//find_first_of，用于条件为范围的查找
	//例如查找字符串中的\t或\n或空格
	{
		const char* WS = "\t\n ";
		const int n_WS = strlen(WS);
		char* s1 = "This sentence contains five words.";
		char* s2 = "OneWord";
		char* end1 = std::find_first_of(s1, s1 + strlen(s1),
								 WS, WS + n_WS); 
		char* end2 = std::find_first_of(s2, s2 + strlen(s2),
								 WS, WS + n_WS); 
		printf("First word of s1: %.*s\n", end1 - s1, s1); 
		printf("First word of s2: %.*s\n", end2 - s2, s2); 
	}
	
	{
		//search，用于子串的查找
		const char S1[] = "Hello, world!";
		const char S2[] = "world";
		const int N1 = sizeof(S1) - 1;
		const int N2 = sizeof(S2) - 1;
		const char* p = std::search(S1, S1 + N1, S2, S2 + N2);
		printf("Found subsequence \"%s\" at character %d of sequence \"%s\".\n",
			 S2, p - S1, S1);
			 
		//search，还可以用于连续的匹配
		//下面是查找个位连续为1,2,3的整数的位置
		int A[10] = {23, 46, 81, 2, 43, 19, 14, 98, 72, 5};
		int digits[3] = {1, 2, 3};
		int *seq = std::search(A, A + 10, digits, digits + 3, congruent<int>(10));
		std::cout << "Subsequent: ";
		std::copy(seq, seq + 3, std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
	}
	
	{
		//find_end，类似于search，但它查找最后匹配的子串
		char* s = "executable.exe";
		char* suffix = "exe";
		const int N = strlen(s);
		const int N_suf = strlen(suffix);
		char* location = std::find_end(s, s + N, 
			suffix, suffix + N_suf);
		if (location != s + N) 
		{
			std::cout << "Found a match for " << suffix << " within " << s << std::endl;
			std::cout << s << std::endl;
			int i;
			for (i = 0; i < (location - s); ++i)
				std::cout << ' ';
			for (i = 0; i < N_suf; ++i)
				std::cout << '^';
			std::cout << std::endl;
		}
		else
			std::cout << "No match for " << suffix << " within " << s << std::endl;
	}
	
	{
		//search_n，用于连续n次出现的子串匹配
		const int N = 10;
		int A[N] = {1, 2, 1, 1, 3, -3, 1, 1, 1, 1};
		//连续出现4个1的序列
		lookup(A, A+N, 4, 1);
		//连续出现2个绝对值为3的序列
		lookup_nosign(A, A+N, 2, 3);
	}
	
	{
		//count，用于计算某元素的个数
		int A[] = { 2, 0, 4, 6, 0, 3, 1, -7 };
		const int N = sizeof(A) / sizeof(int);
		std::cout << "Number of zeros: " 
			<< std::count(A, A + N, 0)
			<< std::endl;
	}
	
	{
		//count_if，用于计算满足某个条件的元素个数
		//下面是计算偶数的个数
		int A[] = { 2, 0, 4, 6, 0, 3, 1, -7 };
		const int N = sizeof(A) / sizeof(int);
		std::cout << "Number of even elements: " 
			<< std::count_if(A, A + N,
				__gnu_cxx::compose1(std::bind2nd(std::equal_to<int>(), 0), 
				std::bind2nd(std::modulus<int>(), 2)))
			<< std::endl;
	}
	
	{
		//for_each，用于以只读的函数遍历所有元素
		int A[] = {1, 4, 2, 8, 5, 7};
		const int N = sizeof(A) / sizeof(int);
		//最后的参数还可以直接传入一个C函数的指针，参数是容器的元素类型
		//这里的print<int>()是带状态的
		print<int> P = std::for_each(A, A + N, print<int>(std::cout));
		//利用返回值取出函数对象的状态值
		std::cout << std::endl << P.count << " objects printed." << std::endl;
	}
	
	{
		//equal，用于判断序列是否相等，true或false
		int A1[] = { 3, 1, 4, 1, 5, 9, 3 };
		int A2[] = { 3, 1, 4, 2, 8, 5, 7 };
		const int N = sizeof(A1) / sizeof(int);
		std::cout << "Result of comparison: " << (std::equal(A1, A1 + N, A2) ? "true" : "false") << std::endl;
	}
	
	{
		//mismatch，用于判断两个序列出现首个不同的位置
		int A1[] = { 3, 1, 4, 1, 5, 9, 3 };
		int A2[] = { 3, 1, 4, 2, 8, 5, 7 };
		const int N = sizeof(A1) / sizeof(int);
		std::pair<int*, int*> result = std::mismatch(A1, A1 + N, A2);
		std::cout << "The first mismatch is in position " << result.first - A1 << std::endl;
		std::cout << "Values are: " << *(result.first) << ", " << *(result.second) << std::endl;
	}
	
	{
		//lexicographical_compare，用于字典序列比较
		int A1[] = {3, 1, 4, 1, 5, 9, 3};
		int A2[] = {3, 1, 4, 2, 8, 5, 7};
		int A3[] = {1, 2, 3, 4};
		int A4[] = {1, 2, 3, 4, 5};
		const int N1 = sizeof(A1) / sizeof(int);
		const int N2 = sizeof(A2) / sizeof(int);
		const int N3 = sizeof(A3) / sizeof(int);
		const int N4 = sizeof(A4) / sizeof(int);
		bool C12 = std::lexicographical_compare(A1, A1 + N1, A2, A2 + N2);
		bool C34 = std::lexicographical_compare(A3, A3 + N3, A4, A4 + N4);
		std::cout << "A1[] < A2[]: " << (C12 ? "true" : "false") << std::endl;
		std::cout << "A3[] < A4[]: " << (C34 ? "true" : "false") << std::endl;
	}
	
	{
		//min/max，用于较小值/较大值
		const int x_min = std::min(3, 9);
		const int x_max = std::max(3, 9);
		std::cout << "x_min == " << x_min << std::endl;
		std::cout << "x_max == " << x_max << std::endl;
	}
	
	{
		//min_element/max_element，用于求一个序列的最小值/最大值
		std::list<int> L;
		std::generate_n(std::front_inserter(L), 1000, rand);
		std::list<int>::const_iterator it = std::min_element(L.begin(), L.end());
		std::list<int>::const_iterator it2 = std::max_element(L.begin(), L.end());
		std::cout << "The smallest element is " << *it << std::endl;
		std::cout << "The largest element is " << *it2 << std::endl;
	}
	
	return 0;
}

 

 

 

// 编译命令行：
// g++ test003.cpp

// 演示STL algorithm functions (motifications)，
// 包括部分数学运算算法
//

#include <iostream>
#include <iterator>
#include <list>
#include <vector>
#include <ext/slist>
#include <functional>
//#include <ext/functional>
// for iota
#include <ext/numeric>
//有时用function.h更方便
//因为mingw的compose1和select1st并不在std内
//而是在__gnu_cxx内
//不过这样做会引入std名字空间
//#include <function.h>

//for random_sample
#include <ext/algorithm>

struct string_length_exceeds
{
	string_length_exceeds(int i):N(i){}
	int N;
	bool operator()(const char * str) const
	{
		return strlen(str) > N;
	}
};

inline bool eq_nocase(char c1, char c2) 
{ 
	return tolower(c1) == tolower(c2); 
}

inline bool lt_nocase(char c1, char c2) 
{ 
	return tolower(c1) < tolower(c2); 
}

struct eq_div
{
	eq_div(int i):N(i){}
	int N;
	//这里有两个括号
	bool operator()(int a, int b) const 
	{ 
		return (a/N) == (b/N); 
	}
};

template <class BidirectionalIterator> 
void snail_sort(BidirectionalIterator first, BidirectionalIterator last)
{
	//循环比较，执行O(n!)排序法，直至排序结束，回滚到第一个序列
	//（即返回最小的那个序列）
	//这个函数还可接受第三个参数（比较规则函数）
	while (std::next_permutation(first, last)) 
	{
		
	}
}

int main(int argc, const char *argv[])
{
	std::cout << "Test STL algorithm functions (motifications)" << std::endl;
	
	//33
	{
		//copy，用于复制序列（即使容器不同类）（指定目标区间的左范围）
		std::vector<int> V(5);
		//生成一个相对于value的增一序列
		__gnu_cxx::iota(V.begin(), V.end(), 1);
		std::list<int> L(V.size());
		std::copy(V.begin(), V.end(), L.begin());
		assert(std::equal(V.begin(), V.end(), L.begin()));
		std::cout << "V == L" << std::endl;
			
		//copy，还可用于输出
		char A[] = "Hello";
		std::vector<char> V2(A, A + strlen(A));
		__gnu_cxx::slist<char> L2(V2.size());
		std::copy(V2.begin(), V2.end(), L2.begin());
		assert(std::equal(V2.begin(), V2.end(), L2.begin()));
		
		std::vector<char> V3;
		//V3没有元素，需要使用back_inserter
		std::copy(V2.begin(), V2.end(), std::back_inserter(V3));
		//以int的形式输出到控制台
		copy(V3.begin(), V3.end(),
			std::ostream_iterator<int>(std::cout, "\n"));
	}
	
	{
		//copy_backward，类似于copy，用于指定目标区间的右范围的复制
		//把[first, last)复制到[result - (last - first), result)
		std::vector<int> V(15);
		__gnu_cxx::iota(V.begin(), V.end(), 1);
		std::copy_backward(V.begin(), V.begin() + 10, V.begin() + 15);
		std::copy(V.begin(), V.end(),
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
	}
	
	{
		//swap，用于交换两个变量的值
		int x = 1;
		int y = 2;
		std::cout << x << "," << y << std::endl;
		std::swap(x, y);
		std::cout << x << "," << y << std::endl;
	}

	{
		//iter_swap，用于交换两个指针对应变量的值
		int x = 1;
		int y = 2;
		std::cout << x << "," << y << std::endl;
		std::iter_swap(&x, &y);
		std::cout << x << "," << y << std::endl;
	}
	
	{
		//swap_ranges，用于交换两个容器的区间
		std::vector<int> V1, V2;
		V1.push_back(1);
		V1.push_back(2);
		V2.push_back(3);
		V2.push_back(4);
		std::cout << "before swap_ranges:"<< std::endl;
		std::copy(V1.begin(), V1.end(),
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
		std::copy(V2.begin(), V2.end(),
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
		std::swap_ranges(V1.begin(), V1.end(), V2.begin());
		std::cout << "after swap_ranges:"<< std::endl;
		std::copy(V1.begin(), V1.end(),
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
		std::copy(V2.begin(), V2.end(),
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
	}
	
	{
		//transform用于原地变换或不同容器的变换
		//对序列取负
		const int N = 10;
		double A[N];
		__gnu_cxx::iota(A, A+N, 1);
		std::cout << "before transform:"<< std::endl;
		std::copy(A, A + N,
			std::ostream_iterator<double>(std::cout, " "));
		std::cout << std::endl;
		std::transform(A, A+N, A, std::negate<double>());
		std::cout << "after transform:"<< std::endl;
		std::copy(A, A + N,
			std::ostream_iterator<double>(std::cout, " "));
		std::cout << std::endl;
		
		// V3 = V1 + V2
		//const int N = 10;
		std::vector<int> V1(N);
		std::vector<int> V2(N);
		std::vector<int> V3(N);
		__gnu_cxx::iota(V1.begin(), V1.end(), 1);
		std::fill(V2.begin(), V2.end(), 75);
		assert(V2.size() >= V1.size() && V3.size() >= V1.size());
		std::transform(V1.begin(), V1.end(), V2.begin(), V3.begin(),
			std::plus<int>());
		std::cout << "V1, V2, V3, ostream_iterator:"<< std::endl;
		std::copy(V1.begin(), V1.end(),
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
		std::copy(V2.begin(), V2.end(),
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
		std::copy(V3.begin(), V3.end(),
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
		//直接输出到控制台
		std::transform(V1.begin(), V1.end(), V2.begin(),
			std::ostream_iterator<int>(std::cout, " "),
			std::plus<int>());
		std::cout << std::endl;
	}
	
	{
		//replace，用于原地替换
		std::vector<int> V;
		V.push_back(1);
		V.push_back(2);
		V.push_back(3);
		V.push_back(1);
		std::cout << "befor replace:" << std::endl;
		std::copy(V.begin(), V.end(), 
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
		//把1换成99
		std::replace(V.begin(), V.end(), 1, 99);
		std::cout << "after replace:" << std::endl;
		std::copy(V.begin(), V.end(),
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
	}
	
	{
		//replace_if，用于原地条件替换
		std::vector<int> V;
		V.push_back(1);
		V.push_back(-3);
		V.push_back(2);
		V.push_back(-1);
		std::cout << "before replace_if:" << std::endl;
		std::copy(V.begin(), V.end(),
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
		std::replace_if(V.begin(), V.end(), std::bind2nd(std::less<int>(), 0), -1);
		std::cout << "after replace_if:" << std::endl;
		std::copy(V.begin(), V.end(),
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
		
		//也可用于字符串
		const char * A[] = {"apple", "banana", "pear", "unknown"};
		const int N = sizeof(A) / sizeof(char *);
		std::cout << "before replace_if:" << std::endl;
		std::copy(A, A + N, 
			std::ostream_iterator<const char *>(std::cout, " "));
		std::cout << std::endl;
		std::replace_if(A, A+N,
			string_length_exceeds(6),
			"******");
		std::cout << "after replace_if:" << std::endl;
		std::copy(A, A + N, 
			std::ostream_iterator<const char *>(std::cout, " "));
		std::cout << std::endl;
	}
	
	{
		//replace_copy，用于两容器间复制后替换
		std::vector<int> V1;
		V1.push_back(1);
		V1.push_back(2);
		V1.push_back(3);
		V1.push_back(1);
		std::vector<int> V2(4);
		std::replace_copy(V1.begin(), V1.end(), V2.begin(), 1, 99);
		std::cout << "V1, V2:" << std::endl;
		std::copy(V1.begin(), V1.end(),
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
		std::copy(V2.begin(), V2.end(),
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
	}
	
	{
		//replace_copy_if，用于两容器间复制后条件替换
		std::vector<int> V1;
		V1.push_back(1);
		V1.push_back(-1);
		V1.push_back(-5);
		V1.push_back(2);
		std::vector<int> V2(4);
		std::replace_copy_if(V1.begin(), V1.end(), V2.begin(),
			std::bind2nd(std::less<int>(), 0),
			0);
		std::cout << "V1, V2:" << std::endl;
		std::copy(V1.begin(), V1.end(),
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
		std::copy(V2.begin(), V2.end(),
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
	}
	
	{
		//fill/fill_n，用于元素填充（后者常用于插入）
		std::vector<double> V(4);
		std::fill(V.begin(), V.end(), 137);
		assert(V[0] == 137 && V[1] == 137 && V[2] == 137 && V[3] == 137);
		std::cout << "V == 137" << std::endl;
		
		//从后面插入4个42
		std::vector<double> V2;
		std::fill_n(std::back_inserter(V2), 4, 42);
		assert(V2.size() == 4 && V2[0] == 42 && V2[1] == 42 && V2[2] == 42 && V2[3] == 42);
		std::cout << "V2 == 42" << std::endl;
	}
	
	{
		//generate/generate_n，用于按根据函数（没有参数）的结果产生序列
		std::vector<int> V(5);
		std::generate(V.begin(), V.end(), rand);
		std::cout << "rand:" << std::endl;
		std::copy(V.begin(), V.end(),
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
		
		//generate_n常用于插入
		std::generate_n(std::ostream_iterator<int>(std::cout, " "), 5, rand);
		std::cout << std::endl;
	}
	
	{
		//remove，用于原地删除指定值，但真正的删除是发生在erase后
		std::vector<int> V;
		V.push_back(3);
		V.push_back(1);
		V.push_back(4);
		V.push_back(1);
		V.push_back(5);
		V.push_back(9);
		std::cout << "before remove" << std::endl;
		std::copy(V.begin(), V.end(), 
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
		//删除值为1的元素
		std::vector<int>::iterator new_end = 
			std::remove(V.begin(), V.end(), 1);
		std::cout << "after remove" << std::endl;
		std::copy(V.begin(), new_end, 
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
		V.erase(new_end, V.end());
		std::cout << "after erase" << std::endl;
		std::copy(V.begin(), V.end(), 
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
	}
	
	{
		//remove_if，用于原地删除指定条件值，但真正的删除是发生在erase后
		std::vector<int> V;
		V.push_back(1);
		V.push_back(4);
		V.push_back(2);
		V.push_back(8);
		V.push_back(5);
		V.push_back(7);
		std::cout << "before remove_if" << std::endl;
		std::copy(V.begin(), V.end(), 
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
		//删除偶数
		std::vector<int>::iterator new_end = 
			std::remove_if(V.begin(), V.end(), 
				__gnu_cxx::compose1(std::bind2nd(std::equal_to<int>(), 0),
					std::bind2nd(std::modulus<int>(), 2)));
		V.erase(new_end, V.end());
		std::cout << "after remove_if" << std::endl;
		std::copy(V.begin(), V.end(), 
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
	}
	
	{
		//remove_copy，用于容器之间的复制后删除指定值，常用于插入
		std::vector<int> V;
		V.push_back(-2);
		V.push_back(0);
		V.push_back(-1);
		V.push_back(0);
		V.push_back(1);
		V.push_back(2);
		//删除0
		std::remove_copy(V.begin(), V.end(), 
			std::ostream_iterator<int>(std::cout, " "),
			0);
		std::cout << std::endl;
	}
	
	{
		//remove_copy_if，用于容器之间的复制后删除指定条件的值，常用于插入
		//copy_if(first, last, result, pred)等价于
		//remove_copy_if(first, last, result, not1(pred))
		std::vector<int> V1;
		V1.push_back(-2);
		V1.push_back(0);
		V1.push_back(-1);
		V1.push_back(0);
		V1.push_back(1);
		V1.push_back(2);
		std::vector<int> V2;
		//插入复制后删除负数
		std::remove_copy_if(V1.begin(), V1.end(), 
			std::back_inserter(V2),
			std::bind2nd(std::less<int>(), 0));
		std::copy(V2.begin(), V2.end(), 
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
	}
	
	{
		//unique，用于原地删除相邻重复
		//如果配合sort使用就是删除所有重复的值
		std::vector<int> V;
		V.push_back(1);
		V.push_back(3);
		V.push_back(3);
		V.push_back(3);
		V.push_back(2);
		V.push_back(2);
		V.push_back(1);
		std::vector<int>::iterator new_end = std::unique(V.begin(), V.end());
		// 1 3 2 1
		std::copy(V.begin(), new_end, 
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
		
		//配合sort使用，就变成删除所有重复项
		const char init[] = "The Standard Template Library";
		std::vector<char> V2(init, init + strlen(init));
		std::sort(V2.begin(), V2.end(), lt_nocase);
		std::copy(V2.begin(), V2.end(), 
			std::ostream_iterator<char>(std::cout));
		std::cout << std::endl;
		std::vector<char>::iterator new_end2 = std::unique(V2.begin(), V2.end(), eq_nocase);
		std::copy(V2.begin(), new_end2, 
			std::ostream_iterator<char>(std::cout));
		std::cout << std::endl;
	}
	
	{
		//unique_copy，用于容器间复制后删除相邻重复
		const int A[] = {2, 7, 7, 7, 1, 1, 8, 8, 8, 2, 8, 8};
		std::unique_copy(A, A + sizeof(A) / sizeof(int), 
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
		
		//还可以指定相等的特定规则函数
		//下面是复制后删除相邻除于10相等的值
		const int A2[] = {2, 7, 7, 7, 11, 11, 18, 18, 18, 12, 18, 18};
		std::unique_copy(A2, A2 + sizeof(A2) / sizeof(int),
			std::ostream_iterator<int>(std::cout, " "),
			eq_div(10));
		std::cout << std::endl;			
	}
	
	{
		//reverse，用于原地反序
		std::vector<int> V;
		V.push_back(0);
		V.push_back(1);
		V.push_back(2);
		std::copy(V.begin(), V.end(), 
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;	
		std::reverse(V.begin(), V.end());
		std::copy(V.begin(), V.end(), 
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;	
	}
	
	{
		//reverse_copy，用于容器间复制后反序
		std::vector<int> V;
		V.push_back(0);
		V.push_back(1);
		V.push_back(2);
		std::copy(V.begin(), V.end(), 
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
		std::list<int> L(V.size());
		std::reverse_copy(V.begin(), V.end(), L.begin());
		copy(L.begin(), L.end(), 
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
	}
	
	{
		//rotate，用于两个子串原地互换位置
		char alpha[] = "abcdefghijklmnopqrstuvwxyz";
		std::rotate(alpha, alpha + 13, alpha + 26);
		std::cout << alpha << std::endl;
	}
	
	{
		//rotate_copy，用于两个容器复制后两个子串互换位置
		const char alpha[] = "abcdefghijklmnopqrstuvwxyz";
		std::rotate_copy(alpha, alpha + 13, alpha + 26, 
			std::ostream_iterator<char>(std::cout));
		std::cout << std::endl;
	}
	
	{
		//next_permutation/prev_permutation，向前或向后获取n!排列
		
		//O(n!)排序法
		int A[] = {8, 3, 6, 1, 2, 5, 7, 4};
		//int A[] = {1, 2, 3};
		const int N = sizeof(A) / sizeof(int);
		snail_sort(A, A+N);
		std::copy(A, A+N, 
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
		
		// 输出n!个排列
		int A2[] = {1, 2, 3};
		const int N2 = 3;
		do
		{
			std::copy(A2, A2 + N2,
				std::ostream_iterator<int>(std::cout, " "));
			std::cout << std::endl;
		} while(std::next_permutation(A2, A2 + N2));
		
		// 获取前或后的n!排列
		int A3[] = {2, 3, 4, 5, 6, 1};
		const int N3 = sizeof(A3) / sizeof(int);
		std::cout << "Initially:              ";
		std::copy(A3, A3 + N3, 
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
		std::prev_permutation(A3, A3 + N3);
		std::cout << "After prev_permutation: ";
		std::copy(A3, A3 + N3, 
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
		std::next_permutation(A3, A3 + N3);
		std::cout << "After next_permutation: ";
		std::copy(A3, A3 + N3, 
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
	}
	
	{
		//partition，用于把符合条件的值移到区间的最左边
		int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
		const int N = sizeof(A)/sizeof(int);
		//把偶数都移到区间左边
		std::partition(A, A + N,
			__gnu_cxx::compose1(std::bind2nd(std::equal_to<int>(), 0),
				std::bind2nd(std::modulus<int>(), 2)));
		std::copy(A, A + N, 
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
	}
	
	{
		//stable_partition，用于把符合条件的值移到区间的最左边，然后排序
		int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
		const int N = sizeof(A)/sizeof(int);
		std::stable_partition(A, A + N,
			__gnu_cxx::compose1(std::bind2nd(std::equal_to<int>(), 0),
				std::bind2nd(std::modulus<int>(), 2)));
		std::copy(A, A + N, 
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
	}
	
	{
		//random_shuffle，用于产生均匀分布的随机N!排列
		//可提供第三参数用于乱数生成器
		const int N = 8;
		int A[] = {1, 2, 3, 4, 5, 6, 7, 8};
		std::random_shuffle(A, A + N);
		std::copy(A, A + N, 
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
	}
	
	{
		//random_sample/random_sample_n，从N个数中取n个数，概率相等
		//可提供第三参数用于乱数生成器
		const int N = 10;
		const int n = 4;
		int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
		int B[n];
		__gnu_cxx::random_sample(A, A+N, B, B+n);
		// 10选4
		std::copy(B, B + n, 
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
		
		//插入随机序列（10选4）
		__gnu_cxx::random_sample_n(A, A+N, 
			std::ostream_iterator<int>(std::cout, " "), 4);
		std::cout << std::endl;
	}
	
	{
		//accumulate，常用于累加或连乘
		//需要指定一个初始值
		int A[] = {1, 2, 3, 4, 5};
		const int N = sizeof(A) / sizeof(int);
		//累加
		std::cout << "The sum of all elements in A is " 
			<< std::accumulate(A, A + N, 0)
			<< std::endl;
		//连乘
		std::cout << "The product of all elements in A is "
			<< std::accumulate(A, A + N, 1, std::multiplies<int>())
			<< std::endl;
	}
	
	{
		//inner_product，用于计算内积
		int A1[] = {1, 2, 3};
		int A2[] = {4, 1, -2};
		const int N1 = sizeof(A1) / sizeof(int);
		// 1 * 4 + 2 * 1 + 3 * (-2)
		std::cout << "The inner product of A1 and A2 is " 
		   << std::inner_product(A1, A1 + N1, A2, 0)
		   << std::endl;
	}
	
	{
		//partial_sum，用于计算部分总和序列
		//（部分总和，指每步相加的和）
		const int N = 10;
		int A[N];
		std::fill(A, A+N, 1);
		std::cout << "A:                 ";
		std::copy(A, A+N, 
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
		std::cout << "Partial sums of A: ";
		std::partial_sum(A, A+N, 
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
	}
	
	{
		//adjacent_difference，用于生成差分序列，
		//即相邻元素的差的序列
		//（如果是第一个，就直接取第一个元素的值）
		//用partial_sum可还原为原来的序列
		int A[] = {1, 4, 9, 16, 25, 36, 49, 64, 81, 100};
		const int N = sizeof(A) / sizeof(int);
		int B[N];
		std::cout << "A[]:         ";
		std::copy(A, A + N, 
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
		std::adjacent_difference(A, A + N, B);
		std::cout << "Differences: ";
		std::copy(B, B + N, 
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
		//用partial_sum还原为原来的序列
		std::cout << "Reconstruct: ";
		std::partial_sum(B, B + N, 
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
	}
	return 0;
}

 

 

 

// 编译命令行：
// g++ test004.cpp

// 演示STL排序/查找算法

// for cout
#include <iostream>
// for ostream_iterator
#include <iterator>
//函数对象
#include <functional>
//算法
#include <algorithm>
// for string
#include <string>
// for vector
#include <vector>
// for is_sorted
#include<ext/algorithm>

inline bool lt_nocase(char c1, char c2) 
{ 
	return tolower(c1) < tolower(c2); 
}

//分治法排序，即stable_sort（经修改）
template<class BidirectionalIter>
void mergesort(BidirectionalIter first, BidirectionalIter last)
{
	typename std::iterator_traits<BidirectionalIter>::difference_type n = 
		std::distance(first, last);
	if(n == 0 || n == 1)
		return ;
	else
	{
		BidirectionalIter mid = first + n / 2;
		mergesort(first, mid);
		mergesort(mid, last);
		std::inplace_merge(first, mid, last);
	}
}

int main(int argc, const char *argv[])
{
	std::cout << "Test STL sort functions" << std::endl;
	
	{
		//sort，用于非稳定排序
		//不保证等价元素（即x既不小于y，y也不小于x）的相对次序
		int A[] = {1, 4, 2, 8, 5, 7};
		const int N = sizeof(A) / sizeof(int);
		//从小到大排序
		std::sort(A, A + N);
		std::copy(A, A + N, 
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;	
		
		//判断是否排序成功
		assert(__gnu_cxx::is_sorted(A, A + N));
		
		//还可以接受第三个参数，以判断大小或指定排序的顺序
		//下面从大到小对字符串排序
		const char *A2[] = {"apple", "banana", "pear"};
		const int N2 = sizeof(A2) / sizeof(const char *);
		std::sort(A2, A2 + N2, std::greater<std::string>());
		//or
		//std::sort(A2, A2 + N2, std::greater<const char*>());
		std::copy(A2, A2 + N2,
			std::ostream_iterator<const char*>(std::cout, " "));
		std::cout << std::endl;
	}
	
	{
		//stable_sort，用于稳定排序
		//保证等价元素（即x既不小于y，y也不小于x）的相对次序
		char A[] = "fdBeACFDbEac";
		const int N = sizeof(A) - 1;
		std::stable_sort(A, A+N, lt_nocase);
		std::cout << A << std::endl;
	}
	
	{
		//partial_sort/partial_sort_copy，用于原地或容器间复制的局部排序
		//即把某个区间的前n个最小元素排序后移到区间左边
		//如果第二和第三参数相同，则等价于sort
		//即partial_sort(A, A+N, A+N)相当于sort(A, A+N)
		int A[] = {7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5};
		const int N = sizeof(A) / sizeof(int);
		//只对最小的前5个数排序
		std::partial_sort(A, A + 5, A + N);
		std::copy(A, A + N, 
			std::ostream_iterator<int>(std::cout, " "));
		std::cout <<std::endl;
		
		std::vector<int> V(4);
		//只对最小的前4个数排序
		std::partial_sort_copy(A, A + N, V.begin(), V.end());
		std::copy(V.begin(), V.end(),
			std::ostream_iterator<int>(std::cout, " "));
		std::cout <<std::endl;
	}
	
	{
		//nth_element，用于把某个区间的前n个最小元素不排序，但移到区间左边
		int A[] = {7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5};
		const int N = sizeof(A) / sizeof(int);
		//前6个最小值
		std::nth_element(A, A + 6, A + N);
		std::copy(A, A + N, 
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
	}
	
	{
		//is_sorted，用于判断序列是否已经被排序
		int A[] = {1, 4, 2, 8, 5, 7};
		const int N = sizeof(A) / sizeof(int);
		assert(!__gnu_cxx::is_sorted(A, A + N));
		std::cout << "A is not sorted" << std::endl;
		std::sort(A, A + N);
		assert(__gnu_cxx::is_sorted(A, A + N));
		std::cout << "A is sorted" << std::endl;
	}
	
	{
		//binary_search，用于判断已排序序列内是否存在i，用二分法查找
		//基于已排序序列
		int A[] = { 1, 2, 3, 3, 3, 5, 8 };
		const int N = sizeof(A) / sizeof(int);
		for (int i = 1; i <= 10; ++i) 
		{
			std::cout << "Searching for " << i << ": "
				<< (std::binary_search(A, A + N, i) ? "present" : "not present") 
				<< std::endl;
		}
	}
	
	{
		//lower_bound/upper_bound/equal_range，用于找到不破坏原有顺序的第一个/最后一个插入位置
		//（其中equal同时计算两个值）
		//基于已排序序列
		int A[] = { 1, 2, 3, 3, 3, 5, 8 };
		const int N = sizeof(A) / sizeof(int);
		for (int i = 1; i <= 10; ++i) 
		{
			int* p = std::lower_bound(A, A + N, i);
			std::cout << "Searching for " << i << ".  ";
			std::cout << "Result: index = " << p - A << ", ";
			if (p != A + N)
				std::cout << "A[" << p - A << "] == " << *p << std::endl;
			else
				std::cout << "which is off-the-end." << std::endl;
		}
		
		for (int i2 = 1; i2 <= 10; ++i2) 
		{
			int* p = std::upper_bound(A, A + N, i2);
			std::cout << "Searching for " << i2 << ".  ";
			std::cout << "Result: index = " << p - A << ", ";
			if (p != A + N)
				std::cout << "A[" << p - A << "] == " << *p << std::endl;
			else
				std::cout << "which is off-the-end." << std::endl;
		}
		
		int A3[] = { 1, 2, 3, 3, 3, 5, 8 };
		const int N3 = sizeof(A) / sizeof(int);
		for (int i3 = 2; i3 <= 4; ++i3) 
		{
			std::pair<int*, int*> result = std::equal_range(A3, A3 + N3, i3);
			std::cout << std::endl;
			std::cout << "Searching for " << i3 << std::endl;
			std::cout << "  First position where " << i3 << " could be inserted: "
				<< result.first - A3 << std::endl;
			std::cout << "  Last position where " << i3 << " could be inserted: "
				<< result.second - A3 << std::endl;
			if (result.first < A3 + N3)
				std::cout << "  *result.first = " << *result.first << std::endl;
			if (result.second < A3 + N3)
				std::cout << "  *result.second = " << *result.second << std::endl;
		}
	}
	
	{
		//merge，用于合并两个已排序序列成为一个排序序列
		int A1[] = { 1, 3, 5, 7 };
		int A2[] = { 2, 4, 6, 8 };
		const int N1 = sizeof(A1) / sizeof(int);
		const int N2 = sizeof(A2) / sizeof(int);
		std::merge(A1, A1 + N1, A2, A2 + N2, 
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
	}
	
	{
		//inplace_merge，用于对同一序列的两个已排序区间进行合并，成为一个排序序列
		int A[] = { 1, 3, 5, 7, 2, 4, 6, 8 };
		std::inplace_merge(A, A + 4, A + 8);
		std::copy(A, A + 8, 
			std::ostream_iterator<int>(std::cout, " "));  
		std::cout << std::endl;
		
		//使用inplace_merge实现分治法排序
		int A2[] = { 1, 3, 5, 7, 2, 4, 6, 8 }; 
		const int N2 = sizeof(A2) / sizeof(int);
		mergesort(A2, A2 + N2);
		std::cout << "inplace_merge sort : " << std::endl;
		std::copy(A2, A2 + N2, 
			std::ostream_iterator<int>(std::cout, " "));  
		std::cout << std::endl;
	}
	
	{
		//includes，用于判断一个排序序列是否包含在另一个排序序列中
		int A1[] = { 1, 2, 3, 4, 5, 6, 7 };
		int A2[] = { 1, 4, 7 };
		int A3[] = { 2, 7, 9 };
		int A4[] = { 1, 1, 2, 3, 5, 8, 13, 21 };
		int A5[] = { 1, 2, 13, 13 };
		int A6[] = { 1, 1, 3, 21 };
		const int N1 = sizeof(A1) / sizeof(int);
		const int N2 = sizeof(A2) / sizeof(int);
		const int N3 = sizeof(A3) / sizeof(int);
		const int N4 = sizeof(A4) / sizeof(int);
		const int N5 = sizeof(A5) / sizeof(int);
		const int N6 = sizeof(A6) / sizeof(int);
		std::cout << "A2 contained in A1: " 
			<< (std::includes(A1, A1 + N1, A2, A2 + N2) ? "true" : "false") 
			<< std::endl;
		std::cout << "A3 contained in A1: " 
			<< (std::includes(A1, A1 + N2, A3, A3 + N3) ? "true" : "false") 
			<< std::endl;
		std::cout << "A5 contained in A4: " 
			<< (std::includes(A4, A4 + N4, A5, A5 + N5) ? "true" : "false") 
			<< std::endl;
		std::cout << "A6 contained in A4: " 
			<< (std::includes(A4, A4 + N4, A6, A6 + N6) ? "true" : "false") 
			<< std::endl;
	}
	
	{
		//set_union，用于求两个排序序列的并集
		int A1[] = {1, 3, 5, 7, 9, 11};
		int A2[] = {1, 1, 2, 3, 5, 8, 13};  
		char A3[] = {'a', 'b', 'B', 'B', 'f', 'H'};
		char A4[] = {'A', 'B', 'b', 'C', 'D', 'F', 'F', 'h', 'h'};
		const int N1 = sizeof(A1) / sizeof(int);
		const int N2 = sizeof(A2) / sizeof(int); 
		const int N3 = sizeof(A3);
		const int N4 = sizeof(A4);
		std::cout << "Union of A1 and A2: ";
		std::set_union(A1, A1 + N1, A2, A2 + N2,
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl 
			<< "Union of A3 and A4: ";
		std::set_union(A3, A3 + N3, A4, A4 + N4, 
			std::ostream_iterator<char>(std::cout, " "),
			lt_nocase);
		std::cout << std::endl;
	}
	
	{
		//set_intersection，用于求两个排序序列的交集
		int A1[] = {1, 3, 5, 7, 9, 11};
		int A2[] = {1, 1, 2, 3, 5, 8, 13};  
		char A3[] = {'a', 'b', 'b', 'B', 'B', 'f', 'h', 'H'};
		char A4[] = {'A', 'B', 'B', 'C', 'D', 'F', 'F', 'H' };
		const int N1 = sizeof(A1) / sizeof(int);
		const int N2 = sizeof(A2) / sizeof(int); 
		const int N3 = sizeof(A3);
		const int N4 = sizeof(A4);
		std::cout << "Intersection of A1 and A2: ";
		std::set_intersection(A1, A1 + N1, A2, A2 + N2,
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl 
		   << "Intersection of A3 and A4: ";
		std::set_intersection(A3, A3 + N3, A4, A4 + N4, 
			std::ostream_iterator<char>(std::cout, " "),
			lt_nocase);
		std::cout << std::endl;
	}
	
	{
		//set_difference，用于求两个排序序列的差集
		int A1[] = {1, 3, 5, 7, 9, 11};
		int A2[] = {1, 1, 2, 3, 5, 8, 13};  
		char A3[] = {'a', 'b', 'b', 'B', 'B', 'f', 'g', 'h', 'H'};
		char A4[] = {'A', 'B', 'B', 'C', 'D', 'F', 'F', 'H' };
		const int N1 = sizeof(A1) / sizeof(int);
		const int N2 = sizeof(A2) / sizeof(int); 
		const int N3 = sizeof(A3);
		const int N4 = sizeof(A4);
		std::cout << "Difference of A1 and A2: ";
		std::set_difference(A1, A1 + N1, A2, A2 + N2,
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl 
			<< "Difference of A3 and A4: ";
		std::set_difference(A3, A3 + N3, A4, A4 + N4, 
			std::ostream_iterator<char>(std::cout, " "),
			lt_nocase);
		std::cout << std::endl;
	}
	
	{
		//set_symmetric_difference，用于求两个排序序列的对称差集
		int A1[] = {1, 3, 5, 7, 9, 11};
		int A2[] = {1, 1, 2, 3, 5, 8, 13};  
		char A3[] = {'a', 'b', 'b', 'B', 'B', 'f', 'g', 'h', 'H'};
		char A4[] = {'A', 'B', 'B', 'C', 'D', 'F', 'F', 'H' };
		const int N1 = sizeof(A1) / sizeof(int);
		const int N2 = sizeof(A2) / sizeof(int); 
		const int N3 = sizeof(A3);
		const int N4 = sizeof(A4);
		std::cout << "Symmetric difference of A1 and A2: ";
		std::set_symmetric_difference(A1, A1 + N1, A2, A2 + N2,
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl 
			<< "Symmetric difference of A3 and A4: ";
		std::set_symmetric_difference(A3, A3 + N3, A4, A4 + N4, 
			std::ostream_iterator<char>(std::cout, " "),
			lt_nocase);
		std::cout << std::endl;
	}
	
	{
		//make_heap/sort_heap/is_heap，用于把一个序列变成堆/进行堆排序/判断是否已经变成堆
		int A[] = {1, 4, 2, 8, 5, 7};
		const int N = sizeof(A) / sizeof(int);
		assert(!__gnu_cxx::is_heap(A, A+N));
		std::make_heap(A, A+N);
		assert(__gnu_cxx::is_heap(A, A+N));
		std::copy(A, A+N, 
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
		std::sort_heap(A, A+N);
		std::copy(A, A+N, 
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
	}
	
	{
		//push_heap/pop_heap，用于扩大（压入新的值）/缩小(把最大值移到区间外)堆的范围
		//输入序列必须是堆
		int A[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
		std::make_heap(A, A + 9);
		std::cout << "[A, A + 9)  = ";
		std::copy(A, A + 9, 
			std::ostream_iterator<int>(std::cout, " "));  
		std::push_heap(A, A + 10);
		std::cout << std::endl << "[A, A + 10) = ";
		std::copy(A, A + 10, 
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
		
		int A2[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
		std::make_heap(A2, A2 + 10);
		std::cout << "[A2, A2 + 10) = ";
		std::copy(A2, A2 + 10, 
			std::ostream_iterator<int>(std::cout, " "));  		
		std::pop_heap(A2, A2 + 10);
		std::cout << std::endl << "[A2, A2 + 9)  = ";
		std::copy(A2, A2 + 9, 
			std::ostream_iterator<int>(std::cout, " "));
		std::cout << std::endl;
	}
	
	return 0;
}