STL模板库

1、什么是STL?

C++ STL从广义来讲包括了三类:算法,容器和迭代器。

算法包括排序,复制等常用算法,以及不同容器特定的算法。

容器就是数据的存放形式,包括序列式容器和关联式容器,序列式容器就是list,vector等,关联式容器就是set,map等。

迭代器就是在不暴露容器内部结构的情况下对容器的遍历。

迭代器与指针的差别:

迭代器:

(1) 迭代器不是指针,是类模板,表现的像指针。他只是 模拟了指针的一些功能,通过重载了指针的一些操作符,->,*,++ --等封装了指针, 指针能指向函数而迭代器不行,迭代器只能指向容器;而指针是存放一个对象地址的指针变量

(2)迭代器返回的是对象引用而不是对象的值。

2、解释一下什么是trivial destructor

“trivial destructor”一般是指用户没有自定义析构函数,由系统自动生成的析构函数,这种析构函数在《STL源码解析》中称为“无关痛痒”的析构函数。

反之,由用户自定义的析构函数,则称之为“non-trivial destructor”,这种析构函数如果申请了新的空间一定要显式的释放,否则会造成内存泄露

对于trivial destructor,如果每次都进行调用,显然对效率是一种伤害,如何进行判断呢?

《STL源码解析》中给出的说明是:

首先利用value_type()获取所指对象的型别,再利用__type_traits判断该型别的析构函数是否trivial,若是(__true_type),则什么也不做,若为(__false_type),则去调用destory()函数

也就是说,在实际的应用当中,STL库提供了相关的判断方法__type_traits,感兴趣的读者可以自行查阅使用方式。除了trivial destructor,还有trivial construct、trivial copy construct等,如果能够对是否trivial进行区分,可以采用内存处理函数memcpy()、malloc()等更加高效的完成相关操作,提升效率。

3、使用智能指针管理内存资源,RAII是怎么回事?

RAII全称是“Resource Acquisition is Initialization”,直译过来是“资源获取即初始化”,也就是说在构造函数中申请分配资源,在析构函数中释放资源。

因为C++的语言机制保证了,当一个对象创建的时候,自动调用构造函数,当对象超出作用域的时候会自动调用析构函数。所以,在RAII的指导下,我们应该使用类来管理资源,将资源和对象的生命周期绑定。

智能指针(std::shared_ptr和std::unique_ptr)即RAII最具代表的实现,使用智能指针,可以实现自动的内存管理,再也不需要担心忘记delete造成的内存泄漏。

毫不夸张的来讲,有了智能指针,代码中几乎不需要再出现delete了。

4、迭代器:++it、it++哪个好,为什么

前置返回一个引用,后置返回一个临时对象

// ++i实现代码为:
int& operator++(){ 
    *this += 1; 
    return *this;
}

前置不会产生临时对象,后置必须产生临时对象,临时对象会导致效率降低

//i++实现代码为: 
int operator++(int) {
    int temp = *this; 
    ++*this; 
    return temp; 
}

5、说一下C++左值引用和右值引用

C++11正是通过引入右值引用来优化性能,具体来说是通过移动语义来避免无谓拷贝的问题,通过move语义来将临时生成的左值中的资源无代价的转移到另外一个对象中去,通过完美转发来解决不能按照参数实际类型来转发的问题(同时,完美转发获得的一个好处是可以实现移动语义)。

在C++11中所有的值必属于左值、右值两者之一,右值又可以细分为纯右值、将亡值。在C++11中可以取地址的、有名字的就是左值,反之,不能取地址的、没有名字的就是右值(将亡值或纯右值)。举个例子,int a = b+c, a 就是左值,其有变量名为a,通过&a可以获取该变量的地址;表达式b+c、函数int func()的返回值是右值,在其被赋值给某一变量前,我们不能通过变量名找到它,&(b+c)这样的操作则不会通过编译。

C++11对C++98中的右值进行了扩充。在C++11中右值又分为纯右值(prvalue,Pure Rvalue)和将亡值(xvalue,eXpiring Value)。其中纯右值的概念等同于我们在C++98标准中右值的概念,指的是临时变量和不跟对象关联的字面量值;将亡值则是C++11新增的跟右值引用相关的表达式,这样表达式通常是将要被移动的对象(移为他用),比如返回右值引用T&&的函数返回值、std::move的返回值,或者转换为T&&的类型转换函数的返回值。将亡值可以理解为通过“盗取”其他变量内存空间的方式获取到的值。在确保其他变量不再被使用、或即将被销毁时,通过“盗取”的方式可以避免内存空间的释放和分配,能够延长变量值的生命期。

左值引用就是对一个左值进行引用的类型。右值引用就是对一个右值进行引用的类型,事实上,由于右值通常不具有名字,我们也只能通过引用的方式找到它的存在。右值引用和左值引用都是属于引用类型。无论是声明一个左值引用还是右值引用,都必须立即进行初始化。而其原因可以理解为是引用类型本身自己并不拥有所绑定对象的内存,只是该对象的一个别名。左值引用是具名变量值的别名,而右值引用则是不具名(匿名)变量的别名。左值引用通常也不能绑定到右值,但常量左值引用是个“万能”的引用类型。它可以接受非常量左值、常量左值、右值对其进行初始化。不过常量左值所引用的右值在它的“余生”中只能是只读的。相对地,非常量左值只能接受非常量左值对其进行初始化。

右值值引用通常不能绑定到任何的左值,要想绑定一个左值到右值引用,通常需要std::move()将左值强制转换为右值。

左值和右值

左值:表示的是可以获取地址的表达式,它能出现在赋值语句的左边,对该表达式进行赋值。但是修饰符const的出现使得可以声明如下的标识符,它可以取得地址,但是没办法对其进行赋值

const int& a = 10;

右值:表示无法获取地址的对象,有常量值、函数返回值、lambda表达式等。无法获取地址,但不表示其不可改变,当定义了右值的右值引用时就可以更改右值。

左值引用和右值引用

左值引用:传统的C++中引用被称为左值引用

右值引用:C++11中增加了右值引用,右值引用关联到右值时,右值被存储到特定位置,右值引用指向该特定位置,也就是说,右值虽然无法获取地址,但是右值引用是可以获取地址的,该地址表示临时对象的存储位置

这里主要说一下右值引用的特点:

特点1:通过右值引用的声明,右值又“重获新生”,其生命周期与右值引用类型变量的生命周期一样长,只要该变量还活着,该右值临时量将会一直存活下去

特点2:右值引用独立于左值和右值。意思是右值引用类型的变量可能是左值也可能是右值

特点3:T&& t在发生自动类型推断的时候,它是左值还是右值取决于它的初始化。

#include <iostream>
#include <utility> // for std::move

// 这是一个转发引用(万能引用)的例子
template<typename T>
void handleValue(T&& t) { // T&& 的具体类型由传入的实参决定
    // ... 可以对 t 进行一些操作
}

int main() {
    int x = 10;

    // 情况 1:用左值初始化
    handleValue(x); // x 是左值
    // 推导过程:
    // T 被推导为 int& (因为要匹配左值x)
    // 函数签名变为 void handleValue(int& && t)
    // 应用引用折叠规则:int& && -> int&
    // 所以最终函数实例化为:void handleValue(int& t)
    // 此时,参数 t 是一个左值引用,绑定到了变量 x 上。

    // 情况 2:用右值初始化
    handleValue(20); // 20 是右值
    handleValue(std::move(x)); // std::move(x) 产生一个右值
    // 推导过程:
    // T 被推导为 int (注意,不是 int&&)
    // 函数签名变为 void handleValue(int&& t)
    // 所以最终函数实例化为:void handleValue(int&& t)
    // 此时,参数 t 是一个右值引用,绑定到了一个临时对象(20)或 x 转换成的右值上。

    return 0;
}

6、STL中hashtable的实现?

STL中的hashtable使用的是开链法解决hash冲突问题,如下图所示。

STL模板库

hashtable中的bucket所维护的list既不是list也不是slist,而是其自己定义的由hashtable_node数据结构组成的linked-list,而bucket聚合体本身使用vector进行存储。hashtable的迭代器只提供前进操作,不提供后退操作

在hashtable设计bucket的数量上,其内置了28个质数[53, 97, 193,...,429496729],在创建hashtable时,会根据存入的元素个数选择大于等于元素个数的质数作为hashtable的容量(vector的长度),其中每个bucket所维护的linked-list长度也等于hashtable的容量。如果插入hashtable的元素个数超过了bucket的容量,就要进行重建table操作,即找出下一个质数,创建新的buckets vector,重新计算元素在新hashtable的位置。

7、简单说一下STL中的traits技法

traits技法利用“内嵌型别“的编程技巧与编译器的template参数推导功能,增强C++未能提供的关于型别认证方面的能力。常用的有iterator_traits和type_traits。

iterator_traits被称为特性萃取机,能够方便的让外界获取以下5中型别:

value_type:迭代器所指对象的型别

difference_type:两个迭代器之间的距离

pointer:迭代器所指向的型别

reference:迭代器所引用的型别

iterator_category:三两句说不清楚,建议看书

type_traits

关注的是型别的特性,例如这个型别是否具备non-trivial defalt ctor(默认构造函数)、non-trivial copy ctor(拷贝构造函数)、non-trivial assignment operator(赋值运算符) 和non-trivial dtor(析构函数),如果答案是否定的,可以采取直接操作内存的方式提高效率,一般来说,type_traits支持以下5中类型的判断:

__type_traits<T>;
::has_trivial_default_constructor__type_traits<T>;
::has_trivial_copy_constructor__type_traits<T>;
::has_trivial_assignment_operator__type_traits<T>;
::has_trivial_destructor__type_traits<T>;
::is_POD_type

由于编译器只针对class object形式的参数进行参数推到,因此上式的返回结果不应该是个bool值,实际上使用的是一种空的结构体:

struct __true_type{};
struct __false_type{};

这两个结构体没有任何成员,不会带来其他的负担,又能满足需求,可谓一举两得

当然,如果我们自行定义了一个Shape类型,也可以针对这个Shape设计type_traits的特化版本

template<> struct __type_traits<Shape>;
{ 
typedef __true_type has_trivial_default_constructor; 
typedef __false_type has_trivial_copy_constructor; 
typedef __false_type has_trivial_assignment_operator; 
typedef __false_type has_trivial_destructor; 
typedef __false_type is_POD_type;
};

8、STL的两级空间配置器

1、首先明白为什么需要二级空间配置器?

我们知道动态开辟内存时,要在堆上申请,但若是我们需要频繁的在堆开辟释放内存,则就会在堆上造成很多外部碎片,浪费了内存空间;每次都要进行调用malloc、free函数等操作,使空间就会增加一些附加信息,降低了空间利用率;随着外部碎片增多,内存分配器在找不到合适内存情况下需要合并空闲块,浪费了时间,大大降低了效率。于是就设置了二级空间配置器,当开辟内存<=128bytes时,即视为开辟小块内存,则调用二级空间配置器。关于STL中一级空间配置器和二级空间配置器的选择上,一般默认选择的为二级空间配置器。 如果大于128字节再转去一级配置器器。

一级配置器

一级空间配置器中重要的函数就是allocate、deallocate、reallocate 。 一级空间配置器是以malloc(),free(),realloc()等C函数执行实际的内存配置 。大致过程是:

1、直接allocate分配内存,其实就是malloc来分配内存,成功则直接返回,失败就调用处理函数

2、如果用户自定义了内存分配失败的处理函数就调用,没有的话就返回异常

3、如果自定义了处理函数就进行处理,完事再继续分配试试

STL模板库

二级配置器

STL模板库

1、维护16条链表,分别是0-15号链表,最小8字节,以8字节逐渐递增,最大128字节,你传入一个字节参数,表示你需要多大的内存,会自动帮你校对到第几号链表(如需要13bytes空间,我们会给它分配16bytes大小),在找到第n个链表后查看链表是否为空,如果不为空直接从对应的free_list中拔出,将已经拨出的指针向后移动一位。

2、对应的free_list为空,先看其内存池是不是空时,如果内存池不为空:
(1)先检验它剩余空间是否够20个节点大小(即所需内存大小(提升后) * 20),若足够则直接从内存池中拿出20个节点大小空间,将其中一个分配给用户使用,另外19个当作自由链表中的区块挂在相应的free_list下,这样下次再有相同大小的内存需求时,可直接拨出。
(2)如果不够20个节点大小,则看它是否能满足1个节点大小,如果够的话则直接拿出一个分配给用户,然后从剩余的空间中分配尽可能多的节点挂在相应的free_list中。
(3)如果连一个节点内存都不能满足的话,则将内存池中剩余的空间挂在相应的free_list中(找到相应的free_list),然后再给内存池申请内存,转到3。
3、内存池为空,申请内存 此时二级空间配置器会使用malloc()从heap上申请内存,(一次所申请的内存大小为2 所需节点内存大小(提升后) 20 + 一段额外空间),申请40块,一半拿来用,一半放内存池中。
4、malloc没有成功 在第三种情况下,如果malloc()失败了,说明heap上没有足够空间分配给我们了,这时,二级空间配置器会从比所需节点空间大的free_list中一一搜索,从比它所需节点空间大的free_list中拔除一个节点来使用。如果这也没找到,说明比其大的free_list中都没有自由区块了,那就要调用一级适配器了。

释放时调用deallocate()函数,若释放的n>128,则调用一级空间配置器,否则就直接将内存块挂上自由链表的合适位置。

STL二级空间配置器虽然解决了外部碎片与提高了效率,但它同时增加了一些缺点:

1.因为自由链表的管理问题,它会把我们需求的内存块自动提升为8的倍数,这时若你需要1个字节,它会给你8个字节,即浪费了7个字节,所以它又引入了内部碎片的问题,若相似情况出现很多次,就会造成很多内部碎片;

2.二级空间配置器是在堆上申请大块的狭义内存池,然后用自由链表管理,供现在使用,在程序执行过程中,它将申请的内存一块一块都挂在自由链表上,即不会还给操作系统,并且它的实现中所有成员全是静态的,所以它申请的所有内存只有在进程结束才会释放内存,还给操作系统,由此带来的问题有:1.即我不断的开辟小块内存,最后整个堆上的空间都被挂在自由链表上,若我想开辟大块内存就会失败;2.若自由链表上挂很多内存块没有被使用,当前进程又占着内存不释放,这时别的进程在堆上申请不到空间,也不可以使用当前进程的空闲内存,由此就会引发多种问题。

一级分配器

GC4.9之后就没有第一级了,只有第二级

二级分配器

——default_alloc_template 剖析

有个自动调整的函数:你传入一个字节参数,表示你需要多大的内存,会自动帮你校对到第几号链表(0-15号链表,最小8字节 最大128字节)

allocate函数:如果要分配的内存大于128字节,就转用第一级分配器,否则也就是小于128字节。那么首先判断落在第几号链表,定位到了,先判断链表是不是空,如果是空就需要充值,(调节到8的倍数,默认一次申请20个区块,当然了也要判断20个是不是能够申请到,如果只申请到一个那就直接返回好了,不止一个的话,把第2到第n个挨个挂到当前链表上,第一个返回回去给容器用,n是不大于20的,当然了如果不在1-20之间,那就是内存碎片了,那就先把碎片挂到某一条链表上,然后再重新malloc了,malloc 2*20个块)去内存池去拿或者重新分配。不为空的话

数据结构描述
Vector(动态数组)底层数据结构为数组,支持快速随机访问和动态大小调整。
List(双向链表)底层数据结构为链表,支持快速插入和删除操作。
Deque(双端队列)底层数据结构通常由中央控制器和多个缓冲区组成,支持快速的首尾插入和删除操作。
Stack(栈)底层一般使用list或deque实现,封装头部操作以实现栈的功能。
Queue(队列)底层一般使用list或deque实现,封装头部操作以实现队列的功能。
Priority_queue(优先队列)底层数据结构一般为vector,通过堆(heap)来管理底层容器以实现有序的优先级操作。
Set(集合)底层数据结构为红黑树,有序且不重复。
Map(映射)底层数据结构为红黑树,有序的键值对集合,键不重复。
Hash_set(哈希集合)底层数据结构为哈希表,无序且元素不重复。
数据结构时间复杂度
std::unordered_set最好:O(1) 最坏:O(N)
std::unordered_map最好:O(1) 最坏:O(N)
std::vector访问,对尾插入/删除O(1);中间插入/删除:O(n)
std::dequeO(1)
std::listO(1)
std::setO(logN)
std::mapO(logN)
std::priority_queueO(logN)
std::stackO(1)
std::queueO(1)

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表,无序,可重复

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

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

vector与list的区别与应用?怎么找某vector或者list的倒数第二个元素

围绕内存空间分布、增删查改进行阐述

Vector是一个动态数组的容器,元素的存储是连续的。

插入和删除元素的时间复杂度为O(n),因为可能需要移动其他元素,尤其是在中间位置插入或删除元素时。

在访问元素方面,由于具备随机访问特性,可以通过下标访问元素,时间复杂度为O(1)。

向量的扩容和收缩可能会导致内存的重新分配和元素的复制,因此在需要频繁插入和删除的场景下效率较低。

向量的内存空间是连续分配的,因此对于需要高效的随机访问操作的场景,vector更合适。

相对于list来说,vector在占用内存空间方面更为节省。

vector与数组最大的区别就是vector不需程序员自己去考虑容量问题,库里面本身已经实现了容量的动态增长,而数组需要程序员手动扩容

List是一个双向链表的容器,每个元素都由一个节点表示,节点包含指向前一个节点和后一个节点的指针。

插入和删除元素的时间复杂度为O(1),因为只需要改变节点的指针,而不需要移动其他元素。

由于节点间的指针关联,内存空间不是连续分配的,因此对于需要频繁的插入和删除操作的场景,list可以更高效。

在访问元素方面,由于不具备随机访问特性,只能通过迭代器逐个遍历,时间复杂度为O(n)。

list可以有效地处理大规模数据的插入和删除,但相对于vector来说占用更多的内存空间。

区别:

vector的随机访问效率高,但在插入和删除时(不包括尾部)需要挪动数据,不易操作。list的访问要遍历整个链表,它的随机访问效率低。但对数据的插入和删除操作等都比较方便,改变指针的指向即可。list是单向的,vector是双向的。vector中的迭代器在使用后就失效了,而list的迭代器在使用之后还可以继续使用。

vector和deque的区别⭐⭐⭐

双端操作:可以在头部和尾部进行高效的插入和删除操作。

分段结构:内部实现采用分段的数据结构,只需要移动对应段内的元素,而不需要移动整个容器中的元素。

随机访问:支持通过索引进行随机访问,可以在常量时间内访问任意位置的元素。

迭代器稳定性:插入和删除不会使已存在的迭代器失效。

增长特性:根据需要自动增长内部存储空间。

内存分配效率:在增加新的段时分配更多的内存空间,提高内存利用效率。

STL模板库

Deque和vector的区别:

插入和删除操作:Deque支持在头部和尾部高效地插入和删除元素,而Vector只能在尾部进行高效操作。

内部实现:Deque采用分段的数据结构,而Vector是一块连续的存储空间。

内存分配方式:Deque在扩容时能更高效地利用内存,并避免频繁的重分配,而Vector需要重新分配整块连续的内存空间。

随机访问性能:Vector的随机访问性能更好,而Deque的随机访问相对较低。

Deque和vector和LIST使用场景:

如果需要高效的随机存取,而不需要在乎插入和删除的效率,使用 vector;

如果需要大量的插入和删除,而不需要关心随机存取,则应使用 list;

如果需要随机存取,而且需要关心两端数据的插入和删除,则应使用 deque。

Vector的底层实现(动态扩展原理)

STL模板库

Vector在堆中分配了一段连续的内存空间来存放元素。

包括三个迭代器,first指向的是vector中对象的起始字节位置;last指向当前最后一个元素的末尾字节;end指向整个vector容器所占用内存空间的末尾字节

vector是动态空间,随着元素的加入,它的内部机制会自动扩充空间以容纳新的元素。vector的关键技术在于对大小的控制以及重新分配时的数据移动效率。

vector采用的数据结构是线性的连续空间(泛型的动态类型顺序表),他以两个迭代器start和finish分别指向配置得来的连续空间中目前已将被使用的空间。迭代器end_of_storage指向整个连续的尾部。

vector在增加元素时,如果超过自身最大的容量,vector则将自身的容量扩充为原来的两倍。扩充空间需要经过的步骤:重新配置空间,元素移动,释放旧的内存空间。一旦vector空间重新配置,则指向原来vector的所有迭代器都失效了,因为vector的地址改变了。

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

为什么要以这样的方式实现自动拓展呢?

对比可以发现采用采用成倍方式扩容,避免频繁的内存重分配和复制,可以保证常数的时间复杂度,而增加指定大小的容量只能达到O(n)的时间复杂度,因此,使用成倍的方式扩容

vector各种成员函数的区别

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

向量容器vector的成员函数pop_back()可以删除最后一个元素;函数erase()可以删除由一个iterator指出的元素,也可以删除一个指定范围的元素。还可以采用通用算法remove()来删除vector容器中的元素.

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

size()函数返回的是已用空间大小,capacity()返回的是总空间大小,capacity()-size()则是剩余的可用空间大小。当size()和capacity()相等,说明vector目前的空间已被用完,如果再添加新元素,则会引起vector空间的动态增长。

reserve(n)预先分配一块较大的指定大小的内存空间,这样当指定大小的内存空间未使用完时,是不会重新分配内存空间的,这样便提升了效率。只有当n>capacity()时,调用reserve(n)才会改变vector容量。resize()成员函数只改变元素的数目,不改变vector的容量。resize()函数只改变容器的元素数目,未改变容器大小。用reserve(size_type)只是扩大capacity值,这些内存空间可能还是“野”的,如果此时使用“[ ]”来访问,则可能会越界。而resize(size_type new_size)会真正使容器具有new_size个对象

Vector如何释放空间?

由于vector的内存占用空间只增不减,比如你首先分配了10,000个字节,然后erase掉后面9,999个,留下一个有效元素,但是内存占用仍为10,000个。所有内存空间是在vector析构时候才能被系统回收empty()用来检测容器是否为空的,clear()可以清空所有元素。但是即使clear(),vector所占用的内存空间依然如故,无法保证内存的回收。

如果要想在删除内容的同时释放内存,那么你可以选择deque容器。

如果需要空间动态缩小,可以考虑使用deque。如果vector,可以用swap()来帮助你释放内存。

vector(Vec).swap(Vec); 将Vec的内存空洞清除; 
vector().swap(Vec); 清空Vec的内存;

vector越界访问下标,map越界访问下标?

通过下标访问vector中的元素时不会做边界检查,即便下标越界。也就是说,下标与first迭代器相加的结果超过了finish迭代器的位置,程序也不会报错,而是返回这个地址中存储的值。如果想在访问vector中的元素时首先进行边界检查,可以使用vector中的at函数。通过使用at函数不但可以通过下标访问vector中的元素,而且在at函数内部会对下标进行边界检查。map的下标运算符[]的作用是:将key作为下标去执行查找,并返回相应的值;如果不存在这个key,就将一个具有该key和value的某值插入这个map。

push_back与emplace_back的区别:

关键区别 - 在容器中直接构造对象(In-Place Construction)

这是 emplace_back 真正发挥优势的地方。你可以将构造 类 所需的参数直接传递给 emplace_back,它会在 vector 分配的内存中直接构造对象,完全省去了创建临时对象和拷贝/移动的步骤

12、容器内部删除一个元素

顺序容器(序列式容器,比如vector、deque)

erase迭代器不仅使所指向被删除的迭代器失效,而且使被删元素之后的所有迭代器失效(list除外),所以不能使用erase(it++)的方式,但是erase的返回值是下一个有效迭代器

It = c.erase(it);

关联容器(关联式容器,比如map、set、multimap、multiset等)

erase迭代器只是被删除元素的迭代器失效,但是返回值是void,所以要采用erase(it++)的方式删除迭代器;

c.erase(it++)

vector容器:在删除元素时需要确保迭代器的有效性。可以使用erase函数来删除元素,并且要注意将erase函数返回的下一个元素的迭代器保存起来,以便正确遍历容器。

auto it = vec.begin();  
while (it != vec.end()) {  
    if (*it % 2 == 0) { // 删除偶数  
        it = vec.erase(it); // erase返回下一个有效迭代器  
    } else {  
        ++it;  
    }  
}

map和set容器:由于其底层数据结构为红黑树,删除当前元素不会影响到下一个元素的迭代器,因此在调用erase函数之前,记录下一个元素的迭代器是一种常见的处理方式。

auto it = myMap.begin();  
while (it != myMap.end()) {  
    if (it->first % 2 == 0) { // 删除key为偶数的元素  
        auto next_it = std::next(it); // 先保存下一个  
        myMap.erase(it); // 删除当前  
        it = next_it; // 跳转到下一个  
    } else {  
        ++it;  
    }  
}

list容器:由于其底层数据结构是链表,使用了不连续分配的内存,且erase函数会返回下一个有效的迭代器,所以无论是记录下一个元素的迭代器还是使用erase返回的迭代器,两种方式都是可行的。

13、STL迭代器如何实现

1、 迭代器是一种抽象的设计理念,通过迭代器可以在不了解容器内部原理的情况下遍历容器,除此之外,STL中迭代器一个最重要的作用就是作为容器与STL算法的粘合剂。

2、 迭代器的作用就是提供一个遍历容器内部所有元素的接口,因此迭代器内部必须保存一个与容器相关联的指针,然后重载各种运算操作来遍历,其中最重要的是*运算符与->运算符,以及++、--等可能需要重载的运算符重载。这和C++中的智能指针很像,智能指针也是将一个指针封装,然后通过引用计数或是其他方法完成自动释放内存的功能。

3、最常用的迭代器的相应型别有五种:value type、difference type、pointer、reference、iterator catagoly;

14、map、set是怎么实现的,红黑树是怎么能够同时实现这两种容器? 为什么使用红黑树?

他们的底层都是以红黑树的结构实现,因此插入删除等操作都在O(logn时间内完成,因此可以完成高效的插入删除;

在这里我们定义了一个模版参数,如果它是key那么它就是set,如果它是map,那么它就是map;底层是红黑树,实现map的红黑树的节点数据类型是key+value,而实现set的节点数据类型是value

因为map和set要求是自动排序的,红黑树能够实现这一功能,而且时间复杂度比较低。

14、hashmap的底层数据结构讲一下(什么时候升级成树,什么时候退化)

底层数据结构:数组+链表/红黑树的组合

树化条件链表长度≥8 数组容量≥64。

退化条件节点数≤6 或 扩容拆分后节点数不足至阈值之下 树结构被破坏。

核心目的:在哈希冲突严重时通过红黑树提升查询效率,在冲突缓解时通过退化节省资源

为什么设置节点为6为退化阈值,怎么中间有个节点为7的情况呢?

树化阈值(8)与退化阈值(6)之间的差值为2,确保结构转换仅在哈希冲突持续严重或缓解时发生,而非临时波动,能够有效避免因为哈希的元素微小波动导致结构的频繁转换

15、如何在共享内存上使用STL标准库?

想像一下把STL容器,例如map, vector, list等等,放入共享内存中,IPC一旦有了这些强大的通用数据结构做辅助,无疑进程间通信的能力一下子强大了很多。

我们没必要再为共享内存设计其他额外的数据结构,另外,STL的高度可扩展性将为IPC所驱使。STL容器被良好的封装,默认情况下有它们自己的内存管理方案。

当一个元素被插入到一个STL列表(list)中时,列表容器自动为其分配内存,保存数据。考虑到要将STL容器放到共享内存中,而容器却自己在堆上分配内存。

一个最笨拙的办法是在堆上构造STL容器,然后把容器复制到共享内存,并且确保所有容器的内部分配的内存指向共享内存中的相应区域,这基本是个不可能完成的任务。

假设进程A在共享内存中放入了数个容器,进程B如何找到这些容器呢?

一个方法就是进程A把容器放在共享内存中的确定地址上(fixed offsets),则进程B可以从该已知地址上获取容器。另外一个改进点的办法是,进程A先在共享内存某块确定地址上放置一个map容器,然后进程A再创建其他容器,然后给其取个名字和地址一并保存到这个map容器里。

进程B知道如何获取该保存了地址映射的map容器,然后同样再根据名字取得其他容器的地址。

16、map插入方式有哪几种?

1) 用insert函数插入pair数据,
mapStudent.insert(pair<int, string>;(1, "student_one"));
2) 用insert函数插入value_type数据
mapStudent.insert(map<int, string>;::value_type (1, "student_one"));
3) 在insert函数中使用make_pair()函数
mapStudent.insert(make_pair(1, "student_one"));
4) 用数组方式插入数据
mapStudent[1] = "student_one";

17、unordered_map(hash_map)和map的区别

unordered_map和map:

区别:

unordered_map是基于哈希表实现的关联容器,它通过哈希函数将元素映射到具体的存储位置,提供了常数时间的插入、查找和删除操作。根据key对应的值判断元素是否相同

map是基于红黑树实现的关联容器,它根据元素的键值进行有序存储,并提供了以对数时间为界的插入、查找和删除操作。map中的元素是按照二叉搜索树存储,进行中序遍历会得到有序遍历

unordered_set和set:

区别:

unordered_set是基于哈希表实现的无序集合容器,它通过哈希函数将元素映射到具体的存储位置,并提供了常数时间的插入、查找和删除操作。

而set是基于红黑树实现的有序集合容器,它根据元素的值进行有序存储,并提供了以对数时间为界的插入、查找和删除操作。

unordered_map和map类似,都是存储的key-value的值,可以通过key快速索引到value。不同的是unordered_map不会根据key的大小进行排序,存储时是根据key的hash值判断元素是否相同,即unordered_map内部元素是无序的,而map中的元素是按照二叉搜索树存储,进行中序遍历会得到有序遍历。

所以使用时map的key需要定义operator<。而unordered_map需要定义hash_value函数并且重载operator==。但是很多系统内置的数据类型都自带这些,那么如果是自定义类型,那么就需要自己重载operator<或者hash_value()了。

unordered_map的底层实现是hash_table;

hash_map底层使用的是hash_table,而hash_table使用的开链法进行冲突避免,所有hash_map采用开链法进行冲突解决。

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

记住前三个:

线性探测

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

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

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

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

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

19、map中[]与find的区别?

map的下标运算符[]的作用是:将关键码作为下标去执行查找,并返回对应的值;如果不存在这个关键码,就将一个具有该关键码和值类型的默认值的项插入这个map。

map的find函数:用关键码执行查找,找到了返回该位置的迭代器;如果不存在这个关键码,就返回尾迭代器。

22、STL中hash_map扩容发生什么?

HashMap是Java中常用的数据结构之一,用于存储键值对。在HashMap内部,元素被存储在一个数组中,每个数组的元素称为桶(bucket),每个桶存储一个链表,用于处理哈希冲突。

具体而言,当元素数量超过负载因子乘以容量时,HashMap就会认为需要进行扩容。

  1. 扩容的具体步骤

一旦满足触发条件,HashMap就会开始扩容。扩容的主要步骤如下:

首先,HashMap会计算新的容量,通常是当前容量的两倍。新容量的选择是为了保持哈希表的效率,避免太频繁的扩容操作。

2.2 创建新的桶数组

接下来,HashMap会创建一个新的桶数组,其长度为新的容量。这个新的数组将会成为HashMap的主要存储结构。

2.3 将元素重新分配到新的桶数组中

HashMap会遍历原有的桶数组,将每个桶中的元素重新计算哈希值,并放入新的桶数组中的合适位置。这一步骤确保元素在扩容后仍能被正确定位。

2.4 更新容量和阈值

扩容完成后,HashMap会更新其内部的容量和负载因子阈值,以反映新的状态。

11.Unordered_map和map,unordered_set和set,分别有什么区别,它们的底层数据结构是什么?⭐⭐

unordered_map和map:

区别:

unordered_map是基于哈希表实现的关联容器,它通过哈希函数将元素映射到具体的存储位置,提供了常数时间的插入、查找和删除操作。而map是基于红黑树实现的关联容器,它根据元素的键值进行有序存储,并提供了以对数时间为界的插入、查找和删除操作。

底层数据结构:

unordered_map使用哈希表作为底层数据结构,而map使用红黑树作为底层数据结构。

unordered_set和set:

区别:

unordered_set是基于哈希表实现的无序集合容器,它通过哈希函数将元素映射到具体的存储位置,并提供了常数时间的插入、查找和删除操作。而set是基于红黑树实现的有序集合容器,它根据元素的值进行有序存储,并提供了以对数时间为界的插入、查找和删除操作。

底层数据结构:

unordered_set使用哈希表作为底层数据结构,而set使用红黑树作为底层数据结构。

20、 STL中list与queue之间的区别

list不再能够像vector一样以普通指针作为迭代器,因为其节点不保证在存储空间中连续存在;

list插入操作和结合操作都不会造成原有的list迭代器失效;

list不仅是一个双向链表,而且还是一个环状双向链表,所以它只需要一个指针;

list不像vector那样有可能在空间不足时做重新配置、数据移动的操作,所以插入前的所有迭代器在插入操作之后都仍然有效;

deque是一种双向开口的连续线性空间,所谓双向开口,意思是可以在头尾两端分别做元素的插入和删除操作;

deque和vector最大的差异,一在于deque允许常数时间内对起头端进行元素的插入或移除操作,二在于deque没有所谓容量概念,因为它是动态地以分段连续空间组合而成,随时可以增加一段新的空间并链接起来,deque没有所谓的空间保留功能。

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;
}

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

此外list也是一个环形链表,因此只要一个指针便能完整表现整个链表。list中node节点指针始终指向尾端的一个空白节点,因此是一种“前闭后开”的区间结构。list的空间管理默认采用alloc作为空间配置器,为了方便的以节点大小为配置单位,还定义一个list_node_allocator函数可一次性配置多个节点空间由于list的双向特性,其支持在头部(front)和尾部(back)两个方向进行push和pop操作,当然还支持erase,splice,sort,merge,reverse,sort等操作,这里不再详细阐述。

21、STL中的allocator、deallocator

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

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

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

空间释放函数deallocate(),该函数首先判断区块大小,大于128bytes时,直接调用一级配置器,小于128bytes就找到对应的free-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之后, 迭代器应该也是全部失效.

28、STL中slist的实现

STL模板库

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(){}//从头部取走元素 
...}

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

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(); 
...
}

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

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

struct __deque_iterator{ 
... 
    T* cur;//迭代器所指缓冲区当前的元素 
    T* first;//迭代器所指缓冲区第一个元素 
    T* last;//迭代器所指缓冲区最后一个元素 
    map_pointer node;//指向map中的node 
...
}

STL模板库

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

STL模板库

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

31、STL中stack和queue的实现

stack

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

STL模板库

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();}
};

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

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

queue

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

STL模板库

类似的,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();}
};

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

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

32、STL中的heap的实现

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

STL模板库

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

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

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

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

push_heap插入算法

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

STL模板库

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

pop_heap算法

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

STL模板库

根节点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;
}

33、STL中的priority_queue的实现

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

STL模板库

默认情况下,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(); 
        }
    };

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

34、STL中set的实现?

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

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

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

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

每个节点不是红色就是黑色

根结点为黑色

如果节点为红色,其子节点必为黑

任一节点至(NULL)树尾端的任何路径,所含的黑节点数量必相同

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

关联式容器尽量使用其自身提供的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使用)

begin() 返回指向map头部的迭代器  
clear() 删除所有元素  
count() 返回指定元素出现的次数  
empty() 如果map为空则返回true  
end() 返回指向map末尾的迭代器  
equal_range() 返回特殊条目的迭代器对  
erase() 删除一个元素,参数可以是迭代器,可以是关键字  
find() 查找一个元素,返回迭代器  
get_allocator() 返回map的配置器  
insert() 插入元素,插入pair  
key_comp() 返回比较元素key的函数  
lower_bound() 返回键值>=给定元素的第一个位置  
max_size() 返回可以容纳的最大元素个数  
rbegin() 返回一个指向map尾部的逆向迭代器  
rend() 返回一个指向map头部的逆向迭代器  
size() 返回map中元素的个数  
swap() 交换两个map  
upper_bound() 返回键值>给定元素的第一个位置  
value_comp() 返回比较元素value的函数

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

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

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

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

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

value_type(k, T());

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

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

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

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

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

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

set只提供一种数据类型的接口,但是会将这一个元素分配到key和value上,Set对象存储的不是键值对形式,它只存储了值,没有键,就和数组类似

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

Map对象和Set对象都不允许键重复(可以将Set对象的键想象成值)。

Map对象的键是不能改的,但是值能改,Set对象只能通过迭代器来更改值

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

栈和队列的区别?

元素的添加和删除方式:在栈中,元素的添加和删除都是在栈顶进行的,因此它是一种“先进后出”(LIFO)的数据结构;而在队列中,元素的添加是在队尾进行的,元素的删除是在队头进行的,因此它是一种“先进先出”(FIFO)的数据结构。

访问顺序:在栈中,只能访问栈顶的元素,而不能访问其他元素;在队列中,可以访问队头和队尾的元素,可以进行遍历操作。

应用场景:栈常用于需要后进先出的场景,例如函数调用、表达式求值等;而队列常用于需要先进先出的场景,例如消息队列、任务调度等。

set和list的区别?

元素的存储方式:List是一种有序的容器类型,它将元素按照插入的顺序存储;而Set是一种无序的容器类型,它将元素按照哈希值或者比较函数的返回值进行存储。

元素的访问方式:List支持通过下标或者迭代器访问元素,可以根据元素的位置进行随机访问;而Set不支持通过下标进行访问,只能通过迭代器进行顺序访问,不支持随机访问。

元素的重复性:List允许元素重复,即可以在容器中添加多个相同的元素;而Set不允许元素重复,即添加重复元素时只会保留一个。

查找效率:由于Set采用了哈希表的数据结构,因此在查找元素时可以达到O(1)的时间复杂度,比List要高效。

内存中的堆和栈

内存中的堆和栈,第一个区别就是申请方式的不同:栈是系统自动分配空间的,而堆则是程序员根据需要自己申请的空间。由于栈上的空间是自动分配自动回收的,所以栈上的数据的生存周期只是在函数的运行过程中,运行后就释放掉,不可以再访问。而堆上的数据只要程序员不释放空间,就一直可以访问到,不过缺点是一旦忘记释放会造成内存泄露。

申请效率的比较:栈由系统自动分配,速度较快。但程序员是无法控制的。堆是由new分配的内存,一般速度比较慢,而且容易产生内存碎片,不过用起来最方便。

红黑树的特性

红黑树(Red-Black Tree)是一种 自平衡的二叉搜索树(BST) ,通过节点颜色标记和旋转操作维护树的平衡性,确保关键操作(插入、删除、查找)的时间复杂度为 O(log n)

二、红黑树的五大特性

红黑树必须满足以下规则:

颜色特性

每个节点是 红色黑色

根节点特性

根节点必须是 黑色

叶子节点特性

所有叶子节点(NIL节点,即空节点)视为 黑色

红色节点限制

红色节点的子节点必须是 黑色(不允许连续红色节点)。

路径黑高一致性

从任一节点到其所有叶子节点的路径上,包含的 黑色节点数量(黑高) 必须相同。

三、红黑树与二叉搜索树(BST)的区别

特性普通二叉搜索树(BST)红黑树
平衡性可能退化为链表(时间复杂度退化为 O(n))通过颜色规则和旋转操作强制保持平衡(O(log n))
节点结构仅存储键值和子节点指针额外存储颜色标记(红/黑)
插入/删除操作可能导致树高度失衡通过颜色调整和旋转自动恢复平衡
应用场景简单场景(数据随机分布)高频动态数据操作(如数据库、STL map/set)

四、红黑树如何维持平衡

旋转操作

左旋:将右子节点提升为父节点。

右旋:将左子节点提升为父节点。

目的:调整树结构,减少高度差异。

颜色调整

插入或删除后,若违反红黑树规则,通过 重新着色 和旋转修复平衡。

示例:插入红色节点后,若父节点为红色,触发颜色翻转或旋转。

黑高约束

所有路径的黑高相等 → 最长路径不超过最短路径的 2倍,确保树高度近似平衡。

五、红黑树的核心优势

插入、删除、查找的时间复杂度稳定为 O(log n) ,避免BST的最坏情况(O(n))插入/删除后只需局部调整(旋转或颜色修改),无需全局重构。仅需额外1 bit存储颜色(如用布尔值表示),内存占用低。

六、示例:红黑树 vs 普通BST的插入

普通BST:依次插入有序序列(1, 2, 3, 4, 5)会退化为链表:

1  

2  

3  

4  

5

查找时间复杂度:O(n)。

红黑树:插入相同序列后,通过旋转和颜色调整保持平衡:

2(B)  
/   
1(B) 4(R)  
/   
3(B)5(B)

查找时间复杂度:O(log n)。

评论区 0