Anscheinend 😉 bieten die Standardcontainer eine Art Garantie.
Welche Art von Garantien und was genau sind die Unterschiede zwischen den verschiedenen Containertypen?
Arbeiten von die SGI-Seite (Über STL) Mir ist folgendes eingefallen:
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)
Fang hier an: STL-Komplexitätsspezifikationen. Lesen Sie dann alle Containertypen auf dieser Website durch und sehen Sie sich die angegebenen Komplexitätsanforderungen an. Hoffe das hilft!
– Chris Jester-Young
8. Oktober 2008 um 7:42 Uhr
Kann ich eine Kopie Ihrer Arbeit haben, um sie in meiner Klasse zu studieren?
– Dzung Nguyen
7. Mai 2010 um 4:14 Uhr
@nXqd: siehe www.sgi.com/tech/stl
– Martin York
9. Mai 2010 um 17:13 Uhr
@MartinYork Dieser Link ist jetzt tot.
– Chani
23. März 2018 um 10:29 Uhr
john-ahlgren.blogspot.com/2013/10/… Schau doch einfach mal hier vorbei 🙂
– Schalomi90
20. November 2018 um 14:27 Uhr