各大容器的特点：

  1. 可以用下标访问的容器有（既可以插入也可以赋值）：vector、deque、map；

    特别要注意一下，vector和deque如果没有预先指定大小，是不能用下标法插入元素的！

  2. 序列式容器才可以在容器初始化的时候制定大小，关联式容器不行；

  3. 注意，关联容器的迭代器不支持it+n操作，仅支持it++操作。

序列式容器

vector

当需要使用数组的情况下，可以考虑使用vector

特点：

(1) 一个动态分配的数组(当数组空间内存不足时，都会执行: 分配新空间-复制元素-释放原空间);

(2) 当删除元素时，不会释放限制的空间，所以向量容器的容量(capacity)大于向量容器的大小(size);

(3) 对于删除或插入操作，执行效率不高，越靠后插入或删除执行效率越高;

(4) 高效的随机访问的容器。

(5)底层内存空间连续

(6)扩容机制：当旧的存储空间不够时，扩充一个新的空间，空间大小为原来大小的两倍，复制元素到新的空间，并释放旧空间。

底层存储结构

为数组，所以支持O（1）快速随机访问，插入尾部为O（n）

创建vecotr对象

(1) vector v1;

(2) vector v2(10);

基本操作：

v.capacity(); //容器容量

v.size(); //容器大小

v.at(int idx); //用法和[]运算符相同

v.push_back(); //尾部插入

v.pop_back(); //尾部删除

v.front(); //获取头部元素

v.back(); //获取尾部元素

v.begin(); //头元素的迭代器

v.end(); //尾部元素的迭代器

v.insert(pos,elem); //pos是vector的插入元素的位置

v.insert(pos, n, elem) //在位置pos上插入n个元素elem

v.insert(pos, begin, end);

v.erase(pos); //移除pos位置上的元素，返回下一个数据的位置

v.erase(begin, end); //移除[begin, end)区间的数据，返回下一个元素的位置

reverse(pos1, pos2); //将vector中的pos1~pos2的元素逆序存储

deque

特点：

(1) deque(double-ended queue 双端队列);

(2) 具有分段数组、索引数组, 分段数组是存储数据的，索引数组是存储每段数组的首地址;

(3) 向两端插入元素效率较高！

若向两端插入元素，如果两端的分段数组未满，既可插入;如果两端的分段数组已满，

则创建新的分段函数，并把分段数组的首地址存储到deque容器中即可)。

中间插入元素效率较低！

底层存储结构

底层内存空间不一定连续，通过map（非STL中的map）数组中的指针来管理不同的连续空间。
在这里插入图片描述

通过建立 map 数组，deque 容器申请的这些分段的连续空间就能实现“整体连续”的效果。换句话说，当 deque 容器需要在头部或尾部增加存储空间时，它会申请一段新的连续空间，同时在 map 数组的开头或结尾添加指向该空间的指针，由此该空间就串接到了 deque 容器的头部或尾部。

创建deque对象

(1) deque d1;

(2) deque d2(10);

基本操作：

(1) 元素访问：

d[i];

d.at[i];

d.front();

d.back();

d.begin();

d.end();

添加元素：

d.push_back();

d.push_front();

d.insert(pos,elem); //pos是vector的插入元素的位置

d.insert(pos, n, elem) //在位置pos上插入n个元素elem

d.insert(pos, begin, end);

删除元素：

d.pop_back();

d.pop_front();

d.erase(pos); //移除pos位置上的元素，返回下一个数据的位置

d.erase(begin, end); //移除[begin, end)区间的数据，返回下一个元素的位置

list

特点：

(1) 双向链表:故可以高效地进行首尾插入删除元素。（2）中间删除元素效率低

底层数据结构

是一个双向链表（每个节点有指向前驱和指向后继的两个指针）。

创建对象：

list L1；

list L2(10);

基本操作：

(1) 元素访问：

lt.front();

lt.back();

lt.begin();

lt.end();

(2) 添加元素：

lt.push_back();

lt.push_front();

lt.insert(pos, elem);

lt.insert(pos, n , elem);

lt.insert(pos, begin, end);

lt.pop_back();

lt.pop_front();

lt.erase(begin, end);

lt.erase(elem);

(3)sort()函数、merge()函数、splice()函数：

sort()函数就是对list中的元素进行排序;

merge()函数的功能是：将两个容器合并，合并成功后会按从小到大的顺序排列;

比如：lt1.merge(lt2); lt1容器中的元素全都合并到容器lt2中。

splice()函数的功能是：可以指定合并位置，但是不能自动排序！

关联式容器

  1. 特点：
    (1) 关联式容器都是有序的，升序排列，自动排序;

(2) 实现的是一个平衡二叉树，每个元素都有一个父节点和两个子节点，

左子树的所有元素都比自己小，右子树的所有元素都比自己大;

set

特点：

构造set集合的主要目的是为了快速检索,去重与排序

(1)使用红黑树实现，其内部元素依据其值自动排序，每个元素值只能出现一次（multiset），不允许重复。

(2)每次插入值的时候，都需要调整红黑树，效率有一定影响。（缺点）

(3)map 和 set 的插入或删除效率比用其他序列容器高，因为对于关联容器来说，不需要做内存拷贝和内存移动。（优点）

总结：由红黑树实现，其内部元素依据其值自动排序，每个元素值只能出现一次，不允许重复，且插入和删除效率比用其他序列容器高。

底层数据结构

红黑树（弱平衡二叉搜索树），但采用二分查找法故搜索高效。

创建对象

  • set<T> s
  • set<T, op(比较结构体)> s; //op为排序规则，默认规则是less< T >(升序排列)，或者是greater< T >(降序规则)。
  • 结构体类型（struct ）的set ，使用时必须要重载 ‘<’ 运算符
#include<iostream>
#include<set>
#include<string>
using namespace std;
struct Info
{
    string name;
    double score;
    bool operator < (const Info &a) const // 重载“<”操作符，自定义排序规则
    {
        //按score由大到小排序。如果要由小到大排序，使用“>”即可。
        return a.score < score;
    }
};
int main()
{
    set<Info> s;
    Info info;

    //插入三个元素
    info.name = "Jack";
    info.score = 80;
    s.insert(info);
    info.name = "Tom";
    info.score = 99;
    s.insert(info);
    info.name = "Steaven";
    info.score = 60;
    s.insert(info);

    set<Info>::iterator it;
    for(it = s.begin(); it != s.end(); it++)
        cout << (*it).name << " : " << (*it).score << endl;
    return 0;
}
/*
运行结果：
Tom : 99
Jack : 80
Steaven : 60
*/

基本操作：

s.size(); //元素的数目

s.max_size(); //可容纳的最大元素的数量

s.empty(); //判断容器是否为空

s.find(elem); //返回值是迭代器类型

s.count(elem); //elem的个数，要么是1，要么是0，multiset可以大于一

begin 返回一个指向集合中第一个元素的迭代器。

cbegin 返回指向集合中第一个元素的const迭代器。

end 返回指向末尾的迭代器。

cend 返回指向末尾的常量迭代器。

rbegin 返回指向末尾的反向迭代器。

rend 返回指向起点的反向迭代器。

crbegin 返回指向末尾的常量反向迭代器。

crend 返回指向起点的常量反向迭代器。

s.insert(elem);

s.insert(pos, elem);

s.insert(begin, end);

s.erase(pos);

s.erase(begin,end);

s.erase(elem);

s.clear();//清除a中所有元素；

pair类模板

  1. 主要作用是将两个数据组成一个数据，用来表示一个二元组或一个元素对。
  2. 两个数据可以是同一个类型也可以是不同的类型。
  3. 当需要将两个元素组合在一起时，可以选择构造pair对象。
  • set的insert返回值为一个pair<set<int>::iterator,bool>。bool标志着插入是否成功，而iterator代表插入的位置，若该键值已经在set中，则iterator表示已存在的该键值在set中的位置。
如：set<int> a;

           a.insert(1);

           a.insert(2);

           a.insert(2);//重复的元素不会被插入；

注意一下：make_pair()函数内调用的仍然是pair构造函数

  • set中的erase()操作是不进行任何的错误检查的，比如定位器的是否合法等等，所以用的时候自己一定要注意。
创建pair对象：
pair<int, float> p1;   //调用构造函数来创建pair对象

make_pair(1,1.2);      //调用make_pair()函数来创建pair对象
pair对象的使用：
pair<int, float> p1(1, 1.2);

cout<< p1.first << endl;

cout<< p1.second << endl;

顺序遍历：begin（）、end（）

set<int> a;

set<int>::iterator it=a.begin();

for(;it!=a.end();it++)

    cout<<*it<<endl;

反序遍历：rbegin（）、rend（）

set<int> a;

set<int>::reverse_iterator rit=a.rbegin();

for(;rit!=a.rend();rit++)

cout<<*rit<<endl;
  • find(key_value);//如果找到查找的键值，则返回该键值的迭代器位置，否则返回集合最后一个元素后一个位置的迭代器，即end();
如：int b[]={1,2,3,4,5};     set<int> a(b,b+5);

        set<int>::iterator it;

        it=a.find(3);

        if(it!=a.end())  cout<<*it<<endl;

        else cout<<“该元素不存在”<<endl;

        it=a.find(10);

        if(it!=a.end())  cout<<*it<<endl;

        else cout<<“该元素不存在”<<endl;

定义比较函数

  • set容器在判定已有元素a和新插入元素b是否相等时，是这么做的：

    1. 将a作为左操作数，b作为右操作数，调用比较函数，并返回比较值 ；

    2. 将b作为左操作数，a作为右操作数，再调用一次比较函数，并返回比较值。

    也就是说，假设有比较函数f(x,y)，要对已有元素a和新插入元素b进行比较时，会先进行f(a,b)操作，再进行f(b,a)操作，然后返回两个bool值。

    如果1、2两步的返回值都是false，则认为a、b是相等的，则b不会被插入set容器中；

    如果1返回true而2返回false，那么认为b要排在a的后面，反之则b要排在a的前面；

    如果1、2两步的返回值都是true，则可能发生未知行为。

自定义比较结构体；
  • 结构体类型（struct ）的set ，使用时必须要重载 ‘<’ 运算符

首先，定义比较结构体 myCompare，然后定义set<数据类型，myCompare> s1 ;

#include <iostream>
#include<set>

using namespace std;
struct myCompare {
	bool operator ()(int a, int b) {
		//return a > b;//降序排列
		return a < b;//升序排列
	}
};
int main() {
	set<int, myCompare> s1;
	s1.insert(1);
	s1.insert(2);
	s1.insert(3);
	for (set<int, mycompare>::iterator it = s1.begin(); it != s1.end(); it++) {
		cout << *it<<endl;
	}
	return 0;
}
重载“<”操作符
  • 定义结构体（结构体中重载" < "）： struct Info
  • 定义set： set<Info> s;
#include<iostream>
#include<set>
#include<string>
using namespace std;
struct Info
{
    string name;
    double score;
    bool operator < (const Info &a) const // 重载“<”操作符，自定义排序规则
    {
        return  score < a.score  //降序排列 调用时候(假设 A是Info的对象)可以看成 A.operator()(a.score); 
        //return score > a.score //升序排列
    }
};
int main()
{
    set<Info> s;
    Info info;

    //插入三个元素
    info.name = "Jack";
    info.score = 80;
    s.insert(info);
    info.name = "Tom";
    info.score = 99;
    s.insert(info);
    info.name = "Steaven";
    info.score = 60;
    s.insert(info);

    set<Info>::iterator it;
    for(it = s.begin(); it != s.end(); it++)
        cout << (*it).name << " : " << (*it).score << endl;
    return 0;
}
/*
运行结果：
Tom : 99
Jack : 80
Steaven : 60
*/

multiset

默认按key排序，允许存在多个相同的key

map

去重类问题
可以打乱重新排列的问题
有清晰的一对一关系的问题

特点：

(1) map为单重映射、multimap为多重映射;

(2) 主要区别是map存储的是无重复键值的元素对，而multimap允许相同的键值重复出现，既一个键值可以对应多个值。

(3) map和multimap内部自建了一颗红黑二叉树，可以对数据进行自动排序，插入、删除效率高，所以map、multimap里的数据都是有序的，这也是我们通过map简化代码的原因。

(4)自动建立key-value的对应关系，key和value可以是你需要的任何类型。

(5) key和value一一对应的关系可以去重。

底层数据结构

都由红黑树实现，但空间占用率高，因为每个节点要保存父、子节点和红黑性质。

创建对象（map与multimap类似）：

map<T1,T2> m;

map<T1,T2, op> m; //op为排序规则，默认规则是less**（升序排列）**只会按键 去排序！，可以用结构体重载（）对 键自定义排序

#include <map>
#include <string>
#include <iostream>
using namespace std;
int main(){
    map<string, int, greater<string> > mapStudent;  //关键是这句话 按字符串长度排序 也只能对键进行排序
    mapStudent["LiMin"]=90;
    mapStudent["ZiLinMi"]=72;
    mapStudent["BoB"]=79;
    map<string, int>::iterator iter=mapStudent.begin();
    for(iter=mapStudent.begin();iter!=mapStudent.end();iter++)
    {
        cout<<iter->first<<" "<<iter->second<<endl;
    }
    return 0;
}

原文链接：https://blog.csdn.net/m0_67392126/article/details/124503986

基本操作：

m.at(key);

m[key];

m.count(key);

m.max_size(); //求算容器最大存储量

m.size(); //容器的大小

m.begin();

m.end();

m.insert(elem);

m.insert(pos, elem);

m.insert(begin, end);

m.erase(pos);

m.erase(begin,end);

m.erase(key);

注意一下：该容器存储的是键值对，所以插入函数与其他容器稍有不同

使用pair<>构造键值对对象

map<int, float> m;

m.insert(pair<int, float>(10,2.3));

使用make_pair()函数构建键值对对象

map<int,float> m;

m.insert(make_pair(10,2.3));

(2) 使用value_type标志

map<int, float> m;

m.insert(map<int,float>::value_type(10,2.3));

 

m[key] = value;   //m只能是map容器，不适用于multimap

multimap

默认按Key排序，允许存在多个相同的key

unordered_map/unordered_multimap

特点

1.与map、multimap的区别之处：无序性，查找相对快，插入删除相对慢。

底层数据结构

都是哈希表，故查找效率相对高为O(n)，适用于查找多的场合。

容器配接器

除了以上基本容器类别，为满足特殊需求，STL还提供了一些特别的（并且预先定义好的）容器配接器，根据基本容器类别实现而成。包括：

stack

stack 容器对元素采取 LIFO（后进先出）的管理策略。

queue

queue 容器对元素采取 FIFO（先进先出）的管理策略。也就是说，它是个普通的缓冲区（buffer）。

priority_queue

优先级队列相当于一个有权值的单向队列queue，在这个队列中，所有元素是按照优先级排列的。
priority_queue根据堆的处理规则来调整元素之间的位置，关于堆的原理，可以参考堆；
根据堆的特性，优先级队列实现了取出最大最小元素时间复杂度为O(1),对于插入和删除，其最坏情况为O(lgn)。

拓展以及延申

  • AVL与红黑树比较。 AVL注重整体，插入删除旋转次数不定，查找效率相对高，维护麻烦。红黑树注重局部，插入最多旋转2次，删除最多旋转3次，故插入删除效率相对高，维护简单。
    在这里插入图片描述
  • unordered_map和map的区别
    链接: unordered_map和map的区别.
  • 各容器底层数据结构总结
    链接: 各容器底层数据结构总结.
# 数据结构 # c++ # 算法
Logo
向您推荐>>Eolink开发者社区

权威｜前沿｜技术｜干货｜国内首个API全生命周期开发者社区

更多推荐

深入理解 Mocha 测试框架：从零实现一个 Mocha

前言什么是自动化测试自动化测试在很多团队中都是Devops环节中很难执行起来的一个环节，主要原因在于测试代码的编写工作很难抽象，99%的场景都需要和业务强绑定，而且写测试代码的编写工作量往往比编写实际业务代码的工作量更多。在一些很多业务场景中投入产出比很低，适合写自动化测试的应该是那些中长期业务以及一些诸如组件一样的基础库。自动化测试是个比较大的概念，其中分类也比较多，比如单元测试，端对端测试，集

avatar 云原生

ELK实现containerd的容器日志采集展示【基于logging的全栈监测】

企业级ELK Stack构建介绍

avatar 云原生

(20200916 Solved)docker-compose up创建容器自动退出

问题描述如题，创建容器后自动退出了。并且docker start container无效解决方案原因是缺失了控制终端的配置，需要在docker-compose.yml中增加tty:true ，有时候这样也不行，需要再增加一个command:/bin/bash，命令不一定是这个，需要是一个不会退出的命令，然后用-d后台启动容器。Referencesdocker-compose启动容器后自动退出...

avatar 云原生