Standard Sequence Containers Sequence Containers Sequ.Containers
|
 fixed-size contiguous array |
|
dynamic contiguous array; amortized O(1) growth strategy; |
|
double-ended queue; fast insert/erase at both ends |
|
doubly-linked list; O(1) insert, erase & splicing; |
|
singly-linked list; O(1) insert, erase & splicing; needs less memory than |
Common
All standard sequence containers are regular types:
- deeply copyable: copying creates a new container object and copies all contained values
- deeply assignable: all contained objects are copied from source to assignment target
- deeply comparable: comparing two containers compares the contained objects
- deep ownership: destroying the container destroys all contained objects
std::vector<int> a {4,7,1,9};
std::vector<int> b {1,2,3};
bool equal1 = (a == b); // false
b = a; // copy assignment ⇒ b: - 4
- 7
- 1
- 9
bool equal2 = (a == b); // true
a[0] = 3; // a: - 3
- 7
- 1
- 9
b: - 4
- 7
- 1
- 9
bool equal3 = (a == b); // false
// different ways of making exact copies,
// i.e., copy-constructing new containers:
std::vector<int> a2 {a};
std::vector<int> a3 (a);
std::vector<int> a4 = a;
auto a5 {a};
auto a6 (a);
auto a7 = a;As of C++17 the element type can be deduced from constructor calls.
std::vector v {1, 2, 3, 4};
std::vector v {1.f, 2.3f, 4.5f};
std::vector v {1., 2.3, 4.6};
struct p2 { int x; int y; };
std::vector v {p2{1,2}};can be obtained from all standard sequence containers either with member functions:
container.begin()→ @first_elementcontainer.end()→ @one_behind_last_element
or with free-standing functions: C++11
std::begin(container)→ @first_elementstd::end(container)→ @one_behind_last_element
If you are not familiar with what iterators are, please refer to this article .
either with member function
container.empty()→ true, if container has no elements
or with free-standing function: C++11
std::empty(container)→ true, if container has no elements
container::value_typecontainer::size_typecontainer::iteratorcontainer::const_iterator
…
using con_t = std::vector<double>;
con_t::size_type i = 0; // std::size_t
auto x = con_t::value_type{0}; // doublearray
- overhead-free random access
- fast traversal; good for linear searches
sizehas to be a constant expression (= known at compile time)- does not support size-changing operations (resize, insert, erase, …)
- potentially slow if element type has high copy/assignment cost (reordering elements requires copying/moving them)
#include <array>
#include <iostream>
int main () {
std::array<int,6> a {4,8,15,16,23,42};
std::cout << a.size() << '\n'; // 6
std::cout << a[0] << '\n'; // 4
std::cout << a[3] << '\n'; // 16
std::cout << a.front() << '\n'; // 4
std::cout << a.back() << '\n'; // 42
std::array<int,3> b {7,8,9};
// a = b; // COMPILER ERROR: types don't match!
}
STACK
| 42 |
| 23 |
| 16 |
| 15 |
| 8 |
| 4 |
| … |
vector
C++'s default
container
- overhead-free random access
- fast traversal; good for linear searches
- insertion at the end in amortized constant time
- potentially slow if insert/erase operations at front and/or random positions dominate
- potentially slow if element type has high copy/assignment cost (reordering elements requires copying/moving them)
- all operations that can change capacity (insert, push_back, …) may invalidate references/pointers to any vector element
- potentially long allocation times for very large amount of values (can be mitigated, see here )
(click for fullscreen view)
deque
Double Ended Queue
- constant-time random access (extremely small overhead)
- fast traversal; good for linear searches
- good insertion and deletion performance at both ends
- insertion does not invalidate references/pointers to elements
- potentially slow if insert/erase operations at random positions dominate
- potentially slow if element type has high copy/assignment cost (reordering elements requires copying/moving them)
- potentially long allocation times for very large amount of values (can be mitigated, see here )
#include <deque>
std::deque<int> d {0, 0, 0};
d.push_back(1);
d.push_front(2);
vector<int> v {3, 4, 5, 6};
d.insert(begin(d),
begin(v), end(v));
d.pop_front();
d.erase(begin(d)+2, begin(d)+5);
- 0
- 0
- 0
- 0
- 0
- 0
- 1
- 2
- 0
- 0
- 0
- 1
v: - 3
- 4
- 5
- 6
⇒
d: - 3
- 4
- 5
- 6
- 2
- 0
- 0
- 0
- 1
- 4
- 5
- 6
- 2
- 0
- 0
- 0
- 1
- 4
- 5
- 6
- 2
- 0
- 0
- 0
- 1
⇒ - 4
- 5
- 0
- 0
- 1
(click for fullscreen view)
list
Doubly-linked List
- restructuring operations don't require elements to be moved/copied (good for storing large objects with high copy/assignment cost)
- constant-time splicing (of complete lists)
- random access only in linear time
- slow traversal due to bad memory locality
#include <list>
std::list<int> l {3};
l.push_back(2);
l.push_front(4);
l.splice(begin(l)+1,
list<int>{8, 4, 7});
l.reverse();
l.sort();
l.unique();
3
3 ⇄ 2
4 ⇄ 3 ⇄ 2
4 ⇄ 8 ⇄ 4 ⇄ 7 ⇄ 3 ⇄ 2
2 ⇄ 3 ⇄ 8 ⇄ 4 ⇄ 7 ⇄ 4
2 ⇄ 3 ⇄ 4 ⇄ 4 ⇄ 7 ⇄ 8
2 ⇄ 3 ⇄ 4 ⇄ 7⇄ 8
(click for fullscreen view)
forward_list
Singly-linked List
- uses less memory than
list - restructuring operations don't require elements to be moved/copied (good for storing large objects with high copy/assignment cost)
- constant-time splicing (of complete lists)
- random access only in linear time
- slow traversal due to bad memory locality
- only forward traversal possible
- somewhat cumbersome interface due to forward-only links
- no:
size(),back(),push_back(),pop_back(),insert() - instead:
insert_after(),splice_after(),before_begin()
- no:
#include <forward_list>
std::forward_list<int> l {23,42,4};
l.insert_after(begin(l), 5);
l.insert_after( before_begin(l), 88);
l.erase_after(begin(l));
23 → 42 → 4
23 → 5 → 42 → 4
88 → 23 → 5 → 42 → 4
88 → 5 → 42 → 4
(click for fullscreen view)
