标准容器的复杂度保证是什么？

Question

显然;-)，标准容器提供某种形式的保证。

什么类型的保证以及不同类型的容器之间的区别是什么？

从SGI页面（关于STL）开始工作，我得出了以下结论：

Container Types:
================
Container:
    Forward Container
        Reverse Container
            Random Access Container
    Sequence
        Front Insert Sequence
        Back  Insert Sequence
    Associative Container
        Simple   Associative Container
        Pair     Associative Container
        Sorted   Associative Container
        Multiple Associative Container

Container Types mapped to Standard Containers
=============================================

std::vector:    Sequence    Back        Sequence                    Forward/Reverse/Random Container
std::deque:     Sequence    Front/Back  Sequence                    Forward/Reverse/Random Container
std::list:      Sequence    Front/Back  Sequence                    Forward/Reverse Container
std::set:       Sorted/Simple/Unique    Associative Container       Forward Container
std::map:       Sorted/Pair/Unique      Associative Container       Forward Container
std::multiset:  Sorted/Simple/Multiple  Associative Container       Forward Container
std::multimap:  Sorted/Pair/Multiple    Associative Container       Forward Container


Container Guarantees:
=====================

                                                                                  Simp
                                                                                  or
                          For   Rev  Rand        Front  Back  Assoc        Sort   Mult
                    Cont: Cont: Cont Cont: Sequ: Sequ:  Sequ: Cont:        Cont:  Cont:
Copy    Const:      O(n)
Fill    Const:                             O(n)
begin()             O(1)
end()               O(1)
rbegin()                        O(1)
rend()                          O(1)
front()                                    O(1)
push_front()                                     O(1)
pop_front()                                      O(1)
push_back()                                             O(1)
pop_back()                                              O(1)
Insert()                                                                          O(ln(n))
Insert: fill                               O(n)
Insert: range                              O(n)                                   O(kln(n)+n)
size()              O(1)
swap()              O(1)
erase key                                                     O(ln(n))
erase element                                                 O(1)
erase range                                                   O(ln(n)+S)
count()                                                       O(log(n)+k)
find()                                                        O(ln(n))
equal range                                                   O(ln(n))
Lower Bound/Upper Bound                                                    O(ln(n))
Equality                  O(n)
InEquality                O(n)
Element Access                       O(1)

- Martin York

---

从这里开始：STL 复杂度规范。然后阅读该网站上所有的容器类型，并查看其所声明的复杂度要求。希望能对你有所帮助！ - C. K. Young

我可以拿一份你的代码来学习吗？ - Dzung Nguyen

@nXqd：请查看www.sgi.com/tech/stl。 - Martin York

@MartinYork 这个链接现在已经失效了。 - Chani

请看这里：http://john-ahlgren.blogspot.com/2013/10/stl-container-performance.html - Shalomi90

Answer 1

我找到了一个很好的资源Standard C++ Containers。这可能是你们都在寻找的。

向量

构造函数

vector<T> v;              Make an empty vector.                                     O(1)
vector<T> v(n);           Make a vector with N elements.                            O(n)
vector<T> v(n, value);    Make a vector with N elements, initialized to value.      O(n)
vector<T> v(begin, end);  Make a vector and copy the elements from begin to end.    O(n)

访问器

v[i]          Return (or set) the I'th element.                        O(1)
v.at(i)       Return (or set) the I'th element, with bounds checking.  O(1)
v.size()      Return current number of elements.                       O(1)
v.empty()     Return true if vector is empty.                          O(1)
v.begin()     Return random access iterator to start.                  O(1)
v.end()       Return random access iterator to end.                    O(1)
v.front()     Return the first element.                                O(1)
v.back()      Return the last element.                                 O(1)
v.capacity()  Return maximum number of elements.                       O(1)

修饰符

v.push_back(value)         Add value to end.                                                O(1) (amortized)
v.insert(iterator, value)  Insert value at the position indexed by iterator.                O(n)
v.pop_back()               Remove value from end.                                           O(1)
v.assign(begin, end)       Clear the container and copy in the elements from begin to end.  O(n)
v.erase(iterator)          Erase value indexed by iterator.                                 O(n)
v.erase(begin, end)        Erase the elements from begin to end.                            O(n)

对于其他容器，请参考该页面。

- Nayana Adassuriya

Answer 2

我不知道是否有一个单一的表格可以让你一目了然地比较它们（我甚至不确定这样的表格是否可行）。

当然，ISO标准文件详细列举了复杂性要求，有时以各种相当易读的表格形式，其他时候则以不太易读的特定方法的符号列表形式。

此外，在STL库参考http://www.cplusplus.com/reference/stl/中适当提供了复杂性要求。

- Mike B

---

cplusplus.com上的信息已经过时（有时也是错误的）。请将人们引用到https://en.cppreference.com/w/cpp/container/。每个容器的每种方法都列出了其强制复杂度。 - Dúthomhas

Answer 3

另外一个快速查找表可以在这个GitHub页面上找到。

注意：此表不考虑所有容器，例如unordered_map等，但仍然很好查看。它只是更清晰的this版本。

- iamakshatjain