• C++ STL详解

    目录

    一：泛型编程          

    二：什么是STL

    三：STL发展

    四：STL组件

    五：容器

    六：类型成员

    七：适配器

    八：迭代器

    九：算法

    十：顺序容器

    十一：向量 vector

    十二：双端队列 queue

    十三：列表 list

    十四：关联容器

    十五：map

    十六：multimap

    十七：set

    十八：multiset

    十九：迭代器

    二十：函数对象

    二十一：已经集成的函数对象

    二十二：自定义函数对象

    二十三：标准C++库中的算法

    二十四：STL算法的头文件

    二十五：标准函数

    二十六：泛型算法例子

    二十七：自定义函数作为算法参数                

    一：泛型编程          

    1. 将程序写得尽可能通用  

    2. 将算法从特定的数据结构中抽象出来，成为通用的

    3. C++的模板为泛型程序设计奠定了关键的基础

    二：什么是STL

    STL（Standard Template Library），即标准模板库，是一个高效的C++程序库

        被容纳于C++标准程序库（C++ Standard Library）中，是ANSI/ISO C++标准中最新的也是极具革命性的一部分

        包含了诸多在计算机科学领域里常用的基本数据结构和基本算法。为广大C++程序员们提供了一个可扩展的应用框架，高度体现了软件的可复用性

    从逻辑层次来看，在STL中体现了泛型化程序设计的思想（generic programming）

         在这种思想里，大部分基本算法被抽象，被泛化，独立于与之对应的数据结构，用于以相同或相近的方式处理各种不同情形

    从实现层次看，整个STL是以一种类型参数化（type parameterized）的方式实现的

        基于模板(template)

    三：STL发展

    1971 : David R. Musser 开始倡导Generic Programming 概念

    1979 : Alexander Stepanov 创造STL

    1987 : Alex 和Musser 开发出一套Ada library

    ???? : Alex 先后在AT&T 及HP实验室以C 及C++实验大量的体系结构和算法形式。

    1992 : Meng Lee 加入称为另一位主要贡献者

    1993/11 : Alex 于ANSI/ISO C++ 会议展示

    1994 夏: STL 被纳入C++标准

    四：STL组件

    Container(容器) 各种基本数据结构

    Adapter(适配器) 可改变containers或function object接口的一种组件

    Algorithm(算法) 各种基本算法如sort、search…等

    Iterator(迭代器)* 连接containers和algorithms

    Function object(函数对象) *

    Allocator(分配器)*

    五：容器

    容器类是容纳、包含一组元素或元素集合的对象

    异类容器类与同类容器类

    顺序容器与关联容器

    七种基本容器：向量（vector）、双端队列（deque）、链表（list）、集合（set）、多重集合（multiset）、映射（map）和多重映射（multimap）

    标准容器的成员绝大部分都具有共同的名称

    六：类型成员

    七：适配器

    适配器是一种接口类

        为已有的类提供新的接口

        目的是简化、约束、使之安全、隐藏或者改变被修改类提供的服务集合

    三种类型的适配器：

        容器适配器：用来扩展7种基本容器，它们和顺序容器相结合构成栈、队列和优先队列容器

        迭代器适配器

        函数对象适配器 

    八：迭代器

    迭代器是面向对象版本的指针，它们提供了访问容器、序列中每个元素的方法

    九：算法

    C++标准模板库中包括70多个算法

        其中包括查找算法，排序算法，消除算法，记数算法，比较算法，变换算法，置换算法和容器管理等等

    这些算法的一个最重要的特性就是它们的统一性，并且可以广泛用于不同的对象和内置的数据类型

    十：顺序容器

    顺序容器的接口

    插入方法

    push_front()，push_back()，insert()，运算符“=”

    删除方法

    pop() ，erase()，clear()

    迭代访问方法

    使用迭代器

    其他顺序容器访问方法（不修改访问方法）

    front()，back()，下标[]运算符

    十一：向量 vector

    1. 向量属于顺序容器，用于容纳不定长线性序列（即线性群体），提供对序列的快速随机访问（也称直接访问）

    2. 数据结构很像一个数组，所以与其他容器相比，vector 能非常方便和高效访问单个元素，支持随机访问迭代子

    3. 向量是动态结构，它的大小不固定，可以在程序运行时增加或减少

        与数组不同，向量的内存用尽时，向量自动分配更大的连续内存区，将原先的元素复制到新的内存区，并释放旧的内存区；这是向量类的优点

    头文件：#include

    vector 基本操作

    (1)头文件

    #include

    (2)创建vector对象

    vector vec;

    (3)尾部插入数字

    vec.push_back(a);

    (4)使用下标访问元素

    cout<

    (5)使用迭代器访问元素

    vector::iterator it;

    for(it=vec.begin();it!=vec.end();it++)

    cout<<*it<

    (6)插入元素

    vec.insert(vec.begin()+i,a);在第i+1个元素前面插入a;

    (7)删除元素   

    vec.erase(vec.begin()+2);删除第3个元素

    vec.erase(vec.begin()+i,vec.end()+j);删除区间[i,j-1];区间从0开始

    (8)向量大小

    vec.size();

    vec.resize;改变大小

    (9)清空

    vec.clear();

    vector，使用示例如下

    1. #include 
    2. #include 
    3. #include 	//包含向量容器头文件
    4. using namespace std ;
    5. void main(){    
    6. 	vector<int>  A(10);	  //创建vector对象
    7. 	int n;	
    8. 	int primecount = 0, i, j;
    9. 	cout<<"Enter a value>=2 as upper limit: ";
    10. 	cin >> n;
    11. 	A[primecount++] = 2;//下标法访问元素
    12. 	for(i = 3; i < n; i++){ 
    13. 		if (primecount == A.size())	
    14. 			A.resize(primecount + 10); //改变容器大小
    15.         if (i % 2 == 0)
    16. 			continue;
    17. 		j = 3;
    18.  		while (j <= i/2 && i % j != 0)
    19. 			j += 2;        
    20. 		if (j > i/2) A[primecount++] = i;
    21. 	}
    22. 	for (i = 0; i//输出质数
    23. 		cout<<setw(5)<
    24. 		if ((i+1) % 10 == 0) //每输出10个数换行一次
    25. 			cout << endl;
    26. 	} 
    27. 	cout<
    28. }

    十二：双端队列 queue

    双端队列是一种放松了访问权限的队列

    元素可以从队列的两端入队和出队，也支持通过下标操作符“[]”进行直接访问

    与向量的对比：

        功能上：和向量没有多少区别，

        性能上：在双端队列起点上的插入和删除操作快

    头文件：#include

    十三：列表 list

    链表主要用于存放双向链表，可以从任意一端开始遍历。链表还提供了拼接（splice）操作，将一个序列中的元素从插入到另一个序列中

    对比：

    元素的插入和删除操作对 list 而言尤为高效

    与 vector 和 deque 相比，对元素的下标访问操作的低效是不能容忍的，因此 list 不提供这类操作

    头文件：#include

    列表，使用示例如下

    1. #include 
    2. #include 
    3. using namespace std ;
    4. int main(){
    5. 	list<int> Link;	//构造一个列表用于存放整数链表
    6. 	int i, key, item;    
    7. 	for(i=0;i < 10;i++)// 输入10个整数依次向表头插入{
    8. 		cin>>item;
    9. 		Link.push_front(item);
    10. 	}
    11. 	cout<<“List: ”; // 输出链表
    12. 	list<int>::iterator p=Link.begin();
    13.     while(p!=Link.end()){ //输出各节点数据，直到链表尾
    14. 		cout <<*p << "  ";
    15. 		p++;  //使P指向下一个节点
    16. 	}
    17. 	cout << endl;
    18. 	cout << "请输入一个需要删除的整数: ";
    19. 	cin >> key;
    20. 	Link.remove(key);   
    21. 	cout << "List: "; // 输出链表
    22. 	p=Link.begin();	// 使P重新指向表头
    23. 	while(p!=Link.end()){ 
    24. 		cout <<*p << "  ";
    25. 		p++; // 使P指向下一个节点
    26. 	}
    27. 	cout << endl;
    28. }

    十四：关联容器

    通过保存在数据项中的索引项，尽可能快速检索数据项

    STL标准库中只包含有序关联容器set、multiset、map、multimap

          set, multiset：数据项就是索引项； multiset允许出现重复的索引项

          map, multimap：数据项是由索引项和其他某种类型的数据组成的一对数据； multimap允许出现重复的索引项

    十五：map

    1. 增加和删除节点对迭代器的影响很小。对于迭代器来说，可以修改实值，而不能修改key

    2. 自动建立Key － value的对应。key 和 value可以是任意你需要的类型

    3. 根据key值快速查找记录，查找的复杂度基本是Log(N)，如果有1000个记录，最多查找10次，1,000,000个记录，最多查找20次

    map的构造函数

    1. 使用map得包含map类所在的头文件
         #include

    2. map对象是模板类，需要关键字和存储对象两个模板参数：
          map personnel;//用int作为索引,存储string对象

    map的成员函数

    1. map类已经对[]操作符进行了重载

    2. 插入2时,先在enumMap中查找主键为2的项，没发现，然后将一个新的对象插入enumMap，键是2，值是一个空字符串，插入完成后，将字符串赋为“Two”;

    3. 但是该方法会将每个值都赋为缺省值，然后再赋为显示的值，如果元素是类对象，则开销比较大。可以用以下insert()来避免开销

    4. 下标操作符给出了获得一个值的最简单方法：

         CString tmp = enumMap[2];

         但是,只有当map中有这个键的实例时才对，否则会自动插入一个实例，值为初始化值

    5. 我们可以使用Find()和Count()方法来发现一个键是否存在

    6. 查找map中是否包含某个关键字条目用find()方法，传入的参数是要查找的key

    7. 通过map对象的方法获取的iterator数据类型是一个std::pair对象，包括两个数据 iterator->first 和 iterator->second 分别代表关键字和存储的数据

    从map中删除元素

    1. 移除某个map中某个条目用erase()

    2. 该成员方法的定义如下

    1. iterator erase(iterator it);              //通过一个条目对象删除
    2. iterator erase(iterator first, iterator last);//删除一个范围
    3.  
    4. size_type erase(const Key& key);   //通过关键字删除

    例如：

    1. enumMap.erase(1);//删掉关键字“1”对应的条目
    2. enumMap.erase(enumMap.begin());//删掉第一个条目
    3. enumMap.erase(enumMap.begin(), enumMap.begin() + 2);//删掉起始的两个条目

    3. clear()就相当于

     enumMap.erase(enumMap.begin(), enumMap.end()); 

    map，使用示例如下

    1. #include 
    2. #include 
    3. #include 
    4. using namespace std;
    5. void main(){
    6. 	map< string, string > trans_map;
    7. 	typedef map< string, string >::value_type valType;
    8. 	trans_map.insert( valType( "001", "grateful" ));
    9. 	trans_map.insert( valType( "002", "them" ));
    10. 	trans_map.insert( valType( "003", "because" ));
    11. 	trans_map.insert( valType( "004", "no" ));
    12. 	trans_map.insert( valType( "005", "says" ));
    13. 	trans_map.insert( valType( "006", "thanks" ));
    14. 	trans_map.insert( valType( "007", "was" ));
    15.     trans_map.insert( valType( "008", "suppose" ));	
    16. 	map< string,string >::iterator it;
    17. 	cout << "Here is our transformation map: \n\n";
    18. 	for(it=trans_map.begin();it!=trans_map.end();++it)
    19. 		cout<<"key: "<<(*it).first<<"\t"<<"value: " <<(*it).second<<"\n";
    20. 	cout<<"Find Key:005"<
    21. 	it=trans_map.find("105");
    22. 	if (it==trans_map.end()){
    23. 		cout<<"not found"<
    24. 	}
    25. 	else{
    26. 		cout<<"key: "<<(*it).first <<"\t"<<"value: " <<(*it).second<<"\n";
    27. 	}
    28. }

    十六：multimap

    multimap 除了元素对的关键字不是唯一外，与 map 相似

    头文件：#include

    十七：set

    set 可以被视为只有关键字而没有相关的元素值的 map，因此 set 的用户接口也发生了微小的变化：成员类型中没有：

         typedef Key value_type;

         typedef Cmp value_compare

         操作中没有元素的下标访问操作

    头文件：#include

    十八：multiset

    multiset 除了关键字不是唯一外，与 set 相似

    头文件：#include

    十九：迭代器

    迭代器是面向对象版本的指针

         指针可以指向内存中的一个地址

         迭代器可以指向容器中的一个位置

    STL的每一个容器类模版中，都定义了一组对应的迭代器类。使用迭代器，算法函数可以访问容器中指定位置的元素，而无需关心元素的具体类型

    迭代器的类型

    1. 输入迭代器

    可以用来从序列中读取数据

    2. 输出迭代器

    允许向序列中写入数据

    3. 前向迭代器

    既是输入迭代器又是输出迭代器，并且可以对序列进行单向的遍历

    4. 双向迭代器

    与前向迭代器相似，但是在两个方向上都可以对数据遍历

    5. 随机访问迭代器

    也是双向迭代器，但能够在序列中的任意两个位置之间进行跳转

    迭代器的类型表

    迭代器，使用示例

    1. #include 
    2. #include 
    3. using namespace std;
    4. int main(){
    5. 	int i,key;
    6. 	list<int> intList;	
    7. 	list<int>::iterator it;
    8. 	cout<<"input 5 digit:";
    9. 	for(i=0;i<5;i++){
    10. 		cin>>key;
    11. 		intList.push_front(key);
    12. 	}	
    13.     cout<<"data list:"<
    14. 	it=intList.end();
    15. 	while(1){
    16. 		cout.width(6);
    17. 		cout<<*(--it);
    18. 		if(it==intList.begin())
    19. 			break;
    20. 	}
    21. 	return 0;
    22. }

    二十：函数对象

    1. 一个行为类似函数的对象，它可以没有参数，也可以带有若干参数，其功能是获取一个值，或者改变操作的状态

    2. 任何普通的函数和任何重载了调用运算符operator()的类的对象都满足函数对象的特征

    3. STL中也定义了一些标准的函数对象，如果以功能划分，可以分为算术运算、关系运算、逻辑运算三大类；为了调用这些标准函数对象，需要包含头文件

    二十一：已经集成的函数对象

    二十二：自定义函数对象

    1. #include 
    2. using namespace std;
    3. class CFunObj{
    4. public:
    5. 	void operator()(){
    6. 		cout<<"hello,function object!"<
    7. 	}
    8. 	int operator()(int i){
    9. 		cout<<"hello, function object other!"<
    10. 		return i+1;
    11. 	}
    12. private:
    13. 	int dat;
    14. };
    15.  
    16. void main(){
    17. 	CFunObj fo;
    18. 	fo();
    19. 	cout<<fo(1)<
    20. 	//CFunObj()();
    21. }

    二十三：标准C++库中的算法

    1. 算法本身是一种函数模板

    2. 不可变序列算法（non-mutating algorithms）

           不直接修改所操作的容器内容的算法

    3. 可变序列算法（mutating algorithms）

           可以修改它们所操作的容器的元素

    4. 算法部分主要由头文件，和组成

    二十四：STL算法的头文件

    是所有STL头文件中最大的一个，它是由一大堆模版函数组成的，可以认为每个函数在很大程度上都是独立的，其中常用到的功能范围涉及到比较、交换、查找、遍历操作、复制、修改、移除、反转、排序、合并等等

    体积很小，只包括几个在序列上面进行简单数学运算的模板函数，包括加法和乘法在序列上的一些操作

    中则定义了一些模板类，用以声明函数对象

    二十五：标准函数

    二十六：泛型算法例子

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7. using namespace std;
    8. int main(){
    9. 	int ia[] = { 1, 2, 3, 4, 5, 7, 9, 11 };
    10. 	vector<int> iv(ia, ia+8);
    11. 	//累加,52
    12. 	cout<<accumulate(iv.begin(),iv.end(),10)<//相邻差值
    13. 	adjacent_difference(iv.begin(),iv.end(),iv.begin());
    14. 	//复制到ostream_iterator 去, 每列印一个元素, 即加上一个空格
    15.     	copy(iv.begin(), iv.end(), ostream_iterator<int>(cout, “ ”));
    16. 	// 1 1 1 1 1 2 2 2 	
    17. 	//计算元素值为2 的个数
    18. 	cout << count(iv.begin(), iv.end(), 2) << endl; // 3
    19. 	//计算奇数元素的个数
    20. 	cout << count_if(iv.begin(), iv.end(),
    21. 	bind2nd(modulus<int>(),2)) << endl; // 5
    22. 	//从头开始填入新值7, 填3 次
    23. 	fill_n(iv.begin(), 3, 7);
    24. 	copy(iv.begin(), iv.end(), ostream_iterator<int>(cout,“ ”));
    25. 	// 7 7 7 1 1 2 2 2
    26. 	//内积, 7*7 + 7*7 + 7*7 + 1*1 + 1*1 + 2*2 + 2*2 + 2*2
    27. 	cout << inner_product(iv.begin(), iv.end(), iv.begin(),0) << endl; 
    28. 	//161
    29.     	//排序
    30. 	sort(iv.begin(), iv.end());
    31. 	copy(iv.begin(), iv.end(), ostream_iterator<int>(cout, “ ”));
    32. 	// 1 1 2 2 2 7 7 7
    33. 	//顛倒元素次序
    34. 	reverse(iv.begin(), iv.end());
    35. 	copy(iv.begin(), iv.end(), ostream_iterator<int>(cout, “ ”));
    36. 	// 7 7 7 2 2 2 1 1
    37. 	//旋转, 交换[first, middle)和[middle, last)
    38. 	rotate(iv.begin(), iv.begin()+3, iv.begin()+6);
    39. 	copy(iv.begin(), iv.end(), ostream_iterator<int>(cout, “ ”));
    40. 	// 2 2 2 7 7 7 1 1
    41. }

    二十七：自定义函数作为算法参数                

    1. #ifndef CMYCLASS_H
    2. #define CMYCLASS_H
    3. #include 
    4. class CMyClass{
    5. public:
    6. 	CMyClass();
    7. 	CMyClass(string name,int age);
    8. 	friend bool Less(const CMyClass &num,const CMyClass &myclass);
    9. 	bool operator==(const CMyClass &myclass);
    10. 	string &GetName();
    11. 	int GetAge();
    12. private:
    13. 	string m_name;
    14. 	int m_age;};
    15. #endif
    1. CMyClass::CMyClass(){
    2. 	m_name="";
    3. 	m_age=12;
    4. }
    5. CMyClass::CMyClass(string name,int age)
    6. {	m_name=name;
    7. 	m_age=age;
    8. }
    9. bool CMyClass::operator==(const CMyClass &myclass){
    10. 	return m_name==myclass.m_name;
    11. }
    12. string & CMyClass::GetName(){
    13. 	return m_name;}
    14. int CMyClass::GetAge(){
    15. 	return m_age;}
    1. #include "MyClass.h"
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7. using namespace std;
    8. bool Less(const CMyClass &num,const CMyClass &myclass){
    9. 	return num.m_name
    10. }
    11. void PrintMyClass(CMyClass &myclass){
    12. 	cout<<"name:"<GetName()<<"\t age:"<GetAge()<
    13. }
    14. bool SearchByName(CMyClass &myclass){
    15. 	return myclass.GetName()=="AAAAZ";
    16. }
    1. void  main(){
    2. 	CMyClass myclass;
    3. 	vector vec;
    4. 	vec.push_back(CMyClass("AAAA",12));
    5. 	vec.push_back(CMyClass("DFKASDF",12));
    6. 	vec.push_back(CMyClass("ASDFSAFA",12));
    7. 	vec.push_back(CMyClass("Z",12));
    8. 	vec.push_back(CMyClass("AAAAZ",12));
    9. 	vec.push_back(CMyClass("DFKSADFZ",12));
    10. 	sort(vec.begin(),vec.end(),Less);
    11. //	for (vector::iterator it=vec.begin();it!=vec.end();it++){
    12. //		cout<GetName()<
    13. 	for_each(vec.begin(),vec.end(),PrintMyClass);
    14. 	vector::iterator r=find_if(vec.begin(),vec.end(),SearchByName);
    15. 	cout<<(*r).GetName()<
    16. }
  • 相关阅读:
    Python：Jupyter：OSError: Initializing from file failed
    深究数据库E-R模型设计
    利用bert4keras实现多任务学习
    HDI的盲孔设计，你注意到这个细节了吗？
    Python运算符 成员运算符、身份运算符，三目运算符
    Springboot 集成 Redis集群配置公网IP连接报私网IP连接失败问题
    内存概念，进程运行的基本原理（指令，逻辑地址与物理地址的转换，程序运行的过程)
    853. 车队【力扣】
    GitHub图床整合JAVA、PicGo
    雷鸟Air+理想L9：开启车内AR沉浸观影新体验
  • 原文地址：https://blog.csdn.net/m0_56051805/article/details/127131897