C++ STL总结

C++ STL总结

文章目录

​​一、vector​​

​​常用函数​​​​初始化​​​​插入​​​​遍历​​​​删除​​​​其他函数​​

​​二、Map​​

​​初始化​​​​插入​​​​查找​​​​删除​​​​遍历​​​​大小​​​​判空​​​​不常用的函数​​

​​三、queue​​

​​常用函数​​​​初始化​​​​入队和出队​​​​返回队首、队尾元素​​​​遍历​​

​​四、deque​​

​​增加​​​​删除​​​​查询搜索​​

​​五、stack​​

​​常用函数​​

​​六、vector、list、deque之间的对比​​​​七、容器空间适配器​​​​八、容器适配器​​​​九、关联容器​​​​十、常用迭代器​​​​十一、函数对象​​

一、vector

常用函数

begin()：返回指向vector首部的迭代器，指向第一个元素end()：返回指向vector尾部的迭代器，并不指向最后一个元素rbegin()：返回指向vector尾部的迭代器，指向最后一个元素rend()：返回指向vector首部的迭代器，并不指向第一个元素pop_back()：删除最后一个元素，无返回值push_back()：在尾部加入一个元素erase()：删除指定位置元素，返回下一个元素的位置(传入迭代器，返回迭代器)erase(begin_pos,end_pos)：删除[begin_pos,end_pos)之间的元素，返回下一个元素的位置(传入迭代器，返回迭代器)assign(begin_iter, end_iter)：将区间中的数据赋值给向量，左闭右开assign(n, elem)：将n个elem的拷贝赋值给向量size()：返回向量中元素数量front()：返回第一个元素back()：返回最后一个元素v1.swap(v2)：将v1和v2在内存中的指向互换，也就达到了两向量元素互换的效果empty()：判空clear()：清除所有数据at(int num)：返回第num个数据insert(pos_iter, elem)：在pos_iter位置插入一个elem数据insert(pos_iter, n, elem)：在pos_iter位置插入n个elem数据reserve(int n)：给容器底层预留n个元素空间(vec.size()==0 && vec.capacity()==n)resize(int n)：不仅给容器预留n个空间，此时容器内也会有n个元素(vec.size()==n && vec.capacity()==n)

注： 使用insert、erase进行插入和删除元素的时候，一定要用迭代器接收返回值，否则使用后迭代器失效

初始化

v1; // 此时向量中没有元素 vector v1(10); // 向量中10个元素，全为0 vector v1(10,1); // 向量中10个元素，全为1 vector v1(v2); //将v2拷贝给v1，实际上是用v2的size以及数据对v1进行初始化，与capacity无关。 vector v1( v2.begin() , v2.end() ); vector v1 = {1, 2, 3};

插入

insert() 和 push_back()

.insert(v1.begin(), 10);//在首部插入一个10 v1.insert(v1.begin(),3, 9);//在首部插入3个9 v1.push_back(1);//在尾部插入1

遍历

//for...each... for(int i : v1){ cout<::iterator it = v2.begin(); it != v2.end(); it++) cout << *it << endl; //反向迭代器，反向输出 for (vector::reverse_iterator it = v1.rbegin(); it != v1.rend(); it++) cout << *it << endl;

删除

erase() 和 pop_back() 和clear()

.erase(v2.begin());//删除首部元素 v1.erase(v1.begin(), v1.end()-2);//删除区间的元素，其他元素前移，左闭右开 v1.pop_back()//删除尾部元素 v1.clear()//删除所有元素

其他函数

.size(); v1.empty(); v1.assign(v2.begin(), v2.end()-1);//将v2指定区间内的元素赋值给v1 v1.assign(5, 10);//v1存放的元素变成5个10 reverse(v1.begin(), v1.end());//将v1逆置，头文件中的逆置函数

二、Map

有序、红黑树、不可重复

常用函数：

begin()返回指向map头部的迭代器end()返回指向map末尾的迭代器rbegin()返回一个指向map尾部的逆向迭代器rend()返回一个指向map头部的逆向迭代器clear(）删除所有元素count()根据key返回指定元素出现的次数，返回值只能是0或1empty()判空erase()根据key删除一个元素find()根据返回key返回迭代器，若没找到就返回指向map尾部的迭代器insert()插入元素lower_bound()返回键值 >= 给定值的最小iteratorupper_bound()返回键值 > 给定值的最小iteratorsize()返回map中元素的个数

初始化

map mp = {{"a", 1}, {"b", 2}, {"c", 3}};

插入

map mp;mp["a"] = 1;// 同 mp.insert(pair("a", 1));mp["b"] = 2;mp["c"] = 3;mp["d"]; // 等价于mp["d"] = string()

map mp;mp.insert(pair("a", 1));mp.insert({"b", 2});mp.insert(make_pair("c", 3));

查找

find() ：根据返回key返回迭代器，若没找到就返回指向map尾部的迭代器 count() ：返回键值出现的次数，只返回0或1

map::iterator iter = mp.find("b");//根据键值返回迭代器cout<first<<":"<second<

删除

erase() ：根据key删除元素，删除成功返回1，删除失败返回0 clear() : 清除map中的所有元素

mp.erase("a");//返回1mp.erase("aa");//返回0mp.clear();//size()变为0

遍历

iter->first ： 打印键 iter->second ： 打印值

for(map::iterator iter = mp.begin(); iter!=mp.end(); iter++){ cout<first<<":"<second<& p : mp){ cout<

大小

size() : 返回map中键值对个数 max_size() : 返回map最大容纳键值对的数量

mp.size();//返回键值对个数mp.max_size();//256204778801521550

判空

mp.empty()

不常用的函数

lower_bound() 返回键值 >= 给定值的最小iteratorupper_bound() 返回键值 > 给定值的最小iterator

可参考​​这里​​

三、queue

常用函数

empty()//判空，返回boolpush()// 从队尾入队列，无返回值pop()// 从队首出队列，无返回值front()// 返回队首元素back()// 返回队尾元素size()// 返回队列元素个数

初始化

queue q;//定义一个空队列

入队和出队

q.push(1);//入队列q.push(2);q.push(3);q.pop(); //队首元素出队列

检查 pop 操作是否只是头指针移动，而元素还在

if(*(&(q.front())-1) != 1){ cout<<"已经移除1"<

运行结果：

返回队首、队尾元素

q.front();//返回队首元素q.back();//返回队尾元素

遍历

由于STL没有提供遍历队列的操作，只能先找到队首元素的地址，再挨个往后访问

for(int i=0; i

四、deque

deque是双端队列容器，底层数据是动态扩容的二维数组。一维数组从2开始，以2倍的方式进行扩容，每次扩容后原来第二维的数组从新的第一维数组的下标​​oldsize/2​​开始存放，上下留出相同的空间，方便deque首尾入队。

由于是双端队列，所以最开始的时候，​​first​​​ 和 ​​last​​其实是指向相同地方的

扩容后：

增加

push_back(num)push_front(num)insert(iter, num)

删除

pop_back(num)pop_front(num)erase(iter)

查询搜索

连续insert和erase要考虑迭代器失效的问题

list的底层数据结构是一个双向循环链表，操作和deque一模一样

五、stack

常用函数

入栈：如s.push(x);出栈:如 s.pop()，注：出栈操作只是删除栈顶的元素，并不返回该元素。访问栈顶：如s.top();判断栈空：如s.empty()，返回bool值访问栈中的元素个数，如s.size()

六、vector、list、deque之间的对比

​​vector​​​和​​deque​​之间的区别？

底层数据结构：动态扩容的一维数组和动态扩容的二维数组前中后删除元素的时间复杂度内存使用效率：vector需要的内存空间完全连续，deque只要求部分连续即可中间插入和删除的时候，vector由于内存完全连续，移动元素方便。而deque内存不完全连续，元素移动不太方便。

​​vector​​​和​​list​​​之间的区别？ 根据底层数据结构（动态扩容的一维数组 和 双向循环链表）对比访问，增删的效率即可

七、容器空间适配器

容器的空间配置器allocator是将内存开辟、内存释放、对象构造、对象析构四个操作分开，而不是像​​new​​​一样把内存开辟和对象构造同时做，像​​delete​​一样把内存释放和对象析构同时做。

// 定义容器的空间配置器struct Allocator { // 1. 开辟空间 T* allocator(size_t size) { return (T*)malloc(sizeof(T) * size); } // 2. 释放空间 void deallocator(void* p) { free(p); } // 3. 构造对象 void construct(T* p, const T& val) { // 定位new，在指定内存上构造一个值为val的对象，调用拷贝构造 new (p) T(val); } // 4. 负责对象析构 void destroy(T* p) { p->~T(); }};

说一下STL容器的swap：

若两个容器使用的空间配置器相同，即内存管理方式一样，那么两个容器交换资源就仅仅就是交换一下成员变量（也可以理解为交换指针的指向），没有开辟空间，数据拷贝等操作，效率较高。若两个容器使用的空间配置器不同，即内存管理方式不一样，此时交换资源就需要开辟空间，拷贝数据，效率低，这在实际使用中属于少数情况

八、容器适配器

什么是容器适配器？

适配器底层没有实现自己的数据结构，它是另外一个容器的封装，它的方法全部依赖底层的容器实现，就是一种代理。容器适配器没有实现自己的迭代器

​​stack​​​的底层就是封装了​​deque​​​，也即​​stack​​就是容器适配器

template>class Stack {public: void push(const T& val) { con.push_back(val); } void pop() { con.pop_back(); } T top() const { return con.back(); };private: Container con;};

常见的容器适配器有：stack(deque)、queue(deque)、priority_queue(vector、大顶堆)

面试官：stack和queue为什么依赖deque，而不依赖vector？

vector的内存利用效率太低；vector：0->1->2->4->8，而deque是4096/sizeof(T)，deque无需很多的内存扩容的操作对于queue来说，需要进行头删尾插的操作；vector只在尾部操作快，头部操作很慢。而deque则两头操作都是O(1)vector需要大片的连续内存，而deque只要求部分内存连续即可。当存储数据较多是，deque的内存效率更高。

面试官：priority_queue为什么依赖vector，而不依赖deque？

由于priority_queue底层是一个大顶堆，所有节点通过索引访问，这需要连续内存，即依赖vector

九、关联容器

无序关联容器（底层哈希表）

#include#include#includeusing namespace std;int main() { unordered_set set1; // 1. 插入 for (int i = 0; i < 20; i++) { set1.insert(rand() % 20); } // cout << set1.size() << endl; // < 20 // cout << set1.count(5) << endl; // 0或1 // 2. 遍历，迭代器可访问所有容器 for (auto iter = set1.begin(); iter != set1.end(); iter++) { cout << *iter << " "; } cout << endl; // for_each，底层就是用迭代器 for (int v : set1) { cout << v << " "; } cout << endl; // 3. 删除 erase(iter)， erase(key) for (auto iter = set1.begin(); iter != set1.end(); ) { if (*iter == 10) { // erase后iter失效，删除后从当前位置开始比较，不用++ iter = set1.erase(iter); } else { iter++; } } // 4. 查找find(key)，找到返回对应位置iter，否则返回end() auto iter = set1.find(20); if (iter != set1.end()) { set1.erase(iter); } return 0;}

有序关联容器（底层红黑树）

set

有序、不可重复

#include#include // set multiset 红黑树using namespace std;class Student {public: Student(int id, string name) :_id(id), _name(name) {}; bool operator<(const Student& stu) const{ return _id < stu._id; }private: int _id; string _name; friend ostream& operator<<(ostream& out, const Student& stu);};ostream& operator<<(ostream& out, const Student& stu) { out << stu._id << " " << stu._name << endl; return out;}int main() { set set1; set1.insert(Student(10, "张三")); set1.insert(Student(30, "李二")); set1.insert(Student(20, "王五")); for (const Student& stu : set1) { cout << stu; } return 0;}

map

有序、不可重复

#include#include

十、常用迭代器

vec; vector::const_iterator it1 = vec.begin(); // 可读不可写，子类 vector::iterator it1 = vec.begin(); // 可读可写，派生类 vector::const_reverse_iterator r_beg = vec.rbegin(); vector::reverse_iterator r_beg = vec.rbegin(); // 返回最后一个元素的反向迭代器表示 vector::const_reverse_iterator r_end = vec.rend(); vector::reverse_iterator r_end = vec.rend(); // 返回首元素前驱的反向迭代器表示

十一、函数对象

C语言中的函数指针实现函数调用，有函数开销

#includeusing namespace std;templatebool my_greater(const T& a, const T& b) { return a > b;}templatebool my_less(const T& a, const T& b) { return a < b;}templatebool compare(const T& a, const T& b, Compare comp) { // 函数指针调用，有函数开销，无法内联 // 编译过程中，看到函数指针comp，无法知道调用的是哪个函数，所以无法写死，只能动态地从函数地址取出函数 return comp(a, b);}int main() { cout << compare(10, 20, my_greater); return 0;}

把有​​operator()​​运算符重载函数的对象，称作函数对象，也叫仿函数

可以确定调用函数， 完全可以内联，省去函数调用开销

#includeusing namespace std;templateclass my_greater {public: bool operator()(const T& a, const T& b) { return a > b; }};templateclass my_less {public: bool operator()(const T& a, const T& b) { return a < b; }};templatebool compare(const T& a, const T& b, Compare comp) { //可以确定调用函数， 完全可以内联，省去函数调用开销 return comp(a, b);}int main() { cout << compare(10,20, my_greater()); return 0;}

使用函数对象改变priority_queue的排序方式

int main() { // 降序，默认less priority_queue q1; // 升序 // using MinQueue = priority_queue, greater>; priority_queue, greater> q2; // 升序，默认less set s1; // 降序 set> s2; return 0;}

#include#include#include#includeusing namespace std;int main(){ /* find_if需要一元函数对象 找第一个大于100的数字 greater:a>b less:a vec = { 5,432,5,7,6586,7876,234,14,1 }; // 找到返回对应迭代器，找不到返回end // auto iter = find_if(vec.begin(), vec.end(), bind1st(less(), 100)); auto iter = find_if(vec.begin(), vec.end(), [](int val)->bool {return val > 100; } // lambda表达式 ); vec.insert(iter, 100); for (int i : vec) { cout << i << " "; } cout << endl; for_each(vec.begin(), vec.end(), [](int val)->void { if (val % 2 == 0) { cout << val << " "; } } ); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。