C++ 底层实现
文章目录
- STL库的底层实现
-
- array
- vector
- deque
- list
- forward_list
- set、map
- unordered_map、unordered_set
- 迭代器
STL库的底层实现
-
顺序容器
- array数组
- vector向量
- deque双向队列
- list双向链表
- forward_list前向链表
-
关联容器
- map 关联数组key value
- map、multimap 排序实现
- unordered_map、unordered_multimap 哈希实现
- set 只保留关键子key
- set、multiset 排序实现
- unordered_set、unordered_multiset 哈希实现
- map 关联数组key value
-
容器适配器
- stack 栈
- queue 队列
- priority_queue 前向队列
各个容器的时间复制度
操作 | 访问,一般是指下标[n] 访问,关联容器应该是用key |
push_back() |
push_front() |
insert() |
pop_back() |
pop_front() |
erase() |
find() |
---|---|---|---|---|---|---|---|---|
顺序容器 | ||||||||
list | O(n)O(n)O(n) | O(1)O(1)O(1) | O(1)O(1)O(1) | O(1)O(1)O(1),但是确定迭代器的位置需要O(n)O(n)O(n) | O(1)O(1)O(1) | O(1)O(1)O(1) | O(1)O(1)O(1) | 不支持 |
vector | O(1)O(1)O(1) | O(1)O(1)O(1) | 不支持 | O(n)O(n)O(n) | O(1)O(1)O(1) | 不支持 | O(n)O(n)O(n) | 不支持 |
deque | O(1)O(1)O(1) | O(1)O(1)O(1) | O(1)O(1)O(1) | O(n)O(n)O(n) | O(1)O(1)O(1) | O(1)O(1)O(1) | O(n)O(n)O(n) | 不支持 |
关联容器红黑树实现 | ||||||||
map、multimap、set、multiset | O(log(n))O(log(n))O(log(n)) | 不支持 | 不支持 | O(log(n))O(log(n))O(log(n)) | 不支持 | 不支持 | O(log(n))O(log(n))O(log(n)) | O(log(n))O(log(n))O(log(n)) |
关联容器 hashtable实现 | ||||||||
unordered_map、unordered_multimap、unordered_set、unordered_multiset | O(1)O(1)O(1) | 不支持 | 不支持 | O(1)O(1)O(1) | 不支持 | 不支持 | O(1))O(1))O(1)) | O(1))O(1))O(1)) |
最坏情况:出现哈希冲突时 | O(n)O(n)O(n) | 不支持 | 不支持 | O(n)O(n)O(n) | 不支持 | 不支持 | O(n))O(n))O(n)) | O(n))O(n))O(n)) |
哈希冲突的时间复杂度,不应该取决于hash的桶内用什么方式存储key value吗?
array
固定大小数组,支持快速随机访问,但不能插入或删除元素;
vector
vector底层是一个动态数组,包含三个迭代器,start和finish之间是已经被使用的空间范围,end_of_storage是整块连续空间包括备用空间的尾部。
连续空间,扩容机制,开辟新的内存(2倍),拷贝过去。进行扩容操作时可能导致迭代器失效。
支持下标访问。
vector<int> vec(10,100); //创建10个元素,每个元素值为100vec.resize(r,vector<int>(c,0)); //二维数组初始化vec.reserve(100); //改变vector的大小size()
vec.reserve(100); //只改变vector的容量capacity()扩充到已经确定的大小find(vec.begin(),vec.end(),1); //查找元素
reverse(vec.begin(),vec.end()) //将元素翻转
sort(vec.begin(),vec.end()); //排序,默认升序排列
vec.push_back(val); //尾部插入数字
vec.size(); //向量大小
vec.capacity(); //经分配的内存中可以容纳多少元素
iterator = vec.erase(iterator) //删除元素vec.clear(); //清空内容,但是不释放内存。
vector<int>().swap(vec); //清空内容,且释放内存,想得到一个全新的vector。
vec.shrink_to_fit(); //请求容器降低其capacity和size匹配。
vec.clear();vec.shrink_to_fit();//清空内容,且释放内存。
deque
双向开口的连续线性空间(双端队列)。一块内存前后都有空闲的空间用来存取。
支持头尾插入。
deque.push_back(elem) //在尾部加入一个数据。
deque.pop_back() //删除尾部数据。
deque.push_front(elem) //在头部插入一个数据。
deque.pop_front() //删除头部数据。
deque.size() //返回容器中实际数据的个数。
deque.at(idx) //传回索引idx所指的数据,如果idx越界,抛出out_of_range。
list
双向链表,非连续空间,用一块申请,删除也是以节点为单位。
方便大量插入。
list.push_back(elem) //在尾部加入一个数据
list.pop_back() //删除尾部数据
list.push_front(elem) //在头部插入一个数据
list.pop_front() //删除头部数据auto it = list.begin();
list.insert(it, 10); //需要使用迭代器在制定位置插入list.size() //返回容器中实际数据的个数
list.sort() //排序,默认由小到大
list.unique() //移除数值相同的连续元素
list.back() //取尾部迭代器
list.erase(iterator) //删除一个元素,参数是迭代器,返回的是删除迭代器的下一个位置
forward_list
单向链表
set、map
红黑树,平衡、有序二叉树。红黑树介绍https://www.iamshuaidi.com/2061.html。key和value存储在节点中。插入与删除主要是调整节点的指针。
搜索O(log(n))O(log(n))O(log(n))
//常用函数
map<int,string> mymap;
mymap.begin() //返回指向容器起始位置的迭代器(iterator)
mymap.end() //返回指向容器末尾位置的迭代器
bool bempty = mymap.empty() //若容器为空,则返回true,否则false
mymap.find(k) //寻找键值为k的元素,并用返回其地址
int size = mymap.size() //返回map中已存在元素的数量
mymap.insert({int,string}) //插入元素
for (auto iter = mymap.begin(); itor != mymap.end();++iter;)
{if (iter->second == "target")mymap.erase(itor++) ; // erase之后,令当前迭代器指向其后继。
}//几种不同的插入方式
map<int,string> ;
mapStudent.insert(pair<int, string>(1, "student_one"));
mapStudent.insert(map<int, string>::value_type (1, "student_one"));
mapStudent.insert(make_pair(1, "student_one"));
mapStudent[1] = "student_one"; map[2]//下标方式访问,没有值会创建key value(默认值)的值插入
unordered_map、unordered_set
hashtable散列函数函数实现,通过哈希映射实现增删改查时间复杂度为O(1)O(1)O(1)
unordered_map.begin() //返回指向容器起始位置的迭代器(iterator)
unordered_map.end() //返回指向容器末尾位置的迭代器
unordered_map.cbegin() //返回指向容器起始位置的常迭代器(const_iterator)
unordered_map.cend() //返回指向容器末尾位置的常迭代器
unordered_map.size() //返回有效元素个数
unordered_map.insert(key) //插入元素
unordered_map.find(key) //查找元素,返回迭代器
unordered_map.count(key) //返回匹配给定主键的元素的个数
迭代器
https://www.iamshuaidi.com/2328.html
底层实现 萃取技术(推导类型),模板特化技术具体实现。
迭代器失效 当存储数据的内存位置发生改变时。
顺序容器:删除迭代器it = c.erase(it);
返回值下一个迭代器。因为除了list外,erase会导致当前迭代器失效,不能使用it++
。
关联容器:删除迭代器c.erase(it++);
返回值是void。所以使用it++
获取下一个迭代器。