小董的BLOG
0%

C++-顺序容器

发表于 更新于

顺序容器概述

容器：一些特定类型对象的集合。顺序容器提供了控制元素存储和访问顺序的能力，且该顺序与元素的内容无关，而与元素加入容器时的位置相关

标准库中的顺序容器

C++中提供了多种多种顺序容器，这些容器根据下两方面性能的选择都有不同的折中：

  • 向容器中不同位置添加、删除元素的代价
  • 非顺序访问容器中的元素的代价
vector 可变大小数组；支持快速任意元素随机访问；在尾部之外插入元素代价较大
deque 双端队列；支持快速任意元素随机访问；在头、尾部之外插入元素代价较大
list 双向链表；只支持双向顺序访问，不支持随机访问；任何位置插入元素速度都快
forward_list 单向链表，只支持单向顺序访问，其余同双向链表
array 固定大小数组；支持快速任意元素随机访问；不能添加、删除元素
string 字符串，与vector相似，专门用于保存字符；在尾部之外插入元素代价较大

array是C++新标准添加的类型，比内置的数组更加安全、更容易使用

选择顺序容器的原则

  • 通常，使用vector是最好的选择

  • 如果需存放的元素很多、元素很小，并且空间的开销很重要，则不要选择list或forward_list

  • 其余原则根据：

    • 程序是否要随机访问元素
    • 程序是否要在中间、头部、尾部插入元素

    进行选择

  • 如果程序只在读取输入时才需要在中间位置插入元素，随后只需要随机访问元素：

    可以在输入阶段使用list，输入完成后将元素拷贝至一个vector

如果目前不确定使用哪种容器，可以先选定一个容器类型，在程序中只使用vector和list的公共操作：使用迭代器，而不是使用下标。这样后续改变容器类型会很方便

容器通用操作

一般来说，每个容器都定义在对应的头文件中，且文件名与类型名相同

类型别名

每个容器都定义了多个类型，我们可以通过这些类型的类型别名来定义一个变量以供使用，例如：

1
2
vector<int> a{1};
auto i=a.begin();

通常我们使用auto来创建一个容器内的类型对象，因为通常这样更方便，但是同时可以通过类型别名具体地定义这些变量的类型，例如这里的i类型实际上是:vector<int>::iterator这里的iterator就是一个类型别名，所以这里还可以：

1
2
vector<int> a{1};
vector<int>::iterator i=a.begin();

像这样的类型别名还有：

iterator 此容器的迭代器类型
const_iterator 只读迭代器类型
size_type 无符号整数类型，用于保存容器长度，可用于索引
difference_type 带符号整数类型，用于保存两迭代器之间的距离
value_type 容器的元素类型
reference 元素的左值类型
const_reference 只读左值类型

容器定义和初始化

为方便理解，我们先像这样定义容器元素的类型：

1
2
3
4
5
6
7
8
9
struct person
{   
    person() =default;
    person(string s) {name=s;}
    person(string s1, string s2)  {name=s1;addr=s2;}
   
    string name;
    string addr;
};

可以看到，该类有三个默认构造函数，接下来对容器的定义和初始化的元素均是该类型对象。

容器的定义与初始化有以下方式（均已vector为例）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<person> men;
vector<person> men1(10);
vector<person> men2(men1);

string a("dhk"),b("aca");
vector<person> men3(10,a);
vector<person> men3(10,a);
vector<person> men4(10,{a,b});

vector<person> men5{a,b,a,b};
vector<person> men6{{a,b},{b,a}};

vector<person>::iterator i=men1.begin(), e=men1.end();
vector<person> men7(i,e);

写在前面：有关元素类对象的构造函数生成元素的方法后面还会讲到更好用的办法，因此不建议在初始化容器时就添加元素

  • men为经过默认容器构造函数定义的容器对象，每个容器类型都定义了一个默认的构造函数，除了array容器之外，其他容器的默认构造函数都会创建一个指定类型的空容器。而对于array来说，用C中数组思维理解，由于在创建时长度已经给定，因此array中每个元素都会被初始化。

  • men1为创建一个含有10个person类元素的vector容器，这些元素都已经经过初始化，并且全部相同。

  • men2为创建一个vector容器，其含有的元素未men1的拷贝，这就要求men1和men2必须是相同的类型，且元素也为相同的类型。对于array容器而言，长度还必须相等。

  • men3为创建一个含有10个person类元素的vector容器，而这些元素通过person的第二个构造函数进行了初始化，而不是像men1一样进行默认初始化。也就是说，现在men3内有10个name为”dhk”，addr为默认初始化值的相同元素。

  • men4为创建一个含有10个person类元素的vector容器，而这些元素经过person的第三个构造函数进行了初始化。也就是说，现在men3内有10个name为”dhk”，addr为”aca”的相同元素。

    到此可以看出，当使用小括号进行容器初始化时，且当第一个值为一个整数n时，代表初始化n个相同的元素，而第二个参数可以为元素的构造函数参数，但这个参数有且只能有1个！！！，因为这n个元素是相同的，不能在这里对其中两个元素使用不同的构造函数参数，因此，vector<person> men3(10,a,b);是错误的写法！

    而如果当元素的构造函数参数有多个时，只需要像men4一样将这些参数通过大括号括起来即可。

  • men5为创建一个含有4个person类元素的vector容器，这些元素通过person的第二个构造函数进行初始化，分别是name为”dhk”,”aca”,”dhk”,”aca”；addr为默认初始化值的person对象。

  • men6为创建一个含有2个person类元素的vector容器，而这些元素经过person的第三个构造函数进行了初始化，分别是name为”dhk”，addr为”aca”和name为”dhk”，addr为”aca”的两个元素

  • men7为迭代器i和e指定范围内中元素的拷贝，这些元素类型也需和men7中的元素类型相同

array类型的初始化

array类型由于需指定大小，初始化方式稍微有一点不一样：

1
array<person,10> men={a,b,a};

并且初始化时不能像men6一样使用大括号实现多个构造函数参数初始化

string容器初始化

C++字符串、向量和数组 | 小董的BLOG (gitee.io)

赋值操作

除了一般初始化列表拷贝（不支持array），插入函数之外，这里将介绍assign函数和swap函数

assign

顺序容器中定义了assign成员，该函数允许从一个不同但可以兼容的类型元素赋值（不支持array），例如：

1
2
3
4
list<string> names;
vector<const char*> oldstyle;
names=oldstyle;//错误的，不可以直接将类型不同的容器赋值
names=assign( oldstyle.begin(),oldstyle.end() );

assign会直接替换掉旧的元素，并且assign中使用的迭代器不能指向调用assign的容器

assign也支持输入一个整数和一个元素值：

1
2
list<string> names(1);
name.assign(10,"dhk");//替换为10个相同的指定元素

swap

swap函数的作用是交换两个相同类型容器的元素，但是swap的速度要快于一般的值拷贝，因为其本质的操作并没有改变这些元素的地址，而是改变了两个容器的数据结构，我个人的理解是就好像基于FreeRTOS的列表学习 | 小董的BLOG (gitee.io)中列表与列表项之间的关系，swap只是改变了首尾列表项与对应列表的指针关系；也就是说容器内元素的地址未发生变化，只是用于存储它们所属容器信息的某个变量（应该只有首尾元素）发生了变化。因此，swap操作是在一个常数时间内完成的，因为它跟元素的个数无关

因此，在swap前使用的迭代器、引用、指针在swap后都不会失效，因为元素本身的地址是没有改变的，这点就不同于assign的值拷贝。也就是说我们在使用swap后仍可以使用之前的迭代器、引用和指针，它们依旧指向（绑定）swap前的那个元素，只是这个元素不再属于之前的容器了

需要注意的是：

  • 对于string，调用swap会导致之前的迭代器、指针和引用失效
  • 对于array，两容器长度必须相等。swap会真正地交换元素值，但元素地址还是没有改变的，也就是swap前的迭代器、指针和引用仍然可以使用，只是它指向（绑定）的元素的元素内容发生了变化

关系运算符

所有容器都支持使用关系运算符，但运算对象类型必须一致，运算原则：

  • 长度相等且元素两两对应相等则两个容器相等
  • 如果长度不等，但元素相等（较小容器的所有元素都等于较大容器的元素），则小容器＜大容器
  • 如果长度不等且元素不等，则关系取决于第一个不不相等元素的大小关系

需要注意的是，只有当容器元素的类型也定义了相应的运算符时才可以使用关系运算符比较两个容器

顺序容器操作

添加元素

以下函数皆为类成员函数

函数 作用 返回值
push_back(t) 在容器尾部添加一个t元素 void
push_front(t) 在容器头部添加一个t元素 void
insert(p,t) 在迭代器p指向的元素之前添加一个t元素 新元素的迭代器
insert(p,n,t) 插入n个t元素 第一个新元素的迭代器
insert(p,b,e) 在迭代器p之前添加迭代器b到e范围内的元素 第一个新元素的迭代器
insert(p,il) 插入一个il列表，例如{1,2,3} 第一个新元素的迭代器

当容器元素需要通过构造函数创建时，可以使用以下函数直接在容器内存中构造元素：

函数 作用 返回值
emplace_back(arg1,arg2,…) 直接添加一个由元素类构造函数构建的新元素到容器尾部 void
emplace_front(arg1,arg2,…) 直接添加一个由元素类构造函数构建的新元素到容器头部 void
emplace(p,arg1,arg2,…) 直接添加一个由元素类构造函数构建的元素到迭代器p前 新元素的迭代器

从arg1开始的参数要严格符合元素的构造函数参数要求

使用这些函数有几个需要注意的点：

  • array不能使用这些操作
  • forward_list有专用函数，不能使用这些函数
  • forward_list不支持push_back和emplace_back
  • vector和string不支持push_front和emplace_front
  • 向一个vector、string或deque插入元素会使原来的迭代器、指针、引用失效
  • 将元素插入到vector、deque和string中是合法的，但是消耗资源较大

访问元素

以下皆为类成员函数

函数 作用
begin() 返回首元素迭代器
end() 返回尾元素之后位置的迭代器
front() 返回首元素的引用
back() 返回尾元素的引用
c[n] 返回容器c中下标n元素的引用，下标越界会导致运行出错
at(n) 同上，但如果下标越界，会抛出一个out_of_range异常
  • 对一个空容器调用这些函数都属于越界访问
  • at和下标操作只适用于vector、string、deque和array
  • 如果容器是const的，则返回元素的引用也是const的，不可改变

删除元素

函数 作用 返回值
pop_back() 删除尾部元素，若容器为空则函数未定义 void
pop_front() 删除头部元素 void
erase(p) 删除迭代器p处元素，若p为尾后迭代器，则函数未定义 被删元素之后的元素迭代器
erase(b,e) 删除迭代器b和e范围内的元素 最后一个被删元素之后的迭代器
clear() 删除所有元素 void
  • array不能使用这些操作
  • forward_list不支持pop_back()
  • vector和string不支持pop_front()

forward_list的特殊操作

前面讲到，forward_list为单向链表，当我们使用前面的这些函数操作某个元素时，需要找到该元素的前驱，因为无论是添加、删除元素都需要改变前驱的链接。但是单向链表无法通过简单的办法找到一个节点的上一个节点，因此单向链表的实现方式有所不同：通过要操作的元素的上一个元素的迭代器来找到待操作元素

函数 作用 返回值
before_begin() 返回首元素之前的迭代器，该迭代器不可解引用 ~
insert_after(p,t) 在迭代器p后插入t 插入的元素的迭代器
insert_after(p,n,t) 在迭代器p后插入n个t 最后一个插入的元素的迭代器
insert_after(p,b,e) 在p后插入迭代器b和e之间的元素 最后一个插入的元素的迭代器
insert_after(p,il) 在p后插入一个花括号列表 最后一个插入的元素的迭代器
emplace_after(p,args1,args2,…) 在p后插入一个由构造函数构造的元素 新元素的迭代器
erase_after(p) 删除p指向的元素之后的那一个元素 被删元素之后的迭代器
erase_after(b,e) 删除从b之后到e之间的元素，即(b,e] 被删元素之后的迭代器

改变容器大小

对应除array之外的容器，其容量都是随时可变的，可以通过添加、删除元素实时改变容器的大小，这里提供了resize函数来可视化管理容器的大小：

函数 作用
resize(n) 将容器大小调整为n
resize(n,t) 任何新添加的元素都初始化为t

对于调整值n，若n小于容器本身大小，则多出的元素被丢弃；若n大于容器大小，新的元素都将进行初始化

改变容器大小可能会因为删除元素导致迭代器失效

管理容器的内存

对于vector和string来说，为了支持快速随机访问，其元素在内存上是连续存储的。

因此，当容器需要扩充容量时，因为元素必须连续纯粹的关系，每次添加扩容的新元素时，容器都会重新分配内存空间以保证所有的元素在内存上都连续存储（此时原来的空间内存就会被释放），这种操作会严重影响性能。

为了减轻这种代价，标准库实现者在容器不得不获取新的内存空间时，会分配比新的空间需求更大的内存空间，多出的空间作为预留备用，可以一定程度避免多次重新分配内存空间。而在实际中，这种策略也确实大大提高了性能

为了方便用户管理这些内存，容器类型中也提供了相关的成员函数：

函数 作用
shrink_to_fit() 删除预留的空间，使用后内存空间与size()一致
capacity() 容器目前在不重新分配空间的前提下最多可以保存多少元素
reserve(n) 为容器分配一个至少能容纳n个元素的空间

根据我的使用经验，当reserve的值超过目前容器实际容量一定值之后，reserve的值会等于capacity。并且，reserve与resize函数最大的区别就是：reserve仅分配内存空间，而resize会将元素进行初始化，但它们都是以元素的个数为单位，而不是字节之类的

  • capacity和reserve只适用于vector和string

额外的string操作

构造string的其他方法

函数 作用
string s(cp,n) s是cp指向的数组前n个字符的拷贝
string s(s2,pos2) s是string变量s2从下标pos2开始的字符的拷贝
string s(s2,pos2,len2) 同上，len的长度可以超过s2长度，此时至多拷贝size-pos2个字符

子字符串操作

函数 作用
substr(pos,n) 返回一个string，返回值同第二个构造函数

关联容器

关联容器和顺序容器有根本的区别，简单来说，关联容器通过关键字来保存、访问元素；而顺序容器是通过元素在容器中的位置来操作元素的。

标准库提供了8个关联容器：

类型 功能
map 关联数组：关键字与值一一对应
set 关键字即值，只保存关键字的容器
multimap 关键字可重复出现，允许多个元素对应一个关键字的map
multiset 关键字可重复出现的set
下方为无序容器 ~
unordered_map 用哈希函数组织的map
unordered_set 用哈希函数组织的set
unordered_multimap ~
unordered_multiset ~

使用它们需包含对应的头文件

关联容器概述

关联容器支持上面讲的容器通用操作，不支持顺序容器操作，且关联容器的迭代器都是双向的

关联容器定义

没什么需要特别讲的，基本可以看明白

  • map：

    1
    map<string, int> test={{"dhk",1},{"aca",2}};

  • set：

    1
    set<int> test={1,2,3,4};

关键字类型要求

对于关键字的类型必须是可以比较的。

关联容器操作

关联容器特有类型别名

  • key_type：容器的关键字类型
  • mapped_type：关键字对应值的类型，只适用于map
  • value_type：对于set，于key_type相同；对于map，为pair<const key_type,mapped_type>

(pair可以简单理解为一个类似小容器的类型，每个对象只允许有两个成员)

关联容器迭代器

对于顺序容器，迭代器的解引用为元素的值；而对于关联容器：

  • set的迭代器解引用对象为key_type

  • map的迭代器解引用对象为一个pair类型，因此：

    1
    2
    3
    4
    map<string,int> test({"dhk",1},{"aca",2});
    auto i=test.begin();
    string a=(*i).first;
    int b=i->second;

    需要注意的是，关联容器的关键字是const的，不可修改

    同时，对于关联容器，begin函数返回的不一定是初始化时的第一个元素，而是经过关键字比较过后最小的元素

插入元素

对于map，以下几种方式都可以

1
2
3
4
test.insert({"dhk",1});
test.insert(makepair("dhk",1));//makepair为现场构造一个pair
test.insert(pair<string,int>("dhk",1));
test.insert(map<string,int>::value_type("dhk",1));

同时也可以使用emplace函数，同顺序容器

删除元素

使用erase函数，参数可以为关键字或迭代器

map的下标操作

1
2
3
map<string,int> test({"dhk",1});
map["dhk"]=2;
map["aca"]=2;

map的下标接受一个关键字，会获取该关键字关联的值

如果容器中未存在该关键字，则会创建一个新的元素插入容器中，因此下标操作只能对非const容器使用

通用访问操作

函数 功能 返回值
find(k) 访问容器中第一次出现的关键字为k的元素 该元素迭代器
count(k) 关键字为k的元素数量 数量
lower_bound(k) 访问第一次出现的关键字≤k的元素 该元素迭代器
upper_bound(k) 访问第一次出现的关键字＞k的元素 该元素迭代器
equal_range(k) 关键字为k的所有元素的范围 一个pair，两个成员均为迭代器

对于允许关键字重复的容器，关键字相同的元素会在容器中相邻存储，也就是可以通过迭代器递增的方式依次访问

这些操作与下标操作不同的是不能创建新元素

单词转换程序

根据书上的思路写了一个简化版的拼音转汉字程序

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
40
41
42
43
44
45
46
47
#include<iostream>
#include<fstream>
#include<sstream>
#include<string>
#include<vector>
#include<array>
#include<unordered_map>
#include<map>
using namespace std;

/*将文件流绑定的文件数据导入到本程序的map中,文件数据格式如下*/
/*拼音 对应汉字*/
map<string,string> bulidmap(ifstream &map_file)//返回值为一个map<string,string>
{
    map<string,string> the_map;
    string key,value;
    while(map_file>>key && getline(map_file,value))
    //将拼音存入key变量中，该行剩下的内容存入value中
    {
        //如果value有值，则删除开头的空格
        if(value.size()>1)  the_map[key]=value.substr(1);
    }
    return the_map;
}


int main()
{
    ifstream mapfile;//创建一个读取文件流用于读取文件
    stringstream str("cy shi wo die");//字符串流用于程序输入
    mapfile.open("c++\\ass_container\\map.txt");
    auto trans_map=bulidmap(mapfile);//将文件流内容导入新创建的map类型变量中
    auto end=trans_map.end();//指向map末端之后的一个迭代器
    string s,s1;
    while(str>>s)
    {
        auto i= trans_map.find(s);//将字符串流中的每一个单词取出，在map中寻找有无对应的key
        if (i !=end)//如果未寻找到，迭代器i会等于end
        {
            s=i->second;//用寻找到的key对应的value（拼音对应汉字）覆盖s中原有的拼音
        }
        s1=s1+s;//s1用于存储全部的转换结果
    }
    cout<<s1<<endl;
    system("pause");
    return 0;
}
  • 21行：字符串删除函数，可以删除字符串中指定数量的字符
  • 38行：find函数如果未找到对应关键字则会返回队尾之后的迭代器

无序容器

无序容器也属于关联容器的一种，但无序容器不是使用比较关键字的方式来组织元素顺序，而是通过一个哈希函数算法进行组织元素，简单地来说，该算法就是用比普通关联容器组织方式代价更小的方式进行元素组织，通常用于关键字没有明显的序关系等情况下使用，也许可以节省性能的占用

类型 功能
unordered_map 用哈希函数组织的map
unordered_set 用哈希函数组织的set
unordered_multimap ~
unordered_multiset ~

无序容器的管理措施

无序容器在存储上组织为一组“桶”，哈希函数会计算每个元素的哈希值，具有相同哈希值的元素会被存入一个桶中，对于桶的维护，标准库也给出了一系列函数，但是我觉得用处不大，就先不写在这里了

无序容器对关键字类型的要求

无序容器中有一个hash类型用于存储哈希值，内置类型和string等标准库类型均定义了hash类型，均可以作为关键字。不能作为无序容器关键字的是另一个自定义的无序容器，原因与模板有关。