C++11、STL面试题

C++11

1、请你说一下你理解的c++中的smart pointer四个智能指针

shared_ptr,unique_ptr,weak_ptr,auto_ptr

C++里面的四个智能指针: auto_ptr, shared_ptr, weak_ptr, unique_ptr 其中后三个是c++11支持,并且第一个已经被11弃用。为什么要使用智能指针:智能指针的作用是管理一个指针,因为存在以下这种情况:申请的空间在函数结束时忘记释放,造成内存泄漏。使用智能指针可以很大程度上的避免这个问题,因为智能指针就是一个类,当超出了类的作用域是,类会自动调用析构函数,析构函数会自动释放资源。所以智能指针的作用原理就是在函数结束时自动释放内存空间,不需要手动释放内存空间。
①auto_ptr(c++98的方案,cpp11已经抛弃)
采用所有权模式。

auto_ptr< string> p1 (new string ("I reigned lonely as a cloud.”));
auto_ptr<string> p2;
p2 = p1; //auto_ptr不会报错.

此时不会报错,p2剥夺了p1的所有权,但是当程序运行时访问p1将会报错。所以auto_ptr的缺点是:存在潜在的内存崩溃问题!

②unique_ptr(替换auto_ptr)
unique_ptr实现独占式拥有或严格拥有概念,保证同一时间内只有一个智能指针可以指向该对象。它对于避免资源泄露(例如“以new创建对象后因为发生异常而忘记调用delete”)特别有用。

采用所有权模式,还是上面那个例子

unique_ptr<string> p3 (new string ("auto"));   //#4
unique_ptr<string> p4;                       //#5
p4 = p3;//此时会报错!!

编译器认为p4=p3非法,避免了p3不再指向有效数据的问题。因此,unique_ptr比auto_ptr更安全。

另外unique_ptr还有更聪明的地方:当程序试图将一个 unique_ptr 赋值给另一个时,如果源 unique_ptr 是个临时右值,编译器允许这么做;如果源 unique_ptr 将存在一段时间,编译器将禁止这么做,比如:

unique_ptr<string> pu1(new string ("hello world"));
unique_ptr<string> pu2;
pu2 = pu1;                                      // #1 not allowed
unique_ptr<string> pu3;
pu3 = unique_ptr<string>(new string ("You"));   // #2 allowed

其中#1留下悬挂的unique_ptr(pu1),这可能导致危害。而#2不会留下悬挂的unique_ptr,因为它调用 unique_ptr 的构造函数,该构造函数创建的临时对象在其所有权让给 pu3 后就会被销毁。这种随情况而已的行为表明,unique_ptr 优于允许两种赋值的auto_ptr 。

注:如果确实想执行类似与#1的操作,要安全的重用这种指针,可给它赋新值。C++有一个标准库函数std::move(),让你能够将一个unique_ptr赋给另一个。例如:

unique_ptr<string> ps1, ps2;
ps1 = demo("hello");
ps2 = move(ps1);
ps1 = demo("alexia");
cout << *ps2 << *ps1 << endl;

③shared_ptr
shared_ptr实现共享式拥有概念。多个智能指针可以指向相同对象,该对象和其相关资源会在“最后一个引用被销毁”时候释放。从名字share就可以看出了资源可以被多个指针共享,它使用计数机制来表明资源被几个指针共享。可以通过成员函数use_count()来查看资源的所有者个数。除了可以通过new来构造,还可以通过传入auto_ptr, unique_ptr,weak_ptr来构造。当我们调用release()时,当前指针会释放资源所有权,计数减一。当计数等于0时,资源会被释放。
shared_ptr 是为了解决 auto_ptr 在对象所有权上的局限性(auto_ptr 是独占的), 在使用引用计数的机制上提供了可以共享所有权的智能指针。
成员函数:
use_count 返回引用计数的个数
unique 返回是否是独占所有权( use_count 为 1)
swap 交换两个 shared_ptr 对象(即交换所拥有的对象)
reset 放弃内部对象的所有权或拥有对象的变更, 会引起原有对象的引用计数的减少
get 返回内部对象(指针), 由于已经重载了()方法, 因此和直接使用对象是一样的.如 shared_ptr<int> sp(new int(1)); sp 与 sp.get()是等价的

④weak_ptr

weak_ptr 是一种不控制对象生命周期的智能指针, 它指向一个 shared_ptr 管理的对象. 进行该对象的内存管理的是那个强引用的 shared_ptr. weak_ptr只是提供了对管理对象的一个访问手段。weak_ptr 设计的目的是为配合 shared_ptr 而引入的一种智能指针来协助 shared_ptr 工作, 它只可以从一个 shared_ptr 或另一个 weak_ptr 对象构造, 它的构造和析构不会引起引用记数的增加或减少。weak_ptr是用来解决shared_ptr相互引用时的死锁问题,如果说两个shared_ptr相互引用,那么这两个指针的引用计数永远不可能下降为0,资源永远不会释放。它是对对象的一种弱引用,不会增加对象的引用计数,和shared_ptr之间可以相互转化,shared_ptr可以直接赋值给它,它可以通过调用lock函数来获得shared_ptr。

class B;
class A
{
public:
    shared_ptr<B> pb_;
    ~A()
    {
        cout<<"A delete\n";
    }
};
class B
{
public:
    shared_ptr<A> pa_;
    ~B()
    {
        cout<<"B delete\n";
    }
};
void fun()
{
    shared_ptr<B> pb(new B());
    shared_ptr<A> pa(new A());
    pb->pa_ = pa;
    pa->pb_ = pb;
    cout<<pb.use_count()<<endl;
    cout<<pa.use_count()<<endl;
}

可以看到fun函数中pa ,pb之间互相引用,两个资源的引用计数为2,当要跳出函数时,智能指针pa,pb析构时两个资源引用计数会减一,但是两者引用计数还是为1,导致跳出函数时资源没有被释放(A B的析构函数没有被调用),如果把其中一个改为weak_ptr就可以了,我们把类A里面的shared_ptr pb_; 改为weak_ptr pb_; 运行结果如下,这样的话,资源B的引用开始就只有1,当pb析构时,B的计数变为0,B得到释放,B释放的同时也会使A的计数减一,同时pa析构时使A的计数减一,那么A的计数为0,A得到释放。
注意的是我们不能通过weak_ptr直接访问对象的方法,比如B对象中有一个方法print(),我们不能这样访问,pa->pb_->print(); 英文pb_是一个weak_ptr,应该先把它转化为shared_ptr,如:shared_ptr p = pa->pb_.lock(); p->print();

2、C++11的新特性

nullptr、override、final、=default =delete、Raw String Literals、Range-Based for、auto

右值引用&&、移动拷贝

3、右值引用、移动拷贝作用

不能返回栈对象的引用,在栈对象返回的时候,如果没有编译器的优化下-fno-elide-constructors,就会产生临时对象。这时只会产生一次拷贝,上面说的第二次拷贝就已经没有了,因为这里右值引用,将原来本应该消失的临时变量利用起来,直接传给了ra。一次拷贝是在产生临时变量的时候产生的,这个是不可避免的,因为,栈对象不能返回引用,返回引用才能避免产生临时对象,避免拷贝。

其实在C++11之前我们也有解决方法,就是const引用。其本质也是产生了临时对象,并且该临时对象是const 的。

STL

STL包含6大部件:容器、迭代器、算法、仿函数、适配器和空间配置器

1、vector

(1)vector的底层结构

vector底层是一个动态数组,包含三个迭代器,start和finish之间是已经被使用的空间范围,end_of_storage是整块连续空间包括备用空间的尾部。当空间不够装下数据(vec.push_back(val))时,会自动申请另一片更大的空间(1.5倍或者2倍),然后把原来的数据拷贝到新的内存空间,接着释放原来的那片空间【vector内存增长机制】。当释放或者删除(vec.clear())里面的数据时,其存储空间不释放,仅仅是清空了里面的数据。因此,对vector的任何操作一旦引起了空间的重新配置,指向原vector的所有迭代器会都失效了。

(2)vector中的reserve和resize的区别
  reserve是直接扩充到已经确定的大小,可以减少多次开辟、释放空间的问题(优化push_back),就可以提高效率,其次还可以减少多次要拷贝数据的问题。reserve只是保证vector中的空间大小(capacity)最少达到参数所指定的大小n。reserve()只有一个参数。

  resize()可以改变有效空间的大小,也有改变默认值的功能。capacity的大小也会随着改变。resize()可以有多个参数。

resize 可以改变 size 的大小,变大等价于调用 push_back(),变小等于 pop_back() ,resize 可以使capacity 的大小变大可以,但是不能让他变小。reserve 只可变大 vector 的 capacity 而不可以使其减小。不能改变size的大小。

(3)vector中的size和capacity的区别

  size表示当前vector中有多少个元素finish - start),而capacity函数则表示它已经分配的内存中可以容纳多少元素end_of_storage - start)。

(4)vector的元素类型可以是引用吗?

  vector的底层实现要求连续的对象排列引用并非对象,没有实际地址,因此vector的元素类型不能是引用

(5)正确释放vector的内存(clear(), swap(), shrink_to_fit())
  vec.clear():清空内容,但是不释放内存。

  vector<int>().swap(vec):清空内容,且释放内存,想得到一个全新的vector。

  vec.shrink_to_fit():请求容器降低其capacity和size匹配。

  vec.clear();vec.shrink_to_fit();:清空内容,且释放内存。

(6)vector 扩容为什么要以1.5倍或者2倍扩容?
  根据查阅的资料显示,考虑可能产生的堆空间浪费,成倍增长倍数不能太大,使用较为广泛的扩容方式有两种,以2倍的方式扩容,或者以1.5倍的方式扩容。
(7)vector的常用函数

vector<int> vec(10,100);        创建10个元素,每个元素值为100
vec.resize(r,vector<int>(c,0)); 二维数组初始化
reverse(vec.begin(),vec.end())  将元素翻转
sort(vec.begin(),vec.end());    排序,默认升序排列
vec.push_back(val);             尾部插入数字
vec.size();                     向量大小
find(vec.begin(),vec.end(),1);  查找元素
iterator = vec.erase(iterator)  删除元素

2、list

(1)list的底层原理

  list的底层是一个双向链表,以结点为单位存放数据,结点的地址在内存中不一定连续,每次插入或删除一个元素,就配置或释放一个元素空间。

  list不支持随机存取,如果需要大量的插入和删除,而不关心随即存取

(2)list的常用函数

list.push_back(elem)    在尾部加入一个数据
list.pop_back()            删除尾部数据
list.push_front(elem)    在头部插入一个数据
list.pop_front()        删除头部数据
list.size()                返回容器中实际数据的个数
list.sort()             排序,默认由小到大 
list.unique()           移除数值相同的连续元素
list.back()             取尾部迭代器
list.erase(iterator)    删除一个元素,参数是迭代器,返回的是删除迭代器的下一个位置

3、queue

queue、stack、priority_queue都是用deque适配器适配出来的

qi.empty()
qi.front();//用front
qi.pop();

4、stack

si.empty()
si.top();//使用top
si.pop();//pop数据

5、priority_queue

(1)priority_queue的底层原理

  priority_queue:优先队列,其底层是用堆来实现的。在优先队列中,队首元素一定是当前队列中优先级最高的那一个。

(2)priority_queue的常用函数

priority_queue<int, vector<int>, greater<int>> pq;   最小堆
priority_queue<int, vector<int>, less<int>> pq;      最大堆
pq.empty()   如果队列为空返回真
pq.pop()     删除对顶元素
pq.push(val) 加入一个元素
pq.size()    返回优先队列中拥有的元素个数
pq.top()     返回优先级最高的元素

6、map、multimap

(1)map 、set、multiset、multimap的底层原理
  map 、set、multiset、multimap的底层实现都是红黑树,epoll模型的底层数据结构也是红黑树,linux系统中CFS进程调度算法,也用到红黑树。

在这里插入图片描述

红黑树的特性:

  1. 每个结点或是红色或是黑色;
  2. 根结点是黑色;
  3. 每个叶结点是黑的;
  4. 如果一个结点是红的,则它的两个儿子均是黑色;
  5. 每个结点到其子孙结点的所有路径上包含相同数目的黑色结点。

  对于STL里的map容器,count方法与find方法,都可以用来判断一个key是否出现,mp.count(key) > 0统计的是key出现的次数,因此只能为0/1,而mp.find(key) != mp.end()则表示key存在。

(2)map 、set、multiset、multimap的特点
  set和multiset会根据特定的排序准则自动将元素排序,set中元素不允许重复,multiset可以重复。

  map和multimap将key和value组成的pair作为元素,根据key的排序准则自动将元素排序(因为红黑树也是二叉搜索树,所以map默认是按key排序的),map中元素的key不允许重复,multimap可以重复。

  map和set的增删改查速度为都是logn,是比较高效的。

(3)为何map和set的插入删除效率比其他序列容器高,而且每次insert之后,以前保存的iterator不会失效?
  因为存储的是结点,不需要内存拷贝和内存移动。

  因为插入操作只是结点指针换来换去,结点内存没有改变。而iterator就像指向结点的指针,内存没变,指向内存的指针也不会变。

(4)为何map和set不能像vector一样有个reserve函数来预分配数据?
  因为在map和set内部存储的已经不是元素本身了,而是包含元素的结点。也就是说map内部使用的Alloc并不是map<Key, Data, Compare, Alloc>声明的时候从参数中传入的Alloc。

(5)map 、set、multiset、multimap的常用函数

it map.begin()          返回指向容器起始位置的迭代器(iterator) 
it map.end()             返回指向容器末尾位置的迭代器 
bool map.empty()         若容器为空,则返回true,否则false
it map.find(k)           寻找键值为k的元素,并用返回其地址
int map.size()           返回map中已存在元素的数量
map.insert({int,string}) 插入元素
for (itor = map.begin(); itor != map.end();)
{
    if (itor->second == "target")
        map.erase(itor++) ; // erase之后,令当前迭代器指向其后继。
    else
        ++itor;
}

7、set、multiset

8、unordered_map

(1)unordered_map、unordered_set的底层原理
  unordered_map的底层是一个防冗余的哈希表(采用除留余数法)。哈希表最大的优点,就是把数据的存储和查找消耗的时间大大降低,时间复杂度为O(1);而代价仅仅是消耗比较多的内存。

  使用一个下标范围比较大的数组来存储元素。可以设计一个函数(哈希函数(一般使用除留取余法),也叫做散列函数),使得每个元素的key都与一个函数值(即数组下标,hash值)相对应,于是用这个数组单元来存储这个元素;也可以简单的理解为,按照key为每一个元素“分类”,然后将这个元素存储在相应“类”所对应的地方,称为桶。

  但是,不能够保证每个元素的key与函数值是一一对应的,因此极有可能出现对于不同的元素,却计算出了相同的函数值,这样就产生了“冲突”,换句话说,就是把不同的元素分在了相同的“类”之中。 一般可采用拉链法解决冲突:

(2)unordered_map 与map的区别?使用场景?
构造函数:unordered_map 需要hash函数,等于函数;map只需要比较函数(小于函数).
存储结构:unordered_map 采用hash表存储,map一般采用红黑树(RB Tree) 实现。因此其memory数据结构是不一样的。

  总体来说,unordered_map 查找速度会比map快,而且查找速度基本和数据数据量大小,属于常数级别;而map的查找速度是log(n)级别。并不一定常数就比log(n)小,hash还有hash函数的耗时,明白了吧,如果你考虑效率,特别是在元素达到一定数量级时,考虑考虑unordered_map 。但若你对内存使用特别严格,希望程序尽可能少消耗内存,那么一定要小心,unordered_map 可能会让你陷入尴尬,特别是当你的unordered_map 对象特别多时,你就更无法控制了,而且unordered_map 的构造速度较慢。

(4)unordered_map、unordered_set的常用函数

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)  返回匹配给定主键的元素的个数 

9、algorithm

find
用法:find(first, end, value);

返回区间[first,end)中第一个值等于value的元素位置;若未找到,返回end。函数返回的是迭代器或指针,即位置信息。
String是这一种顺序存储结构,其find函数返回的是下标索引。set,map,multiset,multimap都不是顺序索引的数据结构,所以返回的是迭代器。
vector没有实现find函数,除此之外,常见容器都实现了自己的find函数。对于string,通过a.find(value)==string::npos判断
count
count函数的功能是:统计容器中等于value元素的个数。

先看一下函数的参数:
count(first,last,value); first是容器的首迭代器,last是容器的末迭代器,value是询问的元素。返回这个值出现次数的统计结果。
remove_if
remove_if(beg, end, op) //移除区间[beg,end)中每一个“令判断式:op(elem)获得true”的元素;
  remove_if(remove和unique也是相同情况)的参数是迭代器,通过迭代器无法得到容器本身,而要删除容器内的元素只能通过容器的成员函 数来进行,因此remove系列函数无法真正删除元素,只能把要删除的元素移到容器末尾并返回要被删除元素的迭代器,然后通过erase成员函数来真正删除。用法如下:

bool IsSpace(char x) { return x == ' '; }

string str2 = "Text with some spaces";
str2.erase(remove_if(str2.begin(), str2.end(), IsSpace), str2.end()); // "Textwithsomespaces"
count_if
count_if(first,last,comp) (在comp为true的情况下计数) 或者 count_if(first,last,value,comp) (这个是在comp为true的情况下统计容器中等于value的元素):first为首迭代器,last为末迭代器,value为要查询的元素,comp为比较bool函数,为true则计数,函数返回型是int。

max
传两个参数取最大值
min
传两个参数取最小值
lower_bound
merge
merge函数的作用是:将两个有序的序列合并为一个有序的序列。函数参数:merge(first1,last1,first2,last2,result,compare);

//firs1t为第一个容器的首迭代器,last1为第一个容器的末迭代器,first2为第二个容器的首迭代器,last2为容器的末迭代器,result为存放结果的容器,comapre为比较函数(可略写,默认为合并为一个升序序列)。

remove
remove(beg,end,const T& value) //移除区间{beg,end)中每一个“与value相等”的元素;
  remove只是通过迭代器的指针向前移动来删除,将没有被删除的元素放在链表的前面,并返回一个指向新的超尾值的迭代器。由于remove()函数不是成员,因此不能调整链表的长度。remove()函数并不是真正的删除,要想真正删除元素则可以使用erase()或者resize()函数。
string str1 = "Text with some spaces";
str1.erase(std::remove(str1.begin(), str1.end(), ' '), str1.end()); // "Textwithsomespaces"
unique
unique是STL比较实用的一个函数。用于“去除”容器内相邻的重复的元素(只保留一个)。这里说的去除并不是真正将容器内的重复元素删去,只是把重复的元素移到容器最后,但是依然在容器内。 对于数组而言返回去重后最后一个元素的指针,而其他容器则是返回去重后最后一个元素的迭代器。
reverse
函数参数:reverse(first,last),其中first,last分别指向被反转序列中初始及末尾位置的双向迭代器(Bidirectional iterators)。这个范围即 [first,last) ,包括 first 到 last 间的所有元素,包括 first 指向的元素,但不包括 last 指向的元素。
sort
sort(vi.begin(),vi.end());默认大序
erase

substr
substr有2种用法:
假设:string s = "0123456789";
string sub1 = s.substr(5); //只有一个数字5表示从下标为5开始一直到结尾:sub1 = "56789"
string sub2 = s.substr(5, 3); //从下标为5开始截取长度为3位:sub2 = "567"

erase
vector中真正去除重复元素的方法,先排序,然后使用vi.erase(unique(vi.begin(),vi.end()),vi.end())

Last modification:February 9th, 2020 at 01:59 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment