1.4. C++ Tips

1.4.1. 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.

../_images/lbub.png

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

../_images/lower_upper_bound.png

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:

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.

1  const vector<int> raw = {5, 3, 4, 1};
2  lower = lower_bound(raw.begin(), raw.end(), 4);
3  EXPECT_TRUE(lower == next(raw.begin(), 2));
4  lower = lower_bound(raw.begin(), raw.end(), 6);
5  EXPECT_TRUE(lower == raw.end());
6  lower = lower_bound(raw.begin(), raw.end(), 0);
7  EXPECT_TRUE(lower == raw.begin());

Note

They can also be applied to std::list.

1  const list<int> data = {1, 2, 2, 3, 4, 4, 4, 4, 5, 6, 7, 9, 9, 10};
2  auto lower = lower_bound(data.begin(), data.end(), 4);
3  EXPECT_TRUE(lower == next(data.begin(), 4));

Reference:

1.4.2. 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.

../_images/cpp-virtual-function.png

1.4.3. shared_ptr unique_ptr weak_ptr

1.4.3.1. 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.

1.4.3.2. 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.

../_images/shared_ptr.png

1.4.3.3. 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.

../_images/cycle.jpg