主要是关于标准库容器的整理
空间配置器
主要看SGI的实现,有两个空间配置器
- _malloc_alloc_template<0>
- __default_alloc_template<...>
用户可以选择单独使用第一个分配器,或者一起使用两个分配器。
当用户选择使用两个分配器时,编译器会分别将上述两个分配器typedef成 malloc_alloc
和 alloc
, 容器的分配器默认使用alloc,即第二个分配器。
两个配置器的接口都有allocate() deallocate() reallocate(),这里主要聚焦于前两个接口。
第一个配置器(malloc_alloc)的allocate()从typedef的名字上可以看出,它只是简单调用malloc(), deallocate()也只是简单调用free(),唯一的特别之处是,这个配置器能够模拟C++ new 运算符的set_new_handler()以处理内存不足的情况。
而第二个配置器(alloc), 当内存小于128字节时则由自己管理这些内存块
,会自己管理一个内存池;当分配的内存大于128字节时
,直接调用malloc::allocate()。如果系统空间不足,那么也调用malloc::allocate(),因为以及内存分配器处理程序处理内存不足的情况。
为什么对于小于128bytes的内存块使用内存池来管理?
1.防止内存碎片
2.若使用malloc直接分配的内存,每块都带有一些cookie,若小内存偏分配次数多,那么cookie的占用空间相比于有用空间会很大,空间利用率不高。
alloc配置器如何管理内存池?这里只记个大概,细节看书。
alloc管理一个16个长度的数组,数组的每个元素都指向一个free_list, 每个free list都管理一种大小的空闲数据块。
内存块大小有8bytes 、16bytes、24bytes ... 128bytes。 因此一共要16个free list来进行空闲块的管理。
最初,alloc的内存池空无一物,当有请求来时,比如要申请8字节的空间,就调用malloc向系统申请空间大小为8 * 40,将其中的1块返回给用户,其中19块做切割处理后交给对应的free list管理,剩余的20块留给内存池的备用。当再有8字节申请时,则直接从这个free list中拨给用户空闲空间。当有16字节申请时,从内存池中的备用空间中找空闲内存,如果不够则再调用malloc重复刚刚的操作,但是在当前情景中,确实是存在备用内存的(刚刚分配8字节内存时剩余的20块)。
由此可见,这确实减少了cookie的大小,因为我们只是使用了一次malloc,只有一个cookie。
处理内存申请时,如果申请的内存块小于128bytes, alloc将从以下几方面递进式地申请内存
- 首先看看对应freelist有无空闲空间
- alloc的内存池的备用内存是否有空余块(end_free - start_free)
- 如果没有,则使用malloc向系统申请内存
- 如果malloc还失败了,那么再看看其他freelist是否还有没有划分出去的内存块
- 最后,已然山穷水尽,调用malloc_alloc(第一个配置器)的allocate()看看它的 handler 处理程序能否空出一些内存
有几个问题值得探讨
- sgi版本的stl管理内存的方式乍一看和linux内核的伙伴系统很像,但是stl内存池根本不涉及连续内存块合并的操作,也就是说没有伙伴的概念
- 内存池管理的内存在程序运行期间,并没有被调用free()库函数,也更谈不上这些内存会归还给操作系统了。
type traits
使用了模板推导、模板偏特化、模板特化特性而得的类型萃取机制。
可以仿照源码写一些自己的萃取机制:
-
首先定义两个trueType、falseType,这两个只是类型,然后顶一个模板类,typetraits,仿照源码定义一些类型,我这里使用的是using,也可以使用typedef。除了指针类型和基本类型,其他类型的TypeTraits::isPointer都是falseType类型,TypeTraits::isFundamentalType都是falsetype类型。包括用户自定义的类。
struct trueType{}; struct falseType{}; template <typename T> class TypeTraits { public: using isPointer = falseType; };
-
写T* 和 const T*的偏特化,这两个类是指针类型,也是基本类型:
/* 对指针类型的偏特化版本*/ template <typename T> class TypeTraits<T*> { public: using isPointer = trueType; }; template <typename T> class TypeTraits<const T*> { public: using isPointer = trueType; };
-
然后再写char、short 、int 、long 、longlong、float、double等以及usigned等基本变量的全特化,它们不是指针类型
/*全特化, char short int long longlong float double, 以及unsinged系列 */ template <> class TypeTraits<char> { public: using isPointer = falseType; }; template <> class TypeTraits<int> { public: using isPointer = falseType; }; // .... 等等 .....//
-
如何使用?我们都知道编译期多态的一种涉及到模板,下面就来看看萃取机制如何做到编译器多态。
定义一个模板函数,将其转发给doIt函数:
template<class T> void dosomething(T x) { doIt(x, typename TypeTraits<T>::isPointer()); // 萃取出T类型是否是pointer类型 }
doIt函数有两个版本,它使用第二个参数的参数类型做重载:即判断参数类型是否为指针类型,进行不同操作。
// 重载方法 template<class T> void doIt(T x, trueType) { cout << "doIt , pointer version\n"; } template<class T> void doIt(T x, falseType) { cout << "doIt , NOT pointer version\n"; }
-
测试:
class A { public: int a; }; int main() { int integerA = 1; int* ptrA = &integerA; dosomething(integerA); dosomething(ptrA); A classA; dosomething(classA); A* classAptr = new A(); dosomething(classAptr); A& classRef = classA; dosomething(classRef); }
输出如下:
doIt , NOT pointer version # int 类型不是指针类型 doIt , is pointer version # int* 类型是指针类型 doIt , NOT pointer version # class A 类型不是指针类型 doIt , is pointer version # class A* 类型是指针类型 doIt , NOT pointer version # class A& 类型不是指针类型
容器
vector
迭代器
vector的迭代器是原生指针,因此用不着重载 operator* operator-> operator++ operator--等。
template <class T, class Alloc = alloc>
class vector {
public:
typedef T value_type;
typedef value_type* iterator; // iterator的类型是原生指针
// ....
}
因此它属于random access iterator
vector数据成员
只有三个itetor,start、finish、 end_of_storage,因为vecotr的迭代器是原生指针,因此对任何一个vector进行size of 都返回3个指针的大小。在64位机器上,是24bytes。
protected:
typedef simple_alloc<value_type, Alloc> data_allocator;
iterator start;
iterator finish;
iterator end_of_storage;
start指向这个vector所管理空间的头部元素,finish指向目前使用空间的尾部的后一个元素(前闭后开区间),end_of_storage指向可用空间的尾部的后一个元素。
finish - start = vector::size()
end_of_storage - start= vector::capacity()
[start,finish)这段已经被分配,且有拷贝\构造(如果元素有non-trivial 构造函数的化)函数作用其上;
[finish,end_of_storage)这段空间已经被分配,但是没有元素被构造其上,如果读取这里的内存会造成未定义行为
member function
-
push_back : 在finish之后的内存上再构造一个元素。如果此时finish = end_of_storage,造成空间的再分配,会申请新的空间,大小为源vector的
两倍
,将旧容器的元素一一拷贝\构造到新的内存中,析构并释放原vector的内容
,最后重新设置vector的三个数据成员的指向(指向新的空间)。因此如果pushback引起空间重分配,那么原先vector的迭代器将全部失效
。那么push_back的时间复杂度为?
“均摊”时间复杂度还是O(1)
-
pop_back: finish指针--,然后析构最后一个元素
-
insert:引起元素的拷贝赋值,插入元素之后的元素整体向后挪。可能造成空间重分配,因此有可能全部迭代器失效,也有可能只有在插入元素之后的迭代器失效。
-
erase:将要删除元素之后的元素往前移覆盖掉要删除的元素,然后调用destroy函数析构(但不释放空间)后面多余的元素,finish迭代器往前移动对应的距离。注意只是析构,没有释放内存空间,所以size方法的返回值会变,而capacity方法的返回值不会变。
iterator erase(iterator position) { if (position + 1 != end()) copy(position + 1, finish, position); // 将被删除元素接下来的所有元素都往前挪一个位置 --finish; // finish指针往前移动一格 destroy(finish); // 析构最后一个元素 return position; } iterator erase(iterator first, iterator last) { iterator i = copy(last, finish, first); // last之后的元素移动到first上 destroy(i, finish); // 析构多余的元素 finish = finish - (last - first); // finish指针往前移动(last - first)个位置 return first; }
-
resize(n):强行将vector的元素数量增至或者减至n,即最后size() == n
-
void resize(size_type new_size) { resize(new_size, T()); } // 正真做事的是下面这个重载方法 void resize(size_type new_size, const T& x) { if (new_size < size()) erase(begin() + new_size, end()); else insert(end(), new_size - size(), x); }
-
如果n < size(), 那么调用erase 删除剩余元素
-
如果n > size() , 那么调用insert增减对应数量元素。(此时也可能有insert引起内存扩容)
-
-
reserve(n), 将vector的容量增至能够容纳n个元素的大小,调用该方法后,capacity()的结果 == n
-
void reserve(size_type n) { if (capacity() < n) { const size_type old_size = size(); iterator tmp = allocate_and_copy(n, start, finish); destroy(start, finish); deallocate(); start = tmp; finish = tmp + old_size; end_of_storage = start + n; } }
-
如果原来的容量能够容纳n个元素,那么什么都不用做。
-
如果不能,则进行内存重分配,与
resize
不同的是,reserve只会为分配增加空间,但不会为增加的空间调用构造函数
-
-
clear(): 清空元素,注意不能释放空间!
void clear() { erase(begin(), end()); }
如上所示,clear只是调用了erase方法,但是通过上面的erase方法已经知道了erase仅仅是析构元素(通过调用destroy),但是没有释放空间。
在调用clear后,size()的调用结果为0,但是capacity()的调用结果不变。
-
发现无论是clear还是resize都不能正真地减小vector的capacity大小,该如何缩小或者清空vector占用的内存呢? --- 使用swap:
vector(Vec).swap(Vec); //将Vec中多余内存清除; vector().swap(Vec); //清空Vec的全部内存;
迭代器失效
可能造成迭代器失效的成员函数:
- erase:造成被删除元素及之后的迭代器失效
- insert:
- 如果没有造成空间重分配,则插入元素及之后的迭代器失效
- 如果造成了空间重分配,所有迭代器都失效
- push_back:
- 如果没有造成空间重分配,只有end()迭代器失效
- 如果造成了空间重分配,所有迭代器都失效
- emplace:同insert
- emplace_back: 同push_back
- popback: 末尾元素的迭代器以及end()迭代器失效
扩容因子
关于扩容因子:为什么g++ vector的扩容因子是2,但是vc vector的扩容因子是1.5呢?
- 使用1.5的扩容因子,有机会重新使用之前分配的地址
- 但是为什么g++的vector的扩容因子是2?我个人想到了两点原因,
- 内存池freelist管理的对象大小都是2的幂次方,malloc自身的内存池分配的大小也是2的幂次方,linux系统的伙伴系统分配的内存以页对齐,也是2的幂次方。所以从C++应用层到linux内核层,在linux上的C++应用分配得到的内存地址大概率是2的幂次方,因此g++的vector的扩容因子设置为2,方便系统的内存分配和回收。
- 内存池freelist中串联的内存并不保证连续,而重用之前分配的地址则需要先后分配的地址连续。
list
迭代器
list的迭代器就不会像vector那么简单了,因为list的迭代器不能使用原生指针。
list的迭代器的数据成员成员只有一个,一根指向list node的指针,然后重载一些列操作符模拟原生指针的行为
template<class T, class Ref, class Ptr>
struct __list_iterator {
// ...
typedef __list_node<T>* link_type;
// ...
link_type node; // 指向一个listnode
bool operator==(const self& x) const { return node == x.node; }
bool operator!=(const self& x) const { return node != x.node; }
// 模拟原生指针的 * 和 ->操作
reference operator*() const { return (*node).data; } // 直接返回所指listnode的data
pointer operator->() const { return &(operator*()); } // 调用*() 调用所致listnode的地址
self& operator++() { // 前置自增
node = (link_type)((*node).next);
return *this;
}
self operator++(int) { // 后置自增
self tmp = *this;
++*this;
return tmp;
}
self& operator--() { // 前置自减
node = (link_type)((*node).prev);
return *this;
}
self operator--(int) { // 后置自减
self tmp = *this;
--*this;
return tmp;
}
}
注意前置自增和后置自增的区别,前置自增仅仅把node指向下一个节点;而后置自增创建临时对象
保存当前iter的状态,然后调用前置自增改变node指向,最后返回临时对象。正因此,两者返回值也不同
,前置自增返回引用,而后置自增返回对象,因为我们不可能返回一个临时对象的引用。
为什么有这样的区别?我想同样是为了与C++的对基本数据类型后置自增操作相容。 i++ 被决议为旧值,然后执行+1, ++i则直接+1,被决议为新值。
从重载 -- 操作符可以看出,list的迭代器是一个bidirectional_iterator
数据成员
list只需要一个node指针即可表示整个链表(2.9版本,当前版本存储了3个指针)
class list {
typedef list_node* link_type;
...
link_type node;
}
listnode 则有两个指针,和一笔数据
template <class T>
struct __list_node {
typedef void* void_pointer;
void_pointer next;
void_pointer prev;
T data;
};
其他实现比较简单(相对来说),erase操作只会使当前的迭代器失效,插入操作不会引起迭代器失效
deque
概览
vector是单向开口的连续线性空间,deque则是一种双向开口的连续线性空间。
然而deque的连续性是伪装的,主要依靠重载迭代器的++ 和 --操作来给出这种错觉。
内存布局上,一个deque有一个“中控器”和许多等长度的缓冲块组成。
如图所示,deque拥有一个map指针,指向“中控器”,中控器的每个元素分别指向不同的缓冲区,这些缓冲区才是正真存放元素的地方。
迭代器
deque迭代器有4个指针
T* cur; // 指向某个缓冲区的当前元素
T* first; // 指向某个缓冲区的头部元素
T* last; // // 指向某个缓冲区的尾部元素
map_pointer node; // 指向中控器 map的一个元素
deque的迭代器重载++、--等运算符,维护deque “整体连续的错觉”。
self& operator++() {
++cur;
if (cur == last) { // 如果指向了当前缓冲区的最后一个元素
set_node(node + 1); // 那么将node、fist、指针指向下一个缓冲区的对应位置
cur = first; // 改变cur指针,指向新缓冲区的首元素
}
return *this;
}
void set_node(map_pointer new_node) {
node = new_node;
first = *new_node;
last = first + difference_type(buffer_size());
}
此外deque的迭代器类型是random_access_iterator
,为了实现随机存取,需要重载 []、 +、 +=、-、-= 运算符
其中减号调用加号完成。而且[]调用+号,而+号调用+=号,因此主要任务落在了+=函数上。大体逻辑与++运算符是相似的,都是判断索要的元素在不在当前缓冲区,如果在就很容易实现,和vector差不多;但如果不在一个缓冲区中,那么就要向后寻找对应的缓冲区。
self& operator+=(difference_type n) {
difference_type offset = n + (cur - first);
if (offset >= 0 && offset < difference_type(buffer_size()))
// 目标位置在同一缓冲区
cur += n;
else {
// 目标位置不在同一缓冲区
difference_type node_offset =
offset > 0 ? offset / difference_type(buffer_size())
: -difference_type((-offset - 1) / buffer_size()) - 1;
// 切换至目标缓冲区
set_node(node + node_offset);
// 设置cur指针
cur = first + (offset - node_offset * difference_type(buffer_size()));
}
return *this;
}
deque数据成员
每一个deque容器有4个成员,其中有两个迭代器分别指向第一个节点和最后一个节点,一个map指针指向中控器,一个size_t变量记录中控器有多长。
又deque的迭代器存放4个指针,因此一个deque容器的大小为40bytes(16*2 + 4 + 4)。
protected: // Data members
iterator start; // 指向第一个缓冲区的第一个元素
iterator finish; // 指向最后一个缓冲区的最后一个元素
map_pointer map; // map数组的指针
size_type map_size; // map数组的大小
deque的内存布局如下图所示,存放20个元素,要开辟3个长度为8的缓冲区,前两个缓冲区放满,后一个缓冲区留4个空位。
start迭代器的cur指针指向第一个缓冲区的头部,finish的cur指针指向最后一个缓冲区的最后一个有效元素。
member function
deque的成员函数实在是太长了,细节看书吧。
- push_back: 首先会在finish所指向的缓冲区插入新元素,如果缓冲区不够了,那么就开辟一块缓冲区将其挂在到map上,然后finish指向这个新的缓冲区执行插入。如果map的所有元素都已经挂在了缓冲区,那么此时需要重新分配map和缓冲区,将旧数据拷贝到新空间中;与vector类似,新map的大小几乎是旧map大小的两倍,且所有原迭代器均失效。
- pop_back: 会在finish迭代器的cur指向的缓冲区元素上调用析构函数,如果这个缓冲区空了(finish.first == finish.cur),则会
释放这块缓冲区
。这是与vector不同的点,vector只会动态扩张,而deque则会动态伸缩
。 - insert 、 erase等操作与vector类似,会引发一系列的赋值拷贝行为。但deque是一个双端“连续”结构,它会检测插入\删除的位置,如果离deque头更近,则将操作元素之前的元素整体向前挪,如果离deque尾最近,则将操作元素之后的元素整体向后挪动。
stack、queue
这俩其实算是接配器,而不是容器,因为它们封装其他容器的接口,来实现它们的功能。
用来实现它们功能的底层容器可以有多种,默认为deque。
它们都没有迭代器
。
priority_queue
这也是接配器,默认的使用vector作为底层容器。配合push_heap pop_heap算法,使用连续内存的底层容器来实现堆的特性(根元素)
它没有迭代器。
map、set
红黑树
map和set底层都是红黑树,rb_tree对插入、查找、删除的复杂度都是O(logN);
红黑树相比于二叉搜索树的优点
:当插入的数据有序时,二叉搜索树会退化为链表,因此所有操作的时间复杂度都与链表相同。
红黑树相比于平衡二叉树的优点
:平衡树的左右子树高度严格不大于1,它的搜索操作可能比红黑树快,但是插入和删除操作叫容易引起存储结构的调整,因此时间复杂度比红黑是慢。
红黑树的整体结构如图所示:
一个红黑树结构需要三个成员来描述:
template <class Key, class Value, class KeyOfValue, class Compare,
class Alloc = alloc>
class rb_tree {
...
typedef rb_tree_node* link_type;
protected:
size_type node_count; // 整棵的节点个数
link_type header; // header节点的指针,见上图
Compare key_compare; // 节点值得比较准则,是一个function object
...
}
而一个node则由5笔数据来表现:
- 3个指针,分别指向父节点、左子节点、右子节点
- 表示颜色的bool值
- 正真的存储数据
rb_tree有两个插入元素的函数
- __insert_equal, 允许插入重复的元素
- __insert_unique, 不允许插入重复的元素
multimap与map的区别,multiset与set的区别
,都在这两个函数上。
__insert_unique的返回值是一个pair,其第一个元素是红黑树的某个迭代器,第二个元素是一个布尔值,表示插入是否成功。
如果调用__insert_unique插入了一个重复值,则返回的迭代器指向已经存在的哪个节点,布尔值则为false。
如果调用__insert_unique插入了一个不重复的值,则返回的迭代器指向新插入的节点,布尔值为true。
反正,不管怎么样__insert_unique都会返回一个合法的迭代器,在下面的[]运算符中有作用。
map与set的区别
map存放在节点的值是一个键值对,而set存放在节点的值就是单个值。然而这两个的底层数据结构都是红黑树,怎么做到的呢?
得从红黑树的类模板参数看起:
template <class Key, class Value, class KeyOfValue, class Compare,
class Alloc = alloc>
class rb_tree {
// ...
typedef __rb_tree_node<Value> rb_tree_node; // 红黑树节点的值只是存放Value而没有Key
// ...
Compare key_compare; // 比较节点的Key的大小关系
}
红黑树的模板参数有5个,其中
- Key : 键的类型
- Value : 值的类型
KeyOfValue
: 从Value中提取出Key的方法
从上面三个可以看出,红黑树把Key视为Value的一部分
,通过上层指定的KeyOfValue从Value中提取Key, KeyOfValue是同时实现set和map的精髓所在
。
每个红黑树节点实际存储的就是Value
,可以从上面代码的typedef可以看出。
模板参数的Compare则是用于比较节点Key之间的大小关系。
现在看set模板类的定义
template <class Key, class Compare = less<Key>, class Alloc = alloc>
class set {
// ...
typedef Key key_type;
typedef Key value_type;
typedef Compare key_compare; // 键的比较函数与值的比较函数相同,都是Compare,默认为less<Key>
typedef Compare value_compare;
// ...
private:
typedef rb_tree<key_type, value_type,
identity<value_type>, key_compare, Alloc> rep_type; // 注意这里的identity<value_type>
rep_type t; // set里有一个红黑树
// ...
}
关键在于几个typedef,set将建和值的类型都定义成了模板参数Key的类型
,然后传给rb_tree的模板参数的KeyOfValue指定为identity<value_type>
,看名字也能看出,当这个函数作用Value时返回等值得Key,也就是说在Set里得Key和Value是一回事。
因此,set的红黑树的节点能说存放Key,也能说存放Value
再看map模板类的定义
template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
class map {
public:
// ...
typedef Key key_type;
typedef pair<const Key, T> value_type;
//...
typedef Compare key_compare;
typedef Compare key_compare;
class value_compare {
// 另外定义value的比较规则
}
private:
typedef rb_tree<key_type, value_type,
select1st<value_type>, key_compare, Alloc> rep_type; // 注意这里的select1st<value_type>
rep_type t;
}
能够清楚地看到,map怎样使用红黑树存储key-value键值对。
主要还是在两个typedef中,map将key的类型定义为Key(也就是键值对中的键),将value的类型定义为一个pair,这个pair的第一个存储const类型的Key,pair的第二个存储键值对中的值。
然后定义红黑树时,自然地与set产生了不同,Key模板参数是键值对中的键,而Value模板参数则是整个KeyValue对组成的pair。KeyOfValue则是select1st,即取出pair中的第一个就是key,这很简单。
显而易见,map的红黑树节点存储的值是键值对组成的pair。
迭代器
红黑树的迭代器,是一个bidirectional_iterator
,为了实现这一点,重载 ++ 和 -- 运算符。
它的迭代器只存储一个node指针,指向某个红黑树节点。
set和map的迭代器直接使用红黑树的迭代器即可,
typedef typename rep_type::iterator iterator;
迭代器失效
insert方法:不会引起迭代器失效
erase方法:除了被删除的那个迭代器,其他迭代器都不会失效。
map的[]运算符
验证effective STL的条款24。
其源码如下:
T& operator[](const key_type& k) {
return (*((insert(value_type(k, T()))).first)).second;
}
- value_type(k, T()): 其中T表示data_type, k表示key_type变量的一个引用,而在map中value_type则是一个pair类型,具体为pair<const key_type, T>。那么这句话的意思就是,创建一个pair类型,其第一个元素的类型为key_type,值为k, 第二元素的类型为data_type,其值为该类型变量的默认值T()。 因此value_type(k, T()) 可以等效地看为pair<key_type,T>
- 然后调用insert(pair<key_type,T>{k ,T()}), insert会调用__insert_unique函数。从上面几节的内容可以了解到,_insert_unique函数会返回一个pair<iterator, bool>, 其中bool表示插入是否成功,如果有元素重复则插入不成功,则返回旧值,如果成功则返回新值,这里的新值的value是一个默认量T()。
那么调用[]插入新元素和直接调用insert插入新元素的区别很容易看出来。
-
[]运算符,首先调用insert使用用户给的键和默认的值构建了一个pair临时对象,把这个临时对象插入到红黑树中。上面说过,如果insert插入成功则返回pari,它的第一个值是指向新节点的迭代器,以引用的形式返回迭代器的第二个值,以便用户赋值。最后再用=运算符为这个新节点赋值。
-
而insert则直接按照用户需求构造这个键值对,插入红黑树就完事了。
-
所以如果想要插入一个新的值,直接insert会比 先[] 然后 = 赋值 来的快一些。
umap[0] = "0"; // 住[]使用v默认值构造临时对象的值,这里会为临时变量使用=号赋值 umap.insert({0,"0"}) // 新对象使用其他重载构造函数创建,直接一步到位
可以看出第一种方法额外多了一步=赋值操作。
unordered_map 和 unordered_set
实现
stl源码一书上的库版本还没有将这两个容器纳入标准之内,但是也已经实现了hash_set 和 hash_map这两个类。
这两个容器的底层数据结构都是hash_table,如何使用一种数据结构同时实现hash_set和hash_map的技巧,与上一节的map和set类似,关键在hash_table的类模板参数的ExtractKey上。
template <class Value, class Key, class HashFcn,
class ExtractKey, class EqualKey,
class Alloc>
class hashtable {///}
可以预见,hash_map 和 hash_set对这个模板参数的设置是不同的,与上一节完全相同。
下面主要记录以下hash_table的实现:
-
stl的hash_table使用
开链法
处理碰撞 -
hash_table里有一个vector,用它的元素当作“桶”,但是hash_table自己控制vector的扩容时机,以及扩容大小
- hash_table的buckets扩容时机:
当负载因子(现有元素个数/桶的数量) > 1
时, 每次在insert时检测是否要扩容 - hash_table的buckets扩容大小:新的buckets大小并不是简单的两倍于旧的buckets大小。hash_table有一个static const数组,从小到大存放了128个质数。扩容时,从小到达的遍历这个数组,选择第一个比当前buckets大小更大的
质数
,这个新的质数就是新的buckets的大小。 - 扩容的rehash操作会导致所有迭代器失效!
- hash_table的buckets扩容时机:
-
insert操作同样有两个版本,一个insert_unique,一个insert_equal,看名字就知道什么意思了。
-
hashtable的
find
和count
函数,记录这两个函数主要是为了验证effective stl的条款45中关于这两个函数的建议。iterator find(const key_type& key) { size_type n = bkt_num_key(key); node* first; for ( first = buckets[n]; first && !equals(get_key(first->val), key); // 找到一个相同的就退出 first = first->next) {} return iterator(first, this); } size_type count(const key_type& key) const { const size_type n = bkt_num_key(key); size_type result = 0; for (const node* cur = buckets[n]; cur; cur = cur->next) if (equals(get_key(cur->val), key)) ++result; // 遍历完所有的元素才退出 return result; }
-
hashtable的迭代器的类型是ForwardIterator,不能执行自减操作
迭代器失效
erase方法:除了被删除的那个元素,其他迭代器都不会失效
insert方法:
- 如果该方法没有引起扩容进行rehash则没有迭代器会失效。
- 如果该方法引起了rehash,则所有迭代器失效。
hash碰撞处理策略
另外再补充一些关于hahs碰撞的内容:
参考文章:
处理碰撞,主要分两种:
-
开放寻址法
- 线性探测
- 做法:当要放入的bucket已被占用时,向后 + 1 寻找
- 负载因子很小时,cache命中率很高,因此性能也高。与开放寻址的其他方法相比,当负载因子很大时,由于
“主集团”(primary clustring)的影响
,性能会大幅降低。 此外,分布不均匀的输入对线性探测有更大的影响,它需要更好的hash函数来消除输入的不均匀性.
- 二次探测(quadratic probing) :
- 做法: 当要放入的bucket已被占用时,向后 + (i) ^ 2 继续寻找,i 是探测的次数
- 相比于线性探测,二次探测解决了因主集团的性能下降问题。但是却有次集团问题
- 介于线性探测和double hashing之间
- double hashing:
- It uses one hash value generated by the hash function as the starting point and then increments the position by an interval which is decided using a second, independent hash function
- 解决了集团问题,但是cache命中率差(降低了局部性),且计算量更大。
- 线性探测
-
开链法
-
优点 : 相比于开放寻址,它不会受clustring的影响;随着负载因子的提高,性能下降地更“优雅”
-
缺点: cache命中率比open addressing 低(太多分散的指针了);不容易被序列化(也是由于指针)
-
一般而言,开放寻址法的负载因子严格限制在了0.7-0.8,而开链法的负载因子能够趋近1(stl的实现就是当负载因子等于1时在扩容并rehash)
算法
sort
Introsort - C++’s Sorting Weapon - GeeksforGeeks : 很好的关于Introsort的文章
std::sort使用introsort算法,集成了quicksort、insertion sort以及heapsort。
-
为什么使用insertionsort? 因为插入排序在小数据集的情况下时间复杂度低,且对部分有序数组的排序性能很高为O(kn)。参考Insertion sort - Wikipedia
-
Quicksort vs. Heapsort | Baeldung on Computer Science : 讲了quicksort与heapsort的对比。虽然quicksort与heapsort的平均时间复杂度都是O(nlogn),但是在实践中,quicksort比heapsort快,因为heapsort的时间复杂度的常数项比quicksort大。但如果空间复杂度有要求(比如嵌入式系统),那么heapsort可能是一个很好的选择。但是为了避免quicksort的时间复杂度退化为O(n2)的情况,当递归深度超出限制时,在introsort的策略下将改用heapsort。
introsort的部分C++实现源码:
template <class RandomAccessIterator>
inline void sort(RandomAccessIterator first, RandomAccessIterator last) {
if (first != last) {
__introsort_loop(first, last, value_type(first), __lg(last - first) * 2); // 最大递归深度限制为 log(last - first) * 2
// 上面的函数推出后,元素为部分有序状态
__final_insertion_sort(first, last); // 插入排序
}
}
template <class Size>
inline Size __lg(Size n) {
Size k;
for (k = 0; n > 1; n >>= 1) ++k;
return k;
}
//
template <class RandomAccessIterator, class T, class Size>
void __introsort_loop(RandomAccessIterator first,
RandomAccessIterator last, T*,
Size depth_limit) {
while (last - first > __stl_threshold) { // 元素个数大于16时一直循环,否则退出
if (depth_limit == 0) {
partial_sort(first, last, last); // 超出允许的递归深度,改用堆排序
return;
}
// 执行正常的quicksort流程
--depth_limit;
RandomAccessIterator cut = __unguarded_partition
(first, last, T(__median(*first, *(first + (last - first)/2),
*(last - 1)))); // quicksort的partition操作
__introsort_loop(cut, last, value_type(first), depth_limit);
last = cut;
}
}
标签:node,迭代,读书笔记,STL,元素,源码,内存,type,first
From: https://www.cnblogs.com/HeyLUMouMou/p/17372440.html