一、順序容器概述

　　一個(gè)容器就是一些特定類型對(duì)象的集合。順序容器為程序員提供了控制元素存儲(chǔ)和訪問(wèn)順序的能力。這種順序不依賴于元素的值，而是與元素加入容器時(shí)的位置相對(duì)應(yīng)。

　　順序容器類型：

容器類型	說(shuō)明
vector	可變大小數(shù)組。支持快速隨機(jī)訪問(wèn)。在尾部之外的位置插入或刪除元素可能會(huì)很慢。
deque	雙端列表。支持快速隨機(jī)訪問(wèn)。在頭尾位置插入/刪除速度很快。
list	雙向鏈表。只支持雙向順序訪問(wèn)。在list中任何位置進(jìn)行插入/刪除操作速度都很快。
forward_list	單向鏈表。只支持單向順序訪問(wèn)。在鏈表任何位置進(jìn)行插入/刪除操作速度都很快。
array	固定大小數(shù)組。支持快速隨機(jī)訪問(wèn)。不能添加或刪除元素。
string	與vector相似的容器，但專門用于保存字符。支持快速隨機(jī)訪問(wèn)。在尾部插入/刪除速度快。

　　string和vector將元素保存在連續(xù)的內(nèi)存空間中。由于元素是連續(xù)存儲(chǔ)的，由元素的下標(biāo)來(lái)計(jì)算其地址是非常快速的。但是，在這兩種容器的中間位置添加或刪除元素就會(huì)非常耗時(shí)。

　　list和forward_list這兩個(gè)容器的設(shè)計(jì)目的是令容器任何位置的添加和刪除元素都很快速。作為代價(jià)，這兩個(gè)容器不支持元素的隨機(jī)訪問(wèn)：為了訪問(wèn)一個(gè)元素，我們只能遍歷整個(gè)容器。而且，與vector、deque和array相比，這兩個(gè)容器的額外內(nèi)存開銷也很大。

　　deque是一個(gè)更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。與string和vector類似，在deque的中間位置添加或刪除元素的代價(jià)（可能）很高。但是，在deque的兩端添加或刪除元素都是很快的（只花費(fèi)常數(shù)時(shí)間），與list和forward_list添加刪除元素的速度相當(dāng)。

　　forward_list和array是新C++標(biāo)準(zhǔn)增加的類型。與內(nèi)置數(shù)組相比，array是一種更安全、更容易使用的數(shù)組類型。forward_list的設(shè)計(jì)目標(biāo)是達(dá)到與最好的手寫的單向鏈表數(shù)據(jù)結(jié)構(gòu)相當(dāng)?shù)男阅堋Ｒ虼?#xff0c;forward_list沒(méi)有size操作，因?yàn)楸４婊蛴?jì)算其大小就會(huì)比手寫鏈表多出額外的開銷。

?

二、容器庫(kù)概述

　　一般來(lái)說(shuō)，每個(gè)容器都定義在一個(gè)頭文件中，文件名與類型名相同。

　　順序容器幾乎可以保存任意類型的元素。特別是，我們可以定義一個(gè)容器，其元素的類型是另一個(gè)容器。這種容器的定義與任何其他容器類型完全一樣。但某些容器操作對(duì)元素類型有其自己的特殊要求。我們可以為不支持特定操作需求的類型定義容器，但這種情況下就只能使用那些沒(méi)有特殊要求的容器操作了。

　　所有容器類型（也包括關(guān)聯(lián)容器）都支持的操作：

類型別名	說(shuō)明
iterator	此容器類型的迭代器類型
const_iterator	可以讀取元素，但不能修改元素的迭代器類型
size_type	無(wú)符號(hào)整數(shù)類型，足夠保存此種容器類型最大可能容器的大小
difference_type	帶符號(hào)整數(shù)類型，足夠保存兩個(gè)迭代器之間的距離
value_type	元素類型
reference	元素的左值類型；與value_type&含義相同
const_reference	元素的const左值類型（即，const value_type&）
構(gòu)造函數(shù)	?
C c;	默認(rèn)構(gòu)造函數(shù)，構(gòu)造空容器（array不支持）
C c1(c2);	構(gòu)造c2的拷貝c1
C c(b, e);	構(gòu)造c，將迭代器b和e指定的范圍內(nèi)的元素拷貝到c（array不支持）
C c{a, b, c, ...};	列表初始化c
賦值與swap	?
c1 = c2	將c1中的元素替換為c2中元素
c1 = {a, b, c, ...}	將c1中的元素替換為列表中元素（array不支持）
a.swap(b)	交換a和b的元素
swap(a,b)	與a.swap(b)等價(jià)
大小	?
c.size()	c中元素的數(shù)目（不支持forward_list）
c.max_size()	c可保存的最大元素?cái)?shù)目
c.empty()	若c中存儲(chǔ)了元素，返回false，否則返回true
添加/刪除元素（array不支持） 注：在不同容器中，這些操作的接口都不同	?
c.insert(args)	將args中的元素拷貝進(jìn)c
c.emplace(inits)	使用inits構(gòu)造c中的一個(gè)元素
c.erase(args)	刪除args指定的元素
c.clear()	刪除c中的所有元素，返回void
關(guān)系運(yùn)算符	?
==, !=	所有容器都支持相等（不相等）運(yùn)算符
<, <=, >, >=	關(guān)系運(yùn)算符（無(wú)序關(guān)聯(lián)容器不支持）
獲取迭代器	?
c.begin(), c.end()	返回指向c的首元素和尾元素之后位置的迭代器
c.cbegin(), c.cend()	返回const_iterator
反向容器的額外成員（不支持forward_list）	?
reverse_iterator	按逆序?qū)ぶ吩氐牡?/td>
const_reverse_iterator	不能修改元素的逆序迭代器
c.rbegin(), c.rend()	返回指向c的尾元素和首元素之前位置的迭代器
c.crbegin(), c.crend()	返回const_reverse_iterator
?	?

1、迭代器

　　標(biāo)準(zhǔn)容器迭代器的運(yùn)算符：

運(yùn)算符	說(shuō)明
*iter	返回迭代器iter所指元素的引用
iter->mem	解引用iter并獲取該元素的名為mem的成員，等價(jià)于(*iter).mem
++iter	令iter指向容器的下一個(gè)元素
--iter	令iter指向容器中的上一個(gè)元素
iter1 == iter2	判斷兩個(gè)迭代器是否相等（不相等），如果兩個(gè)迭代器指示的是同一個(gè)元素或者它們是同一個(gè)容器的尾后迭代器，則相等；反之，不相等
iter1 != iter2	?

其中，forward_list迭代器不支持遞減運(yùn)算符（--）。

?

　　string、vector、deque、array的迭代器支持的算術(shù)運(yùn)算：

算術(shù)運(yùn)算	說(shuō)明
iter + n	迭代器加上一個(gè)整數(shù)值仍得一個(gè)迭代器，迭代器指示的新位置與原來(lái)相比向前移動(dòng)了若干個(gè)元素。結(jié)果迭代器或者指示容器內(nèi)的一個(gè)元素，或者等于容器尾后迭代器
iter - n	迭代器減去一個(gè)整數(shù)值仍得一個(gè)迭代器，迭代器指示的新位置與原來(lái)相比向后移動(dòng)了若干個(gè)元素
iter += n	迭代器加法的復(fù)合賦值語(yǔ)句，將iter加n的結(jié)果賦給iter
iter -= n	迭代器減法的復(fù)合賦值語(yǔ)句，將iter減n的結(jié)果賦給iter
iter1 - iter2	兩個(gè)迭代器相減的結(jié)果是它們之間的距離。參與運(yùn)算的必須是同一個(gè)容器的迭代器
>、>=、<、<=	迭代器的關(guān)系運(yùn)算符，如果某迭代器指向的容器位置在另一個(gè)迭代器所指位置之前，則說(shuō)明前者小于后者。參與運(yùn)算的必須是同一個(gè)容器的迭代器

注意：上面的迭代器的范圍區(qū)間是[begin(),end()]，如果運(yùn)算結(jié)果不在這個(gè)區(qū)間內(nèi)，會(huì)報(bào)錯(cuò)。

　　

　　一個(gè)迭代器范圍是由一對(duì)迭代器表示，兩個(gè)迭代器分別指向同一個(gè)容器中的元素或者尾元素之后的位置。這兩個(gè)迭代器通常被稱為begin和end。這種元素范圍被稱為左閉右合區(qū)間，其標(biāo)準(zhǔn)數(shù)學(xué)描述為：[begin, end)。

　　當(dāng)auto與begin或end結(jié)合使用時(shí)，獲得的迭代器類型依賴于容器類型，如果對(duì)象是常量，返回const_iterator；如果對(duì)象不是常量，返回iterator。cbegin和cend不論對(duì)象是否是常量，返回值都是const_iterator。

?

2、容器定義和初始化

操作	說(shuō)明
C c	默認(rèn)構(gòu)造函數(shù)。如果c是一個(gè)array，則c中元素按默認(rèn)方式初始化；否則c為空
C c1(c2)	c1初始化為c2的拷貝。c1和c2必須是相同類型（即，它們必須是相同的容器類型，且保存的是相同的元素類型；對(duì)于array來(lái)說(shuō)，兩者還必須具有相同大小）
C c1=c2	同上
C c{a, b, c, ...}	c初始化為初始化列表中元素的拷貝。列表中元素的類型必須與c的元素類型相容。對(duì)于array類型，列表中元素?cái)?shù)目必須等于或小于array的大小，任何遺漏的元素都進(jìn)行值初始化。初始化列表隱含地指定了容器的大小：容器將包含與初始值一樣多的元素。
C c={a, b, c, ...}	同上
C c(b, e)	c初始化為迭代器b和e指定范圍中的元素的拷貝。范圍中元素的類型必須與c的元素類型相容（array不適用）
只有順序容器（不包括array）的構(gòu)造函數(shù)才能接受大小參數(shù)	?
C seq(n)	seq包含n個(gè)元素，這些元素進(jìn)行了值初始化；此構(gòu)造函數(shù)是explicit的
C seq(n, t)	seq包含n個(gè)初始化為值t的元素

　　將一個(gè)容器初始化為另一個(gè)容器的拷貝的例子：

1 #include <iostream> 2 #include <string> 3 #include <vector> 4 #include <deque> 5 #include <list> 6 #include <forward_list> 7 #include <array> 8 9 int main() 10 { 11 std::list<std::string> authors = { "abc", "QAQ", "hello" }; 12 std::vector<const char*> articles = { "a", "ab", "the" }; 13 14 std::list<std::string> list2(authors); // 類型匹配 15 //std::deque<std::string> auth(authors); // 錯(cuò)誤：容器類型不匹配 16 std::forward_list<std::string> words(articles.begin(), articles.end()); // 元素類型可以相互轉(zhuǎn)換 17 return 0; 18 } View Code

1）標(biāo)準(zhǔn)庫(kù)array具有固定大小

　　與內(nèi)置數(shù)組一樣，標(biāo)準(zhǔn)庫(kù)array的大小也是類型的一部分。當(dāng)定義一個(gè)array時(shí)，除了指定元素類型，還要指定容器大小。使用array時(shí)也要指定容器大小。

1 #include <iostream> 2 #include <string> 3 #include <vector> 4 #include <deque> 5 #include <list> 6 #include <forward_list> 7 #include <array> 8 9 int main() 10 { 11 std::array<int, 10> arr; // 類型為10個(gè)int的數(shù)組 12 std::array<int, 10>::size_type i; // 數(shù)組類型包括元素類型和大小 13 return 0; 14 } View Code

　　一個(gè)默認(rèn)構(gòu)造的array是非空的：它包含了與其大小一樣多的元素。這些元素都被默認(rèn)初始化。如果我們對(duì)array進(jìn)行列表初始化，初始值的數(shù)目必須等于或小于array的大小。如果初始值數(shù)目小于array的大小，則它們被用來(lái)初始化array中靠前的元素，所有剩下的元素都會(huì)進(jìn)行值初始化。

　　雖然我們不能對(duì)內(nèi)置數(shù)組類型進(jìn)行拷貝或?qū)ο筚x值操作，但array并無(wú)此限制。

1 #include <iostream> 2 #include <string> 3 #include <vector> 4 #include <deque> 5 #include <list> 6 #include <forward_list> 7 #include <array> 8 9 int main() 10 { 11 std::array<int, 10> arr = { 2, 3 }; 12 std::array<int, 10> copy = arr; 13 return 0; 14 } View Code

?

3、賦值和swap

?　　賦值運(yùn)算符將其左邊容器中的全部元素替換為右邊容器中元素的拷貝。

　　所有容器都支持的賦值運(yùn)算：

操作	說(shuō)明
c1=c2	將c1中的元素替換為c2中元素的拷貝。c1和c2必須具有相同的容器類型，且保存的是相同的元素類型
c={a, b, c, ...}	將c1中的元素替換為初始化列表中元素的拷貝（array不適用）。保存的必須是相同的元素類型
swap(c1, c2)	交換c1和c2中的元素。c1和c2必須具有相同的類型。swap通常比從c2向c1拷貝元素快得多
c1.swap(c2)	同上
assign操作不適用于關(guān)聯(lián)容器和array	?
seq.assign(b, e)	將seq中的元素替換為迭代器b和e所表示的范圍中的元素。迭代器b和e不能指向seq中的元素。保存的元素類型必須相容。
seq.assign(items)	將seq中的元素替換為初始化列表items中的元素
seq.assign(n, t)	將seq中的元素替換為n個(gè)值為t的元素?

　　賦值相關(guān)運(yùn)算會(huì)導(dǎo)致指向左邊容器內(nèi)部的迭代器、引用和指針失效。

　　swap操作將容器內(nèi)容交換不會(huì)導(dǎo)致指向容器的迭代器、引用和指針失效（容器類型為array和string的情況除外）。

1）使用assign（僅順序容器）

　　順序容器（array除外）還定義了一個(gè)名為assign的成員，允許我們從一個(gè)不同但相容的類型賦值，或者從容器的一個(gè)子序列賦值。

1 #include <iostream> 2 #include <string> 3 #include <vector> 4 #include <deque> 5 #include <list> 6 #include <forward_list> 7 #include <array> 8 9 int main() 10 { 11 std::vector<int> vec = { 1, 2, 3 }; 12 std::vector<double> vec2 = { 4.5, 5.5, 6.5 }; 13 // vec = vec2; // 錯(cuò)誤：類型不同 14 std::list<double> lst = { 7, 8, 9 }; 15 vec.assign(lst.begin(), lst.end()); 16 return 0; 17 } View Code

2）使用swap

　　除array外，交換兩個(gè)容器內(nèi)容的操作保證會(huì)很快----元素本身并未交換，swap只是交換了兩個(gè)容器的內(nèi)部數(shù)據(jù)結(jié)構(gòu)。

　　元素不會(huì)被移動(dòng)的事實(shí)意味著，除string外，指向容器的迭代器、引用和指針在swap操作都不會(huì)失效。他們?nèi)匀恢赶虿僮髦八赶虻哪切┰亍５?#xff0c;在swap之后，這些元素已經(jīng)屬于不同的容器了。

　　對(duì)一個(gè)string調(diào)用swap會(huì)導(dǎo)致迭代器、引用和指針失效。

　　swap兩個(gè)array會(huì)真正交換它們的元素。因此，交換兩個(gè)array所需的時(shí)間與array中元素的數(shù)目成正比。

　　因此，對(duì)于array，在swap操作之后，指針、引用和迭代器所綁定的元素保持不變，但元素值已經(jīng)與另一個(gè)array中對(duì)應(yīng)元素的值進(jìn)行了交換。

?

5、關(guān)系運(yùn)算符

　　每個(gè)容器類型都支持相等運(yùn)算符（==和!=）；除了無(wú)序關(guān)聯(lián)容器外的所有容器都支持關(guān)系運(yùn)算符（>、>=、<、<=）。關(guān)系運(yùn)算符左右兩邊的運(yùn)算對(duì)象必須是相同類型的容器，且必須保存相同類型的元素。

　　比較兩個(gè)容器實(shí)際上是進(jìn)行元素的比較。這些運(yùn)算符的工作方式與string的關(guān)系運(yùn)算類似：

a、如果兩個(gè)容器具有相同大小且所有元素都兩兩對(duì)應(yīng)相等，則這兩個(gè)容器相等；否則兩個(gè)容器不等。

b、如果兩個(gè)容器大小不同，但較小容器中每個(gè)元素都等于較大容器中的對(duì)應(yīng)元素，則較小容器小于較大容器。

c、如果兩個(gè)容器都不是另一個(gè)容器的前綴子序列，則它們的比較結(jié)果取決于第一個(gè)不相等的元素的比較結(jié)果。

　　只有當(dāng)其元素類型也定義了相應(yīng)的比較運(yùn)算符時(shí)，我們才可以使用關(guān)系運(yùn)算符比較兩個(gè)容器。

　　容器的相等運(yùn)算實(shí)際上是使用元素的==運(yùn)算符實(shí)現(xiàn)比較的，而其他關(guān)系運(yùn)算符是使用元素的<運(yùn)算符。如果元素不支持所需運(yùn)算符，那么保存這種元素的容器就不能使用相應(yīng)的關(guān)系運(yùn)算。

轉(zhuǎn)載于:https://www.cnblogs.com/ACGame/p/10219585.html

總結(jié)

以上是生活随笔為你收集整理的顺序容器----顺序容器概述，容器库概览的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。