# [AIdrifter CS 浮生筆錄](https://hackmd.io/s/rypeUnYSb) <br> C++ Standard Libraries(STL)

[TOC]

## Overview
- C++ Standard libraries
- C++ Standard Template libraries(subset)
- Object Origin Programming
- Combine Algorithms and Containers
- But each containers is different! how should we do that ?
- Iterrators
- give same interface for containers and algorithns
- Implement Algorithms via **iterators** !!
- N Alog * M Containers = M + N Implementations

- half-open : **[begin,end)**

// First Example:
using namespace std;

vector<int> vec;
vec.push_back(4);
vec.push_back(1);
vec.push_back(8);  // vec: {4, 1, 8}

vector<int>::iterator itr1 = vec.begin();  // half-open:  [begin, end)
vector<int>::iterator itr2 = vec.end();

for (vector<int>::iterator itr = itr1; itr!=itr2; ++itr)
   cout << *itr << " ";  // Print out:  4 1 8

sort(itr1, itr2);  // vec: {1, 4, 8}

## Reasons to use C++ standard libraries
- code reuse, no need to reinvent the wheel
- Efficiency (fast and use less resouces). Modern C++ compiler are usually tuned to optimize for C++ standard library code.
- Accurate, less buggy
- Terse, readable code ,reduced control flow
- Standardization, guaranteed availability
- A role model of writing library
- Good knowledge of data structures and algorithms

# Sequence Container

## STL Headers

#include <vector>
#include <deque>
#include <list>
#include <set>   // set and multiset
#include <map>   // map and multimap
#include <unordered_set>  // unordered set/multiset
#include <unordered_map>  // unordered map/multimap
#include <iterator>
#include <algorithm>
#include <numeric>    // some numeric algorithm
#include <functional>

## vector
* Properties:
* 1. fast insert/remove at the end: O(1)
* 2. slow insert/remove at the begining or in the middle: O(n)
* 3. slow search: O(n)

/*
 * Vector
 */
vector<int> vec;   // vec.size() == 0
vec.push_back(4);
vec.push_back(1);
vec.push_back(8);  // vec: {4, 1, 8};    vec.size() == 3

// Vector specific operations:
cout << vec[2];     // 8  (no range check)
cout << vec.at(2);  // 8  (throw range_error exception of out of range)

for (int i; i < vec.size(); i++) {
   cout << vec[i] << " ";

for (list<int>::iterator itr = vec.begin(); itr!= vec.end(); ++itr)
   cout << *itr << " ";  

for (it: vec)    // C++ 11
   cout << it << " ";

// Vector is a dynamically allocated contiguous array in memory
int* p = &vec[0];   p[2] = 6;

- **Common member functions of all containers.**
- empty()
- size()
- swap()
- copy constructor ...

// vec: {4, 1, 8}
if (vec.empty()) { cout << "Not possible.\n"; }

cout << vec.size();   // 3

vector<int> vec2(vec);  // Copy constructor, vec2: {4, 1, 8}

vec.clear();    // Remove all items in vec;   vec.size() == 0

vec2.swap(vec);   // vec2 becomes empty, and vec has 3 items.


// Notes: No penalty of abstraction, very efficient.

/* Properties of Vector:
 * 1. fast insert/remove at the end: O(1)
 * 2. slow insert/remove at the begining or in the middle: O(n)
 * 3. slow search: O(n)
 */

## deque
* Properties:
* 1. fast insert/remove at the begining and the end;
* 2. slow insert/remove in the middle: O(n)
* 3. slow search: O(n)

/*
 * Deque
 */
deque<int> deq = { 4, 6, 7 };
deq.push_front(2);  // deq: {2, 4, 6, 7}
deq.push_back(3);   // deq: {2, 4, 6, 7, 3}

// Deque has similar interface with vector
cout << deq[1];  // 4

## list
* double linked list
* Properties:
* 1. fast insert/remove at any place: O(1)
* 2. slow search: O(n)
* 3. no random access, no [] operator.

list<int> mylist = {5, 2, 9 }; 
mylist.push_back(6);  // mylist: { 5, 2, 9, 6}
mylist.push_front(4); // mylist: { 4, 5, 2, 9, 6}

   
list<int>::iterator itr = find(mylist.begin(), mylist.end(), 2); // itr -> 2
mylist.insert(itr, 8);   // mylist: {4, 5, 8, 2, 9, 6}  
                         // O(1), faster than vector/deque
itr++;                   // itr -> 9
mylist.erase(itr);       // mylist: {4, 8, 5, 2, 6}   O(1)

mylist1.splice(itr, mylist2, itr_a, itr_b );   // O(1)

## forward list
## array
- vecotr vs array
- array size() can not be changed.
- a and b is different types
- 文中指的是 a 和 b 雖然元素內容一樣 但是宣告的size不一樣 是不同的type

int a[3] = {3,4,5};
array<int, 3> a = {3, 4 ,5};
a.begin()
a.end()
a.size()
a.swap()

array<int, 4 > b ={3, 4 ,5};

# Associate Container
- each elelemt's key associateive with his value
- set/multiset means each element has same key(special case)
- map/multimap has different key
- **binary tree**
- insert o(log(n)
- Always sorted , default criteria is <
- Becuase is not sequence container => No push_back(),push_front()

## Set & multiset
* Properties:
* 1. Fast search: O(log(n))
* 2. Traversing is slow (compared to vector & deque)
* 3. No random access, no [] operator.
### Set
- No duplicates item

  set<int> myset;
  myset.insert(3);    // myset: {3}
  myset.insert(1);    // myset: {1, 3}
  myset.insert(7);    // myset: {1, 3, 7},  O(log(n))

  set<int>::iterator it;
  it = myset.find(7);  // O(log(n)), it points to 7
                  // Sequence containers don't even have find() member function
  pair<set<int>::iterator, bool> ret;
  ret = myset.insert(3);  // no new element inserted
  if (ret.second==false) 
     it=ret.first;       // "it" now points to element 3
                        
                        // 原本插入要log(n) 先用iterator先找到後  插入只要O(1)  
                        // 當然iterator在找的時候也是花掉log(n)
  myset.insert(it, 9);  // myset:  {1, 3, 7, 9}   O(log(n)) => O(1)
                         // it points to 3
  myset.erase(it);         // myset:  {1, 7, 9}

  myset.erase(7);   // myset:  {1, 9}
   // Note: none of the sequence containers provide this kind of erase.

### multiset
- multiset is a set that allows duplicated items
- set and multiset : value of the elements cannot be modified
- you may destory the data structure => matain failed ...

// multiset is a set that allows duplicated items
multiset<int> myset;

// set/multiset: value of the elements cannot be modified
*it = 10;  // *it is read-only

## map & multimap
### map
- No duplicated key

map<char,int> mymap;
mymap.insert ( pair<char,int>('a',100) );
mymap.insert ( make_pair('z',200) );

map<char,int>::iterator it = mymap.begin();
mymap.insert(it, pair<char,int>('b',300));  // "it" is a hint

it = mymap.find('z');  // O(log(n))

// showing contents:
for ( it=mymap.begin() ; it != mymap.end(); it++ )
  cout << (*it).first << " => " << (*it).second << endl;

### multimap
- multimap is a map that allows duplicated keys
- value can be modifed , but key can not be modified.
- because key is the index ...

// multimap is a map that allows duplicated keys
multimap<char,int> mymap;

// map/multimap: 
//  -- keys cannot be modified
//     type of *it:   pair<const char, int>
     (*it).first = 'd';  // Error

## What's does "Associative" mean?
- map: key and value has associative.
- set: key and value has associative, **but key is same(special case)**

# Unordered Container(C++ 11)

## define
- unordered multiset : unodered set that allows duplicated elements
- unordered map : unordered set of pairs
- unordered multimap : unordered map that allows duplicated keys

- hash collision => performance degree
- many item insert at same bucket
## Properties of Unordered Containers
- Fastest search/insert at any place : O(1)
- Associate Conatiner takes O(log(n))
- vector, deque takes O(n)
- list takes O(1) to insert , O(n) to search
- Unordered set/Multiset : element value cannot be changed.
- Unordered map/multimap : element key cannot be changed.(應該連value都不行吧...)

- Note About Associative Array
- Search time: unordered_map , O(1); map, O(log(n))
- Unordered_map may degrade to O(n);
- Can't use multimap and unordered_multimap, they don't have `[]` operator.
- 因為muiltimap 可以keys重複 , they don;t have unique key

## Container Adaptor
- Provide a restricted interface to meet special needs
- Implemented with fundamental container classes
- stack: LIFO, push(), pop(), top()
- queue: FIFO, push(), pop(), front(), back()
- priority queue: first item always has the greatest priority
- push() ,pop() , top()
- Another way of categorizing containers:
- array based containers: vector, deque
- Node base containers: list + associative containers + unordered container
- Array based cintainers invalidates pointers:
- native pointers, iterators , references

vector<int> vec = {1,2,3,4};
int *p = &vec[2];            // p points to 3
vec,insert(vec.begin(), 0);
cout<< *p << endl;           // 2 or crash , but if the containers is belong to node base rather than array based, we don't have this problem

# iterators and algorithms
## iterators

// Iterators

// 1. Random Access Iterator: vector , deque ,array

vector<int> iter;
iter += 5;
iter -= 4;
if(iter2 > iter1) ...
++iter; // faster than iter++ , because this operation without return value
--iter

// 2. Bidirectional iterator: list, set/multiset, map/multimap
list<int> itr;
++itr;
--itr;

// 3.forward iterator: forward_list
forward_list<int> itr;
++itr;

// unordered containers provide "at least" forward iterators.


// 4.Input iterator: read and process values while iterating forward
int x = *itr;

// 5.Output Iterator: output values while iterating forward
*itr = 100;

## const iterator

// Every container has a iterator and a const_iterator
set<int>::iterator itr;
set<int>::const_iterator citr; // read only access to container elements

set<int> myset = {2,4,5,1,9};

for(citr = muset.begin(); citr != myset.end() )
    cout << *citr << endl;

for_each(myset.cbegin(), myset.cend(), MyFunction);  // only in C++ 11

// Iterator Functions
advance(itr, 5);       // move itr forward 5 spots. itr += 5
distance(itr1, itr2);  // Measure the distance between itr1 and itr2

## iterator Adaptor (Predefined Iterator)
- A special, more powerful iterator
- Insert iterator
- Stream iterator
- Reverse iterator
- Move iterator (C++ 11)

// 1. Insert Iterator:
vector<int> vec1 = {4,5};
vector<int> vec2 = {12,14,16,18};
vector<int>::iterator it = find(vec2.begin() , vec2.end(), 16);
insert_iterator< vector<int>> i_itr(vec2,it);

//  {source start, source end, destination}
//        vec2: {12, 14 ,4 ,5 ,16 ,18}
// other insert iterators : back_insert_iterator, front_insert_iterator
copy(vec1.begin(), vec1.end(), i_itr);

// 2. Stream Iterator
vecotr<string> vec4;
copy(istream_iterator<string>(cin), istream_iterator<string>(), back_inserter(vec4));
copy(vec4.begin(), vec4.end(), ostream_Iterator<string>(cout, " "));

// make it terse
unique_copy(istream_iterator<string>(cin), istream_iterator<string>(), ostream_iterator<string>(cout," "));


// 3. Reverse Iterator
reverse_iterator<vector<int>::iterator> ritr;
for (ritr = vec.rbegin(); ritr != vec.rend(); ritr++)
    cout<< *ritr << end; // prints 7 6 5 4

## algorithms
- mostly loops

vector<int> vec = {4,2,5,1,3,9};
vector<int>::iterator itr = min_element(vec.begin(), vec.end()); // itr->1

// Note 1: Algorithms always process ranges in a half-open way : [begin, end)

sort(vec.begin(), itr); // vec: {2,4,5,1,3,9}
rverse(itr,vec.end());  // vec: {2,4,5,9,3,1} itr => 9

// Note 2:
vector<int> vec2(2);
copy(itr, vec.end(),         // source
          vec2.begin());     // destination
          
// vec2 needs to have at least space for 3 elements


// Note 3:
vector<int> vec3;
copy(itr, vec.end(), back_inserter(vec3));     // Inserting instead of overwriting
                    // back_insert_iterator : Not effect

// Note 4: Algorithms with function
bool isOdd(int i){
    return i%2;
}


int main() {
    vector<int> vec = {2,4,5,9,2};
    vector<int>::iterator itr = find_if(vec.begin(), vec.end(), isOdd); // return itr = 5
}

//  Note 5 : algorithm with native C++ array
int arr[4] = {6,3,7,4};
sort(arr, arr+4);

# Functors
- A functor is something that can be **mapped over**.

/*
 * Function Objects (functors)
 *
 * Example:
 */
class X {
   public:
   void operator()(string str) { 
      cout << "Calling functor X with parameter " << str<< endl;
   }  
};

int main()
{
   X foo;
   foo("Hi");    // Calling functor X with parameter Hi
}
/*
 * Benefits of functor:
 * 1. Smart function: capabilities beyond operator()
 * 	It can remember state.
 * 2. It can have its own type.
 */






// 
//   operator string () const { return "X"; }



/*
 * Benefits of functor:
 * 1. Smart function: capabilities beyond operator()
 * 	It can remember state.
 * 2. It can have its own type.
 */


/*
 * Parameterized Function
 */
class X {
   public:
   X(int i) {}
   void operator()(string str) { 
      cout << "Calling functor X with parameter " << str<< endl;
   }
};

int main()
{
   X(8)("Hi");
}

## Why we use functors ?

void add2(int i) {
   cout << i+2 << endl;
}

template<int val>
void addVal(int i) {
   cout << val+i << endl;
}

class AddValue {
   int val;
   public:
   AddValue(int j) : val(j) { }
   void operator()(int i) {
      cout << i+val << endl;
   }
};

int main()
{
   vector<int> vec = { 2, 3, 4, 5};   
   //for_each(vec.begin(), vec.end(), add2); // {4, 5, 6, 7}
   int x = 2;
   //for_each(vec.begin(), vec.end(), addVal<x>); // {4, 5, 6, 7} , you will compile failed ... 
   for_each(vec.begin(), vec.end(), AddValue(x)); // {4, 5, 6, 7}
}

/* Notes:
//global variable: int val;

template<int val>
void addVal(int i) {
   cout << val+i << endl;
}
//std::for_each(vec.begin(), vec.end(), addVal<3>); 

class AddValue {
   int val;
   public:
   AddValue(int j) : val(j) { }
   void operator()(int i) {
      cout << i+val << endl;
   }
};
//int x = 9;
//std::for_each(vec.begin(), vec.end(), AddValue(x)); 
*/

## STL functors

/*
 * Build-in Functors
 */
less greater  greater_equal  less_equal  not_equal_to
logical_and  logical_not  logical_or
multiplies minus  plus  divide  modulus  negate

int x = multiplies<int>()(3,4);  //  x = 3 * 4 

if (not_equal_to<int>()(x, 10))   // if (x != 10)
   cout << x << endl;

## Parameter Binding C++ 11

/*
 * Parameter Binding
 */
set<int> myset = { 2, 3, 4, 5};   
vector<int> vec;


int x = multiplies<int>()(3,4);  //  x = 3 * 4 

// Multiply myset's elements by 10 and save in vec:
transform(myset.begin(), myset.end(),    // source
	      back_inserter(vec),              // destination
			bind(multiplies<int>(), placeholders::_1, 10));  // functor
    // First parameter of multiplies<int>() is substituted with myset's element
    // vec: {20, 30, 40, 50}


void addVal(int i, int val) {
   cout << i+val << endl;
}
for_each(vec.begin(), vec.end(), bind(addVal, placeholders::_1, 2));

// C++ 03: bind1st, bind2nd








void addVal(int i, int val) {
   cout << i+val << endl;
}
for_each(vec.begin(), vec.end(), bind(addVal, placeholders::_1, 2));


// C++ 03: bind1st, bind2nd

// Convert a regular function to a functor
double Pow(double x, double y) {
	return pow(x, y);
}

int main()
{
  set<int> myset = {3, 1, 25, 7, 12};
  deque<int> d;
  auto f = function<double (double,double)>(Pow);   //C++ 11
  transform(myset.begin(), myset.end(),     // source
		      back_inserter(d),              // destination
				bind(f, placeholders::_1, 2));  // functor
            //  d: {1, 9, 49, 144, 625}
}
// C++ 03 uses ptr_fun 







set<int> myset = {3, 1, 25, 7, 12};
// when (x > 20) || (x < 5),  copy from myset to d
deque<int> d;

bool needCopy(int x){
   return (x>20)||(x<5);
}


transform(myset.begin(), myset.end(),     // source
          back_inserter(d),               // destination
          needCopy
          );

// C++ 11 lambda function:
transform(myset.begin(), myset.end(),     // source
          back_inserter(d),              // destination
          [](int x){return (x>20)||(x<5);}
          );

/*
          bind(logical_or<bool>, 
              bind(greater<int>(), placeholders::_1, 20),
              bind(less<int>(), placeholders::_1, 5))

// C++ 11 lambda function:
transform(myset.begin(), myset.end(),     // source
          back_inserter(d),              // destination
          [](int x){return (x>20)||(x<5);}
          );

bool needCopy(int x){
   return (x>20)||(x<5);
}
*/

## Why do we need functor in STL ?

/*
 * Why do we need functor in STL?
 *
 */

set<int> myset = {3, 1, 25, 7, 12}; // myset: {1, 3, 7, 12, 25}
// same as:
set<int, less<int> > myset = {3, 1, 25, 7, 12};

bool lsb_less(int x, int y) {
      return (x%10)<(y%10);
}

class Lsb_less {
   public:
   bool operator()(int x, int y) {
      return (x%10)<(y%10);
   }
};
int main()
{
  set<int, Lsb_less> myset = {3, 1, 25, 7, 12};  // myset: {1,12,3,25,7}
  ...
}

/* Notes
 
bool lsb_less(int x, int y) {
      return (x%10)<(y%10);
}

class Lsb_less {
   public:
   bool operator()(int x, int y) {
      return (x%10)<(y%10);
   }
};
*/

## Predicate

/*
 * Predicate
 *
 * A functor or function that:
 * 1. Returns a boolean
 * 2. Does not modify data
 */

class NeedCopy {
   bool operator()(int x){   
      return (x>20)||(x<5);  
   }
};

transform(myset.begin(), myset.end(),     // source
          back_inserter(d),               // destination
          NeedCopy()
          );

// Predicate is used for comparison or condition check









// More About Functors

# C++ STL Algorithms
## Non-modifying algorithms
## Modifying algorithms
## Sorting
## Sorted Data Algorithms and Numeric Algorithms
## C++ String Constructor and Size