04 C++: C++ STL

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?

1. Slow log(mn):

for (auto i=v.begin(); i!=v.end(); ) {

if (*i==1) i=v.erase(i); else ++i; }

1. Wrong: remove(v.begin(), v.end(), 1);
2. 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?

1. Slow by copy:

auto i = remove(l.begin(), l.end(), 1);

l.erase(i, l.end());

1. Fast by reassigning pointers:

c.remove(1);

How to remove 1 from associative set?

1. Slow by copy linear time:

auto i = remove(s.begin(), c.end(), 1);

c.erase(i, s.end());

1. 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