C++ Tips
*********************************************

.. _lower_upper_bound:

lower_bound and upper_bound
===================================
STL provides binary search functions `std::lower_bound` and `std::upper_bound`.

If you have multiple elements in the range `[first, last)` where no value equals the value you are searching for, `lower_bound` and `upper_bound` return the same iterator. If there is value euqal to what you are searching for, there will be difference.

Assuming you want to insert a value to a **sorted** array, `lower_bound` returns the left-most position you can insert the value into, and `upper_bound` return the right-most position you can insert.

.. figure:: lbub.png
  :align: center
  :name: bound

Let’s assume we use them to search for 2 in the following collections. The arrows show what iterators the two would return:

.. figure:: lower_upper_bound.png
  :align: center
  :name: lower and upper bound

lower_bound result can be equal or greater than the given key K, but ``upper_bound result is always greater than K``.

In Java, ``floorEntry()`` returns a key-value mapping associated with ``the greatest key less than or equal to the given key``, or null if there is no such key.
In C++'s ``map``, the equivalent code should be like:

.. code-block:: c++

  auto it = prev(map.upper_bound(key));

Also, `std::equal_range` will return both the lower and upper bound in a pair, in a single call.

STL ``std::map`` and ``std::set`` have two member functions with the same names.

.. note::

  The two functions only require the first two parameters are *forward iterators* and the value is comparable, so it is fine to apply to unsorted sequence if necessary.


.. literalinclude:: lower_bound_test.cpp
  :language: c++
  :linenos:
  :lines: 14-20

.. note::

  They can also be applied to ``std::list``.

.. literalinclude:: lower_bound_test.cpp
  :language: c++
  :linenos:
  :lines: 24-26

Reference:

  - Longest Increasing Subsequence(LIS)(:numref:`dp_lis`)
  - Question: Maximum Profit in Job Scheduling(:numref:`dp_max_profit_job_scheduling`)
  - https://www.geeksforgeeks.org/java-util-treemap-floorentry-floorkey-java/

.. only:: html

  - https://en.cppreference.com/w/cpp/algorithm/lower_bound
  - dynamic dispatch, vpointer and virtual table: https://blog.csdn.net/luanfenlian0992/article/details/118771472

Virtual Function
=====================

A virtual function is a member function in the base class that we expect to redefine in derived classes.

Basically, a virtual function is used in the base class in order to ensure that the function is overridden. This especially applies to cases where a pointer of base class points to an object of a derived class.


.. image:: cpp-virtual-function.png
  :width: 300

.. only:: html

  - https://pabloariasal.github.io/2017/06/10/understanding-virtual-tables/


shared_ptr unique_ptr weak_ptr
=================================

unique_ptr
^^^^^^^^^^^^^^^^^^^

- std::unique_ptr is a small, fast, move-only smart pointer for managing resources with exclusive-ownership semantics.
- By default, resource destruction takes place via delete, but custom deleters can be specified. Stateful deleters and function pointers as deleters increase the size of std::unique_ptr objects.
- Converting a std::unique_ptr to a std::shared_ptr is easy.

shared_ptr
^^^^^^^^^^^^^^^^^^^

- std::shared_ptrs offer convenience approaching that of garbage collection for the shared lifetime management of arbitrary resources.
- Compared to std::unique_ptr, std::shared_ptr objects are typically twice as big, incur overhead for control blocks, and require atomic reference count manipulations.
- Default resource destruction is via delete, but custom deleters are supported. The type of the deleter has no effect on the type of the std::shared_ptr.
- Avoid creating std::shared_ptrs from variables of raw pointer type.

.. image:: shared_ptr.png
  :width: 300

weak_ptr
^^^^^^^^^^^^^^^^^^^

- Use std::weak_ptr for std::shared_ptr-like pointers that can dangle.
- Potential use cases for std::weak_ptr include caching, observer lists, and the prevention of std::shared_ptr cycles.

.. image:: cycle.jpg
  :width: 300

.. only:: html

  - https://www.oreilly.com/library/view/effective-modern-c/9781491908419/ch04.html
  - https://www.nextptr.com/tutorial/ta1358374985/shared_ptr-basics-and-internals-with-examples
  - https://www.modernescpp.com/index.php/std-weak-ptr