container.at(2) is same as container[2], but at(2) can throw range_error if it is out of range.
empty(), size(), clear(), swap(), copy constr - are some common methods for all containers.
Sequential Containers - dynamic array
[] -> subscript operator
Vector - dynamic array, one sided (push_back only)
Fast remove and insert only at the end of the array (append).
Search, delete, insert at non terminal location is linear time.
Deque - dynamic array, two sided (push_front and push_back)
Fast remove and insert only at the end or start of the array (append).
Search, delete, insert at non terminal location is linear time.
list - linked list (bi-directional)
Fast insert and remove at any place.
Search is linear. But because of non contiguous memory location, it is slower than vector.
special function - splice - cut a range of data from mylist2 and insert into mylist1 very easily with constant time complexity.
mylist1.splice(itr, mylist2.begin(), mylist.end());
container array - array
array a = {3,4,5};
Associative Containers - Binary tree - always sorted, insert at proper location all the time (that's why its not editable(key non editable in case of maps)).
Find is very fast - log(n)
Traversing is slow (compared to vector and deque)
No random access, no [] operator like vector or array
set - unique (a map of key = value) - has '<' operator default overloaded.
multiset - dupes allowed.
map - unique - (mostly implemented as a red black tree)
multimap - dupes allowed
C++11 introduced Unordered Container - hashmaps - most of the operations are O(1).
unordered_set
unordered_map
empty(), size(), clear(), swap(), copy constr - are some common methods for all containers.
Sequential Containers - dynamic array
[] -> subscript operator
Vector - dynamic array, one sided (push_back only)
Fast remove and insert only at the end of the array (append).
Search, delete, insert at non terminal location is linear time.
Deque - dynamic array, two sided (push_front and push_back)
Fast remove and insert only at the end or start of the array (append).
Search, delete, insert at non terminal location is linear time.
Fast insert and remove at any place.
Search is linear. But because of non contiguous memory location, it is slower than vector.
special function - splice - cut a range of data from mylist2 and insert into mylist1 very easily with constant time complexity.
mylist1.splice(itr, mylist2.begin(), mylist.end());
container array - array
array
Associative Containers - Binary tree - always sorted, insert at proper location all the time (that's why its not editable(key non editable in case of maps)).
Find is very fast - log(n)
Traversing is slow (compared to vector and deque)
No random access, no [] operator like vector or array
set - unique (a map of key = value) - has '<' operator default overloaded.
multiset - dupes allowed.
map - unique - (mostly implemented as a red black tree)
multimap - dupes allowed
C++11 introduced Unordered Container - hashmaps - most of the operations are O(1).
unordered_set
unordered_map
Internally implemented as hashtable, array of linked list
Arrays is also called array of buckets and link list is called entries
Each element has a hashvalue, and based on that value its inserted in its own place in entries.
Hash collision - performance degrade
Hash collision occurs when most elements are in the same linked list (entry).
If it degrades, it goes to linear time; so if your business logic has chances of degrading the hash, better go for map, which guarantees log(n) at all times.
No comments:
Post a Comment