目录

1. 泛型编程的基本概念

2. 常用容器简介

3. 有序关联容器

3. 迭代器简介

4. 函数对象简介

5. STL常用算法简介

5.1 for_each：调用函数对象对输入迭代器区间内元素作处理

5.2 count 和 count_if：计算输入迭代器区间内指定值相等的元素个数

5.3 find 和 find_if：查找输入迭代器区间内与指定相等的首个元素

5.4 sort：对随机迭代器指定空间内元素进行排序

5.5 transform：将迭代器区间内的每对元素加工处理后输出至输出迭代器

5.6 set_union、set_intersection 和 set_difference：对两个输入迭代器区间指定的递增排序元素组成的集合进行集合并、交、差运算

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

template
void PrintContents(string title, const ContainerT& con, const char* delim = nullptr)
{
	cout << title << ":";
	for (auto it = con.begin(); it != con.end(); it++)
	{
		cout << *it;
		if (delim)
		{
			cout << delim;
		}
	}
	cout << endl;
}

int main()
{
	set S1{ 1, 3, 9, 7, 5 };
	unordered_set S2{ 1, 3, 9, 7, 5 };
	list L1{ 1, 3, 9, 7, 5 };
	deque DQ1{ 1, 3, 9, 7, 5 };
	PrintContents("set S1", S1, "t");
	PrintContents("unordered_set S2", S2, "t");
	PrintContents("list L1", L1, "t");
	PrintContents("deque DQ1", DQ1, "t");
	return 0;
}

2. 常用容器简介

• 向量（vector）：所有元素连续存储
• 链表（list）：双向链表，每个节点包含
• 双端队列（deque）：所有元素分多段存放，段间不连续，段内连续
• 集合（set）：基于红黑树，每个节点包含一个元素，元素间有序，无相同元素
• 多重集合（multiset）：基于红黑树，每个节点包含一个元素，元素间有序，有相同元素
• 无序集合（unordered_set）：基于哈希表实现，元素间无序，无相同元素

基于容器的数据结构不同，可分为三类：顺序容器、关联容器、无序容器

3. 有序关联容器

#include 
#include 
#include 

3. 迭代器简介

迭代器（iterator）是泛型程序设计中的“指针”，用于表示容器中确定的元素位置。

STL提供泛型copy算法，此算法需要输入迭代器、输出迭代器，使用时需要包含头文件，等效实现如下：

template
OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result)
{
	while (first != last)
	{
		*result = *first;
		result++;
		first++;
	}
	return result;
}

copy_if原型

template
OutputIterator copy_if(InputIterator first, InputIterator last,
	OutputIterator result, UnaryPredicate pred)
{
	while (first != last)
	{
		if (pred(*first))
		{
			*result = *first;
			result++;
		}
		first++;
	}
	return result;
}

用copy算法实现将容器L内的元素输出至输出流：

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

int main()
{
	list L;
	copy(istream_iterator(cin), istream_iterator(),
		back_inserter(L));
	copy(L.begin(), L.end(), ostream_iterator(cout, "t"));
	return 0;
}

4. 函数对象简介

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

inline bool BeEven(int x)
{
	return (x % 2 == 0);
}

class EvenPredicate
{
public:
	bool operator()(int x)const
	{
		return (x % 2 == 0);
	}
};

int main()
{
	list L;
	vector V;
	set S;

	copy(istream_iterator(cin), istream_iterator(),
		back_inserter(L));
	copy(L.begin(), L.end(), ostream_iterator(cout, " "));
	cout << endl;

	copy_if(L.begin(), L.end(), back_inserter(V), BeEven);
	copy(V.begin(), V.end(), ostream_iterator(cout, " "));
	cout << endl;

	copy_if(L.begin(), L.end(), inserter(S, S.begin()), EvenPredicate());
	copy(S.begin(), S.end(), ostream_iterator(cout, " "));
	cout << endl;

	return 0;
}

lambda表达式简介

lambda函数的定义：

auto fun = []()
{
	cout << "Hello, lambda" << endl;
};

[]()
{
	cout << "Hello, lambda" << endl;
}();

lambad函数的一般形式：

[...]{...}

[...](...){...}

• [...]表示捕捉外部数据的方式
• (...)表示函数参数表

#include 
using namespace std;

int main()
{
	int x = 1, y = 2, z = 3;
	auto f1 = [x, &y](int z)
	{
		cout << " x = " << x << ",t y = " << y << ",t z = " << z << endl;
		y++;
		z++;
	};
	auto f2 = [=, &y](int z)mutable
	{
		cout << " x = " << x << ",t y = " << y << ",t z" << z << endl;
        x++;    //用mutable修饰后传值参数可修改
		y++;
		z++;
	};

	x = 10;
	y = 11;
	z = 12;
	f1(z);
	f1(z);
	cout << " x = " << x << ",t y = " << y << ",t z = " << z << endl;
	f2(z);
	f2(z);
	cout << " x = " << x << ",t y = " << y << ",t z = " << z << endl;
	return 0;
}

lambda函数对象本质：匿名函数对象，简化函数对象的应用

5. STL常用算法简介

5.1 for_each：调用函数对象对输入迭代器区间内元素作处理

template
Function for_each(InputIterator first, InputIterator last, Function fn)
{
	while (first != last)
	{
		fn(*first)
		{
			first++;
		}
	}
	return fn;
}

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

int main()
{
	int A[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	vector V;

	copy_if(begin(A), end(A), back_inserter(V), [](int x) {return (x % 2 == 0); });
	copy(begin(V), end(V), ostream_iterator(cout, "t"));
	cout << endl;

	for_each(begin(V), end(V), [](int& x) {x = x * x; });	//针对向量容器内每个元素作平方运算

	copy(begin(V), end(V), ostream_iterator(cout, "t"));
	cout << endl;
	return 0;
}

5.2 count 和 count_if：计算输入迭代器区间内指定值相等的元素个数

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

int main()
{
	vector namesVect{ "She", "Sells", "Sea", "Shells", "by", "the", "Sea" };
	namesVect.push_back("shore");
	string value("Sea");
	copy(namesVect.begin(), namesVect.end(), ostream_iterator(cout, "t"));
	cout << endl;
	size_t result1 = count(begin(namesVect), end(namesVect), value);
	cout << "Number of elements that match"Sea" = " << result1 << endl;
	size_t result2 = count_if(begin(namesVect), end(namesVect),
		[](const string& str) {return !str.empty() && str[0] == 'S'; });
	cout << "Number of elements that start with 'S' = " << result2 << endl;
	return 0;
}

5.3 find 和 find_if：查找输入迭代器区间内与指定相等的首个元素

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

int main()
{
	vector namesList{ "She", "Sells", "Sea", "Shells", "by", "the", "Sea" };
	namesList.push_back("shore");
	string value("Sea");
	copy(namesList.begin(), namesList.end(), ostream_iterator(cout, "t"));
	cout << endl;
	auto it = begin(namesList);
	while (true)
	{
		it = find(it, end(namesList), value);
		if (it == end(namesList))
		{
			break;
		}
		cout << *it << "t";
		it++;
	}
	cout << endl;
	it = begin(namesList);
	while (true)
	{
		it = find_if(it, end(namesList),
			[](const string& str)
			{
				return !str.empty() && str[0] == 'S';
			});
		if (it == end(namesList))
		{
			break;
		}
		cout << *it << "t";
		it++;
	}
	cout << endl;
	return 0;
}

5.4 sort：对随机迭代器指定空间内元素进行排序

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

class CSample
{
public:
	CSample(int a, int b) :first(a), second(b) {}
	int first;
	int second;
	bool operator<(const CSample& m)const
	{
		return first < m.first || (first == m.first && second < m.second);
	}
};

bool less_second(const CSample& m1, const CSample& m2)
{
	return m1.second < m2.second || (m1.first < m2.first&& m1.second == m2.second);
}

int main()
{
	deque dqCont;
	for (int i = 0; i < 8; i++)
	{
		CSample my(8 - i, i * i - i * 2);
		dqCont.push_back(my);
	}
	for (size_t i = 0; i < dqCont.size(); i++)
	{
		cout << "(" << dqCont[i].first << "," << dqCont[i].second << ")n";
	}
	sort(dqCont.begin(), dqCont.end());
	cout << "after sorted by first: " << endl;
	for (size_t i = 0; i < dqCont.size(); i++)
	{
		cout << "(" << dqCont[i].first << "," << dqCont[i].second << ")n";
	}
	sort(dqCont.begin(), dqCont.end(), less_second);	//本语句与下面语句效果相同
	sort(dqCont.begin(), dqCont.end(), [](const CSample& x, const CSample& y) 
		{return x.second < y.second || (x.first < y.first&& x.second == y.second); });
	cout << "after sorted by second: " << endl;
	for (size_t i = 0; i < dqCont.size(); i++)
	{
		cout << "(" << dqCont[i].first << "," << dqCont[i].second << ")n";
	}
	return 0;
}

5.5 transform：将迭代器区间内的每对元素加工处理后输出至输出迭代器

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

int main()
{
	int A[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	vector V;
	copy_if(begin(A), end(A), back_inserter(V), [](int x) {return (x % 2 != 0); });
	copy(begin(V), end(V), ostream_iterator(cout, "t"));
	cout << endl;
	list L;
	//将向量容器内的每个元素平方后插入链表容器尾部
	transform(begin(V), end(V), back_inserter(L), [](int x) {return x * x; });
	copy(begin(L), end(L), ostream_iterator(cout, "t"));
	cout << endl;
	//将向量容器内的元素和链表容器内对应元素相加后，替换链表容器内原元素
	transform(begin(V), end(V), begin(L), begin(L), [](int x, int y) {return x + y; });
	copy(begin(L), end(L), ostream_iterator(cout, "t"));
	cout << endl;
	return 0;
}

5.6 set_union、set_intersection 和 set_difference：对两个输入迭代器区间指定的递增排序元素组成的集合进行集合并、交、差运算

#include 
#include 
#include 
using namespace std;

class CSet
{
private:
	list m_elements;
public:
	bool Add(int x);
	void Display();
	CSet UnionBy(const CSet& rhs)const;
	CSet IntersectionBy(const CSet& rhs)const;
	CSet DifferentBy(const CSet& rhs)const;
	bool Remove(int x);
	bool In(int x);
};

bool CSet::Add(int x)
{
	auto it = this->m_elements.begin();
	while (it != this->m_elements.end() && x > *it)
	{
		it++;
	}
	if (it != this->m_elements.end() && x == *it)
	{
		return false;
	}
	this->m_elements.insert(it, x);
	return true;
}

void CSet::Display()
{
	cout << "{ ";
	auto it = this->m_elements.begin();
	if (it != this->m_elements.end())
	{
		cout << *it;
		it++;
	}
	for (; it != this->m_elements.end(); it++)
	{
		cout << "," << *it;
	}
	cout << endl;
}

CSet CSet::UnionBy(const CSet& rhs)const
{
	CSet result;
	set_union(this->m_elements.begin(), this->m_elements.end(),
		rhs.m_elements.begin(), rhs.m_elements.end(), back_inserter(result.m_elements));
	return result;
}

CSet CSet::IntersectionBy(const CSet& rhs)const
{
	CSet result;
	set_intersection(this->m_elements.begin(), this->m_elements.end(),
		rhs.m_elements.begin(), rhs.m_elements.end(), back_inserter(result.m_elements));
	return result;
}

CSet CSet::DifferentBy(const CSet& rhs)const
{
	CSet result;
	set_difference(this->m_elements.begin(), this->m_elements.end(),
		rhs.m_elements.begin(), rhs.m_elements.end(), back_inserter(result.m_elements));
	return result;
}

bool CSet::Remove(int x)
{
	auto it = this->m_elements.begin();
	while (it != this->m_elements.end() && x > *it)
	{
		it++;
	}
	if (it != this->m_elements.end() && x == *it)
	{
		this->m_elements.erase(it);
		return true;
	}
	return false;
}

bool CSet::In(int x)
{
	auto it = find(this->m_elements.begin(), this->m_elements.end(), x);
	return it != this->m_elements.end();
}

int main()
{
	CSet A, B, S1, S2;
	int i, m, n, x;
	cin >> m >> n;
	for (i = 0; i < m; i++)
	{
		cin >> x;
		A.Add(x);
	}
	for (i = 0; i < n; i++)
	{
		cin >> x;
		B.Add(x);
	}
	A.Display();
	B.Display();
	S1 = A.UnionBy(B);
	S1.Display();
	S1.IntersectionBy(B);
	S1.Display();
	S1 = A.DifferentBy(B);
	S1.Display();
	return 0;
}