C++ :: std vector/ list/ map/ set/ priority queue

(1) Vector
Common method:
      vector<int> v;
      vector v(10, 0); // {0,0,0,0,0,0,0,0,0,0}
      v[i]                  // access element at index i
      v.size()            // return number of element
      v.clear()           // erase all element
      v.empty()         // return True/False, any element in v or not
      v.erase(it )       // delete the element at position it, O(n) complexity since all element after it need to arrange
      v.insert(it, val)  // insert val at position it, O(n) complexity
      v.push_back(val) // add element val at end of vector, O(1) complexity
      v.pop_back()   // return element at end
      v.begin()          // the iterator at the front
      v.end()             // the iterator at the end
      lower_bound( it_begin(), it_end() ) also takes O(n)

Other idea:
- Better use v.empty() to check if there is any element in vector (don't use v.size()). 
Most of time it is ok for vector. Takes O(1) complexity to v.size(). But v.size() for list takes O(n) complexity.
- In vector, the difference between size and capacity?

- There are many approach when we aim to copy one vector to another.
http://workhahard.blogspot.com/2016/04/c-vector.html
      1. one by one by for loop
            for(int i=0;i<v.size();i++)
                   v2[i] = v[i]
      2. vector.assign()
            v2.assign(v.begin(), v.end())
      3. reserve
             v2.reserve(v.size())
             v2.insert( v2.end(), v.begin(), v.end())
      4. constructor
             v2 = vector(v)

- It is common when you get a vector from address reference and don't want to change the original value, for example:
      vector<vector<int>> permute(vector<int>& nums) {
            copy nums to vectorTmp
            ...
      }

- Difference between Vector and List:
https://stackoverflow.com/questions/2209224/vector-vs-list-in-stl

(2) List
Common method:
      list<int> li;
      li[i]                  // access element at index i
      li.size()            // return number of element
      li.clear()           // erase all element
      li.empty()         // return True/False, any element in v or not
      li.erase(it )       // delete the element at position it, O(1) complexity since all element after it need to arrange
      li.insert(it, val)  // insert val at position it, O(1) complexity
      li.push_back(val) // add element val at end of vector, O(1) complexity
      li.pop_back()   // return element at end
      li.begin()          // the iterator at the front
      li.end()             // the iterator at the end

(3) Map
Composed of nodes, each node is a pair of {key, value}. Key in unique in each map.













Two container are support as a map in C++
map<int, string> m;
      Implement by Red-Black tree ( insertion()/ find()/ and delete() takes O(logn) lower_bound( it_begin(), it_end() ) also takes O(logn))
unordered_map<int, string> m2;
      Implement by hash table (insertion()/ find()/ and delete() takes O(1), but require huge extra space)

Common method:
      m.insert(pair<int, string>(100, "Watermelon")) // insert a node
      m[200] = "StrewBerry"                   // insert by array
      auto it = m.find("Apple")                 // return the iterator of node which value = "Apple"
            if( it!= m.end()){
                 cout << it -> second            // return value = pari< key, value>
            }else{
                 cout << "can't find"
            }
      m.count( x)                           // return 1 if this map contain node with key = x, o otherwise

A example: Leetcode 771. Jewels and Stones:
https://leetcode.com/problems/jewels-and-stones/description/
Thought to use set at first place, but it would be more convenient to use map to count

      map<char,int>Own;
      ret = Own.insert({S[i],1});   //map.insert的回傳是pair<iterator,bool>
      if(ret.second == false){//用boolean來判斷有沒有插入成功
            Own.find(S[i])->second++;//map.find的回傳是iterator
      }

(4) Set:
Set is same as map, only value is equal with key. Remember there will be no repeat key in map => there will be no repeat element in set (all unique)

Two container are support as a set in C++
set<int> a;
      Implement by Red-Black tree ( insertion()/ find()/ and delete() takes O(logn) lower_bound( it_begin(), it_end() ) also takes O(logn))
unordered_set<int, string> m2;
      Implement by hash table (insertion()/ find()/ and delete() takes O(1), but require huge extra space)
Common method:
      s.insert(x)                        // insert element x into this set
      s.count(x)                        // return 1 if this set contain node with key = x, o otherwise
      s.find(x)                           // return the iterator with element x, s.end() is not found
Set also support Boolean functions like intersection/ union/ difference
The example from cpp reference: 
   first = s1.begin(); second = s2.begin();
   it=std::set_intersection (first, first+5, second, second+5, v.begin());

   v.resize(it-v.begin());

Another example: use inserter 

      set_union(s1.begin(),s1.end(),s2.begin(),s2.end(),inserter(s3,s3.begin()));
      set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(),inserter(s3,s3.begin()));
      set_difference(s1.begin(),s1.end(),s2.begin(),s2.end(),inserter(s3,s3.begin()));  
Inserter can insert element in the specific position. Almost every container in C++ support this method

(6) Heap
https://en.wikipedia.org/wiki/Binary_heap
https://www.geeksforgeeks.org/binary-heap/
http://alrightchiu.github.io/SecondRound/comparison-sort-heap-sortdui-ji-pai-xu-fa.html

Definition of heap:
a binary tree, root node is larger than children nodes. (root node is smaller than children if it is a min-Heap). Notice that no special relation between two children.

Left_Child < Root < Right_Child only true in Binary search tree

  
(7) Priority Queue:

Need to implement comparison function (so we can assign the indicator we would like use )
The container defined is:

      // The entity in this queue
      struct puzzle{
            int dist=0;
            int gn=0;
            bool u=false,d=false,l=false,r=false;
            string arrayS = "123456870";
      };
      // The comparison function, use dist in puzzle to compare
      struct compare_cost{
            bool operator() ( const puzzle& a, const  puzzle& b) const{
                  return a.dist >= b.dist ;
            }
      };
      // Priority queue container, follow the definition above
      // puzzle is class, vector is container, compare_cost is comparison function
      std::priority_queue<puzzle,vector<puzzle>,compare_cost> q;

Common method:
      q.push( class T)                 // put an entity in to p.q
      q.top()                                // return the entity with maximal distance
      q.pop()                               // erase the entity with the maximal distance

Reference:

[1] STL

http://www.cnblogs.com/Xredman/archive/2009/04/26/1443737.html

[2] Mr. Opengate

http://mropengate.blogspot.com/

[3] vector copy

http://workhahard.blogspot.com/2016/04/c-vector.html

[4] cpp reference
http://www.cplusplus.com/reference/