oop.md

• inheritance
  • unless the destructor ~Base is marked virtual, the destructor ~Child won't be called on delete base where base is of type Child*.
• algorithm
  • lower_bound(first, last, value) and upper_bound(first, last, value)

    set<int> s { 1, 3, 6, 10, 13, 32, 45 };
    // first element x such that x >= 13
    s.lower_bound(13); // 13
    // first element x such that x > 13
    s.upper_bound(13); // 32

    note that we use the set method lower_bound not std::lower_bound because for non random access iterators such those provided by set and other associative containers makes the algorithm (binary search) used by std::lower_bound do number of iterator increments that is linear in N so the member lower_bound functions should be preferred.
• containers:
  • iterator adaptors:
    • back_inserter(Container) needs a container with push_back method
    • front_inserter(Container) needs a container with push_front method
    • inserter(Container, Container::iterator) needs a container with insert method
  • method size() in some containers (e.g. list) is NOT $O(1)$ but the method empty() in all containers is $O(1)$
  • sequence container: vector, deque, list
    • all sequence container except array has a count-value constructor

      vector<int> v(100, 5) // declare v as 100 5's vector

    • vector
      • random access $O(1)$
      • random access iterator
      • insertion/deletion at end $O(1)$
      • insertion/deletion elsewhere $O(n)$
    • deque
      • random access $O(1)$ BUT slower than vector
      • random access iterator
      • insertion/deletion at begin/end $O(1)$
      • insertion/deletion elsewhere $O(n)$
      • elements are NOT stored contiguously
    • list
      • random access $O(n)$
      • bidirectional iterator
      • insertion/deletion at begin/end/known pos $O(1)$]
      • method merge merges two sorted lists
        • does nothing if other refers to the same objects as *this
        • if *this or other is not sorted, the behavior is undefined
      • method splice moves element(s) from another list

            list<int> x { 1, 5, 2, 6 };
            list<int> y { 3, 7, 4 };
            x.splice(x.end(), y);
            // move all y elements to th end of x
            x.splice(x.begin(), y, y.begin());
            // move the y element at y.begin() to the front of x
            x.splice(x.begin(), y, y.begin(), y.end());
            // equivalent to x.splice(x.begin(), y)

      • list method unique removes consecutive duplicate elements

            list<int> x { 1, 2, 1, 1, 3, 3 };
            x.unique();
            // x is now [ 1 2 1 3 ]

  • associative container: set/map (unimodal) and multiset/multimap (multimodal)
    • search, removal, and insertion is $O(log(n))$
    • ordered and by default is std::less so elements are sorted ascendingly
    • bidirectional iterator
    • set: ordered set of unique objects
    • map: ordered set of key-value pairs with unique keys
    • multiset: ordered collection of objects, multiples are allowed
    • multimap: ordered collection of key-value pairs, multiples are allowed
  • unordered associative container: unordered_set/unordered_map (unimodal) and unordered_multiset/unordered_multimap (multimodal)
    • search, removal, and insertion is on average $O(1)$ and $O(n)$ at worst.
    • bidirectional iterator
    • unordered_set: unordered set of unique objects, hashed by keys
    • unordered_map: unordered set of key-value pairs with unique keys, hashed by keys
    • unordered_multiset: unordered collection of objects, multiples are allowed, hashed by keys
    • unordered_multimap: unordered collection of key-value pairs, multiples are allowed, hashed by keys
  • container adapters stack/queue/priority_queue
    • do not support iterators
    • method push/pop is common in them
    • stack container:
      • lifo ordering (last in first out)
    • queue containr
      • access at front() and back()
      • fifo ordering (first in first out)
    • priority queue
      • insertion order is irrelevant
      • top() is the element such that for every element x in the container Compare(x, top()) is true.
      • By default Compare is std::less so top() is the largest element in the container.
• UML
  • C++ access modifier correspondence
    • private: -
    • protected: #
    • public: +
  • data type notation

    - id: int
    # width: double
    # length: double
    

  • parameter and return type notation

    + setWidth(w: double): void
    + getWidth(): double
    

  • no return type for constructors or destructors