Iterators
class MyContainer{
public:
const int* array;
int size;
class Iterator{
const int *obj;
public:
Iterator(const int* obj):obj(obj){
}
bool operator !=(Iterator other){
cout<<"call != \n";
if(other.obj==this->obj)
return false;
return true;
}
Iterator operator++(){
obj++;
cout<<"call ++ \n";
return *this;
}
const int& operator*()const {
cout<<"call * \n";
return *obj;
}
};
template <int i>
MyContainer(int const (&obj)[i]):array(obj),size(i){
}
Iterator begin(){
MyContainer::Iterator iterator(this->array);
cout<<"call begin\n";
return iterator;
}
Iterator end() {
MyContainer::Iterator iterator(this->array+size);
cout << "call begin\n";
return iterator;
}
};
int main(int argc,char* argv[]){
MyContainer mc({1,2,3,4,5,6});
for(const auto& vv:mc){
cout<<vv<<endl;
}
return 0;
}simple forward iterator and the result is
call begin
call !=
call *
1
call ++
call !=
call *
2
call ++
call !=
call *
3
call ++
call !=
call *
4
call ++
call !=
call *
5
call ++
call !=
call *
6
call ++
call !=
| Iterator category | Properties | Container |
|---|---|---|
| Forward iterator | ++It, It++, *It | unordered associative container |
It == It2, It != It2 | std::forward_list | |
| Bidirectional iterator | --It, It-- | ordered associative container |
std::list | ||
| Random access iterator | It[i] | std::array |
It+= n, It-= n | std::vector | |
It+n, It-n | std::deque | |
n+It | std::string | |
It-It2 | ||
It < It2, It <= It2, It > It2 | ||
It >= It2 |
| Global function | Description |
|---|---|
std::begin(cont) | Returns a begin iterator to the container cont. |
std::end(cont) | Returns an end iterator to the container cont. |
std::rbegin(cont) | Returns a reverse begin iterator to the container cont. |
std::rend(cont) | Returns a reverse end iterator to the container cont. |
std::cbegin(cont) | Returns a constant begin iterator to the container cont. |
std::cend(cont) | Returns a constant end iterator to the container cont. |
std::crbegin(cont) | Returns a reverse constant begin iterator to the container cont. |
std::crend(cont) | Returns a reverse constant end iterator to the container cont. |
std::prev(it) | Returns an iterator, which points to a position before it |
std::next(it) | Returns an iterator, which points to a position after it. |
std::distance(fir, sec) | Returns the number of elements between fir and sec. |
std::advance(it, n) | Puts the iterator it n positions further. |
// iteratorUtilities.cpp
...
#include <iterator>
...
using std::cout;
std::unordered_map<std::string, int> myMap{{"Rainer", 1966}, {"Beatrix", 1966},
{"Juliette", 1997}, {"Marius", 1999}};
for (auto m: myMap) cout << "{" << m.first << "," << m.second << "} ";
// {Juliette,1997},{Marius,1999},{Beatrix,1966},{Rainer,1966}
auto mapItBegin= std::begin(myMap);
cout << mapItBegin->first << " " << mapItBegin->second; // Juliette 1997
auto mapIt= std::next(mapItBegin);
cout << mapIt->first << " " << mapIt->second; // Marius 1999
cout << std::distance(mapItBegin, mapIt); // 1
std::array<int, 10> myArr{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
for (auto a: myArr) std::cout << a << " "; // 0 1 2 3 4 5 6 7 8 9
auto arrItEnd= std::end(myArr);
auto arrIt= std::prev(arrItEnd);
cout << *arrIt << std::endl; // 9
std::advance(arrIt, -5);
cout << *arrIt; // 4
Containers
The table shows you the constructors and destructors of a container. A std:vector stands for the rest of them.
| Type | Example |
|---|---|
| Default | std::vector<int> vec1 |
| Range | std::vector<int> vec2(vec1.begin(), vec1.end()) |
| Copy | std::vector<int> vec3(vec2) |
| Copy | std::vector<int> vec3= vec2 |
| Move | std::vector<int> vec4(std::move(vec3)) |
| Move | std::vector<int> vec4= std::move(vec3) |
| Sequence (Initializer list) | std::vector<int> vec5 {1, 2, 3, 4, 5} |
| Sequence (Initializer list) | std::vector<int> vec5= {1, 2, 3, 4, 5} |
| Destructor | vec5.~vector() |
| Delete elements | vec5.clear() |
Because std::array is generated at compile time, there are a few things that are special. std::array has no move constructor and can neither be created with a range nor with an initialiser list. However, you can initialize a std::array with an aggregate initialisation. Also, std::array has no method for removing its elements.
#include <map>
#include <unordered_map>
#include <vector>
...
using namespace std;
vector<int> vec= {1, 2, 3, 4, 5, 6, 7, 8, 9};
map<string, int> m= {{"bart", 12345}, {"jenne", 34929}, {"huber", 840284} };
unordered_map<string, int> um{m.begin(), m.end()};
for (auto v: vec) cout << v << " "; // 1 2 3 4 5 6 7 8 9
for (auto p: m) cout << p.first << "," << p.second << " ";
// bart,12345 huber,840284 jenne,34929
for (auto p: um) cout << p.first << "," << p.second << " ";
// bart,12345 jenne,34929 huber,840284
vector<int> vec2= vec;
cout << vec.size() << endl; // 9
cout << vec2.size() << endl; // 9
vector<int> vec3= move(vec);
cout << vec.size() << endl; // 0
cout << vec3.size() << endl; // 9
vec3.clear();
cout << vec3.size() << endl; // 0size+empty+max_size
#include <map>
#include <set>
#include <vector>
...
using namespace std;
vector<int> intVec{1, 2, 3, 4, 5, 6, 7, 8, 9};
map<string, int> str2Int = {{"bart", 12345},
{"jenne", 34929}, {"huber", 840284}};
set<double> douSet{3.14, 2.5};
cout << intVec.empty() << endl; // false
cout << str2Int.empty() << endl; // false
cout << douSet.empty() << endl; // false
cout << intVec.size() << endl; // 9
cout << str2Int.size() << endl; // 3
cout << douSet.size() << endl; // 2
cout << intVec.max_size() << endl; // 4611686018427387903
cout << str2Int.max_size() << endl; // 384307168202282325
cout << douSet.max_size() << endl; // 461168601842738790std::copy
template<class InputIterator, class OutputIterator>
OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result)
{
while (first!=last) {
*result = *first;
++result; ++first;
}
return result;
}access
| Iterator | Description |
|---|---|
cont.begin() and cont.end() | Pair of iterators to iterate forward. |
cont.cbegin() and cont.cend() | Pair of iterators to iterate const forward. |
cont.rbegin() and cont.rend() | Pair of iterators to iterate backward. |
cont.crbegin() and cont.crend() | Pair of iterators to iterate const backward. |
assign new elements
You can assign new elements to existing containers or swap two containers. For the assignment of a container cont2 to a container cont, there exists the copy assignment cont= cont2 and the move assignment cont= std::move(cont2). A special form of assignment is the one with an initialiser list: cont= {1, 2, 3, 4, 5}. That’s not possible for std::array, but you can instead use the aggregate initialisation. The function swap exists in two forms. You have it as a method cont(swap(cont2)) or as a function template std::swap(cont, cont2).
comparison operators
Containers support the comparison operators ==, !=, <, >, <=, >=. The comparison of two containers happens on the elements of the containers. If you compare associative containers, their key is compared. Unordered associative containers support only the comparison operator == and !=.
Sequential Container
| Criteria | array | vector | deque | list | forward_list |
|---|---|---|---|---|---|
| Size | static | dynamic | dynamic | dynamic | dynamic |
| Implementation | static array | dynamic array | sequence of arrays | doubled linked list | single linked list |
| Access | random | random | random | forward and backward | forward |
| Optimized for insert and delete at | end: O(1) | begin and end: O(1) | begin and end: O(1) | begin(1) | |
| arbitrary: O(1) | arbitrary: O(1) | ||||
| Memory reservation | yes | no | no | no | |
| Release of memory | shrink_to_fit | shrink_to_fit | always | always | |
| Strength | no memory allocation; minimal memory requirements | 95% solution | insertion and deletion at the begin and end | insertion and deletion at an arbitrary position | fast insertion and deletion; minimal memory requirements |
| Weakness | no dynamic memory | Insertion and deletion | Insertion and deletion | no random access | no random access |
| memory allocation | at an arbitrary position: O(n) | at an arbitrary position: O(n) |
std::vector is a homogeneous container, for which it’s length can be adjusted at runtime. std::vector needs the header <vector>. As it stores its elements contiguously in memory, std::vector support pointer arithmetic.
std::deque, which consists of a sequence of arrays, is quite similar to std::vector. std::deque need the header <deque>. The std::deque has three additional methods deq.push_front(elem), deq.pop_front() and `deq.emplace_front(args… ) to add or remove elements at its beginning.
std::list is a doubled linked list. std::list needs the header <list>.
Although it has a similar interface to std::vector or std::deque, std::list is quite different to both of them. That’s due to its structure.
Associative Container
| Associative container | Sorted | Associated value | More identical keys | Access time |
|---|---|---|---|---|
std::set | yes | no | no | logarithmic |
std::unordered_set | no | no | no | constant |
std::map | yes | yes | no | logarithmic |
std::unordered_map | no | yes | no | constant |
std::multiset | yes | no | yes | logarithmic |
std::unordered_multiset | no | no | yes | constant |
std::multimap | yes | yes | yes | logarithmic |
std::unordered_multimap | no | yes | yes | constant |
Adaptors for Containers
stack
...
#include <stack>
...
std::stack<int> myStack;
std::cout << myStack.empty() << std::endl; // true
std::cout << myStack.size() << std::endl; // 0
myStack.push(1);
myStack.push(2);
myStack.push(3);
std::cout << myStack.top() << std::endl; // 3
while (!myStack.empty()){
std::cout << myStack.top() << " ";
myStack.pop();
} // 3 2 1
std::cout << myStack.empty() << std::endl; // true
std::cout << myStack.size() << std::endl; // 0queue
...
#include <queue>
...
std::queue<int> myQueue;
std::cout << myQueue.empty() << std::endl; // true
std::cout << myQueue.size() << std::endl; // 0
myQueue.push(1);
myQueue.push(2);
myQueue.push(3);
std::cout << myQueue.back() << std::endl; // 3
std::cout << myQueue.front() << std::endl; // 1
while (!myQueue.empty()){
std::cout << myQueue.back() << " ";
std::cout << myQueue.front() << " : ";
myQueue.pop();
} // 3 1 : 3 2 : 3 3
std::cout << myQueue.empty() << std::endl; // true
std::cout << myQueue.size() << std::endl; // 0#include <queue>
...
std::priority_queue<int> myPriorityQueue;
std::cout << myPriorityQueue.empty() << std::endl; // true
std::cout << myPriorityQueue.size() << std::endl; // 0
myPriorityQueue.push(3);
myPriorityQueue.push(1);
myPriorityQueue.push(2);
std::cout << myPriorityQueue.top() << std::endl; // 3
while (!myPriorityQueue.empty()){
std::cout << myPriorityQueue.top() << " ";
myPriorityQueue.pop();
} // 3 2 1
std::cout << myPriorityQueue.empty() << std::endl; // true
std::cout << myPriorityQueue.size() << std::endl; // 0
std::priority_queue<std::string, std::vector<std::string>,
std::greater<std::string>> myPriorityQueue2;
myPriorityQueue2.push("Only");
myPriorityQueue2.push("for");
myPriorityQueue2.push("testing");
myPriorityQueue2.push("purpose");
myPriorityQueue2.push(".");
while (!myPriorityQueue2.empty()){
std::cout << myPriorityQueue2.top() << " ";
myPriorityQueue2.pop();
} // . Only for purpose testingback_inserter + front_inserter + inserter
#include <iterator>
...
std::deque<int> deq{5, 6, 7, 10, 11, 12};
std::vector<int> vec{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
std::copy(std::find(vec.begin(), vec.end(), 13),
vec.end(), std::back_inserter(deq));
for (auto d: deq) std::cout << d << " ";
// 5 6 7 10 11 12 13 14 15
std::copy(std::find(vec.begin(), vec.end(), 8),
std::find(vec.begin(), vec.end(), 10),
std::inserter(deq,
std::find(deq.begin(), deq.end(), 10)));d
for (auto d: deq) std::cout << d << " ";
// 5 6 7 8 9 10 11 12 13 14 15
std::copy(vec.rbegin()+11, vec.rend(),
std::front_inserter(deq));
for (auto d: deq) std::cout << d << " ";
// 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15