门户网站模块,应用软件下载app,北京软件开发公司找和丰软件专业,wordpress注册增加性别选项原文网址
参考网址
C语言中文网
请你来说一下map和set有什么区别#xff0c;分别又是怎么实现的#xff1f;
map和set都是C的关联容器#xff0c;其底层实现都是红黑树#xff08;RB-Tree#xff09;。由于 map 和set所开放的各种操作接口#xff0c;RB-tree 也都提供…原文网址
参考网址
C语言中文网
请你来说一下map和set有什么区别分别又是怎么实现的
map和set都是C的关联容器其底层实现都是红黑树RB-Tree。由于 map 和set所开放的各种操作接口RB-tree 也都提供了所以几乎所有的 map 和set的操作行为都只是转调 RB-tree 的操作行为。
map和set区别在于
1map中的元素是key-value关键字—值对关键字起到索引的作用值则表示与索引相关联的数据Set与之相对就是关键字的简单集合set中每个元素只包含一个关键字。2set的迭代器是const的不允许修改元素的值map允许修改value但不允许修改key。其原因是因为map和set是根据关键字排序来保证其有序性的如果允许修改key的话那么首先需要删除该键然后调节平衡再插入修改后的键值调节平衡如此一来严重破坏了map和set的结构导致iterator失效不知道应该指向改变前的位置还是指向改变后的位置。所以STL中将set的迭代器设置成const不允许修改迭代器的值而map的迭代器则不允许修改key值允许修改value值。3map支持下标操作set不支持下标操作。map可以用key做下标map的下标运算符[ ]将关键码作为下标去执行查找如果关键码不存在则插入一个具有该关键码和mapped_type类型默认值的元素至map中因此下标运算符[ ]在map应用中需要慎用const_map不能用只希望确定某一个关键值是否存在而不希望插入元素时也不应该使用mapped_type类型没有默认值也不应该使用。如果find能解决需要尽可能用find。
请你来介绍一下STL的allocaotr
STL的分配器用于封装STL容器在内存管理上的底层细节。在C中其内存配置和释放如下new运算分两个阶段(1)调用::operator new配置内存;(2)调用对象构造函数构造对象内容delete运算分两个阶段(1)调用对象析构函数(2)调用::operator delete释放内存为了精密分工STL allocator将两个阶段操作区分开来内存配置有alloc::allocate()负责内存释放由alloc::deallocate()负责对象构造由::construct()负责对象析构由::destroy()负责。同时为了提升内存管理的效率减少申请小内存造成的内存碎片问题SGI STL采用了两级配置器当分配的空间大小超过128B时会使用第一级空间配置器当分配的空间大小小于128B时将使用第二级空间配置器。第一级空间配置器直接使用malloc()、realloc()、free()函数进行内存空间的分配和释放而第二级空间配置器采用了内存池技术通过空闲链表来管理内存。
参考链接
标准库 STL Allocator能做什么C中std::allocator的使用第10篇:C 堆内存管理器-allocator请你来说一说STL迭代器删除元素
这个主要考察的是迭代器失效的问题。1.对于序列容器vector,deque来说使用erase(itertor)后后边的每个元素的迭代器都会失效但是后边每个元素都会往前移动一个位置但是erase会返回下一个有效的迭代器2.对于关联容器map set来说使用了erase(iterator)后当前元素的迭代器失效但是其结构是红黑树删除当前元素的不会影响到下一个元素的迭代器所以在调用erase之前记录下一个元素的迭代器即可。3.对于list来说它使用了不连续分配的内存并且它的erase方法也会返回下一个有效的iterator因此上面两种正确的方法都可以使用。
请你说一说STL中MAP数据存放形式
红黑树。unordered map底层结构是哈希表
请你讲讲STL有什么基本组成
容器、算法、迭代器、函数对象、适配器、内存分配器这 6 部分构成其中后面 4 部分是为前 2 部分服务的
STL的组成含义容器一些封装数据结构的模板类例如 vector 向量容器、list 列表容器等。算法STL 提供了非常多大约 100 个的数据结构算法它们都被设计成一个个的模板函数这些算法在 std 命名空间中定义其中大部分算法都包含在头文件 algorithm 中少部分位于头文件 numeric 中。迭代器在 C STL 中对容器中数据的读和写是通过迭代器完成的扮演着容器和算法之间的胶合剂。函数对象如果一个类将 () 运算符重载为成员函数这个类就称为函数对象类这个类的对象就是函数对象又称仿函数。适配器可以使一个类的接口模板的参数适配成用户指定的形式从而让原本不能在一起工作的两个类工作在一起。值得一提的是容器、迭代器和函数都有适配器。内存分配器为容器类模板提供自定义的内存申请和释放功能由于往往只有高级用户才有改变内存分配策略的需求因此内存分配器对于一般用户来说并不常用。
头文件
iterator functional vector deque list queue stack set map algorithm numeric memory utility
注意事项
分配器给容器分配存储空间算法通过迭代器获取容器中的内容仿函数可以协助算法完成各种操作配接器用来套接适配仿函数
参考链接
C STL基本组成6大组件13个头文件
请你说说STL中map与unordered_map
Map映射
map 的所有元素都是 pair同时拥有实值value和键值key。pair 的第一元素被视为键值第二元素被视为实值。所有元素都会根据元素的键值自动被排序。不允许键值重复。底层实现红黑树适用场景有序键值对不重复映射
Multimap
多重映射。multimap 的所有元素都是 pair同时拥有实值value和键值key。pair 的第一元素被视为键值第二元素被视为实值。所有元素都会根据元素的键值自动被排序。允许键值重复。底层实现红黑树适用场景有序键值对可重复映射
请你说一说vector和list的区别应用越详细越好
Vector
连续存储的容器动态数组在堆上分配空间本质是链表底层实现数组两倍容量增长vector 增加插入新元素时如果未超过当时的容量则还有剩余空间那么直接添加到最后插入指定位置然后调整迭代器。如果没有剩余空间了则会重新配置原有元素个数的两倍空间然后将原空间元素通过复制的方式初始化新空间再向新空间增加元素最后析构并释放原空间之前的迭代器会失效。
性能
访问O(1)插入在最后插入空间够很快在最后插入空间不够需要内存申请和释放以及对之前数据进行拷贝。在中间插入空间够内存拷贝在中间插入空间不够需要内存申请和释放以及对之前数据进行拷贝。删除在最后删除很快在中间删除内存拷贝适用场景经常随机访问且不经常对非尾节点进行插入删除。
List
动态链表在堆上分配空间每插入一个元数都会分配空间每删除一个元素都会释放空间。底层双向链表
性能
访问随机访问性能很差只能快速访问头尾节点。插入很快一般是常数开销删除很快一般是常数开销适用场景经常插入删除大量数据
区别
1vector底层实现是数组list是双向 链表。2vector支持随机访问list不支持。3vector是顺序内存list不是。4vector在中间节点进行插入删除会导致内存拷贝list不会。5vector一次性分配好内存不够时才进行2倍扩容list每次插入新节点都会进行内存申请。6vector随机访问性能好插入删除性能差list随机访问性能差插入删除性能好。
应用
vector拥有一段连续的内存空间因此支持随机访问如果需要高效的随即访问而不在乎插入和删除的效率使用vector。list拥有一段不连续的内存空间如果需要高效的插入和删除而不关心随机访问则应使用list。
请你来说一下STL中迭代器的作用有指针为何还要迭代器
1、迭代器
Iterator迭代器模式又称Cursor游标模式用于提供一种方法顺序访问一个聚合对象中各个元素, 而又不需暴露该对象的内部表示。或者这样说可能更容易理解Iterator模式是运用于聚合对象的一种模式通过运用该模式使得我们可以在不知道对象内部表示的情况下按照一定顺序由iterator提供的方法访问聚合对象中的各个元素。由于Iterator模式的以上特性与聚合对象耦合在一定程度上限制了它的广泛运用一般仅用于底层聚合支持类如STL的list、vector、stack等容器类及ostream_iterator等扩展iterator。
2、迭代器和指针的区别
迭代器不是指针是类模板表现的像指针。他只是模拟了指针的一些功能通过重载了指针的一些操作符-、*、、--等。迭代器封装了指针是一个“可遍历STL Standard Template Library容器内全部或部分元素”的对象 本质是封装了原生指针是指针概念的一种提升lift提供了比指针更高级的行为相当于一种智能指针他可以根据不同类型的数据结构来实现不同的--等操作。迭代器返回的是对象引用而不是对象的值所以cout只能输出迭代器使用*取值后的值而不能直接输出其自身。
3、迭代器产生原因
Iterator类的访问方式就是把不同集合类的访问逻辑抽象出来使得不用暴露集合内部的结构而达到循环遍历集合的效果。
请你说一说epoll原理
调用顺序int epoll_create(int size);int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);int epoll_wait(int epfd, struct epoll_event *events,int maxevents, int timeout);首先创建一个epoll对象然后使用epoll_ctl对这个对象进行操作把需要监控的描述添加进去这些描述如将会以epoll_event结构体的形式组成一颗红黑树接着阻塞在epoll_wait进入大循环当某个fd上有事件发生时内核将会把其对应的结构体放入到一个链表中返回有事件发生的链表。
参考链接
epoll使用详解n个整数的无序数组找到每个元素后面比它大的第一个数要求时间复杂度为O(N)
#include iostream
#include vector
#include stack
using namespace std;//n个整数的无序数组找到每个元素后面比它大的第一个数要求时间复杂度为O(N)
vectorint find(vectorint num)
{int len num.size();//空数组返回空if(len 0)return {};stackint notFind;//栈num中还未找到符合条件的元素索引vectorint res(len, -1);//返回结果初始化-1表示未找到int i 0;while(i len)//遍历数组{//如果栈空或者当前num元素不大于栈顶将当前元素压栈索引后移if(notFind.empty() || num[notFind.top()] num[i])notFind.push(i);else//有待处理元素且num当前元素大于栈顶索引元素符合条件更新结果数组中该索引的值栈顶出栈。{res[notFind.top()] num[i];notFind.pop();}}return res;
}int main()
{vectorint num {1, 3, 2, 4, 99, 101, 5, 8};// vectorint num {1, 1, 1, 1, 1, 1, 1};// vectorint num {};vectorint res find(num);for(auto i : res)cout i ;return 0;
}
请你回答一下STL里resize和reserve的区别
resize()改变当前容器内含有元素的数量(size())eg: vectorintv; v.resize(len);v的size变为len,如果原来v的size小于len那么容器新增len-size个元素元素的值为默认为0.当v.push_back(3);之后则是3是放在了v的末尾即下标为len此时容器是size为len1reserve()改变当前容器的最大容量capacity,它不会生成元素只是确定这个容器允许放入多少对象如果reserve(len)的值大于当前的capacity()那么会重新分配一块能存len个对象的空间然后把之前v.size()个对象通过copy construtor复制过来销毁之前的内存vector 的reserve增加了vector的capacity但是它的size没有改变而resize改变了vector的capacity同时也增加了它的size原因如下 reserve是容器预留空间但在空间内不真正创建元素对象所以在没有添加新的对象之前不能引用容器内的元素。加入新的元素时要调用push_back()/insert()函数。 resize是改变容器的大小且在创建对象因此调用这个函数之后就可以引用容器内的对象了因此当加入新的元素时用operator[]操作符或者用迭代器来引用元素对象。此时再调用push_back()函数是加在这个新的空间后面的。resize增加大的容量超过reserve会将capacity和size一样resize减少容量 不会影响到capacity通过 shrink_to_fit 将capacity保持和size一致的大小
参考链接
vector::shrink_to_fit()
测试代码
#include iostream
#include vector
using namespace std;
int main() {vectorint a;a.reserve(100);a.resize(50);couta.size() a.capacity()endl;//50 100a.resize(150);couta.size() a.capacity()endl;//150 150a.reserve(50);couta.size() a.capacity()endl;//150 150a.reserve(200);couta.size() a.capacity()endl;//150 200a.resize(50);couta.size() a.capacity()endl;//50 200a.shrink_to_fit();couta.size() a.capacity()endl;//50 50
}
请你说一说stl里面set和map怎么实现的
集合所有元素都会根据元素的值自动被排序且不允许重复。底层实现红黑树set 底层是通过红黑树RB-tree来实现的由于红黑树是一种平衡二叉搜索树自动排序的效果很不错所以标准的 STL 的 set 即以 RB-Tree 为底层机制。又由于 set 所开放的各种操作接口RB-tree 也都提供了所以几乎所有的 set 操作行为都只有转调用 RB-tree 的操作行为而已。适用场景有序不重复集合map映射。map 的所有元素都是 pair同时拥有实值value和键值key。pair 的第一元素被视为键值第二元素被视为实值。所有元素都会根据元素的键值自动被排序。不允许键值重复。底层红黑树适用场景有序键值对不重复映射
