C++容器

发表于 | 分类于 | 阅读次数: |

map和set的区别

map和set都是C++的关联容器，其底层实现都是红黑树（RB-Tree）。由于map和set所开放的各种操作接口，RB-Tree也都提供了，所以几乎所有的map和set的操作行为，都只是转调RB-Tree的操作行为。

map和set区别在于

  1. map中的元素是key-value对：关键字起到索引的作用，值则表示与索引相关联的数据；set与之相对就是关键字的简单集合，set中每一个元素只包含一个关键字。
  2. set的迭代器是const的，不允许修改元素的值；map允许修改value，但不允许修改key。其原因是因为map和set是根据关键字排序来保证其有序性的，如果允许修改key的话，那么首先需要删除该键，然后调节平衡，再插入修改后的键值，调节平衡，如此一来，严重破坏了map和set的结构，导致iterator失效，不知道应该指向改变前的位置，还是指向改变后的位置。所以STL中将set的迭代器设置成const，不允许修改迭代器的值；而map的迭代器则不允许修改key值，允许修改value值。
  3. map支持下标操作，set不支持下标操作。map可以用key做下标，map的下标运算符[]将关键码作为下标去执行查找，如果关键码不存在，则插入一个具有该关键码和mapped_type类型默认值得元素至map中，因此下标运算符[]在map引用中需要慎用，const_map不能用，只希望确定某一个关键值是否存在而不希望插入元素时也不应该使用，mapped_type类型没有默认值也不应该使用。如果find能解决需要，尽可能用find。

红黑树

性质：

  1. 每个节点要么是黑色，要么是红色。

  2. 根节点是黑色

  3. 每个叶子节点也是黑色

  4. 每个红色节点的两个子节点一定都是黑色

  5. 任意一节点到每个叶子节点的路径都包含数目相同的黑节点。

    ​ 如果一个节点存在黑子节点，那么该节点肯定有两个子节点。

说一说STL的allocator

STL的分配器用于封装STL容器在内存管理上的底层细节。在C++中，其内存配置和释放如下：

new运算分为两个阶段：

  1. 调用::operator new配置内存
  2. 调用对象构造函数构造对象内容

delete运算分为两个阶段

  1. 调用对象析构函数
  2. 调用::operator delete释放内存

为了精密分工，STL allocator将两个操作分开：

  • 内存开辟由alloc::allocate()负责
  • 内存释放由alloc::deallocate()负责
  • 对象构造由::construct()负责
  • 对象析构由::destroy()负责

同时为了提升内存管理的效率，减少申请小内存造成的内存碎片问题，SGI STL采用了两级配置器，当分配的空间大小超过128B时，会使用第一级空间配置器；当分配的空间大小小于128B时，将使用第二级空间配置器。第一级空间配置器直接使用malloc(),realloc(),free()函数进行内存的分配和释放，而第二级的空间配置器采用了内存池技术，通过空闲链表来管理内存。

STL迭代器删除元素

  1. 对于序列容器vector，queue来说，使用erase(iterator)后，后面的每个元素的迭代器都会失效，但是后面每个元素都会往前移动一个位置，但是erase会返回下一个有效的迭代器。
  2. 对于关联容器map，set来说，使用了erase(iterator)后，当前元素的迭代器失效，但是其结构是红黑树，删除当前元素的，不会影响到下一个元素的迭代器，所以在调用erase之前，记录下一个元素的迭代器即可。
  3. 对于list来说，它使用了不连续分配的内存，并且它的erase方法也会返回下一个有效的iterator，因此上面两种正确的方法都可以使用。

STL由什么组成

容器 迭代器 仿函数算法 分配器 配接器

他们之间的关系是：分配器给容器分配存储空间，算法通过迭代器获取容器中的内容，仿函数可以协助算法完成各种操作，配接器用来套接适配仿函数。

STL里面的resize和reserve的区别

resize()：

改变当前容器内含有元素的数量(size())

1
2
vector<int>vec;
vec.resize(len);

vec的size变为len，如果原来vec的size小于len，那么容器新增(len-size)个元素，新增的元素默认为0。

reserve():

改变当前容器的最大容量(capacity)，他不会生成元素，只是确定这个容器允许放入多少对象，如果reserve(len)的值大于当前的capacity()，那么会重新分配一块能存len个对象的空间，然后把之前vec.size()个对象通过拷贝构造函数复制过来，销毁之前的内存。

说一说STL中迭代器的作用，有了指针为何还要迭代器

迭代器和指针的区别

迭代器不是指针，是类模板，表现的像指针。他只是模拟了指针的一些功能，可能通过重载了指针的一些操作符，-> * ++ –等。迭代器封装了指针，是一个“可遍历STL容器内全部或部分元素”的对象，本质是封装了原生指针，是指针概念的一种提升(lift)，提供了比指针更高级的行为，相当于一种智能指针，他可以根据不同类型的数据结构来实现不同的++，–等操作。

迭代器返回的事对象引用而不是对象的值，所以cout只能输出迭代器使用*取值后的值而不能直接输出其自身。

迭代器产生原因

lterator类的访问方式就是把不同集合类的访问逻辑抽象出来，使得不用暴露集合内部的结构而达到循环遍历集合的效果。

说一说epoll原理

调用顺序

1
2
3
int epoll_creat(int size);
int epoll_ctl(int epfd,int op,int fd,struct epoll_event *event);
int epoll_wait(int epfd,struct epoll_event *events,int maxevents,int timeout);

首先创建一个epoll对象，然后使用epoll_ctl对这个对象进行操作，把需要监控的描述添加进去，这些描述如会将以epoll_event结构体的形式组成一颗红黑树，接着阻塞在epoll_wait，进入大循环，当某个fd上有事件发生时，内核将会把其对应的结构体放入到一个链表中，返回有事件发生的链表。

n个无序的数组，求每个元素后面比他大的第一个数，要求复杂度为O(n)

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
/*
 * @Author: onlooker
 * @Date: 2020-08-12 19:59:13
 * @LastEditTime: 2020-09-05 10:35:58
 * @FilePath: \code\a.cpp
 */
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    vector<int>vec;
    for(int i=0;i<10;i++){
        vec.push_back(rand()%100);
        cout<<vec[i]<<" ";
    }
    vec.push_back(100);//给最后一个数尾部添一个最大值
    cout<<endl;
    stack<int>s;
    int ans[10];
    for(int i=0;i<11;i++){
        if(s.empty()||vec[i]<vec[s.top()]){//是递减的序列继续添加
            s.push(i);
        }
        else{
            while(!s.empty()&&vec[i]>vec[s.top()]){//不是的话就把当前数弹出，并且记录答案
                int x=s.top();
                s.pop();
                ans[x]=i;
            }
            s.push(i);
        }
    }
    for(int i=0;i<10;i++){
        cout<<ans[i]<<" ";
    }
    cout<<endl;
    return 0;
}