[C++笔记]泛型程序设计与STL

#include <iostream>
using namespace std;

int main() {
	istream_iterator<int> is_i = istream_iterator<int>(cin);
	ostream_iterator<int> os_i = ostream_iterator<int>(cout, "\n"); //第二个参数 delimiter

	int a = *is_i;
	is_i++;
	int b = *is_i;
	*os_i = a;
	os_i++;
	*os_i = a + b;


	cout << "----------------" << endl;
	for (int i = 0; i < 10; i++) {
		*os_i = i;
		os_i++;
	}
	
	return 0;
}

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


// 实现泛型排序
template<class T, class input_iterator, class output_iterator>
void mySort(input_iterator first, input_iterator last, output_iterator result) {
	vector<T> v;
	for ( ; first !=  last; ++first) v.push_back(*first);
	sort(v.begin(), v.end());
	copy(v.begin(), v.end(), result);
}


int main() {
	double arr[] = { 1.1, 2.7, 9.0, 1.25, 0.3 };
	mySort<double>(arr, arr + 5, ostream_iterator<double>(cout, "  "));

	//mySort<int>(istream_iterator<int>(cin), istream_iterator<int>(), ostream_iterator<int>(cout, " "));
	return 0;
}

#include <iostream>
using namespace std;
#include <vector>
#include <deque>
#include <list>
template<class T>
void printContainer(T iterator_begin, T iterator_end) {
	while (iterator_begin != iterator_end) {
		cout << *iterator_begin << " ";
		iterator_begin++;
	}
	cout << endl;
}

int main() {
	vector<int> v;
	v.resize(10);
	for (int i = 0; i < v.size(); i++) {
		v[i] = i;
	}
	for (vector<int>::iterator v_it = v.begin(); v_it != v.end(); v_it++) {
		cout << *v_it << " ";
	}
	cout << endl;

	deque<int> d(v.rbegin(), v.rend());
	while (!d.empty()) {
		deque<int>::const_iterator d_c_it =  d.end()-1 ;
		cout << *d_c_it << " ";
		d.pop_back();
	}
	cout << endl;

	list<int> l;
	l.assign(v.begin(), v.end());
	l.push_back(100);
	l.pop_front();
	l.erase(l.begin());
	printContainer<list<int>::iterator>(l.begin(), l.end());
	return 0;
}

template<class FrontlnsertionSequence>class front_insert_iterator;
template<class Sequence>class back_insert_iterator; 
template<class Sequence>class insert_iterator;

template<class FrontlnsertionSequence> 
front_insert_iterator<FrontlnsertionSequence> front_inserter(FrontlnsertionSequence& s);
template<class Sequence> 
back_insert_iterator<Sequence> back_inserter(Sequence& s);
template<class Sequence , class Iterator> 
insert_iterator<Sequence> inserter(Sequence& s , Iterator i);

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

int main() {
	stack<int, vector<int>> s;     // 使用容器适配器将vector的接口转换成stack的接口
	for (int i = 0; i < 5; i++) {
		s.push(i);
	}
	while (!s.empty()) {
		cout << s.top() << endl;
		s.pop();
	}
	return 0;
}

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

int main() {
	set<string> s;
	s.insert("happy");
	pair<set<string>::iterator, bool> res = s.insert("happy");
	cout << res.second << endl;  // 0
	s.insert("good");
	s.insert("funk");
	copy(s.begin(), s.end(), ostream_iterator<string>(cout, " ")); // funk good happy
	return 0;
}

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

int main() {
	map<string, int> m;
	m.insert(pair<string, int>("zhangsan", 18));
	m.insert(make_pair("lisi", 39));
	m.insert(make_pair("wangwu", 10));
	m.insert(make_pair("slacr", 92));
	m.erase("slacr");
	m["lisi"] = 100;
	for (pair<string, int> entry : m) {
		cout << entry.first << " " << entry.second << endl;
	}
	//lisi 100
	//wangwu 10
	//zhangsan 18
}

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


template<class T>
T muti(T t1, T t2) { return t1 * t2; };

template<class T>
class myplus {
public:
	T operator()(T t1, T t2) { return t1 + t2; }
};

int main() {
	list<int> l;
	l.push_back(4);
	l.push_back(2);
	l.push_back(5);
	cout << accumulate(l.begin(), l.end(), 1, muti<int>) << endl;
	cout << accumulate(l.begin(), l.end(), 0, myplus<int>()) << endl;   // 仿函数， 这里的muplus<int>()整体是函数名，括号是重载的运算符

	return 0;
}

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

int main() {
	int arr[] = { 1, 3, 4, 5, 2 };
	vector<int> vi(arr, arr + 5);
	sort(vi.begin(), vi.end(), less<int>());
	copy(vi.begin(), vi.end(), ostream_iterator<int>(cout, " "));
	return 0;
}

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


class my_binary_pred : public binary_function<pair<string, int>, pair<string, int>, bool> {
public:
	bool operator()(pair<string, int> p1, pair<string, int> p2) {
		return p1.second < p2.second;
	}
};

int main() {
	vector<pair<string, int>> sheet;
	sheet.push_back(make_pair("slacr", 98));
	sheet.push_back(make_pair("Tim", 66));
	sheet.push_back(make_pair("Jose", 54));
	sheet.push_back(make_pair("frank", 99));
	sort(sheet.begin(), sheet.end(), my_binary_pred());
	for (pair<string, int> p : sheet) { cout << p.first << " " << p.second << endl; }

	return 0;
}

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


greater<int> g;
bool greater5(int x) {
	return g(x, 5);
}

int main() {
	int arr[] = { 2, 3, 1, 4, 7 };
	if (find_if(arr, arr + 5, greater5)) {
		cout << "find it" << endl;
	}  // find it


	// std::binder2nd<_Fn>::binder2nd(const _Fn & _Func, const typename _Fn::second_argument_type & _Right)
	if (find_if(arr, arr + 5, bind2nd(greater<int>(), 5))) { 
		cout << "find it" << endl;
	}
	return 0;
}

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

bool g(int x, int y) { return x > y; }

int main() {
	int arr[] = { 30, 40, 50 , 60, 70 };
	const int len = sizeof arr / sizeof arr[0];
	vector<int> v(arr, arr + len);

	vector<int>::iterator p;
	p = find_if(v.begin(), v.end(), bind2nd(ptr_fun(g), 40)); // 指针函数适配器
	if (p == v.end()) {
		cout << "none" << endl;
	} else {
		cout << "found" << endl;
	}
	p = find_if(v.begin(), v.end(), not1(bind2nd(greater<int>(), 40)));
	if (p == v.end()) {
		cout << "none" << endl;
	} else {
		cout << "found" << endl;
	}
	p = find_if(v.begin(), v.end(), bind2nd(not2(greater<int>()), 40));
	if (p == v.end()) {
		cout << "none" << endl;
	} else {
		cout << "found" << endl;
	}
	return 0;
}

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

bool g(int x, int y) { return x > y; }

int main() {
	int arr[] = { 1, 2, 3, 4, 5, 5, 6, 6, 7 };
	int len = sizeof(arr) / sizeof(arr[0]);
	vector<int> v1(arr, arr+len);

	int sub_arr[] = { 3, 4 };
	len = sizeof(sub_arr)/ sizeof(sub_arr[0]);
	vector<int> v2(sub_arr, sub_arr + len);
	cout << *adjacent_find(v1.begin(), v1.end()) << endl;
	// 找出第一个相邻元素

	cout << count_if(v1.begin(), v1.end(), bind2nd(greater<int>(), 5)) << endl;
	// 统计大于5的元素个数

	cout << *find_if(v1.begin(), v1.end(), bind2nd(less<int>(), 2)) << endl;
	// 找出第一个小于2的元素

	cout << *search(v1.begin(), v1.end(), v2.begin(), v2.end()) << endl;
	// 找出子序列在原序列中第一次出现位置的元素

	cout << *search_n(v1.begin(), v1.end(), 3, 4, greater<int>()) << endl;
	// 找出第一次连续出现3个>4的元素的元素

	cout << equal(v1.begin(), v1.end(), v2.begin(), v2.end()) << endl;
	// 判断两个序列是否相等

	pair<vector<int>::iterator, vector<int>::iterator> res = mismatch(v1.begin(), v1.end(), v2.begin(), v2.end());
	// 查找v2在v1中不匹配的首位置    
	return 0;
}

#include<iostream>
using namespace std;
#include<algorithm>
#include<functional>
#include<vector>
#include<random>
class myGenerator {
public:
	int operator()() {
		// 创建随机数生成器
		random_device rd;
		mt19937 gen(rd());
		// 创建分布器
		uniform_int_distribution<> dis(1, 9);
		// 生成随机数
		return dis(gen);
	}
};

bool g(int x, int y) { return x > y; }

int main() {
	int arr[] = { 1, 2, 3, 4, 5, 5, 6, 6, 7 };
	int len = sizeof(arr) / sizeof(arr[0]);
	vector<int> v1(arr, arr+len);

	int sub_arr[] = { 3, 4 };
	len = sizeof(sub_arr)/ sizeof(sub_arr[0]);
	vector<int> v2(sub_arr, sub_arr + len);
	ostream_iterator<int> output(cout, " ");

	fill(v1.begin(), v1.end(), 0);
	// 将v1填充 0 
	copy(v1.begin(), v1.end(), output);
	cout << endl;

	generate(v1.begin(), v1.end(), myGenerator());
	// 生成每一个元素为随机值
	copy(v1.begin(), v1.end(), output);
	cout << endl;

	remove_copy(v1.begin(), v1.end(), back_inserter(v2), 5);
	// 删除v1小于5的元素并放到v2后
	copy(v2.begin(), v2.end(), output);
	cout << endl;

	v2.erase(remove_if(v2.begin(), v2.end(), bind2nd(less<int>(), 4)));
	// 删除v2小于4的值, 只用remove_if不会清除原来空间
	copy(v2.begin(), v2.end(), output);
	cout << endl;

	replace(v2.begin(), v2.end(), 4, 0);
	// 将v2中4改为0
	copy(v2.begin(), v2.end(), output);
	cout << endl;

	reverse(v2.begin(), v2.end());
	// 逆序
	copy(v2.begin(), v2.end(), output);
	cout << endl;

	rotate_copy(v2.begin(), v2.begin() + 4, v2.end(), output);
	// 将两个区间旋转输出, 不会改变原容器
	cout << endl;


	vector<int> temp(v2);
	rotate_copy(temp.begin(), temp.begin() + 4, temp.end(), v2.begin());
	// 旋转序列改变原序列.
	copy(v2.begin(), v2.end(), output);

	return 0;
}

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

int main() {
	int arr[] = { 24, 32, 42, 51, 12, 34, 54 };
	vector<int> v(arr, arr + sizeof(arr) / sizeof(arr[0]));
	int arr1[] = { 39, 54, 87, 43 };
	vector<int> v2(arr1, arr1 + sizeof(arr1) / sizeof(arr1[0]));


	vector<int>::iterator p = max_element(v.begin(), v.end());
	// 计算区间最值
	int n = p - v.begin();
	int dist = distance(v.begin(), p); // 这个函数也可以算
	cout << "max_e: " << *p << " idx: " << n << " distance: " << dist << endl;

	vector<int> v1(5);
	partial_sort_copy(v.begin(), v.end(), v1.begin(), v1.end());
	// 将v局部排序并拷贝到其他容器, v本身不变化
	copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
	cout << endl;

	sort(v.begin(), v.end(), greater<int>());
	// 降序排列
	copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
	cout << endl;

	cout << *lower_bound(v.begin(), v.end(), 50, greater<int>()) << endl;
	// 默认的lower_bound必须要求按照升序排序后才行, 之前是是按降序排序的，这里也要传一个相同的谓词
	cout << *upper_bound(v.begin(), v.end(), 50, greater<int>()) << endl;

	cout << binary_search(v.begin(), v.end(), 32, greater<int>()) << endl; // 1

	vector<int> v3(v.size() + v2.size());
	sort(v.begin(), v.end());
	sort(v2.begin(), v2.end());
	merge(v.begin(), v.end(), v2.begin(), v2.end(), v3.begin());
	// 将v，v2合并到v3中
	copy(v3.begin(), v3.end(), ostream_iterator<int>(cout, " "));
	cout << endl;

	random_device rd;
	mt19937 g(rd());
	copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
	cout << endl;
	shuffle(v.begin(), v.end(), g);
	// 打乱元素
	copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
	cout << endl;
	nth_element(v.begin(), v.begin() + 2, v.end());
	// 保证在第n个位置之前的元素都小于等于第n个元素，而在第n个位置之后的元素都大于等于第n个元素。这个能更高效部分查找
	copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
	cout << endl;

	stable_sort(v.begin(), v.end());
	// 稳定的排序， 保持相对位置
	copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
	cout << endl;

	inplace_merge(v.begin(), v.begin()+2, v.end());
	// 合并两个有序序列， 保存到原序列
	copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
	cout << endl;

	cout << lexicographical_compare(v.begin(), v.end(), v2.begin(), v2.end()) << endl;
	// 按字典顺序比较 // 1
	return 0;
}

// 将二元函数转换成一元函数
template<class BinaryFunction>
class binder1st : public unary_function<
	typename BinaryFunction::second_argument_type,
	typename BinaryFunction::result_type> 
{
protected:
	BinaryFunction op;
	typename BinaryFunction::first_argument_type value;
public:
	// 构造函数
	binder1st(const BinaryFunction& op, const typename BinaryFunction::first_argument_type & value) : op(op), value(value) {}
	// 重载()
	typename Operation::result_type operator() (const typename BinaryFunction::second_argument_type& x) const {
		return op(value, x);
	}
};

template<class Category, class T, class Distance = ptrdiff_t,
class Pointer = T*， class Reference = T&> 
struct iterator { 
typedef T value type; 
typedef Distance difference type; 
typedef Pointer poi teri
typedef Reference reference; 
typedef Category iterator_category;
};

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


template<class T>
class IncrementIterator : public iterator<input_iterator_tag, T, ptrdiff_t, const T*, const T&> {
private:
	T value;
public:
	typedef IncrementIterator<T> Self;
	IncrementIterator(const T& value = T()) : value(value) {}  // 构造函数
	bool operator== (const Self& rhs) const { return value == rhs.value; }
	bool operator!= (const Self& rhs) const { return value != rhs.value; }
	Self& operator++() { value++; return *this; } // 前缀++
	Self& operator++(int) {				// 后缀++
		Self tmp = *this;
		value++;
		return tmp;
	}
	const T& operator*() const { return value; }
	const T* operator->() const { return &value; }
};


int main() {
	copy(IncrementIterator<int>(), IncrementIterator<int>(10), ostream_iterator<int>(cout, " "));
	cout << endl;
	int s[] = { 1, 2, 3, 4 ,5 };
	transform(s, s + sizeof(s) / sizeof(int), IncrementIterator<int>(), ostream_iterator<int>(cout, " "), plus<int>());
	//template<class InputIt1, class InputIt2, class OutputIt, class BinaryOperation>
	//	OutputIt transform(InputIt1 first1, InputIt1 last1, InputIt2 first2, OutputIt d_first, BinaryOperation binary_op);
	// 这个transform是一个重载版本, 有两个输入迭代器, 处理函数是plus, 输出迭代器ostream_iterator

	cout << endl;
	// 0 1 2 3 4 5 6 7 8 9
	// 1 3 5 7 9
	return 0;
}

template<class Iterator>struct iterator_traits { 
typedef typename Iterator::difference_type difference_type; 
typedef typename Iterator::value_type value_type; 
typedef typename Iterator::pointer pointer; 
typedef typename Iterator:: reference reference; 
typedef typename Iterator::iterator_category iterator_category;
};

// <iterator> 中还对 iterator_traits 进行了偏特化:
template<class T>struct  iterator_traits <T*>{ 
typedef ptrdiff_t difference_type;
typedef T value_type; 
typedef T* pointer;
typedef T& reference;
typedef random_access_iterator_tag iterator_category;
}
// 
template< class T> struct iterator_traits<const T*> { 
typedef ptrdiff_t difference_type; 
typedef T value_type;
typedef const T* pointer; 
typedef const T& reference; 
typedef random_access_iterator_tag iterator_category;
};

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

template<class InputIterator, class OutputIterator>
void mySort(InputIterator first, InputIterator last, OutputIterator result) {
	vector<typename iterator_traits<InputIterator>::value_type> s(first, last);
	sort(s.begin(), s.end());
	copy(s.begin(), s.end(), result);
}

int main() {
	double a[5] = { 3.1, 4,3, 8.4, 2.0};
	mySort(a, a + 5, ostream_iterator<double>(cout, " "));
	cout << endl;

	mySort(istream_iterator<int>(cin), istream_iterator<int>(), ostream_iterator<int>(cout, " "));
	cout << endl;
	return 0;
}