🎉作者简介:👓 博主在读机器人研究生,目前研一。对计算机后端感兴趣,喜欢 c + + , g o , p y t h o n , 目前熟悉 c + + , g o 语言,数据库,网络编程,了解分布式等相关内容 \textcolor{orange}{博主在读机器人研究生,目前研一。对计算机后端感兴趣,喜欢c++,go,python,目前熟悉c++,go语言,数据库,网络编程,了解分布式等相关内容} 博主在读机器人研究生,目前研一。对计算机后端感兴趣,喜欢c++,go,python,目前熟悉c++,go语言,数据库,网络编程,了解分布式等相关内容 📃 个人主页: \textcolor{gray}{个人主页:} 个人主页: 小呆鸟_coding 🔎 支持 : \textcolor{gray}{支持:} 支持: 如果觉得博主的文章还不错或者您用得到的话,可以免费的关注一下博主,如果三连收藏支持就更好啦 \textcolor{green}{如果觉得博主的文章还不错或者您用得到的话,可以免费的关注一下博主,如果三连收藏支持就更好啦} 如果觉得博主的文章还不错或者您用得到的话,可以免费的关注一下博主,如果三连收藏支持就更好啦👍 就是给予我最大的支持! \textcolor{green}{就是给予我最大的支持!} 就是给予我最大的支持!🎁 💛本文摘要💛
顺序容器类型
容器的选择
通常使用vector是最好的选择,除非你有很好的理由选择其他容器。如果有很多小的元素且空间开销很重要,不用 list如果需要在中间位置插入/删除,用 list或forward_list如果需要在头尾位置插入/删除,用 deque如果需要随机访问,用 vector 或 deque如果需要在中间位置插入,而后随机访问: 如果可以通过排序解决,就像插到尾部,而后排序 在输入阶段用 list ,输入完成后拷贝到 vector 中 ??9.2 容器库概述 '类型别名' iterator const_iterator value_type // 容器元素类型。定义方式: vector<int>::value_type reference // 元素类型的引用。定义方式: vector<int>::reference const_reference // 元素的 const 左值类型 size_type difference_type //带符号整形,保存俩个迭代器之间的距离 '构造函数'-'三种通用的构造函数:同类拷贝、迭代器范围初始化、列表初始化' C c1(c2); // 拷贝构造函数,容器类型与元素类型必须都相同 C c1(c2.begin(),c2.end()); // 要求两种元素类型可以转换即可。 C c1{a,b,c,...}; // 使用初始化列表,容器的大小与初始化列表一样大 C c(n); // 这两种接受大小参数的初始化方式只有顺序容器能用,且 string 无法使用 C c(n,t); '赋值与swap' c1 = c2; c1 = {a,b,c,....} a.swap(b); swap(a, b); // 两种 swap 等价 '大小' c.size(); c.max_size(); // c 可以保存的最大元素数目,是整个内存层面的容量,不是已分配内存。不同于 caplity, caplity 只能用于 vector,queue,string c.empty(); '添加/删除元素(不适用于array)' c.insert(args); // 将 args 中的元素拷贝进 c c.emplace(inits); // 使用 inits 构造 c 中的一个元素 c.erase(args); // 删除指定的元素 c.clear(); '关系运算符' ==; !=; <; <=; >; >= // 所有容器都支持相等和不等运算符。无序关联容器不支持大于小于运算符。 '获取迭代器' c.begin(); c.end(); c.cbegin(); c.cend(); // 返回 const_iterator '反向容器的额外成员' reverse_iterator // 逆序迭代器,这是一个和 iterator 不同的类型 const_reverse_iterator c.rbegin();c.rend(); c.crbegin();c.crend(); ??9.2.1 迭代器 迭代器范围是左闭右开,[begin(), end())begin()指向容器的第一个元素,end()指向容器最后元素的下一位,当begin() == end()则容器为空。所有迭代器都可以递增,forward_list 不可以递减 vector<int>::iterator iter = vec.begin(); // 准确定义迭代器的方式。 'c++11新特性' auto iter = vec.begin(); ??9.2.3 begin 和 end 成员 c.begin(); c.end(); // 返回 iterator c.cbegin(); c.cend(); // 返回 const_iterator c.rbegin();c.rend(); //反向迭代器,返回reverse_iterator c.crbegin();c.crend(); //返回const_reverse_iterator当不需要写访问时应该使用cbegin() 和 cend()
??9.2.4 容器定义和初始化将一个容器初始化为另一个容器的拷贝有俩种方法
直接拷贝整个容器拷贝由一个迭代器对指定的元素范围 list<string> authors = {"hello", "world", "xdn"} vector<const char*> articles = {"a", "an", "the"}; list<string> list2(authors) //正确类型匹配 deque<string> de(authors) //错误,容器类型不匹配 vector<string> word(articles) //错误,元素类型不匹配 list<string> words(articles.begin(), articles.end()); // 正确, const char* 类型可以转换成 string类型注意:
直接拷贝整个容器,要求俩个容器的类型以及元素的类型必须匹配拷贝迭代器范围,不要求俩个容器的类型以及元素的类型必须匹配,只要元素可以进行转换就可以array 初始化
定义array既要指定元素类型,还要指定容器大小 array<int,42>; // 定义一个有42个int 的数组 array<int,42>::size_type; // 定义数组类型也需要包括元素类型和大小只有顺序容器的构造函数才接受大小参数,关联容器并不支持。
array具有固定大小。
和其他容器不同,默认构造的array是非空的。
array 不支持普通容器的构造函数
array 列表初始化时,列表元素个数小于等于 array 大小,剩余元素默认初始化为 0
array 只能默认初始化或列表初始化,如果定义的数组很大并且需要初始化,可以先默认初始化然后用 fill 函数填充值。
array赋值
不能对内置数组拷贝或赋值,但是 array 可以。使用一个 array 对另一个 array 赋值,需要两个array 元素类型与大小都相同。不能用花括号列表对 array 赋值(只可以初始化)要求俩个array的元素类型和大小都要一样 '数组' int digs[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} int copy[10] = digs; //错误,内置数组不支持拷贝或赋值 'array' array<int, 10> ar = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; array<int, 10> br = ar; //正确,只要数组类型匹配即可 br = {0}; //错误,只能用花括号初始化,不能赋值 ??9.2.5 赋值和swap 下面操作适用于所有容器。除array外array 类型不支持assign操作,也不允许用花括号的值列表进行赋值,只能进行初始化。对容器使用赋值运算符(除 array 外),将会使该容器的所有元素被替换。如果两个容器大小不等,赋值后都与右边容器的原大小相同。使用assign(仅顺序容器)
assign 是赋值操作,可以用于顺序容器。“=” 要求两边类型相同, assign 要求只要可以转换即可 lst.assign(vec.begin(), vec.end()); // 使用迭代器范围赋值 lst.assign(il); // il是一个花括号包围的元素值列表 lst.assign(n, t); // 将 lst 的元素替换为 n 个 t '操作等价于' lst.clear(); lst.insert(lst.begin(), n, t);swap
对 array ,swap 交换两个 array 中的元素值。指针、引用和迭代器绑定的元素不变(值变)。对于其他容器,swap 不交换元素,只交换数据结构,因此 swap 操作非常快。对于 string,swap 后,指针、引用和迭代器会失效。对于其他容器,交换后指针指向了另一个容器的相同位置。迭代器并不失效统一使用 swap(a,b),而非 a.swap(b)对于 array,swap 操作的时间与元素数目成正比,对于其他容器,swap 操作的时间是常数。 ??9.2.6 容器大小操作俩个容器内的元素进行比较需要保证俩点
俩个容器必须是相同类型的容器,并且保存相同类型的元素元素类型要支持关系运算符(例如你随便定义一个类类型,如果里面没有重载关系运算符,那么你这俩个类类型,不能进行比较) ??9.3 顺序容器操作 ??9.3.1 向顺序容器添加元素 注意向 vector、string 或 deque 插入元素会使所有指向容器的迭代器、引用和指针失效。添加的都是元素的拷贝,不是元素本身。头尾添加返回 void,中间添加返回指向新添加元素的迭代器push
vector 和 string 不支持 push_front 和 emplace_front;forward_list 不支持 push_back 和 emplace_back;forward_list有自己专有版本的insert和emplace。 c.push_back(t); // 尾部添加一个 t c.push_front(t); // 头部添加一个 tinsert
insert 返回值是指向添加的元素中第一个元素的迭代器inset 是在迭代器指向的位置之前插入一个值emplace 函数在容器中直接构造元素,传递给emplace函数的参数必须与元素类型的构造函数相匹配,因此一般可以为空(默认初始化)。emplace(c++ 11)
新标准引入三个新成员- emplace_front, emplace_back, emplace当调用push 或insert成员函数时,是将元素拷贝到容器中,而emplace 则将参数传递给元素类型的构造对象。emplace 返回值是指向添加元素的迭代器 c.emplace_back(args); // 在尾部添加一个由 args 构建的元素 c.emplace_front(args); // 在头部添加一个由 args 构建的元素 c.emplace(p,args); // 在迭代器 p 所指元素之前添加一个由 args 构建的元素 ??9.3.2 访问元素 访问元素要确保容器非空,不然会出现错误at和下标操作只适用于string、vector、deque、array。begin/end
begin()/end() 返回迭代器front/back
front()/back() 返回元素的引用,可以对元素进行修改 c.front(); c.back(); //返回的是尾元素的引用(注意不同于尾后迭代器)at
at返回下标为 n 的元素的引用at可以快速随机访问的容器都可以使用下标。使用下标一定要保证下标不越界,可以用 at 函数。当下标越界,at 函数会抛出一个 out_of_range 异常 c[n] c.at(n); //返回下标为 n 的元素的引用auto 获得引用
如果要通过 auto 获得元素的引用,定义时一定要记得加上引用符号 c.front() = 42; //将42赋予c中的第一个元素 auto &v = c.back(); //获取指向最后一个元素的引用 v = 1024; //通过引用可以改变元素的值 auto v2 = c.back(); //v2不是一个引用,它是c.back()的一个拷贝 v2 = 0; //未改变c中的元素理解:
c.front() 返回的是引用,因此可以通过 c.front() = 32; 来给 c 的首元素赋值。而auto b = c.front()得到的 b 是等号右端元素的拷贝,不是引用 ??9.3.3 删除元素 头尾删除返回 void,特定位置删除返回被删除元素之后元素的迭代器vector/string 不支持 pop_front,forward_list 不支持 pop_back。forward_list 有自己特殊版本的 erase。删除多个元素
c.clear(); c.erase(c.begin(), c.end()); // 和 c.clear() 等价总结
删除之前要确保元素存在删除 deque 种除首尾之外的任何元素都会使所有迭代器、引用和指针失效。删除 vector 或 string 中的元素会使指向删除点之后位置的迭代器、引用和指针失效。删除 list 中的元素不会影响指向其他位置的迭代器、引用、指针。 ??9.3.4 特殊的forward_list操作 forward_list 是单向链表,添加和删除操作都会同时改变前驱和后继结点,因此一般的添加和删除都不适用于 forward_listforward_list定义了before_begin,即首前(off-the-begining)迭代器,允许我们再在首元素之前添加或删除元素。总结
对于往容器插入元素(insert()),在迭代器p指向的元素之前,插入一个元素,返回指向新元素的迭代器对于往容器删除元素(erase()),删除迭代器p所指向的元素,返回一个指向删除元素之后的元素的迭代器对于forward_list插入操作(insert_after()),在迭代器p之后插入元素,返回一个指向最后一个插入元素的迭代器。对于forward_list删除操作(erase_after()), 删除迭代器p之后的元素,返回一个指向被删除元素之后元素的迭代器值初始化:对于容器而言,可以只提供元素个数而省略初始值,此时库会创建一个值初始化元素初值,并把它赋给容器中的所有元素。这个值初始化有容器当中元素类型决定(例如int,容器自动初始化为0,string容器自动初始化为空字符串) ??9.3.6 容器操作可能使迭代器失效添加和删除元素都可能使指针、引用、迭代器失效。使用失效的指针、引用、迭代器是很严重的错误。
在向容器添加元素后:
如果容器是vector或string,且存储空间被重新分配,则指向容器的迭代器、指针、引用都会失效。对于deque,插入到除首尾位置之外的任何位置都会导致指向容器的迭代器、指针、引用失效。如果在首尾位置添加元素,迭代器会失效,但指向存在元素的引用和指针不会失效。对于list和forward_list,指向容器的迭代器、指针和引用依然有效。在从一个容器中删除元素后:
对于list和forward_list,指向容器其他位置的迭代器、引用和指针仍然有效。对于deque,如果在首尾之外的任何位置删除元素,那么指向被删除元素外其他元素的迭代器、指针、引用都会失效;如果是删除deque的尾元素,则尾后迭代器会失效,但其他不受影响;如果删除的是deque的头元素,这些也不会受影响。对于vector和string,指向被删元素之前的迭代器、引用、指针仍然有效。编写改变容器的循环程序
必须保证每次改变容器后都更新迭代器。insert 和 erase 都会返回迭代器,更新很容易。调用 erase 后,不需要递增迭代器,调用 insert 后,需要递增两次。不要保存 end() 返回的迭代器
push、pop、首尾 emplace 操作都没有返回值,但是都会改变尾后迭代器,因此不能保存 end() 返回值。for 循环判断条件中的 end() 每轮都会重新获取迭代器进行判断,因此不用担心(也因此速度会略慢,当不改变容器大小时,采用下标更快) ??9.4 vector对象是如何增长的 vector和string在内存中是连续存储的,为了避免每添加一个元素就要重新分配一次空间,在每次获取新的内存空间时,vector和string通常会分配比新空间需求更大的内存空间。容器预留这些空间作为备用,可以保存新的元素。虽然每次重新分配需要移动所有元素,但是其扩张操作通常比list和deque快管理容量的成员函数
注意
c.reserve(n) 不会减小容量,只会增大容量,当需求容量大于当前容量,才会分配内存,否则什么都不做。c.resize(), 只改变容器中元素的数目,并不改变容器的容量c.shrink_to_fit() 只是一个请求,实现时标准库可能会不执行。capacity和size
capacity表示不分配新的内存空间前提下它最多保存多少元素size是指它已经保存元素的数目。 ??9.5 额外的string操作 除了与顺序容器共同的操作之外,string提供了一些额外的操作。主要用于c风格字符串和下标访问,允许用下标代替迭代器。 ??9.5.1 构造string的其他方法substr
s.substr(pos,n) 返回 s 的一部分或全部拷贝,范围由参数指定。总结
所有的拷贝或者substr有四种情况: 括号中俩个参数(p, n),p + n没有超过string大小,分别是从下标p位置,拷贝n个字符括号中俩个参数(p, n),p + n超过string大小,此时会拷贝到字符尾部括号中一个参数(p),从下标p的位置,一直拷贝到最后括号中一个参数,但是该参数超过了string的值,此时会抛出异常 ??9.5.2 改变string的其他方法string 支持顺序容器的 assign、insert、erase 操作,此外还增加了两个额外的操作
接受下标版本的 insert 和 erase接受 C 风格字符数组的 insert 和 assignappend 和 replace 函数接受下标的 insert 和 erase
insert 和 erase 接受下标的版本返回的是一个指向 s 的引用(区别于迭代器版本返回指向第一个插入字符的迭代器)。insert 的所有版本都是第一部分参数为 pos,后面的参数为待插入的字符erase 的所有版本的参数都是 pos,pos 分为 起始位置 和 终止位置/长度 s.insert(s.size(), 5, '!'); // 在 s 末尾(s[s.size()]之前)插入 5 个感叹号,注意实际上不存在 s[s.size()]; s.insert(0, s2, 3, s2.size()-3); // 在 s[0] 之前插入 s2 第四个字符开始的 s2.size()-3 个字符 s.erase(s.size()-5, 5); // 从 s 删除最后 5 个字符接受 C 风格字符数组的 insert 和 assign
assign 的所有版本的参数都是要赋的值,由 起始位置 + 终止位置/长度 组成replace 的所有版本的参数都是第一部分参数为要删除的范围,第二部分为要插入的字符。 const char* cp = "stately,plump Buck"; s.assign(cp, 7); // 用从 cp 开始的前 7 个字符向 s 赋值 s.insert(s.size(), cp+7); // 将从 cp+7 开始到 cp 末尾的字符插入到 s 末尾append 和 replace
append:在 string 末尾进行插入操作。replace:等价于调用 erase 和 insert 操作。 s.append(" 4th Ed."); // 等价于 s.insert(s.size()," 4th Ed."); s.erase(11, 3); s.insert(11, "5th") //等价于 s.replace(11, 3, "5th"); // 从下标 11 开始,删除三个字符并插入 3 个新字符 ??9.5.3 string搜索操作 string类提供了6个不同的搜索函数,每个函数都有4个重载版本。每个搜索操作都返回一个string::size_type值,表示匹配发生位置的下标。如果搜索失败则返回一个名为string::npos的static成员(类型是string::size_type,初始化值是-1,也就是string最大的可能大小)。注意:
find 和 rfind 查找的是给定的整个 args,而剩下的查找的是给定的 args 中包含的任意一个字符。 s.find(args); // 查找 s 中 args 第一次出现的位置 s.rfind(args); // 查找 s 中 args 最后一次出现的位置 s.find_first_of(args); // 查找 s 中 args 的任意一个字符第一次出现的位置 s.find_last_of(args); // 查找 s 中 args 的任意一个字符最后一次出现的位置 s.find_first_not_of(args); // 查找 s 中第一个不在 args 中的字符 s.find_last_not_of(args); // 查找 s 中最后一个不在 args 中的字符 'args为以下形式' c,pos // 字符,pos 为搜索开始位置( 从s中位置pos开始查找字符c。pos默认是0) s2,pos // 字符串( 从s中位置pos开始查找字符串s。pos默认是0) cp,pos // 以空字符结尾的 c 风格字符串(从s中位置pos开始查找指针cp指向的以空字符结尾的C风格字符串。pos默认是0) cp,pos,n // c 风格字符串的前 n 个字符( 从s中位置pos开始查找指针cp指向的前n个字符。pos和n无默认值。)使用 pos 循环查找所有 str 包含的字符的位置
string::size_type pos = 0; while((pos=s.find_first_of(str,pos)) != string::npos ){ cout << pos << endl; ++pos;} ??9.5.4 compare 函数 逻辑类似于C标准库的strcmp函数,根据s是等于、大于还是小于参数指定的字符串俩个string对象比较或者一个string对象一个字符数组, 可以比较整体或一部分字符串s.compare返回0、正数或负数。 int cmp = s.compare(s2); int cmp = s.compare(pos1,n1,s2); // 将 s 中 pos1 开始的前 n1 个字符与 s2 比较 int cmp = s.compare(pos1,n1,s2,pos2,n2); // 将 s 中 pos1 开始的前 n1 个字符与 s2 中从 pos2 开始的 n2 个字符进行比较 int cmp = s.compare(cp) // 将 s 与 cp 指向的字符数组比较 int cmp = s.compare(pos1,n1,cp); int cmp = s.compare(pos1,n1,cp,n2); ??9.5.5 数值转换例子
string s2 = "pi = 3.14"; double d = stod(s2.substr(s2.find_first_of("+-.0123456789"))); // 先使用查询方法找出第一个数值字符(因为+ - . 0 1 2在s2中都不存在,所以继续找下一个为3,此时3在s2中是下标为5的位置),返回5,就变成了stod(s2.substr(5)),将字符串从下标为5的位置一直到结束,转换成double类型 ??9.6 容器适配器 标准库定义了三个顺序容器适配器:stack、queue、priority_queue。容器,函数,迭代器都有适配器适配器是一种机制,是某种事物的行为看起来像另一种事物。适配器的通用操作和类型
size_type; value_type; container_type; // 实现适配器的底层容器类型。 A a; //创建一个名为a的空适配器 A a(c) //创建一个名为a的适配器,带有容器c的一个拷贝 关系运算符 //每个适配器都支持所有关系运算符:==、!=、<、 <=、>、>=这些运算符返回底层容器的比较结果 a.empty() //若a包含任何元素,返回false;否则返回true a.size() //返回a中的元素数目 swap(a, b) //交换a和b的内容,a和b必须有相同类型,包括底层容器类型也必须相同 a.swap(b) //同上 所有适配器要求容器具有添加和删除元素的能力,因此array不能当适配器初始化操作
默认情况下,stack 和 queue 是基于 deque 实现的, priority_queue 是在 vector 之上实现的。
因此可以直接用一个 deque 来初始化 stack 和 queue。注意:是直接使用容器对象,不是使用迭代器表示的范围。
priority_queue 不能使用无序的 vector 初始化。
deque<int> deq; stack<int> sta(deq); // 用 deq 初始化 sta如果要使用其他顺序容器实现适配器,要在创建适配器时用一个顺序容器作为第二个类型参数。
stack<int, vector<int>> sta; // 定义基于 vector 实现的 stack总结
stack 可以构造于 vector, list, deque 之上。queue 可以构造于 list, deque 之上。priority_queue 可以构造于 vector、deque 之上。栈适配器:stack
s.pop(); s.push(item); s.emplace(args); // 由 args 构造元素并压入栈顶 s.top(); s.size(); s.empty(); swap(s, s2); s.swap(s2);队列适配器:queue
q.pop(); // 删除 queue 的首元素 q.push(item); // 在 queue 末尾插入一个元素 q.emplace(args); // 构造元素 q.front(); // 返回首元素 q.back(); // 返回尾元素。 q.size(); q.empty(); swap(q,q2);q.swap(q2); queue 为先进先出队列。queue 和 priority_queue 都定义在头文件 queue 中。优先队列:priority_queue
创建 stack, queue, priority_queue 时都可以用一个顺序容器作为第二个类型参数,此外创建 priority_quque 时还可以额外传递第三个参数:一个函数对象来决定如何对 priority_queue 中的元素进行排序。大根堆和小根堆
priority_queue 默认采用的是 less ,默认情况下 q.top() 是最大的元素,即大根堆。 priority_queue <int> q; // 默认采用 vector 作为容器,采用 less<Type> 比较元素,是大根堆 priority_queue <int, vector<int>, greater<int> > q; // 采用 greater<Type> 比较元素,生成小根堆其他操作:
q.pop(); // 删除 priority_queue 的最高优先级元素 q.push(item); // 在 priority_queue 适当的位置插入一个元素 q.emplace(args); // 构造元素 q.top(); // 返回最高优先级元素 q.size(); q.empty(); swap(q, q2); q.swap(q2); priority_queue 为元素建立优先级。新加入的元素排在所有优先级比它低的元素之前。priority_queue 元素可以重复priority_queue 不能使用无序的 vector 初始化。
1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,会注明原创字样,如未注明都非原创,如有侵权请联系删除!;3.作者投稿可能会经我们编辑修改或补充;4.本站不提供任何储存功能只提供收集或者投稿人的网盘链接。 |