70道C语言与C 常见问答题（下）

38 对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'));   //#4unique_ptr<string> p4；                       //#5p4 = 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 allowedunique_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_ptrsp(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';}};class B{public:shared_ptr<A> pa_;~B(){    cout<<'B delete';}};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;}int main(){    fun();    return 0;}

可以看到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();

39 说说强制类型转换运算符

「static_cast」

  • 用于非多态类型的转换
  • 不执行运行时类型检查（转换安全性不如 dynamic_cast）
  • 通常用于转换数值数据类型（如 float -> int）
  • 可以在整个类层次结构中移动指针，子类转化为父类安全（向上转换），父类转化为子类不安全（因为子类可能有不在父类的字段或方法）

「dynamic_cast」

  • 用于多态类型的转换
  • 执行行运行时类型检查
  • 只适用于指针或引用
  • 对不明确的指针的转换将失败（返回 nullptr），但不引发异常
  • 可以在整个类层次结构中移动指针，包括向上转换、向下转换

「const_cast」

  • 用于删除 const、volatile 和 __unaligned 特性（如将 const int 类型转换为 int 类型 ） reinterpret_cast
  • 用于位的简单重新解释
  • 滥用 reinterpret_cast 运算符可能很容易带来风险。除非所需转换本身是低级别的，否则应- 使用其他强制转换运算符之一。
  • 允许将任何指针转换为任何其他指针类型（如 char* 到 int* 或 One_class* 到 Unrelated_class* 之类的转换，但其本身并不安全）
  • 也允许将任何整数类型转换为任何指针类型以及反向转换。
  • reinterpret_cast 运算符不能丢掉 const、volatile 或 __unaligned 特性。
  • reinterpret_cast 的一个实际用途是在哈希函数中，即，通过让两个不同的值几乎不以相同的索引结尾的方式将值映射到索引。

「bad_cast」

  • 由于强制转换为引用类型失败，dynamic_cast 运算符引发 bad_cast 异常。

bad_cast 使用

try {    Circle& ref_circle = dynamic_cast<Circle&>(ref_shape);}catch (bad_cast b) {    cout << 'Caught: ' << b.what();}

40 谈谈你对拷贝构造函数和赋值运算符的认识

拷贝构造函数和赋值运算符重载有以下两个不同之处：

  • 拷贝构造函数生成新的类对象，而赋值运算符不能。
  • 由于拷贝构造函数是直接构造一个新的类对象，所以在初始化这个对象之前不用检验源对象 是否和新建对象相同。而赋值运算符则需要这个操作，另外赋值运算中如果原来的对象中有内存分配要先把内存释放掉。

「注意」：当有类中有指针类型的成员变量时，一定要重写拷贝构造函数和赋值运算符，不要使用默认 的。

41 在C++中，使用malloc申请的内存能否通过delete释放？使用new申请的内存能否用free？

不能，malloc /free主要为了兼容C，new和delete 完全可以取代malloc /free的。malloc /free的操作对象都是必须明确大小的。而且不能用在动态类上。new 和delete会自动进行类型检查和大小，malloc/free不能执行构造函数与析构函数，所以动态对象它是不行的。当然从理论上说使用malloc申请的内存是可以通过delete释放的。不过一般不这样写的。而且也不能保证每个C++的运行时都能正常。

42 用C++设计一个不能被继承的类

template <typename T> class A {    friend T;     private:      A() {}     ~A() {} }; class B : virtual public A<B> {    public:     B() {}    ~B() {} }; class C : virtual public B {    public:      C() {}     ~C() {} }; void main( void ) {     B b;     //C c;     return; } 

「注意」：构造函数是继承实现的关键，每次子类对象构造时，首先调用的是父类的构造函数，然后才 是自己的。

43 C++自己实现一个String类

#include <iostream>#include <cstring> using namespace std; class String{public:    // 默认构造函数    String(const char *str = nullptr);    // 拷贝构造函数    String(const String &str);    // 析构函数    ~String();    // 字符串赋值函数    String& operator=(const String &str); private:    char *m_data;    int m_size;}; // 构造函数String::String(const char *str){    if(str == nullptr)  // 加分点：对m_data加NULL 判断    {        m_data = new char[1];   // 得分点：对空字符串自动申请存放结束标志'\0'的        m_data[0] = '\0';        m_size = 0;    }    else    {        m_size = strlen(str);        m_data = new char[m_size + 1];        strcpy(m_data, str);    }} // 拷贝构造函数String::String(const String &str)   // 得分点：输入参数为const型{    m_size = str.m_size;    m_data = new char[m_size + 1];  //加分点：对m_data加NULL 判断    strcpy(m_data, str.m_data);} // 析构函数String::~String(){    delete[] m_data;} // 字符串赋值函数String& String::operator=(const String &str)  // 得分点：输入参数为const{    if(this == &str)    //得分点：检查自赋值        return *this;     delete[] m_data;    //得分点：释放原有的内存资源    m_size = strlen(str.m_data);    m_data = new char[m_size + 1];  //加分点：对m_data加NULL 判断    strcpy(m_data, str.m_data);    return *this;       //得分点：返回本对象的引用}

44 访问基类的私有虚函数

写出以下程序的输出结果：

#include <iostream.h> class A{    virtual void g()    {       cout << 'A::g' << endl;    }   private:    virtual void f()    {       cout << 'A::f' << endl;    } }; class B : public A {    void g()    {       cout << 'B::g' << endl;    }    virtual void h()    {       cout << 'B::h' << endl;    } }; typedef void( *Fun )( void ); void main() {    B b;    Fun pFun;    for(int i = 0 ; i < 3; i++)    {       pFun = ( Fun )*( ( int* ) * ( int* )( &b ) + i );       pFun();    } } 

输出结果：

B::g A::f B::h

「注意」：考察了面试者对虚函数的理解程度。一个对虚函数不了解的人很难正确的做出本题。在学习面向对象的多态性时一定要深刻理解虚函数表的工作原理。

45 对虚函数和多态的理解

多态的实现主要分为静态多态和动态多态，静态多态主要是重载，在编译的时候就已经确定；动态多态是用虚函数机制实现的，在运行期间动态绑定。举个例子：一个父类类型的指针指向一个子类对象时候，使用父类的指针去调用子类中重写了的父类中的虚函数的时候，会调用子类重写过后的函数，在父类中声明为加了virtual关键字的函数，在子类中重写时候不需要加virtual也是虚函数。

虚函数的实现：在有虚函数的类中，类的最开始部分是一个虚函数表的指针，这个指针指向一个虚函数表，表中放了虚函数的地址，实际的虚函数在代码段(.text)中。当子类继承了父类的时候也会继承其虚函数表，当子类重写父类中虚函数时候，会将其继承到的虚函数表中的地址替换为重新写的函数地址。使用了虚函数，会增加访问内存开销，降低效率。

46 简述类成员函数的重写、重载和隐藏的区别

（1）重写和重载主要有以下几点不同。

  • 范围的区别：被重写的和重写的函数在两个类中，而重载和被重载的函数在同一个类中。
  • 参数的区别：被重写函数和重写函数的参数列表一定相同，而被重载函数和重载函数的参数列表一 定不同。
  • virtual 的区别：重写的基类中被重写的函数必须要有virtual 修饰，而重载函数和被重载函数可以被 virtual 修饰，也可以没有。

（2）隐藏和重写、重载有以下几点不同。

  • 与重载的范围不同：和重写一样，隐藏函数和被隐藏函数不在同一个类中。
  • 参数的区别：隐藏函数和被隐藏的函数的参数列表可以相同，也可不同，但是函数名肯定要相同。当参数不相同时，无论基类中的参数是否被virtual 修饰，基类的函数都是被隐藏，而不是被重写。

「注意」：虽然重载和覆盖都是实现多态的基础，但是两者实现的技术完全不相同，达到的目的也是完 全不同的，覆盖是动态态绑定的多态，而重载是静态绑定的多态。

47 链表和数组有什么区别

  • 存储形式：数组是一块连续的空间，声明时就要确定长度。链表是一块可不连续的动态空间， 长度可变，每个结点要保存相邻结点指针。
  • 数据查找：数组的线性查找速度快，查找操作直接使用偏移地址。链表需要按顺序检索结点， 效率低。
  • 数据插入或删除：链表可以快速插入和删除结点，而数组则可能需要大量数据移动。
  • 越界问题：链表不存在越界问题，数组有越界问题。

「注意」：在选择数组或链表数据结构时，一定要根据实际需要进行选择。数组便于查询，链表便于插 入删除。数组节省空间但是长度固定，链表虽然变长但是占了更多的存储空间。

48 用两个栈实现一个队列的功能

typedef struct node {  int data;  node *next; }node,*LinkStack;  //创建空栈： LinkStack CreateNULLStack( LinkStack &S) {  S = (LinkStack)malloc( sizeof( node ) ); // 申请新结点  if( NULL == S)  {   printf('Fail to malloc a new node.\n');   return NULL;  }  S->data = 0; //初始化新结点  S->next = NULL;   return S; }  //栈的插入函数： LinkStack Push( LinkStack &S, int data) {  if( NULL == S) //检验栈  {   printf('There no node in stack!');   return NULL;  }   LinkStack p = NULL;  p = (LinkStack)malloc( sizeof( node ) ); // 申请新结点   if( NULL == p)  {   printf('Fail to malloc a new node.\n');   return S;  }  if( NULL == S->next)  {   p->next = NULL;  }  else  {   p->next = S->next;  }  p->data = data; //初始化新结点  S->next = p; //插入新结点  return S; }  //出栈函数： node Pop( LinkStack &S) {  node temp;  temp.data = 0;  temp.next = NULL;   if( NULL == S) //检验栈  {   printf('There no node in stack!');   return temp;  }  temp = *S;   if( S->next == NULL )  {   printf('The stack is NULL,can't pop!\n');   return temp;  }  LinkStack p = S ->next; //节点出栈   S->next = S->next->next;  temp = *p;  free( p );  p = NULL;   return temp; }  //双栈实现队列的入队函数： LinkStack StackToQueuPush( LinkStack &S, int data) {  node n;  LinkStack S1 = NULL;  CreateNULLStack( S1 ); //创建空栈   while( NULL != S->next ) //S 出栈入S1  {   n = Pop( S );   Push( S1, n.data );  }  Push( S1, data ); //新结点入栈   while( NULL != S1->next ) //S1 出栈入S  {   n = Pop( S1 );   Push( S, n.data );  }  return S; } 

「注意」：用两个栈能够实现一个队列的功能，那用两个队列能否实现一个队列的功能呢？结果是否定 的，因为栈是先进后出，将两个栈连在一起，就是先进先出。而队列是现先进先出，无论多少个连在一 起都是先进先出，而无法实现先进后出。

49 模板函数和模板类的特例化

「引入原因」

编写单一的模板，它能适应多种类型的需求，使每种类型都具有相同的功能，但对于某种特定类型，如果要实现其特有的功能，单一模板就无法做到，这时就需要模板特例化

「定义」对单一模板提供的一个特殊实例，它将一个或多个模板参数绑定到特定的类型或值上

（1）模板函数特例化

必须为原函数模板的每个模板参数都提供实参，且使用关键字template后跟一个空尖括号对<>，表明将原模板的所有模板参数提供实参，举例如下：

template<typename T> //模板函数int compare(const T &v1,const T &v2){    if(v1 > v2) return -1;    if(v2 > v1) return 1;    return 0;}//模板特例化,满足针对字符串特定的比较，要提供所有实参，这里只有一个Ttemplate<> int compare(const char* const &v1,const char* const &v2){    return strcmp(p1,p2);}

「本质」特例化的本质是实例化一个模板，而非重载它。特例化不影响参数匹配。参数匹配都以最佳匹配为原则。例如，此处如果是compare(3,5)，则调用普通的模板，若为compare(“hi”,”haha”)则调用特例化版本（因为这个cosnt char*相对于T，更匹配实参类型），注意二者函数体的语句不一样了，实现不同功能。

「注意」模板及其特例化版本应该声明在同一个头文件中，且所有同名模板的声明应该放在前面，后面放特例化版本。

（2）类模板特例化

原理类似函数模板，不过在类中，我们可以对模板进行特例化，也可以对类进行部分特例化。对类进行特例化时，仍然用template<>表示是一个特例化版本，例如：

template<>class hash<sales_data>{    size_t operator()(sales_data& s);    //里面所有T都换成特例化类型版本sales_data    //按照最佳匹配原则，若T != sales_data，就用普通类模板，否则，就使用含有特定功能的特例化版本。};

「类模板的部分特例化」

不必为所有模板参数提供实参，可以指定一部分而非所有模板参数，一个类模板的部分特例化本身仍是一个模板，使用它时还必须为其特例化版本中未指定的模板参数提供实参(特例化时类名一定要和原来的模板相同，只是参数类型不同，按最佳匹配原则，哪个最匹配，就用相应的模板)

「特例化类中的部分成员」

可以特例化类中的部分成员函数而不是整个类，举个例子：

template<typename T>class Foo{    void Bar();    void Barst(T a)();};template<>void Foo<int>::Bar(){    //进行int类型的特例化处理    cout << '我是int型特例化' << endl;}Foo<string> fs;Foo<int> fi;//使用特例化fs.Bar();//使用的是普通模板，即Foo<string>::Bar()fi.Bar();//特例化版本，执行Foo<int>::Bar()//Foo<string>::Bar()和Foo<int>::Bar()功能不同

50 为什么析构函数一般写成虚函数

由于类的多态性，基类指针可以指向派生类的对象，如果删除该基类的指针，就会调用该指针指向的派生类析构函数，而派生类的析构函数又自动调用基类的析构函数，这样整个派生类的对象完全被释放。如果析构函数不被声明成虚函数，则编译器实施静态绑定，在删除基类指针时，只会调用基类的析构函数而不调用派生类析构函数，这样就会造成派生类对象析构不完全，造成内存泄漏。所以将析构函数声明为虚函数是十分必要的。在实现多态时，当用基类操作派生类，在析构时防止只析构基类而不析构派生类的状况发生，要将基类的析构函数声明为虚函数。举个例子：

#include <iostream>using namespace std;class Parent{public:    Parent(){        cout << 'Parent construct function'  << endl;    };    ~Parent(){        cout << 'Parent destructor function' <<endl;    }};class Son : public Parent{public:    Son(){        cout << 'Son construct function'  << endl;    };    ~Son(){        cout << 'Son destructor function' <<endl;    }};int main(){    Parent* p = new Son();    delete p;    p = NULL;    return 0;}//运行结果：//Parent construct function//Son construct function//Parent destructor function

将基类的析构函数声明为虚函数：

51 vector的底层原理

vector底层是一个动态数组，包含三个迭代器，start和finish之间是已经被使用的空间范围，end_of_storage是整块连续空间包括备用空间的尾部。

当空间不够装下数据（vec.push_back(val)）时，会自动申请另一片更大的空间（1.5倍或者2倍），然后把原来的数据拷贝到新的内存空间，接着释放原来的那片空间[vector内存增长机制]。

当释放或者删除（vec.clear()）里面的数据时，其存储空间不释放，仅仅是清空了里面的数据。因此，对vector的任何操作一旦引起了空间的重新配置，指向原vector的所有迭代器会都失效了。

52 vector中的reserve和resize的区别

  • reserve是直接扩充到已经确定的大小，可以减少多次开辟、释放空间的问题（优化push_back），就可以提高效率，其次还可以减少多次要拷贝数据的问题。reserve只是保证vector中的空间大小（capacity）最少达到参数所指定的大小n。reserve()只有一个参数。
  • resize()可以改变有效空间的大小，也有改变默认值的功能。capacity的大小也会随着改变。resize()可以有多个参数。

53 vector中的size和capacity的区别

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

54 vector中erase方法与algorithn中的remove方法区别

  • vector中erase方法真正删除了元素，迭代器不能访问了
  • remove只是简单地将元素移到了容器的最后面，迭代器还是可以访问到。因为algorithm通过迭代器进行操作，不知道容器的内部结构，所以无法进行真正的删除。

55 vector迭代器失效的情况

  • 当插入一个元素到vector中，由于引起了内存重新分配，所以指向原内存的迭代器全部失效。
  • 当删除容器中一个元素后,该迭代器所指向的元素已经被删除，那么也造成迭代器失效。erase方法会返回下一个有效的迭代器，所以当我们要删除某个元素时，需要it=vec.erase(it);。

56 正确释放vector的内存(clear(), swap(), shrink_to_fit())

  • vec.clear()：清空内容，但是不释放内存。
  • vector().swap(vec)：清空内容，且释放内存，想得到一个全新的vector。
  • vec.shrink_to_fit()：请求容器降低其capacity和size匹配。
  • vec.clear();vec.shrink_to_fit();：清空内容，且释放内存。

57 list的底层原理

  • ist的底层是一个双向链表，使用链表存储数据，并不会将它们存储到一整块连续的内存空间中。恰恰相反，各元素占用的存储空间（又称为节点）是独立的、分散的，它们之间的线性关系通过指针来维持,每次插入或删除一个元素，就配置或释放一个元素空间。
  • list不支持随机存取，如果需要大量的插入和删除，而不关心随即存取

58 什么情况下用vector，什么情况下用list，什么情况下用deque

  • vector可以随机存储元素（即可以通过公式直接计算出元素地址，而不需要挨个查找），但在非尾部插入删除数据时，效率很低，适合对象简单，对象数量变化不大，随机访问频繁。除非必要，我们尽可能选择使用vector而非deque，因为deque的迭代器比vector迭代器复杂很多。
  • list不支持随机存储，适用于对象大，对象数量变化频繁，插入和删除频繁，比如写多读少的场景。
  • 需要从首尾两端进行插入或删除操作的时候需要选择deque。

59 priority_queue的底层原理

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

60 map 、set、multiset、multimap的底层原理

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

红黑树的特性：

  • 每个结点或是红色或是黑色；
  • 根结点是黑色；
  • 每个叶结点是黑的；
  • 如果一个结点是红的，则它的两个儿子均是黑色；
  • 每个结点到其子孙结点的所有路径上包含相同数目的黑色结点。

61 为何map和set的插入删除效率比其他序列容器高

因为不需要内存拷贝和内存移动

62 为何map和set每次Insert之后，以前保存的iterator不会失效？

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

63 当数据元素增多时（从10000到20000），map的set的查找速度会怎样变化？

RB-TREE用二分查找法，时间复杂度为logn，所以从10000增到20000时，查找次数从log10000=14次到log20000=15次，多了1次而已。

64 map 、set、multiset、multimap的特点

  • set和multiset会根据特定的排序准则自动将元素排序，set中元素不允许重复，multiset可以重复。
  • map和multimap将key和value组成的pair作为元素，根据key的排序准则自动将元素排序（因为红黑树也是二叉搜索树，所以map默认是按key排序的），map中元素的key不允许重复，multimap可以重复。
  • map和set的增删改查速度为都是logn，是比较高效的。

65 为何map和set的插入删除效率比其他序列容器高，而且每次insert之后，以前保存的iterator不会失效？

  • 存储的是结点，不需要内存拷贝和内存移动。
  • 插入操作只是结点指针换来换去，结点内存没有改变。而iterator就像指向结点的指针，内存没变，指向内存的指针也不会变。

66 为何map和set不能像vector一样有个reserve函数来预分配数据?

在map和set内部存储的已经不是元素本身了，而是包含元素的结点。也就是说map内部使用的Alloc并不是map<Key, Data, Compare, Alloc>声明的时候从参数中传入的Alloc。

67 set的底层实现实现为什么不用哈希表而使用红黑树？

set中元素是经过排序的，红黑树也是有序的，哈希是无序的 如果只是单纯的查找元素的话，那么肯定要选哈希表了，因为哈希表在的最好查找时间复杂度为O(1)，并且如果用到set中那么查找时间复杂度的一直是O（1），因为set中是不允许有元素重复的。而红黑树的查找时间复杂度为O(lgn)

68 hash_map与map的区别？什么时候用hash_map，什么时候用map？

  • 构造函数：hash_map需要hash function和等于函数，而map需要比较函数（大于或小于）。
  • 存储结构：hash_map以hashtable为底层，而map以RB-TREE为底层。
  • 总的说来，hash_map查找速度比map快，而且查找速度基本和数据量大小无关，属于常数级别。而map的查找速度是logn级别。但不一定常数就比log小，而且hash_map还有hash function耗时。
  • 如果考虑效率，特别当元素达到一定数量级时，用hash_map。
  • 考虑内存，或者元素数量较少时，用map。

69 迭代器失效的问题

插入操作：

  • 对于vector和string，如果容器内存被重新分配，iterators,pointers,references失效；如果没有重新分配，那么插入点之前的iterator有效，插入点之后的iterator失效；
  • 对于deque，如果插入点位于除front和back的其它位置，iterators,pointers,references失效；当我们插入元素到front和back时，deque的迭代器失效，但reference和pointers有效；
  • 对于list和forward_list，所有的iterator,pointer和refercnce有效。删除操作：
  • 对于vector和string，删除点之前的iterators,pointers,references有效；off-the-end迭代器总是失效的；
  • 对于deque，如果删除点位于除front和back的其它位置，iterators,pointers,references失效；当我们插入元素到front和back时，off-the-end失效，其他的iterators,pointers,references有效；
  • 对于list和forward_list，所有的iterator,pointer和refercnce有效。
  • 对于关联容器map来说，如果某一个元素已经被删除，那么其对应的迭代器就失效了，不应该再被使用，否则会导致程序无定义的行为。

70 STL线程不安全的情况

  • 在对同一个容器进行多线程的读写、写操作时；
  • 在每次调用容器的成员函数期间都要锁定该容器；
  • 在每个容器返回的迭代器（例如通过调用begin或end）的生存期之内都要锁定该容器；
  • 在每个在容器上调用的算法执行期间锁定该容器。
赞 (0)

相关推荐