容器

類目：容器

描述

容器是一個(gè)可以存儲(chǔ)對(duì)象（它的元素），并具有訪問(wèn)其元素的方法的一個(gè)對(duì)象。特別是，每一個(gè)容器模式類型都有一個(gè)關(guān)聯(lián)的迭代器類型來(lái)遍歷容器中的元素。

不能保證容器中的元素按特定的方式來(lái)存儲(chǔ)；事實(shí)上，不同的是每次迭代器是如何通過(guò)容器的。也不能保證容器的多個(gè)迭代器是一直有效的。（特定的容器類型，像前向容器是提供這樣的保證的。）

容器“擁有”它的元素：存儲(chǔ)在一個(gè)容器中的元素的壽命不能超過(guò)容器本身。[1]

完善

Assignable

相關(guān)類型

(Value type)值類型  X::value_type  存儲(chǔ)在容器中的對(duì)象類型。值類型必須是Assignable，但不必是DefaultConstructible.[2]
(Iterator type)迭代器類型 X::iterator  迭代器類型用來(lái)遍歷容器的元素。迭代器的值類型就是容器的值類型。必須可以從iterator type轉(zhuǎn)換成const iterator type。迭代器的類型必須是一個(gè)輸入迭代器。[3]
(Const iterator type)常量迭代器類型 X::const_iterator 是一個(gè)可以查看但不能修改容器中元素的迭代器類型。[3][4]
(Reference type)引用類型 X::reference 是一個(gè)行為像容器值類型引用的類型。[5]
(Const reference type)常量引用類型 X::const_reference 是一個(gè)行為像容器值類型常量引用的類型。[5]
(Pointer type)指針類型 X::pointer 是一個(gè)行為像容器值類型指針的類型。[6]
(Distance type)距離類型 X::distance_type  一個(gè)有符號(hào)整數(shù)類型來(lái)表示兩個(gè)容器迭代器之間的距離。此類型必須跟迭代器之間的距離類型是一樣的。[2]
(Size type)大小類型 X::size_type 一個(gè)無(wú)符號(hào)整數(shù)類型來(lái)表示任何非負(fù)值的容器距離類型。[2]

標(biāo)記法

X    容器模式對(duì)象
a,b  X類型對(duì)象
T    X類型的值

定義

容器的(size)大小就是它所包含的元素個(gè)數(shù)，它是一個(gè)非負(fù)數(shù)。

容器的(area)面積就是它占用的字節(jié)數(shù)。更確切地說(shuō)，它是元素的面積的總和加上與容器本身相關(guān)的任何開(kāi)銷。如果容器的值類型T是一個(gè)簡(jiǎn)單的類型（而不是一個(gè)容器類型），那么這個(gè)容器的面積就是sizeof(T)的常數(shù)倍。也就是說(shuō)，一個(gè)簡(jiǎn)單值類型的容器a的面積是O(a.size())。

一個(gè)(variable sized)可變大小的容器提供插入和/或移除元素的方法；容器大小可能會(huì)變化。一個(gè)(fixed size)固定大小的容器，它的大小在它的生命周期內(nèi)是一只不變的。一些固定大小的容器類型，大小在編譯時(shí)確定。

有效表達(dá)式

除了Assignable,EqualityComparable,和LessThanComparable這些已經(jīng)定義的表達(dá)式，下面的表達(dá)式也必須是有效的。

名稱      表達(dá)式         類型要求    返回類型
范圍起始  a.begin()                  如果是可變的，返回值為iterator(迭代器)，否則為const_iterator[4][7]
范圍結(jié)束  a.end()                    如果是可變的，返回值為iterator(迭代器)，否則為const_iterator[4]
大小      a.size()                   size_type
最大容量  a.max_size()               size_type
空容器    a.empty()                  可轉(zhuǎn)換成bool類型
交換      a.swap(b)                  void

表達(dá)式語(yǔ)義

名稱          表達(dá)式       前提    語(yǔ)義                                                         后置
拷貝構(gòu)造函數(shù)  X(a)                                                                              X().size() == a.size()。X()包含了a中所有元素的副本。
拷貝構(gòu)造函數(shù)  X b(a)                                                                            b().size() == a.size()。b包含了a中所有元素的副本。
賦值運(yùn)算符    b = a                                                                             b().size() == a.size()。b包含了a中所有元素的副本。
析構(gòu)函數(shù)      a.~X()               銷毀a中所有的元素，并釋放為它們分配的內(nèi)存（如果有的話）。
范圍起始      a.begin()            返回一個(gè)指向容器第一個(gè)元素的迭代器(iterator)。[7]            a.begin()要么是提領(lǐng)要么是past-the-end。僅僅當(dāng)a.size == 0的時(shí)候它才是past-the-end。
范圍結(jié)束      a.end()              返回一個(gè)指向容器的最后一個(gè)元素的后面的迭代器(iterator)。     a.end 是 past-the-end。
大小          a.size()             返回容器的大小，也就是元素的個(gè)數(shù)。[8]                        a.size() >= 0 && a.size <= a.max_size()
最大容量      a.max_size()         返回容器的最大容量。[8]                                      a.max_size() >= 0 && a.max_size >= a.size()
空容器        a.empty()            相當(dāng)于 a.size() == 0 （但是可能更快）                        
交換          a.swap(b)            相當(dāng)于swap(a,b)[9]

復(fù)雜性擔(dān)保

拷貝構(gòu)造函數(shù)，復(fù)制操作符，析構(gòu)函數(shù)跟容器大小呈線性關(guān)系。

begin()和end()的攤銷時(shí)間為常數(shù)。

size()跟容器大小呈線性關(guān)系。[10] max_size()和empty()的攤銷時(shí)間為常數(shù)。如果你要測(cè)試一個(gè)容器是否為空，你應(yīng)該總是寫c.empty而不是c.size() == 0。這兩個(gè)表達(dá)式是等價(jià)的，但前者可能要快得多。

swap()的攤銷時(shí)間為常數(shù)。[9]

不變量

有效范圍     任何容器a， [a.begin(), a.end())是一個(gè)有效范圍。[11]
范圍大小     a.size()等于從a.begin()到a.end()的距離。
完整性       一個(gè)迭代算法[a.begin(), a.end())，將會(huì)遍歷a中的每個(gè)元素。[11]

模型

vector

注釋

[1]元素的壽命不能超過(guò)其容器可能看起來(lái)像一個(gè)嚴(yán)重的限制，事實(shí)上，它并不是限制。請(qǐng)注意指針和迭代器都是對(duì)象；就像任何其他對(duì)象一樣，他們可以被存儲(chǔ)在一個(gè)容器內(nèi)。在這種情況下，容器擁有指針本身，而不是它們指向的對(duì)象。

[2]這種表達(dá)式必須是一個(gè)typedef，這是一個(gè)類型的代名詞。

[3]這可能是一個(gè)typedef或者其他類型，或者一個(gè)定義嵌套類作為一個(gè)內(nèi)部類的X的特定的類型。

[4]容器的iterator類型和const iterator類型可能是一樣的：不能保證每個(gè)容器必須有一個(gè)相關(guān)的可變迭代器類型。例如，set和hash_set定義iterator和const iterator為同一類型。

[5]引用類型需要與普通C++引用類型有相同的語(yǔ)義，但它實(shí)際上并不是普通的C++引用。例如，在某些實(shí)現(xiàn)中，可能會(huì)提供額外的引用類型來(lái)支持非標(biāo)準(zhǔn)的內(nèi)存模型。但是請(qǐng)注意，“智能引用”（用戶定義的引用類型提供額外的功能）不是一個(gè)可行的選擇。用戶定義的類型不可能與C++引用類型具有相同語(yǔ)義，因?yàn)镃++語(yǔ)言不支持重新定義的成員訪問(wèn)運(yùn)算符(operator.)。

[6]跟[5]中的引用類型一樣，指針類型需要與C++指針有相同的語(yǔ)義，但實(shí)際并不是C++指針。“智能指針”不同于“智能引用”是有可能的。因?yàn)榭梢詾橛脩舳x類型來(lái)定義的引用操作符和指針成員訪問(wèn)運(yùn)算符可以訪問(wèn)運(yùn)算符*和->。

[7]迭代器類型(iterator type)必須是一個(gè)輸入迭代器(input iterator)，它只提供了一個(gè)非常薄弱的擔(dān)保；特別是，輸入迭代算法必須都是“單通道”。容器只有一個(gè)簡(jiǎn)單的迭代器(iterator)可以隨時(shí)激活。Forward Container(前向容器)沒(méi)有這個(gè)限制。

[8]一個(gè)固定大小的容器，size() == max_size()。

[9]對(duì)于任何Assignable類型，swap可以定義分配條款。這需要三個(gè)任務(wù)，每一個(gè)容器類型，容器的大小呈線性關(guān)系。然而，在某種意義上，a.swap(b)是多余的。它的存在僅僅為了提高效率：許多容器，如vector和list，它實(shí)現(xiàn)swap的時(shí)間復(fù)雜度是不變的，而不是線性的。一些容器類型X，那么它們的模板化swap(X&,X&)可以簡(jiǎn)單地寫在X::swap(X&)。也就是說(shuō)X::swap(X&)只能定義在執(zhí)行時(shí)間是常量的情況下。不是所有的容器類X都需要這樣的一個(gè)成員函數(shù)，但是如果這樣的函數(shù)存在，那么必須保證攤銷時(shí)間為常量。

[10]對(duì)于許多容器，如vector和deque，size是O(1).這滿足了O(N)的要求。

[11]雖然[a.begin(), a.end())必須是一個(gè)有效的范圍，而且每個(gè)元素必須都包含在容器內(nèi)，但是在這個(gè)范圍內(nèi)出現(xiàn)的順序是不確定的。如果你兩次遍歷一個(gè)容器，它不能保證這兩次的遍歷順序是相同的。Forward Container前向容器沒(méi)有這個(gè)限制。

參見(jiàn)

迭代器概述，輸入迭代器，序列