容器

類目：容器

描述

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

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

容器“擁有”它的元素：存儲在一個容器中的元素的壽命不能超過容器本身。[1]

完善

Assignable

相關(guān)類型

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

標(biāo)記法

X    容器模式對象
a,b  X類型對象
T    X類型的值

定義

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

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

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

有效表達(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á)式語義

名稱          表達(dá)式       前提    語義                                                         后置
拷貝構(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()            返回一個指向容器第一個元素的迭代器(iterator)。[7]            a.begin()要么是提領(lǐng)要么是past-the-end。僅僅當(dāng)a.size == 0的時候它才是past-the-end。
范圍結(jié)束      a.end()              返回一個指向容器的最后一個元素的后面的迭代器(iterator)。     a.end 是 past-the-end。
大小          a.size()             返回容器的大小，也就是元素的個數(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ù)。

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

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

不變量

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

模型

vector

注釋

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

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

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

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

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

[6]跟[5]中的引用類型一樣，指針類型需要與C++指針有相同的語義，但實際并不是C++指針。“智能指針”不同于“智能引用”是有可能的。因為可以為用戶定義類型來定義的引用操作符和指針成員訪問運(yùn)算符可以訪問運(yùn)算符*和->。

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

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

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

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

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

參見

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