C _Data_structures - RicoJia/notes GitHub Wiki

========================================================================

Common Things

========================================================================

  1. Most ordering (sort, map, set), are naturally ascending. To get a descending sequence, use greater

    // greater definition
constexpr bool operator()(const T &lhs, const T &rhs) const {
    return lhs > rhs; // assumes that the implementation uses a flat address space
}

std::multimap<int, string, std::greater<int>> mp; 
//makes the second element go first, resulting in a descending arr
std::sort(vec.begin(), vec.end(), [](int a, int b){return a > b; })

  2. erase:

    list: list::erase()
=====
vector
deque: vector.erase(std::remove(vec.begin(), vec.end(), 3))
     - have pop_back()
=====
map.erase(key)
multimap
multiset
set
    • erase() in std::deque, std::vector does not work with reverse_iterator directly! (e.g, rbegin())

  3. insert

    ====
deque.insert(iterator, value); 
vector.insert()
====
multimap.insert()
multiset.insert()
====
map.at();       // complain if key doesn't exist
map[];      // most versatile
map.insert();       // won't insert if key exists
unorderede_map.insert()
unordered_set.insert()

  4. emplace is well supported by STL containers

    1. Main motivation is to avoid creating and destroying temp obj

      • Its ability to take in args only means you don't have to contruct a temp obj yourself (like push_back)
      • push_back = emplace_back, push_front = emplace_front

    2. It can do everything insertion can

      • insert = emplace (this is used by node-based containers (except std::forward_list), which comrise the majority of the STL containers)
        • emplace_after (std::forward_list)
        • emplace_hint (associative containers such as map and set)
      • non-node-based containers are: vector, deque, string also has this

    3. In a few cases, emplace_back might be worse than push_back

      1. Container going to reject the new value as a duplicate (e.g, std::unorderede_map) 
        std::unordered_set<std::string> s {"haha"};
s.emplace("haha");     //a temp will be created for duplicate comparison.
      2. You have to create a ptr and allocate the memory as part of contructing the obj 
        std::list<std::shared_ptr<Widget>> ptrs;
void customDeleter(Widget*) dl;
// new Widget's ptr will be perfect-forwarded to the ptrs, allocate memory for itself. If exception occurs, there'd be memory leak!
ptrs.emplace_back(new Widget, dl);    
//no memory leak, because you're creating shared_ptr first, which will take care of it.
ptrs.push_back(std::shared_ptr<Widget>(new Widget, dl));  
ptrs.push_back({new Widget, dl});

  5. find:

    • in set, map, you can do set.find(key).
    • However, for vector and list, you need to do 
      #include <algorithm>
// which returns end() if nothing is found.
std::find(vec.begin(). vec.end(), something);

========================================================================

Universal Tools for Data Structures

========================================================================

iterator

  1. Basics
  • iterator algebra
    • adding two pointers/iterators together e.g, a+b， 两个都有address. 所以你无法a+b, 只能a-b!
  • Iterator types:
    • output iterator: output_iterator ++ 是可以指向下一个元素的
    • back_inserter 是一种output iterator， ostream_iterator(cout, " ")也是output iterator 
      #include<iterator>
std::copy(vec.begin(), vec.end(), std::back_inserter(vec2));  // back_inserter is a library function that constructs a std::back_insert_iterator. Equivalent to std::back_insert_iterator< std::vector<int> > back_it (vec2)
it = something;     // This will call push_back() on the container. So the container should have push_back. *, ++ does not work on back_inserter.
  1. Const Iterator
  • 什么是const iterator? 是iterator over const type. 所以， 他是node_itr。 const T 在这里成为了type. Const iterator can point to different const objects.
    • General rule of thumb: use const_iterator if you're not modifying any element.
    • const_iterator: const object 需要const_iterator 来access
  • C++98, C++11 and C++ 14 const_iterators,
    • C++98: don't use const_iterator, as there's no portable way to convert const_iterator -> iterator
    • C++98: vector.insert(iterator),const_iterator here won't work, you must have a regular iterator
    • C++11: vector.insert(const_iterator, 1998), more practical.
    • C++11: non_const_vector.cbegin() can give you the const_iterator.
    • C++11: std::begin is introduced. 
        std::begin(const_vector) will give std::vector<int>::const_iterator.
    • C++14: std::cbegin(), std::rbegin() is introduced.
      • C++11, you can define your own cbegin:
        template <typename Container>
  auto cbegin(const Container& c)
  -> decltype(std::begin(c)){
    return std::begin(c);
  // yields const_iterator
  }

  1. Design your own iterator

    1. Design your own const_iterator: make it a template, and add bool to see if it's constant iterator
        #include<type_traits>
    template <typename T, bool is_const = true>
    //we need to make this a separate class because of b++ and it cannot be in class ls for the 					underlying ls object
    class node_itr              //= , != can be synthesized.
    {
    public:
        typedef typename std::conditional<is_const, node<T>*, node<T>* >::type node_T_ptr;}
    1. iterator 要可以转化为const_iterator， 但是const_iterator 无法转化为iterator。 同时要保证iterator =iterator, const_iterator = const_iterator. 如下是一个copy constructor
      node_itr(node_itr<T,true>& n):data(n.data){} //for conversion bw non-const to const.
    • 你不用在定义其他的，因为synthesized = 就是要copy 你指向的address，进而如果你modify 了一个object，你的iterator 有可能被Invalidate.
    • 你需要unqualified type (比方说去掉const volatile int 中的const volatile)来，这样你的pointer也是unqualified,也就有了弹性。不过，你需要用std::remove_cv_t来转换iterator 到const iterator. (c++14)

    1. 一定要保证使用iterator 时，你用pass by value, 而不是pass by reference

        ls(const_iterator b,const_iterator e){uncrear(); ls_crear(b,e);}

    2. 可以考虑当std::iterator 的child class

      template<class Category, class T, class Distance = ptrdiff_t, class Pointer = T*, class Reference = 				T&>.
Argument 1: check out cpp reference for the iterator you want to implement,
Argument 2: the type of object we are going to iterate over.
Argument 3-5: use the default value.

    3. conversion operator: operator node_itr<const T>() const

    4. template里边可以进行简单的Type 处理. 比如

    template<class T, class unqualified_T = std::remove_cv_t<T> >            // specify node_itr<const T> for const_iterator
    1. destructor 不应该destroy 指向的delete,除非是在erase 里. 因为一个iterator 的消失本身并不代表指向的对象也会消失. 8.eg.
    template<class T, class unqualified_T = std::remove_cv_t<T> >            // specify node_itr<const T> for const_iterator
class node_itr:public std::iterator<
  std::bidirectional_iterato
  node<T> >
  {
  public:
      node_itr(node<unqualified_T>* d = 0):data(d){}        //not node_itr& cuz it will be out of scope. but return a new node_itr?? If not, you have to modify data, which means you can never have a const iterator

      T& operator*() const {
    return data->val;
      }

      operator node_itr<const T>() const
      {
    return node_itr<const T>(data);
      }
  private:
      node<unqualified_T>* data;
  }

    typedef node_itr<T> iterator;
    typedef node_itr<const T> const_iterator;

========================================================================

Simple Data Strucutures and Common Things

========================================================================

String

  1. Intro

    • std::string is a typedef alias to std::basic_string<char>

  2. regular expressions - replace something std::regex e("\."); string result; std::regex_replace (std::back_inserter(result), address.begin(), address.end() ,e,"[.]$2");

  3. string Basic Operations

    • insert and replace, string += is same as string.append(), as += is implemented using append

       strng.replace(pos, num_char, "content");        //use ptr. 
 string.append(char); unique 
 string.append(string)
 string.append(char*, size)

    • concatenate int to string

       #include <string>     // std::string, std::to_string
 str+std::to_string(int); //post c++11.

    • Compare 2 strings

       s1!=s2 
 ret = s1.compare(s2);
 // equivalent to pos = (s1>s2), neg = (s1 < s2)
      • >, < will compare strings one char at a time

    • find in string, return size_t

       // return position of the first char, or string::npos if nothing is found. 
 str.find("substring", 4);   //4 is the starting pos

    • delimit: use std::getline, which reads delim and puts strings in a string.

      void delimit(const string& str){
    std::stringstream ss; 
    ss<<str; 
    std::string str2; 
    vector<string> ret; 
    while (std::getline(ss, str2, ' '))
        ret.push_back(str2); 

    for (auto s: ret)
        cout<<s<<endl;
}

    • get a const char* to underlying string: string.c_str()

  4. Misc

    • std::to_string: to_string(123.56) = "123.56";
    • Small Value Optimization (SSO)
      • String allocates dynamic memory, which is expensive heap action
      • compiler reserves a fix number of stack space to avoid that.

  5. Heads-ups

    • ! in C++, "a"+"b" is not legal, you have to have one string obj first! also, "" is char[], '' is char
    • char 16_t[] cannot be directly converted to std::string

char*

  • Basic char* opertations 
      #include<cstring> funcs
    • memcpy (you need memory allocated, like char[40], or str_ptr = new char[])
    • strlen; best way to get length of string. Not counting Null
    • char* c = "lol" is deprecated, use const char* c = "lol" instead.
    • can you pass char arr into char*?
      • char arr <--> char*, allowed

Common Mistakes For String

  1. string::substr(pos, length)!! not string::substr(start, end)
    • return a newly constructed string.
    • if string is shorter, as many as used

Stringstream

  1. stringstream.str() returns a copy of string. Therefore they are temp objects, rvalue, and stringstream.str().c_str() doesn't work
  2. ss.str("somestring") - sets s as the contents of the stream
    • ss.str("") discarding any previous contents

========================================================================

Initializer_List

========================================================================

Initialization

  1. Motivation

    1. c++ 11 invented initializer_list, which unifies copy construction with (). Also called list initalization, or uniform initialization

      1. 3 ways to initialize:

        int i(27);
int i = 27;
int i{27};

      2. = or () both have restrictions.

        • std::atomic doesn't support =
        • default initialization of non-static members in class doesn't support () 
          class Foo{
    int(3);   // doesn't compile
  };
std::atomic<int> i = 3;     //doesn't allow, atomic = invokes copy constructor here, but std::atomic is non-copyable!!

      3. {} is meant to be uniform. {} is neither an expresion, nor a statement, it's for auto only.

    2. std::initialize_list is a temprorary array of const T

  2. Uses

    #include <initializer_list>
// 1
for (auto i : {1,2,3})  cout<<i<<endl; //{} will be automatically converted to std::initializer_list

// 2
void foo(const std::initializer_list<int>& ls){
  std::vector<int> vec;
  vec.insert(vec.end(), ls.begin(), ls.end());
  cout<<ls.size()<<endl;
}

  3. Create a ctor with initializer_list if you can

    • Most regular cases, without ctor with initializer_list, {} and () calls the same ctor 
      #include <initializer_list> 
class Foo{
  public: 
    Foo(int, bool); 
    Foo(int, double); 
  }

int main(){
    Foo f{3,true};  //same as Foo f()
  }
    • Once you add ctor with initializer_list, the compiler will choose the initializer_list ctor.
      • Add initializer_list ctor CAREFULLY. If cannot be used directly, conversions are made 
        class Foo{
    ...
    Foo (std::initializer_list<long double> l );
    operator float(){}
  }

Foo f1(); 
Foo f2(f1);     //copy ctor
Foo f3{f1};     //f1 will convert to float, float convert to long double, then calls default ctor.
Foo f4{std::move(f1)};    //since operator float does specify & or &&, it can be used to convert to float, then long double, then default ctor
    • If no coversion is available, then it tries to find another suitable ctor.Narrowing-conversion is not considered "cannot be converted"
    • Empty initializer_list will call default ctor
    • std::vector is not a great design, as () and {} has very different meanings

  4. Cautions

    1. List initialization doesn't like "narrowing conversions" among built-in types. This is a design choice

      • narrowing conversions means "not all values of datatype can be stored", such as int to uint8_t 
        // 1
class Baz{
  public:
    Baz (std::initializer_list<int> l){}
};

int main()
{
    // narrowing
    // Baz b({1.0,2,3,4,5,6});
}

    2. pay attention to auto, which can be deduced into initializer_list.

    3. why list alone doesn't compile?

      int main() {
  {1,2,3};
  return 0;
}
      • {} is not an expression, and a braced-init-list may appear on the right-hand side of assignment

    4. Most vexing parse is: if anything can be interpreted as a function, it will be. Examples:

      // most vexing parse
class Foo{
    public:
    Foo(int i){};
    Foo() = default;
};
// most vexing parse
Foo f(1);   //You're creating an object
Foo f2();   //May not compile as "function"

    5. Exception The only difference between auto and template is in initializer list (C++11 & 14): auto will be deduced into std::initializer_list<int>, but template won't and gives you an error

      //ok
auto a = {1,2,3};
//compiler error! 
template <typename T> void templated_fn(T) {}
templated_fn({1, 2, 3}); // "{1, 2, 3}" is not an expression. It has no type, so T cannot be deduced
templated_fn<std::vector<int>>({1,2,3});    //this works
templated_fn<std::initializer_list>({1,2,3});    //this works

========================================================================

Unordered_Map & map

========================================================================

  1. Common Basics
    • Internally, unordered_map and unordered_set are both using hash-table; map and set are using red-black tree. Search, insert, delete are all o(log(N))
    #include<unordered_map> // using Hash table under the hood. o(1)
using std::unordered_map
    • For sets and maps, if you have a custom data type, (or something like std::tuple), you need to provide a custom hash function. 
        #include <unordered_set>
  #include <unordered_map>
  #include <tuple>
  #include <functional>

  typedef std::tuple<int, char> nkey_t;

  // Implement a hash functor
  class CustomHash {
      public:
      // Implement a hash function
      std::size_t operator()(const nkey_t& k) const {
          // This could be a bad hash function anyway
          std::size_t h1 = std::hash<int>{}(std::get<0>(k));
          std::size_t h2 = std::hash<char>{}(std::get<1>(k));
          return h1 ^ h2;
      }
  };

  int main() {
      std::unordered_map<nkey_t, std::string, CustomHash> umap;
      std::unordered_set<nkey_t, CustomHash> set;

      nkey_t key{1, 'a'};
      umap[key] = "AAA";
      set.insert(key);
  }

Unordered_map

  1. Basics

    • Reminder: values of types without user ctor will be zero-initalized here. (provided with value). ++map[idx]

    • find

      std::unordered_map<double, double>::const_iterator it= mymap.find(key);
if (it==mymap.end())    //map::find(key) will return an iterator to the value, or unordered_map::end.

    • Random access:

      1. at() is safe.

        • const map, const unordered_map can only work with at(): 因为[]没有const-qualified overloading （即[]会改变map里边的值）。

      2. need to use std::advance on map iterators. can't do it < map.end() and must do it != map.end() instead.

        #include <iterator>
std::advance(iterator, distance);

    • map.insert(): same in map

      1. if key already exists, the element won't be inserted. Return iterator to an iterator. (note in unordered_map it's different) 
        std::unordered_map<int, int> mp = {{3,4}}; 
// test insert and iterator
auto it = mp.insert({1,2});
      2. [] will insert the key with default value, if it's not there yet. 
        const unordered_map<int, int> z = {{5, 6}}; 
int val = z.at(5);  //Success!
int val = z[5];     // Bad, because const doesn't work here!

// this is a pair
for (auto i = z.begin(); i != z.end(); ++i) {
    cout<<i->second<<endl;
}

    • size: mp.size() : number of elements

      • count(key). So in unordered_map, map, it's always 1. multimap.count() is > 1

    • Erase to get rid of a pair.

      • map.erase(iterator) or map.erase(it1, it2), or
      • map.erase(key); returns size that has been erased if erase by key.
        • erase a non-exisitent key? A: that's perfectly fine. You will get zero as output
      • order after erasing is preserved in both unordered_map, map
      • Thread safe for const functions only. at() when map is const is good

Map

  1. Basics

    • Order of iterators is ensured!
    • map is implemented using self-balancing tree. It is red-black tree, where self-balancing will take O(1)! Insertion and deletion will be O(logn).

  2. self-balancing tree:

  3. there're only black and red

  4. root needs to be black

  5. the "black depth" is the same on each branch (black depth: number of blacks from root to leaf)

  6. new insertion is always red

  7. null leaf nodes always black.

  8. No 2 consecutive red nodes, but 2 consecutive black nodes are legit.

Multimap

  1. multiple elements can have the same key, always sorted

    • because of this, there's no array index operator []. or at()
    • so you also have to use insert

  2. Find:

    • equal_range(key). Returns (start_itr, end_itr). If not found, its pairs will be the first itr after key. 
      auto itr_pair = mmp.equal_range(1); 
for (auto i = itr_pair.first; i != itr_pair.second; ++i) {
    cout<<i->first<<" "<<i->second<<endl;
}

  3. multimap implementation

========================================================================

Set & Tuple

========================================================================

Unordered_set

  1. #include <unordered_set> //using hash table
  2. operations:
    1. insert 
      std::unordered_set<double>::const_iterator it = myset.insert(element);
    //return an iterator to the element. (newly added or already existent)
or 
myset.insert(beg, end);
    2. find 
      myset.find(something)

Pair

  1. std::pair: Before you use pair: can you use a 2d vector or 2d array?
    1. c++ 11 beyond can use std::pair{a,b} to initialize
    2. pair.first, second
    3. simple example: 
      #include <iostream>
#include <utility>    // for std::pair
using namespace std;
int main()
{
  int j = 10; 
  std::pair<int, int*> p;  
  p = std::make_pair(j, &j);
  cout<<p.first<<*(p.second)<<endl;
}

Tuple

  1. std::tuple

    • Basics:

      #include <iostream>
#include <tuple>
using namespace std;
int main()
{
    auto t = std::make_tuple(1,2);
    int i, j;
    std::tie(i, j) = t;
    cout<<i<<j<<endl;
    i = std::get<0>(t);       // C++14
}

    • std::tie constructs a tuple<int&>, then tuple = assigns the refereces. Hence can be used to unpack a tuple.

      int i, j; 
std::tie(i,j) = std::make_tuple(i,j); 
// equivalent to 
std::tuple<int&> {i,j} = std::tuple<int>{2,1};

    • Trap:

      auto return_pair(){
    return std::make_tuple(0, 'D');       // deduced as std::tuple<double, char>; 
}

    • tuple length and tuple_cat:

        #include <iostream>
  #include <tuple>
  template <typename T>
  auto get_tuple_size(T& item){
      return std::tuple_size<T>::value;
  }

  int main()
  {
      auto tp1 = std::make_tuple(1,2);    //C++14
      auto tp2 = std::make_tuple("online", 3);
      auto new_tp = std::tuple_cat(tp1, tp2);
      std::cout<<get_tuple_size(new_tp);    //c++11
      return 0;
  }

    • std::pair -> std::tuple native conversion

      std::pair<int, int> p {1,2}; 
std::tuple<int, int> tup(p);

Multiset

  1. e.g, #include<set> 
    #include <set>
multiset<int> s; 
s.insert(12); 
s.insert*(10); 
s.insert*(10); 
s.insert*(2); 

//ascending order
for(auto it = s.begin(); it != s.end(); it++){
  cout << *it <<endl; 
}

auto it1 = s.find(90); 
auto it2 = s.find(10); 
s.erase(it1, it2);

========================================================================

array

========================================================================

  1. why not vector?
    1. std::array has fixed size, where vector is dynamically allocating stuff.
    2. vector DOES NOT AUTOMATICALLY return unused space 
      vec.clear(); 
cout<<vec.capacity()<<endl;     // this still returns a large number
vec.shrink_to_fit();            // this will return the unused memory back to OS
  2. why not traditional array?
    1. This is a proper object. 
      void foo(int *p, int len){}
std::array<int, 4> arr = {1,2,3,4}; 
foo(arr, arr.size());       //illegal, cuz arr does not decade into int*
foo(&arr[0], arr.size());   //This is legal
foo(arr.data(), arr.size());    // also legal

arr.empty();
for(auto &i : array){}
//sort, 
std::sort(arr.begin(), arr.end(), [](int a, int b){return b < a; });
  3. quirks: 
    constexpr len = 3; 
std::array<int, len> arr = {1,2,3};     // must have constexpr length

Raw array

  1. Initialize using ternary: You cannot initialize an array using ternary itself. Use a proper if else statement. Below is wrong: 
    int c_inc[] = (r_inc == 0)? (int[2]){-1, 1}: (int[1]){0};
    • This is wrong because ternary needs an expression (6+7 is an expression, a= 6+7 can be executed, hence it's a statement) but initializer list is neither an expression nor a statement.

========================================================================

List

========================================================================

  1. std::forward_list

    1. singly-linked list, more memory efficient than std::list
    2. The only container that does NOT have .size()
    3. ofc, no bi-directional access

  2. list::splice: inserting elements from one list into another, and delete the elements in the other list

    // ls2 is needed so elements will be removed. 
ls.splice(ls.end(), ls2, ls2.begin());    //Trap: this only moves single element ls2.begin() to list. 
ls.splice(ls.end(), ls2);       //move the entire ls2 here
ls.splice(ls.end(), ls2, ls2.begin(), ls2.end());     // insert ls2 at the endl

// Powerful use: 
// Before: mylist1: 1 10 20 30 3 4 after: 30 3 4 1 10 20
mylist1.splice ( mylist1.begin(), mylist1, it, mylist1.end());
    • two threads splicing at the same time guess is fine, but iterating through them will cause a race condition.?
    • mylist.insert(it1, it2) is also fine

  3. list.begin() is a bi-directional iterator, only supports ++a, not a+n

========================================================================

Vector

========================================================================

  1. Basics

    1. vector::front, vector::back() returns reference

      • ptr to the raw array of vector: 
        vec.data();

    2. Push_back needs dynamically allocate memory. list.insert() is slower than vector, since vector is more compact

      • push_back needs an copy assignment cosntructor.
      • push_back might create temp object or move it, even for rvalue ref. use vec.emplace_back(obj&&), which builds in place.
      • emplace_back works with args too 
        //So push_back will push Widget&& reference.
template <class T ..>
class vector{
    public: 
    //std::vector<int> will pass int as T, so this has to be rvalue.
    void push_back(T&& x){}     
    void push_back( const T& value );   

    template <class ... Args>
    void emplace_back(Args&& ...args);      // This is truly a universal reference
  }

std::vector<int> v; 
v.emplace_back(12);       // So 12 will be deduced to rvalue. 
v.emplace_back<double>(12.5);     // This is an edge case, will push 12 to the vec
v.push_back(12);        // this is an rvalue, no doubt

    3. remove-erase idiom: remove does logical remove, erase deallocate the memory

      v.erase(std::remove(v.begin(), v.end(), item), v.end());
      • erase an element during iteration: vec.erase() returns the itr after the erased element. But for vector, since it's contiguous, we just need ++itr 
        for (auto it = vector.begin(); it!= vector.end();){
    if(...){
        vector.erase(it);
    }
    else{
        ++it; 
    }
}

    4. Construct

      // array to vector: actually copy. 
int a[] = {0,1,2,3};
vector<int> b (a, a+4);     // a+4 is like .end() in a[]

//Initializing a double vector
vector<vector<double> > y_list = {{0,0,1,1,0}, {0, 0, 1,0}};

// reserve without initialization: before allocation, we need to find large enough memory. Reserve just does the finding
vec.reserve(n); 

// construct vector from map
std::vector<std::string> routes;
std::for_each(callback_query_map_.begin(), callback_query_map_.end(), [&routes](const auto& pair){routes.emplace_back(pair.first)});

//use a map's iterator to initialize vector: 
vector<std::pair<int, Vertex> > a(map.begin(), map.end())

    5. reverse a vector: std::reverse(vec.begin(), vec.end())

    6. Check if a vector has distinct elements:

      bool is_distinct(vector<int> vec){
    unordered_set<int> s; 
    for (auto i: vec)
        s.insert(i); 
    if (s.size() == vec.size()) return True; 
    else return False; 
}

  2. Cautions

    1. Before you use vector: Do you need push_back, erase, etc? If not, you can use an array array?
    #include <cstring>
int arr[100]; 
memset(arr, 0, sizeof(arr));            //I tripped here before: it must be sizeof(arr), as this is the number of bytes you need
    1. [] does not check bounds, since You don't pay for what you don't use

========================================================================

Stack Queue Deque List Priority_Queue

========================================================================

Stack

  1. Basic Example 
    std::stack <int> stack
stack.push()
stack.pop()

Queue

  1. this is implemented on top of another STL container, hence called "container adaptor". The functionalities are very basic:

    1. size()
    2. emplace(), push(c), pop()
    3. front(), back()
    4. queue.empty()
    5. queue.swap(another_queue) //swap their contents.

  2. Example:

    void basic_queue(){
    // Cannot do list initialization on queue
    // std::queue<int> q = {2,3,4}; 
    std::queue<int> q; 
    q.push(1); 
    // No queue::top()
    // q.top();
    cout<<q.front()<<endl; 
    q.pop(); 
}

Dequeue

  1. Functionality:

    dq.push_back(); 
dq.push_front(); 
dq.pop_back(); 
dq.pop_front();
    • deque has all basic functionalities as vector.

  2. cons:

    • .at() indexing is not as efficient, as deque does not have a contiguous memory.

  3. This is double ended queue, where

    1. Elements can be added/deleted at the front and the back
    2. You can have random access like a vector
    3. Contiguous memory may not available.

  4. Implementation

    1. This is a linked list of array, where new elements are stored in these arrays. when arrays are full, you allocate more memory and insert them in the linked list.

Priority_Queue

  1. priority_queue
  2. std::priority_queue: like managing a heap, but without accidentally mess up the ordering. Good explanation
    • summary 
      push()
top()
pop()
    • example 
      int main()
{
  // pq is a "container adapter", i.e., on top of an existing container like std::vector or deque
  // allows duplicates, which is like std::multiset
  // O(log(n)) Internally this is a heap
  std::priority_queue<int, std::vector<int>> pq; // by default, top of the pq is the greatest
  
  std::vector<int> vec = {24, 3, 15, 26, 38}; 
  for (unsigned int i = 0; i < vec.size(); ++i) {
    pq.push(vec.at(i)); 
  }

  while (!pq.empty()){
    cout<<pq.top()<<endl; 
    pq.pop(); 
  }
}

========================================================================

Trees

========================================================================

Binary Search Tree

  1. Implementation summary 
    // Time complexity for traversing and insertion: log(n): 2^0+ 2^1 + 2^2 + 2^n
// the simple way is to just use a node and externally keep track of it, instead of having a node class and tree class.
// For Insert's recursion, it is easier to pass in the pointer externally than managing the child's pointer in the current function.
// When doing recursion, we want to only worry about the current node's status
// print- becareful with printing sequence. You print left, then middle, then right

Binary Heap

  1. Basics

    • Use array to store all its elements. Each node must be < or > than children
    • insert:
      1. put an element at the end of the array
      2. compare with its parents
      3. then move up based on the sorting criteria
    • Remove top of heap
      1. take out the root
      2. put the last leaf to the root
      3. "heapify" the heap:
        1. compare the last leaf with the two child leaves
        2. move the leaf node down the tree
    • time complexity: o(1)to find max, o(lg n) for deleting a node, insertion

  2. in python, you do heapq.heappop(H)

    • pop the first element,
    • then move the last element down the tree, o(logn) .
    • equivalent to priority_queue::pop.

  3. Application

    1. In A*, main challenge is when we update the cost of a heap element, we cannot efficiently move the modified heap element up or down.
    2. std::priority_queue does not support that, std::make_heap will take O(n) no matter what your queue is like. otherwise, find min of the vector every time, which is o(n) every time.
    3. std::make_heap for minimum heap, so you have more flexibility to modify nodes! 
      #include <algorithm>
struct node{
    double cost; 
    int id; 
    node (double cost, int id):cost(cost), id(id){}
};

// min heap
struct greaters{        //【注意】： std::greaters 重名
    bool operator()(const node& a,const node& b) const{ 
    return a.cost > b.cost; }
};

int main()
{
    node n1(30, 1);    
    node n2(40, 2);    
    node n3(50, 3);    
    node n4(60, 4);    
    node n5(70, 5);    

    vector<node> vec{n1, n2, n3, n4, n5}; 
    make_heap(vec.begin(), vec.end(), greaters()); 
    while (vec.size()>0){
        cout<<vec.front().id<<" "; 
        // pop_heap()之后， 这还是个heap！，所以你就不用make heap 了。
        pop_heap(vec.begin(), vec.end(), greaters());       
        //  【注意】你需要pop_back， 因为pop_heap 不会自动把最后一个给弄出去！
        vec.pop_back();         
        
        // 注意， 只要当前的是heap，那么你可以push_heap 来接着构建heap
        a.push_back(1);
    push_heap(a.begin(), a.end());
    }
    return 0;
}

========================================================================

Advanced Data Structures

========================================================================

  1. Represent a graph: use an adjacency matrix, implemented by sparcematrices in armadillo

    • Armadillo: ease of use, beats eigen.

  2. key to prerformace: 1. closeness in memory, hash table spreads 2. lack of conditional statements

  3. copying is not a huge deal until you're super concerned

  4. Sometimes, when you have complicated referencing issues, you can store data in lists and let objects find a way to index them.

  5. queues, locks for multi-threading. Don't start with multi-threading.

========================================================================

Common Mistakes

========================================================================

Math

  1. % is remainder, not modulo. -5 mod 3 = 1, -5 % 3 = -2. % always the same sign as the divisor, mod same sign as the dividend
  2. int range is -2^31 <= n <= 2^31 -1: -int(min) = -(-21....48), not representable in int.

vector

  1. max of vector: std::max_element(vec.begin(), vec.end())
  2. referencing auto itr = sum.back().end(); gives seg fault, or heap buffer flow
  3. return a:x * c: : precedes *.
  4. std::find(itr, itr2, num). Map: map.find(key)

queue, deque

  1. queue::pop(), queue::push()
    • queue::top()
  2. deque::pop_front(), deque::pop_back(), deque::push_front()
    • dequeue::front(), deque::back()

Rico's wiki

Home | Copyright © 2021 ricojia

⚠️ **GitHub.com Fallback** ⚠️