容器

類目：容器

描述

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

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

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

完善

Assignable

相關類型

(Value type)值類型  X::value_type  存儲在容器中的對象類型。值類型必須是Assignable，但不必是DefaultConstructible.[2]
(Iterator type)迭代器類型 X::iterator  迭代器類型用來遍歷容器的元素。迭代器的值類型就是容器的值類型。必須可以從iterator type轉換成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  一個有符號整數類型來表示兩個容器迭代器之間的距離。此類型必須跟迭代器之間的距離類型是一樣的。[2]
(Size type)大小類型 X::size_type 一個無符號整數類型來表示任何非負值的容器距離類型。[2]

標記法

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

定義

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

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

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

有效表達式

除了Assignable,EqualityComparable,和LessThanComparable這些已經定義的表達式，下面的表達式也必須是有效的。

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

表達式語義

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

復雜性擔保

拷貝構造函數，復制操作符，析構函數跟容器大小呈線性關系。

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

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

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

不變量

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

模型

vector

注釋

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

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

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

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

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

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

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

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

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

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

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

參見

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