04 C++: C++ STL
Algorithm vs member function
container member function vs algorithm
Any duplicated? Yes! But different.
List:
remove, unique, sort, merge, reverse
Associative:
count, find, lower_bound, upper_bound, equal_range
Unordered:
count, find, equal_range
Difference:
unordered_set.find() amortized constant time but std::find(t.begin(), t.end(), 1) linear time because no knowledge but iteratively.
map.find() log n time but std::find(m.begin(), m.end(), pair(first, second)) take linear time and moreover it compare not only first but also second that makes double penalty.
list.remove(1) and remove(l.begin(), l.end(), 1) looks same linear time but
list.remove() is faster because removal uses redirecting the removed node pointers while std::remove() copy the elements behinds the removed node one by one as if the operation done on vector.
list.remove() reduce the size by 1 but i = std::remove() leaves the last element duplicated so needs extra l.erase(i, s.end());
list.sort() works but sort(l.begin(), l.end()) does not work because require random access iterator but list only has bidirectional iterator
Container member function preferred
Reverse Iterator
vector<int>::reverse_iterator r; r.rbegin();
Iterator can be converted to reverse iterator but in the opposite direction need to assign r.base() to iterator. r.base() return current iterator, where current iterator is the normal iterator off by one to the reverse iterator.
Vector insert erase invalidates all iterators and references to the vector
Equality vs equivalence
std::find(s.begin(), s.end(), 36) uses equality of equal operator, where set::find() uses equivalence !(x<y)&&!(y<x) .
Equality algo, use ==, no sort, list, vec
search, find_end, find_first_of, adjacent_search
Equivalence algo, use <, need sort, asso
binary_search, includes, lower_bound, upper_bound
STL removal
How to remove 1 from sequential vector v?
- Slow log(mn):
for (auto i=v.begin(); i!=v.end(); ) {
if (*i==1) i=v.erase(i); else ++i; }
- Wrong: remove(v.begin(), v.end(), 1);
- Correct log(n)
auto i =remove(v.begin(), v.end(), 1);
v.erase(i, v.end());
v.shrink_to_fit(); // or
vector<int>(c).swap(c);
Also called erase remove idiom
How to remove 1 from sequential list l?
- Slow by copy:
auto i = remove(l.begin(), l.end(), 1);
l.erase(i, l.end());
- Fast by reassigning pointers:
c.remove(1);
How to remove 1 from associative set?
- Slow by copy linear time:
auto i = remove(s.begin(), c.end(), 1);
c.erase(i, s.end());
- Fast by value log(n):
c.erase(1);
vector/deque: algorithm remove erase
list: member function remove
map: member function erase
STL iterator invalidation
For multiset s, simple for loop if *i equal 1 then s.erase(i) will crash because iterator i is invalidated after erase and so subsequent iterator compaison with c.end() will crash, as well as all containers after erase, so solution is to use s.erase(i++) if *i==1 so that iterator i will advance after erase and is valid because iterator after the erased element are still valid due to the tree structure of set.
For vector, v.erase(i++) does not work because after removal the iterator i pointing to the rest elements after erased one are all invalidated, and so the pointer, and so solution is i = v.erase(i)
How to use remove_if for vector?
bool equal(int i, int v) {return i==v;}
v.erase(remove_if(v.begin(), v.end(), bind(equal, placeholders::_1, 99)), v.end());
Or use lamba [](int i){return i==v;}
vector vs deque
Vector capacity grows exponentially 1248163264 for factor 2, some factor 1.5. Drawback is difficult contiguous memory reallocation when memory fragmented, along with data copying with expensive construction and destruction.
vector<C> v(6);// call default ctor 6 times
v.resize(7); // also call default ctor once
v.reserve(1000); // no ctor, good prior knowledge
if size is unknown then
v.reserve(as much);
v.shrink_to_fit();
vector<C>(c).swap(c);
Deque grows linearly with fix size instead of exponential size, no reserve() no capacity(), no reallocation so data reside at original places when new memory allocated. Because of the linked block of memory, locality is lower compared to vector that require more cache misses and page faults.
When to deque or vector?
both push front and back then deque.
high performance then vector.
For user defined class, vector performance drops closer to deque because object construction and destruction dominates the performance hit
Vector contiguous memory allocation difficult because of memory size limited, data too much and memory fragmented.
If data size completely unpredictable then use deque.
Vector push_back may cause memory reallocation and hence all pointers/references/iterators (pri) are all invalidated while deque push_back and push_front will not invalidate pri but note that deque insert at middle will invalidate pri.
Vector can be considered as raw array by using &v[0] except vector<bool> because vector of bool is optimized to store a bool in a bit instead of a byte and so the address of first element is not a pointer to bool but pointer to char.
Object slicing
vector<P> v{C()};
v[0].m(); // call P.m() not C.m()
Object of C is parameter and copy constructed as P and store in vector v, also called object slicing.
P p=C(); // also object slicing
