C++ STL 标准模板库

news/2025/3/13 15:36:49/

C++ STL 标准模板库

标准容器

顺序容器

vector

vector 向量容器

底层数据结构：动态开辟的数组，每次以原来空间大小的2倍进行扩容。采用allocator进行空间开辟和释放，对象创建和析构的分离。具体如C++模板学习笔记中简要实现C++中的vector。

增加：push_back、insert。

删除：pop_back、erase。

查询：operator[]、iterator、find、for-each。注意连续insert和erase中出现的迭代器失效问题。

其他：size、empty、reserve（预留空间）、resize（扩容）、swap（两个容器进行元素替换）。

reserve函数是给容器预留空间，并不会进行容器填充，容器的空间元素大小size为原来的大小。

resize函数是给容器开辟指定大小的内存空间，会对容器中的值进行添加，如果容器内部的元素是int，那么默认添加的元素为0，容器的空间元素大小size为扩容后的大小。

deque

deque 双端队列机制

#define MAP_SIZE=2; #define QUE_SIZE=4096/sizeof(T);

底层数据结构是一个动态开辟的二维数组（类似于邻接表），一维数组从2开始，以2倍的方式进行扩容，每次扩容后，原来的第二维数组，从第一维数组的下标oldsize/2开始存放，上下行都预留相同的空行，方便deque首尾元素的添加。

增加：push_back、push_front、insert

删除：pop_back、pop_front、erase

查询：iterator（连续erase和insert考虑容器失效问题）

deque底层内存是不是连续的？并不是，deque的底层是动态开辟的二维数组，第二维上是连续的，第一维上是不连续的。

list

list 链表容器

底层数据结构是双向循环链表 pre-data-next

增加：push_back、push_front、insert

删除：pop_back、pop_front、erase

查询：iterator（连续erase和insert考虑容器失效问题）

vector和deque的区别

可以从以下角度进行分析：

  1. 底层数据结构。vector是连续的动态数组；deque是第二维连续的动态二维数组。
  2. 前中后插入的时间复杂度。vector前中后插入的时间分别是O(n)/O(n)/O(1)，deque前中后插入的时间复杂度分别是O(1)/O(n)/O(1)。
  3. 对内存的使用效率。vector必须是连续的空间，而deque只需要第二维上是连续的就行。
  4. 中间进行insert或者erase，vector效率稍微高一点，因为vector底层内存是连续的，deque因为空间是不连续的，会涉及内存转化等情况。

vector和list的区别

可以从以下角度进行分析：

  1. 底层数据结构。vector是连续的数组；list的双向循环链表。
  2. 查找和增加、删除的时间复杂度。vector的增加和删除O(n)，查询O(n)，随机访问O(1)；链表的增加和删除O(1)（可能需要涉及搜索时间，具体情况具体分析），查询O(n)，随机访问O(n)。

容器适配器

适配器的基本概念：

1、适配器底层没有自己的数据结构，它是另外一个容器的封装，它的方法全部由底层依赖的容器进行实现。
2、没有实现自己的迭代器。

自定义实现的stack容器：

#include<iostream>
#include<deque>
using namespace std;template<typename T,typename Container=deque<T>>
class Stack
{
public:void push(T &val) { con.push_back(val); }void pop() { con.pop_back(); }T top() const { return con.back(); }private:Container con;
};

容器适配器主要有stack、queue、priority_queue。

stack

主要方法有：push、pop、top、empty、size等

主要特点：先进后出

采用deque实现

queue

主要方法有：push、pop、front、back、empty、size等

主要特点：先进先出

采用deque实现

priority_queue

主要方法和stack的方法一致：push、pop、top、empty、size等

主要特点：和queue的不同在于，优先级高的先出队，并不是先进先出。

采用vector实现

为什么stack和queue都采用deque实现？

  1. vector初始内存效率很低，默认是0-1-2-4-8- ···-2^n，而deque一开始就是4096/sizeof(T)。
  2. queue需要支持头尾插入，所以采用deque效率高。
  3. vector需要大量的连续的内存空间，而deque只需要分段的内存，当存在大量数据时，deque效率会高一点。

为什么priority_queue采用vector实现？

  1. priority_queue的是一种大根堆的结构，一般情况下都是在一段连续的空间或者内存上进行保存。而deque在一维上不是连续的，所以就会导致很难存储大根堆树。

关联容器

常用方法：insert(val)、iterator、erase(iterator)、erase(key)。还有find的方法，查找对应的元素。

无序关联容器

哈希链式表，增删查的时间复杂度为O(1)，也需要注意迭代器失效的问题。set是无序的。

unordered_set

不会存储key值重复的元素

unordered_multiset

会存储key值重复的元素

unordered_set<int> set1;
for (int i = 0; i < 20;++i)
{set1.insert(rand() % 100 + 1);
}
cout << "size:" << set1.size() << endl;
cout << "count 15:" << set1.count(15) << endl;for (int i = 0; i < 50;i++)
{set1.insert(i);
}
auto it1 = set1.begin();
for (; it1 != set1.end();++it1)
{cout << *it1 << " ";
}
cout << endl;
unorder_map

不允许key重复，如果插入过程中会出现key重复情况，那么就会对原来key对应的value的进行替换。

unorder_multimap

允许key可以重复。

map的operator[]重载函数存在一个情况，在查询时key存在的情况下返回value，不存在的情况下会自动创建一个key和value(默认为空)。

有序关联容器

红黑树，增删查时间复杂度为O(log2n)，采用树进行存储

set
multiset
map
multimap

迭代器

迭代器iterator，一般容器内部都包含了iterator。

iterator：普通正向迭代器。一般是begin()/end()。
const_iterator：常量正向迭代器，返回值只能使用，不能修改。operator*操作符重载返回的是常量 const T& operator*。
reverse_iterator：反向迭代器。和前面两个迭代器不同的是，一般是rbegin()/rend()。
const_reverse_iterator：常量反向迭代器。

#include<iostream>
#include<vector>
using namespace std;int main()
{vector<int> v = {2, 3, 4, 6, 9, 8, 4, 2, 4, 5};auto it = v.begin();for (; it != v.end();++it){cout << *it << " ";// *it = 10;//普通正向迭代器可以修改其值}cout << endl;vector<int>::const_iterator c_it = v.begin();for (; c_it != v.end(); ++c_it){cout << *c_it << " ";// *c_it = 10;//常量正向迭代器无法修改其值}cout << endl;vector<int>::reverse_iterator r_it = v.rbegin();//获取最后一个元素的迭代器for (; r_it != v.rend();++r_it){cout << *r_it << " ";// *r_it = 10;//可以修改其值}cout << endl;vector<int>::const_reverse_iterator cr_it = v.rbegin();for (; cr_it != v.rend();++cr_it){cout << *cr_it << " ";}cout << endl;return 0;
}

函数对象

通过函数指针调用函数，是没有办法内联的，效率很低，因为有函数调用的开销

C++的函数对象，实现了operator()操作符重载

通过函数对象调用operator()，可以省略函数调用的开销，比通过函数指针调用函数（不能用内敛调用），效率更高。

函数对象是用类生成的，所以可以添加许多相关的成员变量，用来记录函数对象调用使用的更多信息。

函数调用类似于C语言的函数指针。

using关键字，对函数更改名字，类似于as方法。

#include<iostream>
using namespace std;template <typename T>
class greater2
{public:bool operator()(T&x,T&y)//二元函数对象{return x > y;}
};
template<typename T>
bool greater1(T&x,T&y)
{return x > y;
}
template<typename T,typename Compare>
bool compare(T x,T y,Compare comp)
{//Compare其实就是调用的对象或者函数实现内部功能return comp(x, y);
}
int main()
{//函数调用实现comparecout << compare<int>(10, 20, greater1<int>) << endl;//对象调用实现comparecout << compare<char>('a', 'c', greater2<char>()) << endl;return 0;
}

泛型算法

C++泛型算法都放在#include<algorithm>头文件内部。常见的泛型算法有sort、find、find_if、count、for_each、binary_search等

泛型算法的特点：

  1. 泛型算法的参数接收的都是迭代器。
  2. 泛型算法的参数还可以接收函数对象（C语言函数指针）。
int arr[] = {10, 20, 30, 34, 21, 12, 35, 32, 11, 22};
vector<int> vec(arr, arr + sizeof(arr) / sizeof(arr[0]));for(auto i:vec)
{cout << i << " ";
}
cout << endl;sort(vec.begin(), vec.end());for (auto i : vec)
{cout << i << " ";
}
cout << endl;if(binary_search(vec.begin(), vec.end(), 22))
{cout << "22 is existed" << endl;
}
else
{cout << "22 isn't existed" << endl;
}//传入函数对象greater，改变容器的排序方式的比较方式
sort(vec.begin(), vec.end(), greater<int>());
for (auto i : vec)
{cout << i << " ";
}
cout << endl;

绑定器 + 二元函数对象 -> 一元函数对象

绑定器存在C++的#include<functional>头文件中。

bind1st：把二元函数对象的operator()的第一个形参进行绑定起来。
bind2nd：把二元函数对象的operator()的第二个形参进行绑定起来。

//find_if是查找一个元素，需要一个一元函数对象
//查找第一个小于31的元素，并将其插入到其前面，greate a>b a=31
auto it2 = find_if(vec.begin(), vec.end(), bind1st(greater<int>(),31));
vec.insert(it2, 31);for (auto i : vec)
{cout << i << " ";
}
cout << endl;//在第一个小于19的前面插入19  a<b b=19
auto it3 = find_if(vec.begin(), vec.end(), bind2nd(less<int>(), 19));
vec.insert(it3, 19);for (auto i : vec)
{cout << i << " ";
}
cout << endl;

lambda表达式，类似于函数对象[](形参列表)->函数返回值{函数体}。


http://www.ppmy.cn/news/1066269.html

相关文章

ethers.js5：与智能合约交互

ethers.js5：与智能合约交互

创建可写Contract变量 声明可写的Contract变量的规则： const contract = new ethers.Contract(address, abi, signer) 其中address为合约地址，abi是合约的abi接口，signer是wallet对象。注意，这里你需要提供signer，而在声明可读合约时你只需要提供provider。 你也可以利…
阅读更多...
【管理运筹学】第 6 章 | 运输问题（2，表上作业法 | 初始可行解的确定）

【管理运筹学】第 6 章 | 运输问题（2，表上作业法 | 初始可行解的确定）

文章目录 引言二、表上作业法2.1 初始基可行解的确定2.1.1 最小元素法2.1.2 伏格尔法 写在最后 引言 承接前文&#xff0c;在对运输问题有了基本的了解后&#xff0c;我们开始深入学习表上作业的具体内容。 二、表上作业法 2.1 初始基可行解的确定 2.1.1 最小元素法 基本思…
阅读更多...
信息化发展1

信息化发展1

信息的定义 1 、信息论的奠基者香农认为&#xff1a; 信息是用来消除随机不定性的东西。 2 、信息的目的是用来“消除不确定的因素” 。信息是抽象于物质的映射集合。 3 、香农用概率来定量描述信息的公式如下&#xff1a; 信息的特征 客观性&#xff1a;信息是客观事物在人…
阅读更多...
4、什么是NoSQL

4、什么是NoSQL

4、什么是NoSQL NoSQL NoSQL Not Only SQL&#xff0c;就是不仅仅是SQL的意思 泛指非关系型数据库&#xff0c;随着web2.0的诞生&#xff01;传统的关系型数据库很难对付web2.0时代&#xff0c;因为web2.0时代又很多数据大爆炸新生的产物比如视频、音乐、大数据产生的其他的数…
阅读更多...
js 类、原型及class

js 类、原型及class

js 一直允许定义类。ES6新增了相关语法(包括class关键字)让创建类更容易。新语法创建的类和老式的类原理相同。js 的类和基于原型的继承机制与Java等语言中的类和继承机制有着本质区别。 1 类和原型 类意味着一组对象从同一个原型对象继承属性。因此&#xff0c;原型对象是…
阅读更多...
java-Optional 类详解

java-Optional 类详解

目录 前言 Optional的构造方法 Optional的相关方法介绍 isPresent用法&#xff1a; get用法&#xff1a; filter用法&#xff1a; orElse用法&#xff1a; orElseGet用法 orElseThrow用法 map用法 flatMap用法&#xff1a; 前言 Optional 类是java8的新特性&#xff0…
阅读更多...
Java之BigDecimal系列--去掉小数末尾多余的0

Java之BigDecimal系列--去掉小数末尾多余的0

原文网址&#xff1a;Java之BigDecimal系列--去掉小数末尾多余的0_IT利刃出鞘的博客-CSDN博客 简介 说明 本文介绍Java去掉BigDecimal小数末尾多余的0的方法。 概述 BigDecimal提供了stripTrailingZeros()方法可以实现去掉小数末尾的 0。 调用了stripTrailingZeros()再调…
阅读更多...
【Flutter】Flutter 使用 toggle_switch 实现切换按钮

【Flutter】Flutter 使用 toggle_switch 实现切换按钮

【Flutter】Flutter 使用 toggle_switch 实现切换按钮 文章目录 一、前言二、安装和基本使用三、Toggle Switch 的基础示例四、Toggle Switch 的高级用法五、实际业务中的完整示例六、总结 一、前言 你好&#xff0c;我是小雨青年&#xff0c;今天我要为大家介绍一个非常实用的…
阅读更多...
最新文章

Copyright @ 2022~2023