C++之STL模板库

如果你想在校招中顺利拿到更好的offer,阿秀建议你多看看前人的经验 ,比如准备简历实习上岸经历校招总结阿里、字节、腾讯、美团等一二线大厂真实面经也欢迎来一起参加秋招打卡活动 等;如果你是计算机小白,学习/转行/校招路上感到迷茫或者需要帮助,可以点此联系阿秀;免费分享阿秀个人学习计算机以来的收集到的好资源,点此白嫖;如果你需要《阿秀的学习笔记》网站中求职相关知识点的PDF版本的话,可以点此下载

# 21、STL中的allocator、deallocator

  1. 第一级配置器直接使用malloc()、free()和relloc(),第二级配置器视情况采用不同的策略:当配置区块超过128bytes时,视之为足够大,便调用第一级配置器;当配置器区块小于128bytes时,为了降低额外负担,使用复杂的内存池整理方式,而不再用一级配置器;

  2. 第二级配置器主动将任何小额区块的内存需求量上调至8的倍数,并维护16个free-list,各自管理大小为8~128bytes的小额区块;

  3. 空间配置函数allocate(),首先判断区块大小,大于128就直接调用第一级配置器,小于128时就检查对应的free-list。如果free-list之内有可用区块,就直接拿来用,如果没有可用区块,就将区块大小调整至8的倍数,然后调用refill(),为free-list重新分配空间;

  4. 空间释放函数deallocate(),该函数首先判断区块大小,大于128bytes时,直接调用一级配置器,小于128bytes就找到对应的free-list然后释放内存。

# 22、STL中hash table扩容发生什么?

  1. hash table表格内的元素称为桶(bucket),而由桶所链接的元素称为节点(node),其中存入桶元素的容器为stl本身很重要的一种序列式容器——vector容器。之所以选择vector为存放桶元素的基础容器,主要是因为vector容器本身具有动态扩容能力,无需人工干预。

  2. 向前操作:首先尝试从目前所指的节点出发,前进一个位置(节点),由于节点被安置于list内,所以利用节点的next指针即可轻易完成前进操作,如果目前正巧是list的尾端,就跳至下一个bucket身上,那正是指向下一个list的头部节点。

# 23、常见容器性质总结?

1.vector 底层数据结构为数组 ,支持快速随机访问

2.list 底层数据结构为双向链表,支持快速增删

3.deque 底层数据结构为一个中央控制器和多个缓冲区,详细见STL源码剖析P146,支持首尾(中间不能)快速增删,也支持随机访问

deque是一个双端队列(double-ended queue),也是在堆中保存内容的.它的保存形式如下:

[堆1] --> [堆2] -->[堆3] --> ...

每个堆保存好几个元素,然后堆和堆之间有指针指向,看起来像是list和vector的结合品.

4.stack 底层一般用list或deque实现,封闭头部即可,不用vector的原因应该是容量大小有限制,扩容耗时

5.queue 底层一般用list或deque实现,封闭头部即可,不用vector的原因应该是容量大小有限制,扩容耗时(stack和queue其实是适配器,而不叫容器,因为是对容器的再封装)

6.priority_queue 的底层数据结构一般为vector为底层容器,堆heap为处理规则来管理底层容器实现

7.set 底层数据结构为红黑树,有序,不重复

8.multiset 底层数据结构为红黑树,有序,可重复

9.map 底层数据结构为红黑树,有序,不重复

10.multimap 底层数据结构为红黑树,有序,可重复

11.unordered_set 底层数据结构为hash表,无序,不重复

12.unordered_multiset 底层数据结构为hash表,无序,可重复

13.unordered_map 底层数据结构为hash表,无序,不重复

14.unordered_multimap 底层数据结构为hash表,无序,可重复

# 24、vector的增加删除都是怎么做的?为什么是1.5或者是2倍?

  1. 新增元素:vector通过一个连续的数组存放元素,如果集合已满,在新增数据的时候,就要分配一块更大的内存,将原来的数据复制过来,释放之前的内存,在插入新增的元素;

  2. 对vector的任何操作,一旦引起空间重新配置,指向原vector的所有迭代器就都失效了 ;

  3. 初始时刻vector的capacity为0,塞入第一个元素后capacity增加为1;

  4. 不同的编译器实现的扩容方式不一样,VS2015中以1.5倍扩容,GCC以2倍扩容。

对比可以发现采用采用成倍方式扩容,可以保证常数的时间复杂度,而增加指定大小的容量只能达到O(n)的时间复杂度,因此,使用成倍的方式扩容。

  1. 考虑可能产生的堆空间浪费,成倍增长倍数不能太大,使用较为广泛的扩容方式有两种,以2二倍的方式扩容,或者以1.5倍的方式扩容。

  2. 以2倍的方式扩容,导致下一次申请的内存必然大于之前分配内存的总和,导致之前分配的内存不能再被使用,所以最好倍增长因子设置为(1,2)之间:

  3. 向量容器vector的成员函数pop_back()可以删除最后一个元素.

  4. 而函数erase()可以删除由一个iterator指出的元素,也可以删除一个指定范围的元素。

  5. 还可以采用通用算法remove()来删除vector容器中的元素.

  6. 不同的是:采用remove一般情况下不会改变容器的大小,而pop_back()与erase()等成员函数会改变容器的大小。

# 25、说一下STL每种容器对应的迭代器

容器 迭代器
vector、deque 随机访问迭代器
stack、queue、priority_queue
list、(multi)set/map 双向迭代器
unordered_(multi)set/map、forward_list 前向迭代器

# 26、STL中迭代器失效的情况有哪些?

以vector为例:

插入元素:

1、尾后插入:size < capacity时,首迭代器不失效尾迭代失效(未重新分配空间),size == capacity时,所有迭代器均失效(需要重新分配空间)。

2、中间插入:中间插入:size < capacity时,首迭代器不失效但插入元素之后所有迭代器失效,size == capacity时,所有迭代器均失效。

删除元素:

尾后删除:只有尾迭代失效。

中间删除:删除位置之后所有迭代失效。

deque 和 vector 的情况类似,

而list双向链表每一个节点内存不连续, 删除节点仅当前迭代器失效,erase返回下一个有效迭代器;

map/set等关联容器底层是红黑树删除节点不会影响其他节点的迭代器, 使用递增方法获取下一个迭代器 mmp.erase(iter++);

unordered_(hash) 迭代器意义不大, rehash之后, 迭代器应该也是全部失效.

# 27、STL中vector的实现

vector是一种序列式容器,其数据安排以及操作方式与array非常类似,两者的唯一差别就是对于空间运用的灵活性,众所周知,array占用的是静态空间,一旦配置了就不可以改变大小,如果遇到空间不足的情况还要自行创建更大的空间,并手动将数据拷贝到新的空间中,再把原来的空间释放。vector则使用灵活的动态空间配置,维护一块连续的线性空间,在空间不足时,可以自动扩展空间容纳新元素,做到按需供给。其在扩充空间的过程中仍然需要经历:重新配置空间,移动数据,释放原空间等操作。这里需要说明一下动态扩容的规则:以原大小的两倍配置另外一块较大的空间(或者旧长度+新增元素的个数),源码:

const size_type len  = old_size + max(old_size, n);
1

Vector扩容倍数与平台有关,在Win + VS 下是 1.5倍,在 Linux + GCC 下是 2 倍

测试代码:

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    //在Linux + GCC下
	vector<int> res(2,0);
	cout << res.capacity() <<endl; //2
	res.push_back(1);
	cout << res.capacity() <<endl;//4
	res.push_back(2);
	res.push_back(3);
    cout << res.capacity() <<endl;//8
	return 0;
    
    
    //在 win 10 + VS2019下
    vector<int> res(2,0);
	cout << res.capacity() <<endl; //2
	res.push_back(1);
	cout << res.capacity() <<endl;//3
	res.push_back(2);
	res.push_back(3);
    cout << res.capacity() <<endl;//6
     
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

运行上述代码,一开始配置了一块长度为2的空间,接下来插入一个数据,长度变为原来的两倍,为4,此时已占用的长度为3,再继续两个数据,此时长度变为8,可以清晰的看到空间的变化过程

需要注意的是,频繁对vector调用push_back()对性能是有影响的,这是因为每插入一个元素,如果空间够用的话还能直接插入,若空间不够用,则需要重新配置空间,移动数据,释放原空间等操作,对程序性能会造成一定的影响

# 28、STL中slist的实现

list是双向链表,而slist(single linked list)是单向链表,它们的主要区别在于:前者的迭代器是双向的Bidirectional iterator,后者的迭代器属于单向的Forward iterator。虽然slist的很多功能不如list灵活,但是其所耗用的空间更小,操作更快。

根据STL的习惯,插入操作会将新元素插入到指定位置之前,而非之后,然而slist是不能回头的,只能往后走,因此在slist的其他位置插入或者移除元素是十分不明智的,但是在slist开头却是可取的,slist特别提供了insert_after()和erase_after供灵活应用。考虑到效率问题,slist只提供push_front()操作,元素插入到slist后,存储的次序和输入的次序是相反的

slist的单向迭代器如下图所示:

slist默认采用alloc空间配置器配置节点的空间,其数据结构主要代码如下

template <class T, class Allco = alloc>
class slist
{
	...
private:
    ...
    static list_node* create_node(const value_type& x){}//配置空间、构造元素
    static void destroy_node(list_node* node){}//析构函数、释放空间
private:
    list_node_base head; //头部
public:
    iterator begin(){}
    iterator end(){}
    size_type size(){}
    bool empty(){}
    void swap(slist& L){}//交换两个slist,只需要换head即可
    reference front(){} //取头部元素
    void push_front(const value& x){}//头部插入元素
    void pop_front(){}//从头部取走元素
    ...
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

举个例子:

#include <forward_list>
#include <algorithm>
#include <iostream>
using namespace std;

int main()
{
	forward_list<int> fl;
	fl.push_front(1);
	fl.push_front(3);
	fl.push_front(2);
	fl.push_front(6);
	fl.push_front(5);

	forward_list<int>::iterator ite1 = fl.begin();
	forward_list<int>::iterator ite2 = fl.end();
	for(;ite1 != ite2; ++ite1)
	{
		cout << *ite1 <<" "; // 5 6 2 3 1
	}
	cout << endl;

	ite1 = find(fl.begin(), fl.end(), 2); //寻找2的位置

	if (ite1 != ite2)
		fl.insert_after(ite1, 99);
	for (auto it : fl)
	{
		cout << it << " ";  //5 6 2 99 3 1
	}
	cout << endl;

	ite1 = find(fl.begin(), fl.end(), 6); //寻找6的位置
	if (ite1 != ite2)
		fl.erase_after(ite1);
	for (auto it : fl)
	{
		cout << it << " ";  //5 6 99 3 1
	}
	cout << endl;	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

需要注意的是C++标准委员会没有采用slist的名称,forward_list在C++ 11中出现,它与slist的区别是没有size()方法。

# 29、STL中list的实现

相比于vector的连续线型空间,list显得复杂许多,但是它的好处在于插入或删除都只作用于一个元素空间,因此list对空间的运用是十分精准的,对任何位置元素的插入和删除都是常数时间。list不能保证节点在存储空间中连续存储,也拥有迭代器,迭代器的“++”、“--”操作对于的是指针的操作,list提供的迭代器类型是双向迭代器:Bidirectional iterators。

list节点的结构见如下源码:

template <class T>
struct __list_node{
    typedef void* void_pointer;
    void_pointer prev;
    void_pointer next;
    T data;
}
1
2
3
4
5
6
7

从源码可看出list显然是一个双向链表。list与vector的另一个区别是,在插入和接合操作之后,都不会造成原迭代器失效,而vector可能因为空间重新配置导致迭代器失效。

此外list也是一个环形链表,因此只要一个指针便能完整表现整个链表。list中node节点指针始终指向尾端的一个空白节点,因此是一种“前闭后开”的区间结构

list的空间管理默认采用alloc作为空间配置器,为了方便的以节点大小为配置单位,还定义一个list_node_allocator函数可一次性配置多个节点空间

由于list的双向特性,其支持在头部(front)和尾部(back)两个方向进行push和pop操作,当然还支持erase,splice,sort,merge,reverse,sort等操作,这里不再详细阐述。

# 30、STL中的deque的实现

vector是单向开口(尾部)的连续线性空间,deque则是一种双向开口的连续线性空间,虽然vector也可以在头尾进行元素操作,但是其头部操作的效率十分低下(主要是涉及到整体的移动)

deque和vector的最大差异一个是deque运行在常数时间内对头端进行元素操作,二是deque没有容量的概念,它是动态地以分段连续空间组合而成,可以随时增加一段新的空间并链接起来

deque虽然也提供随机访问的迭代器,但是其迭代器并不是普通的指针,其复杂程度比vector高很多,因此除非必要,否则一般使用vector而非deque。如果需要对deque排序,可以先将deque中的元素复制到vector中,利用sort对vector排序,再将结果复制回deque

deque由一段一段的定量连续空间组成,一旦需要增加新的空间,只要配置一段定量连续空间拼接在头部或尾部即可,因此deque的最大任务是如何维护这个整体的连续性

deque的数据结构如下:

class deque
{
    ...
protected:
    typedef pointer* map_pointer;//指向map指针的指针
    map_pointer map;//指向map
    size_type map_size;//map的大小
public:
    ...
    iterator begin();
    itertator end();
    ...
}
1
2
3
4
5
6
7
8
9
10
11
12
13

deque内部有一个指针指向map,map是一小块连续空间,其中的每个元素称为一个节点,node,每个node都是一个指针,指向另一段较大的连续空间,称为缓冲区,这里就是deque中实际存放数据的区域,默认大小512bytes。整体结构如上图所示。

deque的迭代器数据结构如下:

struct __deque_iterator
{
    ...
    T* cur;//迭代器所指缓冲区当前的元素
    T* first;//迭代器所指缓冲区第一个元素
    T* last;//迭代器所指缓冲区最后一个元素
    map_pointer node;//指向map中的node
    ...
}
1
2
3
4
5
6
7
8
9

从deque的迭代器数据结构可以看出,为了保持与容器联结,迭代器主要包含上述4个元素

deque迭代器的“++”、“--”操作是远比vector迭代器繁琐,其主要工作在于缓冲区边界,如何从当前缓冲区跳到另一个缓冲区,当然deque内部在插入元素时,如果map中node数量全部使用完,且node指向的缓冲区也没有多余的空间,这时会配置新的map(2倍于当前+2的数量)来容纳更多的node,也就是可以指向更多的缓冲区。在deque删除元素时,也提供了元素的析构和空闲缓冲区空间的释放等机制。

# 31、STL中stack和queue的实现

stack

stack(栈)是一种先进后出(First In Last Out)的数据结构,只有一个入口和出口,那就是栈顶,除了获取栈顶元素外,没有其他方法可以获取到内部的其他元素,其结构图如下:

stack这种单向开口的数据结构很容易由双向开口的deque和list形成,只需要根据stack的性质对应移除某些接口即可实现,stack的源码如下:

template <class T, class Sequence = deque<T> >
class stack
{
	...
protected:
    Sequence c;
public:
    bool empty(){return c.empty();}
    size_type size() const{return c.size();}
    reference top() const {return c.back();}
    const_reference top() const{return c.back();}
    void push(const value_type& x){c.push_back(x);}
    void pop(){c.pop_back();}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

从stack的数据结构可以看出,其所有操作都是围绕Sequence完成,而Sequence默认是deque数据结构。stack这种“修改某种接口,形成另一种风貌”的行为,成为adapter(配接器)。常将其归类为container adapter而非container

stack除了默认使用deque作为其底层容器之外,也可以使用双向开口的list,只需要在初始化stack时,将list作为第二个参数即可。由于stack只能操作顶端的元素,因此其内部元素无法被访问,也不提供迭代器。

queue

queue(队列)是一种先进先出(First In First Out)的数据结构,只有一个入口和一个出口,分别位于最底端和最顶端,出口元素外,没有其他方法可以获取到内部的其他元素,其结构图如下:

类似的,queue这种“先进先出”的数据结构很容易由双向开口的deque和list形成,只需要根据queue的性质对应移除某些接口即可实现,queue的源码如下:

template <class T, class Sequence = deque<T> >
class queue
{
	...
protected:
    Sequence c;
public:
    bool empty(){return c.empty();}
    size_type size() const{return c.size();}
    reference front() const {return c.front();}
    const_reference front() const{return c.front();}
    void push(const value_type& x){c.push_back(x);}
    void pop(){c.pop_front();}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

从queue的数据结构可以看出,其所有操作都也都是是围绕Sequence完成,Sequence默认也是deque数据结构。queue也是一类container adapter。

同样,queue也可以使用list作为底层容器,不具有遍历功能,没有迭代器。

# 32、STL中的heap的实现

heap(堆)并不是STL的容器组件,是priority queue(优先队列)的底层实现机制,因为binary max heap(大根堆)总是最大值位于堆的根部,优先级最高。

binary heap本质是一种complete binary tree(完全二叉树),整棵binary tree除了最底层的叶节点之外,都是填满的,但是叶节点从左到右不会出现空隙,如下图所示就是一颗完全二叉树

完全二叉树内没有任何节点漏洞,是非常紧凑的,这样的一个好处是可以使用array来存储所有的节点,因为当其中某个节点位于$i$处,其左节点必定位于$2i$处,右节点位于$2i+1$处,父节点位于$i/2$(向下取整)处。这种以array表示tree的方式称为隐式表述法。

因此我们可以使用一个array和一组heap算法来实现max heap(每个节点的值大于等于其子节点的值)和min heap(每个节点的值小于等于其子节点的值)。由于array不能动态的改变空间大小,用vector代替array是一个不错的选择。

那heap算法有哪些?常见有的插入、弹出、排序和构造算法,下面一一进行描述。

push_heap插入算法

由于完全二叉树的性质,新插入的元素一定是位于树的最底层作为叶子节点,并填补由左至右的第一个空格。事实上,在刚执行插入操作时,新元素位于底层vector的end()处,之后是一个称为percolate up(上溯)的过程,举个例子如下图:

新元素50在插入堆中后,先放在vector的end()存着,之后执行上溯过程,调整其根结点的位置,以便满足max heap的性质,如果了解大根堆的话,这个原理跟大根堆的调整过程是一样的。

pop_heap算法

heap的pop操作实际弹出的是根节点吗,但在heap内部执行pop_heap时,只是将其移动到vector的最后位置,然后再为这个被挤走的元素找到一个合适的安放位置,使整颗树满足完全二叉树的条件。这个被挤掉的元素首先会与根结点的两个子节点比较,并与较大的子节点更换位置,如此一直往下,直到这个被挤掉的元素大于左右两个子节点,或者下放到叶节点为止,这个过程称为percolate down(下溯)。举个例子:

根节点68被pop之后,移到了vector的最底部,将24挤出,24被迫从根节点开始与其子节点进行比较,直到找到合适的位置安身,需要注意的是pop之后元素并没有被移走,如果要将其移走,可以使用pop_back()。

sort算法

一言以蔽之,因为pop_heap可以将当前heap中的最大值置于底层容器vector的末尾,heap范围减1,那么不断的执行pop_heap直到树为空,即可得到一个递增序列。

make_heap算法

将一段数据转化为heap,一个一个数据插入,调用上面说的两种percolate算法即可。

代码实测:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
	vector<int> v = { 0,1,2,3,4,5,6 };
	make_heap(v.begin(), v.end()); //以vector为底层容器
	for (auto i : v)
	{
		cout << i << " "; // 6 4 5 3 1 0 2
	}
	cout << endl;
	v.push_back(7);
	push_heap(v.begin(), v.end());
	for (auto i : v)
	{
		cout << i << " "; // 7 6 5 4 1 0 2 3
	}
	cout << endl;
	pop_heap(v.begin(), v.end());
	cout << v.back() << endl; // 7 
	v.pop_back();
	for (auto i : v)
	{
		cout << i << " "; // 6 4 5 3 1 0 2
	}
	cout << endl;
	sort_heap(v.begin(), v.end());
	for (auto i : v)
	{
		cout << i << " "; // 0 1 2 3 4 5 6
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

# 33、STL中的priority_queue的实现

priority_queue,优先队列,是一个拥有权值观念的queue,它跟queue一样是顶部入口,底部出口,在插入元素时,元素并非按照插入次序排列,它会自动根据权值(通常是元素的实值)排列,权值最高,排在最前面,如下图所示。

默认情况下,priority_queue使用一个max-heap完成,底层容器使用的是一般为vector为底层容器,堆heap为处理规则来管理底层容器实现 。priority_queue的这种实现机制导致其不被归为容器,而是一种容器配接器。关键的源码如下:

template <class T, class Squence = vector<T>, 
class Compare = less<typename Sequence::value_tyoe> >
class priority_queue{
	...
protected:
    Sequence c; // 底层容器
    Compare comp; // 元素大小比较标准
public:
    bool empty() const {return c.empty();}
    size_type size() const {return c.size();}
    const_reference top() const {return c.front()}
    void push(const value_type& x)
    {
        c.push_heap(x);
        push_heap(c.begin(), c.end(),comp);
    }
    void pop()
    {
        pop_heap(c.begin(), c.end(),comp);
        c.pop_back();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

priority_queue的所有元素,进出都有一定的规则,只有queue顶端的元素(权值最高者),才有机会被外界取用,它没有遍历功能,也不提供迭代器

举个例子:

#include <queue>
#include <iostream>
using namespace std;

int main()
{
	int ia[9] = {0,4,1,2,3,6,5,8,7 };
	priority_queue<int> pq(ia, ia + 9);
	cout << pq.size() <<endl;  // 9
	for(int i = 0; i < pq.size(); i++)
	{
		cout << pq.top() << " "; // 8 8 8 8 8 8 8 8 8
	}
	cout << endl;
	while (!pq.empty())
	{
		cout << pq.top() << ' ';// 8 7 6 5 4 3 2 1 0
		pq.pop();
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 34、STL中set的实现?

STL中的容器可分为序列式容器(sequence)和关联式容器(associative),set属于关联式容器。

set的特性是,所有元素都会根据元素的值自动被排序(默认升序),set元素的键值就是实值,实值就是键值,set不允许有两个相同的键值

set不允许迭代器修改元素的值,其迭代器是一种constance iterators

标准的STL set以RB-tree(红黑树)作为底层机制,几乎所有的set操作行为都是转调用RB-tree的操作行为,这里补充一下红黑树的特性:

  • 每个节点不是红色就是黑色
  • 根结点为黑色
  • 如果节点为红色,其子节点必为黑
  • 任一节点至(NULL)树尾端的任何路径,所含的黑节点数量必相同

关于红黑树的具体操作过程,比较复杂读者可以翻阅《算法导论》详细了解。

举个例子:

#include <set>
#include <iostream>
using namespace std;


int main()
{
	int i;
	int ia[5] = { 1,2,3,4,5 };
	set<int> s(ia, ia + 5);
	cout << s.size() << endl; // 5
	cout << s.count(3) << endl; // 1
	cout << s.count(10) << endl; // 0

	s.insert(3); //再插入一个3
	cout << s.size() << endl; // 5
	cout << s.count(3) << endl; // 1

	s.erase(1);
	cout << s.size() << endl; // 4

	set<int>::iterator b = s.begin();
	set<int>::iterator e = s.end();
	for (; b != e; ++b)
		cout << *b << " "; // 2 3 4 5
	cout << endl;

	b = find(s.begin(), s.end(), 5);
	if (b != s.end())
		cout << "5 found" << endl; // 5 found

	b = s.find(2);
	if (b != s.end())
		cout << "2 found" << endl; // 2 found

	b = s.find(1);
	if (b == s.end())
		cout << "1 not found" << endl; // 1 not found
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

关联式容器尽量使用其自身提供的find()函数查找指定的元素,效率更高,因为STL提供的find()函数是一种顺序搜索算法。

# 35、STL中map的实现

map的特性是所有元素会根据键值进行自动排序。map中所有的元素都是pair,拥有键值(key)和实值(value)两个部分,并且不允许元素有相同的key

一旦map的key确定了,那么是无法修改的,但是可以修改这个key对应的value,因此map的迭代器既不是constant iterator,也不是mutable iterator

标准STL map的底层机制是RB-tree(红黑树),另一种以hash table为底层机制实现的称为hash_map。map的架构如下图所示

map的在构造时缺省采用递增排序key,也使用alloc配置器配置空间大小,需要注意的是在插入元素时,调用的是红黑树中的insert_unique()方法,而非insert_euqal()(multimap使用)

举个例子:

#include <map>
#include <iostream>
#include <string>
using namespace std;

int main()
{
	map<string, int> maps;
    //插入若干元素
	maps["jack"] = 1;
	maps["jane"] = 2;
	maps["july"] = 3;
	//以pair形式插入
	pair<string, int> p("david", 4);
	maps.insert(p);
	//迭代输出元素
	map<string, int>::iterator iter = maps.begin();
	for (; iter != maps.end(); ++iter)
	{
		cout << iter->first << " ";
		cout << iter->second << "--"; //david 4--jack 1--jane 2--july 3--
	}
	cout << endl;
	//使用subscipt操作取实值
	int num = maps["july"];
	cout << num << endl; // 3
	//查找某key
	iter = maps.find("jane");
	if(iter != maps.end())
		cout << iter->second << endl; // 2
    //修改实值
	iter->second = 100;
	int num2 = maps["jane"]; // 100
	cout << num2 << endl;
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

需要注意的是subscript(下标)操作既可以作为左值运用(修改内容)也可以作为右值运用(获取实值)。例如:

maps["abc"] = 1; //左值运用int num = masp["abd"]; //右值运用
1

无论如何,subscript操作符都会先根据键值找出实值,源码如下:

...T& operator[](const key_type& k){	
    return (*((insert(value_type(k, T()))).first)).second;
}...
1
2
3

代码运行过程是:首先根据键值和实值做出一个元素,这个元素的实值未知,因此产生一个与实值型别相同的临时对象替代:

value_type(k, T());
1

再将这个对象插入到map中,并返回一个pair:

pair<iterator,bool> insert(value_type(k, T()));
1

pair第一个元素是迭代器,指向当前插入的新元素,如果插入成功返回true,此时对应左值运用,根据键值插入实值。插入失败(重复插入)返回false,此时返回的是已经存在的元素,则可以取到它的实值

(insert(value_type(k, T()))).first; //迭代器
*((insert(value_type(k, T()))).first); //解引用
(*((insert(value_type(k, T()))).first)).second; //取出实值
1
2
3

由于这个实值是以引用方式传递,因此作为左值或者右值都可以

# 36、set和map的区别,multimap和multiset的区别

set只提供一种数据类型的接口,但是会将这一个元素分配到key和value上,而且它的compare_function用的是 identity()函数,这个函数是输入什么输出什么,这样就实现了set机制,set的key和value其实是一样的了。其实他保存的是两份元素,而不是只保存一份元素

map则提供两种数据类型的接口,分别放在key和value的位置上,他的比较function采用的是红黑树的comparefunction(),保存的确实是两份元素。

他们两个的insert都是采用红黑树的insert_unique() 独一无二的插入 。

multimap和map的唯一区别就是:multimap调用的是红黑树的insert_equal(),可以重复插入而map调用的则是独一无二的插入insert_unique(),multiset和set也一样,底层实现都是一样的,只是在插入的时候调用的方法不一样。

红黑树概念

面试时候现场写红黑树代码的概率几乎为0,但是红黑树一些基本概念还是需要掌握的。

1、它是二叉排序树(继承二叉排序树特显):

  • 若左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值。

  • 若右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值。

    • 左、右子树也分别为二叉排序树。

    2、它满足如下几点要求:

    • 树中所有节点非红即黑。

    • 根节点必为黑节点。

    • 红节点的子节点必为黑(黑节点子节点可为黑)。

    • 从根到NULL的任何路径上黑结点数相同。

    3、查找时间一定可以控制在O(logn)。

# 37、STL中unordered_map和map的区别和应用场景

map支持键值的自动排序,底层机制是红黑树,红黑树的查询和维护时间复杂度均为$O(logn)$,但是空间占用比较大,因为每个节点要保持父节点、孩子节点及颜色的信息

unordered_map是C++ 11新添加的容器,底层机制是哈希表,通过hash函数计算元素位置,其查询时间复杂度为O(1),维护时间与bucket桶所维护的list长度有关,但是建立hash表耗时较大

从两者的底层机制和特点可以看出:map适用于有序数据的应用场景,unordered_map适用于高效查询的应用场景

# 38、hashtable中解决冲突有哪些方法?

记住前三个:

线性探测

使用hash函数计算出的位置如果已经有元素占用了,则向后依次寻找,找到表尾则回到表头,直到找到一个空位

开链

每个表格维护一个list,如果hash函数计算出的格子相同,则按顺序存在这个list中

再散列

发生冲突时使用另一种hash函数再计算一个地址,直到不冲突

二次探测

使用hash函数计算出的位置如果已经有元素占用了,按照$1^2$、$2^2$、$3^2$...的步长依次寻找,如果步长是随机数序列,则称之为伪随机探测

公共溢出区

一旦hash函数计算的结果相同,就放入公共溢出区