• C++模板与STL（三）：容器与算法

    注：此博文不具有教学意义，只作为自己复习用。

    目录

    1. STL六大组件

    1.1 容器(Container)：用来管理一组元素 

    1.1.1 序列式容器（Sequence Contaciers）

    1.1.2 关联式容器（Associated Containers）

    1.2 算法(Algorithm)

    1.3 迭代器(Iterator)

    1.4 仿函数(Function object)

    1.5 适配器(Adaptor)

    1.6 空间配置器(Allocator)

    2. 序列式容器

    2.1 Vector

    2.2 Deque

    2.2.1 简单例子：使用deque模拟队列

    2.2.2 简单例子：设计一个具有固定大小的stack

    2.3 List

    3.关联式容器

    3.1 Set/Multiset

    3.2 Map/Multimap

    4.STL：Algorithm（算法）

    4.0 引论和例子

    4.1 STL非变异算法（一）：for_each

    4.2 STL非变异算法（二）：find

    4.2.1 find

    4.2.2 find_if：查找第一个满足条件的位置

    4.2.3 find_first_of：在a数组中，发现b数组元素的位置

    4.2.4 adjacent_find：当前容器首次相邻元素的位置

    4.2.5 find_end：最后一次匹配c数组的位置

    4.2.6 search：首次匹配c数组的位置

    4.3 STL非变异算法（三）：pair

    4.4 STL变异算法（一）：copy与迭代器的组合

    4.5 STL变异算法（二）：swap算法：copy算法重定向到屏幕

    4.6 STL变异算法（三）：transform算法--加密的案例

    4.7 STL变异算法（四）：replace算法

    4.8 STL变异算法（五）：unique算法实现文本单词统计

    4.9 STL变异算法（六）：sort算法与binary算法

    1. STL六大组件

    1.1 容器(Container)：用来管理一组元素 

    1.1.1 序列式容器（Sequence Contaciers）

    • 每个元素都有归固定位置--取决于插入实际和地点，和元素值无关
    • vector，deque，list

    1.1.2 关联式容器（Associated Containers）

    • 元素位置取决于特定排序准则，与插入顺序无关
    • set，multiset，map，multimap

    1.2 算法(Algorithm)

    1.3 迭代器(Iterator)

    1.4 仿函数(Function object)

    1.5 适配器(Adaptor)

    1.6 空间配置器(Allocator)

    2. 序列式容器

    2.1 Vector

    • 动态数组，在堆中分配内存，元素连续存放。
    • 即使减少大小，内存也不会释放。
    • 通常情况下，不会移动内存。
    • 只有保留内存不够的时候，才会对中间和开始处的元素进行移动，如下：

    成倍扩容：

     再次成倍扩容：

    2.2 Deque

    • deque，为“double-ended-queue”的缩写
    • 可以随机存取元素（用索引）
    • 数组头部和尾部添加或一处元素都非常快速，但是在中间插入元素比较费时

     

     

    看出deque与vector分配空间的区别：

    • vector：一块独立的连续存放的内存空间
      • 建立空间
      • 填充数据
      • 空间不够，重新分配更大的空间
      • 复制原空间内容
      • 删除原空间
      • 添加新数据
    • deque：由多个分段连续的内存空间组成
      • 建立空间
      • 填充数据
      • 建立新空间
      • 添加新数据

    2.2.1 简单例子：使用deque模拟队列

    1. template<class T>
    2. class MyQueue {
    3. 	dequed;
    4. public:
    5. 	void push(const T& x) {
    6. 		d.push_back(x);
    7. 	}
    8.  
    9. 	void pop() {
    10. 		d.pop_front();
    11. 	}
    12.  
    13. 	int size() {
    14. 		return d.size();
    15. 	}
    16.  
    17. 	bool empty() {
    18. 		return d.empty();
    19. 	}
    20.  
    21. 	T& front() {
    22. 		return *d.begin();
    23. 	}
    24.  
    25. 	T& back() {
    26. 		return *(d.end() - 1);
    27. 	}
    28. };

    2.2.2 简单例子：设计一个具有固定大小的stack

    1. template<class T,class Container=deque>
    2. class MyStack :public stack {
    3. public:
    4. 	MyStack(int size) :m_MaxSize(size) {
    5.  
    6. 	}
    7. 	void push(const T& x) {
    8. 		if (stack::size() < m_MaxSize) {
    9. 			stack::push(x);
    10. 		}
    11. 		else {
    12. 			cout << "栈空间已满" << x << "未进栈" << endl;
    13. 		}
    14. 	}
    15. private:
    16. 	int m_MaxSize;
    17. };

    2.3 List

    • 双向链表
    • 不提供随机存取
    • 在任何位置上执行插入或删除都非常迅速，内部只需调整一下指针

    这里模拟一个例子：

    由两个文本文件：日志文件

    搜集了若干个机器的基础数据

    包含机器号，机器名，机器的连续运转时间

    由于某种原因，两个日志可能有一些重复的记录：

    ①把两个日志文件的数据映射成两个list元素

    ②对这两个日志按机器号升序排序

    ③合并两个已排好序的list容器元素

    ④利用unique函数去掉机器号重复的元素

    1. class Machine {
    2. public:
    3. 	Machine(string strNo,string strName,int total)
    4. 		:m_strNo(strNo),m_strName(strName),m_nTotal(total)
    5. 	{}
    6. 	bool operator<(Machine& m) {
    7. 		return m_strNo < m.GetNo();
    8. 	}
    9. 	bool operator==(Machine& m) {
    10. 		return m_strNo == m.GetNo();
    11. 	}
    12.  
    13. 	string GetNo() { return m_strNo; }
    14. 	string GetName() { return m_strName; }
    15. 	int GetTotal() { return m_nTotal; }
    16. private:
    17. 	string m_strNo;//机器号
    18. 	string m_strName;//机器名
    19. 	int m_nTotal;//连续工作时间
    20. };
    21.  
    22. ostream& operator<<(ostream& os, Machine& m) {
    23. 	os << m.GetNo() << "\t" << m.GetName() << "\t" << m.GetTotal();
    24. 	return os;
    25. }
    26.  
    27. typedef listLISTMACHINE;
    28. class MachineMgr {
    29. public:
    30. 	bool Add(const Machine& m) {
    31. 		m_list.push_back(m);
    32. 		return true;
    33. 	}
    34.  
    35. 	bool Merge(MachineMgr& machMgr) {
    36. 		this->m_list.sort();
    37. 		machMgr.m_list.sort();
    38. 		this->m_list.merge(machMgr.m_list);
    39. 		this->m_list.unique();
    40. 		return true;
    41. 	}
    42. private:
    43. 	LISTMACHINE m_list;
    44. };

    3.关联式容器

    3.1 Set/Multiset

    • 内部元素依据值自动排序
    • Set内相同数值元素只出现一次，Multiset内可包含多个数值相同的元素
    • 内部由二叉树（红黑树）实现，便于查找

    3.2 Map/Multimap

    • map的元素是成对的key/value，内部元素依据key自动排序
    • map内相同key只能出现一次，一个key对应一个value；
    • multimap一个key可对应多个value
    • 内部由红黑树实现

    c++中map详解_不会编程的小猿的博客-CSDN博客_c++map

    4.STL：Algorithm（算法）

    • 泛型算法通则：
      • 所有算法的前两个参数都是一对 iterators:[first,last)，用来指出容器内一个范围内的元素
      • 每个算法的声明中，都表现出它所需要的最低层次的iterator类型
      • 大部分算法都可以用function object来更改准则。function object又称functor：

    4.0 引论和例子

    算法都是施加在容器上，如果我们要对容器中某一范围的元素进行操作，那么我们使用仿函数。

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5.  
    6. using namespace std;
    7.  
    8. template<class T>
    9. class Add {
    10. public	:
    11. 	void operator()(T& t) {
    12. 		t *= 2;
    13. 	}
    14. };
    15.  
    16. int main() {
    17. 	vector<int>v;
    18. 	v.push_back(1);
    19. 	v.push_back(2);
    20. 	v.push_back(3);
    21. 	v.push_back(4);
    22. 	//Add类仿函数
    23. 	Add<int>myAdd;
    24. 	for_each(v.begin(), v.end(), myAdd);
    25. 	for (auto& it : v) {
    26. 		cout << it << " ";
    27. 	}
    28. 	cout << endl;
    29. 	//lambda匿名仿函数
    30. 	auto fun = [](int a) {a *= 3; };
    31. 	for_each(v.begin(), v.end(), fun);
    32. 	for (auto& it : v) {
    33. 		cout << it << " ";
    34. 	}
    35. 	return 0;
    36. }

    4.1 STL非变异算法（一）：for_each

     传入一个function object而不是函数指针，可以实现多种功能，比如Max，Sum，Min

    unary_function和binay_function_suyinfan的博客-CSDN博客

    1. #include 
    2. #include 
    3. #include 
    4. using namespace std;
    5.  
    6. template<class T,class _outPara>
    7. class PrintInfo :public unary_function {
    8. public:
    9. 	PrintInfo() :count(0), Sum(0) { }
    10. 	T GetSum() { return Sum; }
    11. 	T GetMax() { return Max; }
    12. 	T GetMin() { return Min; }
    13.  
    14. 	_outPara operator()(T x) {
    15. 		if (count == 0) {
    16. 			Max = x;
    17. 			Min = x;
    18. 		}
    19. 		else {
    20. 			if (Max < x) {
    21. 				Max = x;
    22. 			}
    23. 			if (Min > x) {
    24. 				Min = x;
    25. 			}
    26. 		}
    27. 		Sum += x;
    28. 		count++;
    29. 	}
    30.  
    31. private:
    32. 	T Sum;
    33. 	T Max;
    34. 	T Min;
    35. 	int count;
    36. };
    37.  
    38. int main() {
    39. 	float a[] = { 1.0,2.0,3.0,4.0,5.0,6.0 };
    40. 	const int N = sizeof(a) / sizeof(float);
    41.  
    42. 	PrintInfo<float, void> p = for_each(a, a + N, PrintInfo<float, void>());
    43. 	cout << "sum:" << p.GetSum() << endl;
    44. 	cout << "max:" << p.GetMax() << endl;
    45. 	cout << "min:" << p.GetMin() << endl;
    46.  
    47. 	return 0;
    48. }

    4.2 STL非变异算法（二）：find

    1. 	int a[] = { 1,2,2,3,4,4,5,6,7,1,2,3,4 };
    2. 	int n = sizeof(a) / sizeof(int);

    4.2.1 find

    1. 	//第一个等于3
    2. 	int* p1 = find(a, a + n, 3);

    4.2.2 find_if：查找第一个满足条件的位置

    1. bool myGreater(int temp) {
    2. 	return temp > 4;
    3. }
    1. 	//出现第一个大于4
    2. 	int* p2 = find_if(a, a + n, myGreater);

    4.2.3 find_first_of：在a数组中，发现b数组元素的位置

    1. 	//首次在a数组中，发现由b数组元素的位置
    2. 	int b[] = { 7,8,9 };
    3. 	int n1 = sizeof(b) / sizeof(int);
    4. 	int* p3 = find_first_of(a, a + n,b, b + n1);

    4.2.4 adjacent_find：当前容器首次相邻元素的位置

    1. 	//当前容器中首次相邻元素的位置
    2. 	int* p4 = adjacent_find(a, a + n);

    4.2.5 find_end：最后一次匹配c数组的位置

    1. 	//最后一次匹配c数组的位置
    2. 	int c[] = { 2,3 };
    3. 	int nc = sizeof(c) / sizeof(int);
    4. 	int* p5 = find_end(a, a + n, c, c + n);

    4.2.6 search：首次匹配c数组的位置

    1. 	//首次匹配sc数组的位置
    2. 	int* p6 = search(a, a + n, c, c + n);

    4.3 STL非变异算法（三）：pair

    1. 	int A1[] = { 3,1,4,1,5,9,3 };
    2. 	int A2[] = { 3,1,4,2,8,5,7 };
    3. 	const int N = sizeof(A1) / sizeof(int);
    4. 	pair<int*, int*>res = mismatch(A1, A1 + N, A2);
    5. 	cout << "首次出现不一样的位置" << res.first - A1 << endl;
    6. 	cout << "对应的数值" << *(res.first) << "," << *(res.second) << endl;

    4.4 STL变异算法（一）：copy与迭代器的组合

    1. 	int a[] = { 1,2,3,4,5 };
    2. 	vector<int>v;
    3. 	copy(a, a + 5, back_inserter(v));

    4.5 STL变异算法（二）：swap算法：copy算法重定向到屏幕

    swap：基本数据类、数组、基本序列容器

    数组：必须存在真实的空间，大小一定固定

    基本序列：不需要相同的空间大小

    1. 	int a2[] = { 1,3,5,7,9 };
    2. 	int b2[] = { 2,4,6,8,10 };
    3. 	swap_ranges(a2, a2 + 5, b2);
    4. 	copy(a2,a2+5,ostream_iterator<int>(cout,"\t"));
    5. 	cout << endl;
    6. 	copy(b2,b2+5,ostream_iterator<int>(cout,"\t"));

    4.6 STL变异算法（三）：transform算法--加密的案例

    1. template<class T>
    2. class Encrypt {
    3.  
    4. };
    5.  
    6. template<>
    7. class Encrypt {
    8. 	string operator()(const string& src) {
    9. 		string s = src;
    10. 		int len = s.size();
    11. 		//加密
    12. 		for (auto it : s) {
    13. 			it = it + 1;
    14. 		}
    15. 		return s;
    16. 	}
    17. };
    1. 	string strText;
    2. 	vectorv;
    3. 	ifstream in("D:\Encrypt.txt");
    4. 	while (!in.eof()) {
    5. 		getline(in, strText, '\n');
    6. 		v.push_back(strText);
    7. 	}
    8. 	in.close();
    9. 	transform(v.begin(), v.end(), back_inserter(v), Encrypt());
    10. 	copy(v.begin(), v.end(), ostream_iterator(cout, "\n"));

    4.7 STL变异算法（四）：replace算法

    1. 	int aa[] = { 2,3,4,5,2,2,-1 };
    2. 	replace(aa, aa + 7, 2, 10);
    3. 	copy(aa, aa + 7, ostream_iterator<int>(cout, "\t"));

    4.8 STL变异算法（五）：unique算法实现文本单词统计

    unique：消除容器里相邻相等的元素

    stricmp_墨子非阿萨德的博客-CSDN博客_stricmp

    1. 	ifstream out("D:\\DesignPatterns\\Template_STL\\words.txt"); 
    2. 	vectorv;
    3. 	copy(istream_iterator(out), istream_iterator(), back_inserter(v));
    4. 	cout << endl;
    5.  
    6. 	vectorvRes;
    7. 	unique_copy(v.begin(), v.end(), back_inserter(vRes), MyStrComp);
    8. 	copy(vRes.begin(), vRes.end(), ostream_iterator(cout, "\n"));

    4.9 STL变异算法（六）：sort算法与binary算法

     sort的迭代器是随机迭代器，list是双向迭代器：list.sort()，而不是 sort(list.begin(),list.end())

    1. 	int a3[] = { 1,3,3,5,5,7,9,10 };
    2. 	list<int>l(a3, a3 + 8);
    3. 	bool bExsit = binary_search(l.begin(), l.end(), 5);
    4. 	//第一个3
    5. 	list<int>::iterator it = lower_bound(l.begin(), l.end(), 3);
    6. 	if (it != l.end())cout << distance(l.begin(), it) << endl;
    7.  
    8. 	list<int>::iterator it1 = upper_bound(l.begin(), l.end(), 5);
    9. 	if (it1 != l.end())cout << distance(l.begin(), --it1) << endl;

  • 相关阅读:
    Linux（一）Linux理论、Shell
    ros gazebo相关包的安装
    【LinuxC】时间、时区，相关命令、函数
    安卓游戏开发之图形渲染技术优劣分析
    损失函数：DIOU loss手写实现
    JAVA通过COM方式(jeasyopc)接入OPC DA
    信息检索相关任务及数据集介绍
    【嵌入式开源库】使用J-Link打印日志，让你节省一个打印串口
    数据结构---AVL树
    【图论】图文详解Tarjan算法有向图缩点
  • 原文地址：https://blog.csdn.net/Jason6620/article/details/126243630