Modern C++ Programming Cookbook Notes 5: Standard Library Containers, Algorithms and Iterators

Chapter 5 Standard Library Containers, Algorithms and Iterators

5.1 Using vector as a default container

• Use std::vector as the default container unless there is a good reason to use another one. That’s because std::vector has many benefits, among which it’s compatible with C-like arrays (just invoking data() method to get the address of the first element)
• One thing worth noting is that the capacity expansion sounds time-consuming, but actually each element can be regarded as moved just once due to the exponential expansion policy. Clearly speaking, you have four elements, here comes the fifth one and it needs to find a larger space, which can contain eight elements. So we can say space for another four elements is acquired after a move of four elements, which is a one-on-one relationship.

5.2 Using bitset for fixed-size sequences of bits

• std::bitset can be used for a fixed-size sequence of bits, whose template parameter is the size.

• std::bitset can be converted from integral type and string with its constructors and converted to them with its methods:

  c++

  std::bitset<8> b2{ 10 };  // [0,0,0,0,1,0,1,0]
  std::bitset<8> b3{ "1010"s };  // [0,0,0,0,1,0,1,0]
  
  b2.to_ulong();  // 10
  b3.to_string();  // "00001010"

• Bits in std::bitset can be tested by some methods like any(), all(), none(), test() and so on, and can be modified by something like flip(), set() and reset(). Also, std::bitset supports operation like |, & and ^.

5.3 Using vector<bool> for variable-size sequences of bits

• std::vector<bool> is essentially a specialization of std::vector<T> with speed and space optimization: it store a single bit instead of a bool value (1 byte) for each element.

  However, it also brings some drawbacks like the element cannot be referenced, and its iterator cannot be used as a forward iterator:

  c++

  std::vector<bool> bv;
  bv.resize(10);
  auto& bit = bv[0];      // error

• If you don’t want such optimization, std::deque<bool> might be a good choice.

5.4 Finding elements in a range

• STL Algorithms provides many generic functions to find elements in a range, most of which has return value of the end iterator to indicate the not found result.

5.5 Sorting a range

• When using sorting function provided by STL Algorithms, pass in a functor to customize your own compare function:

  c++

  std::vector<int> v{3, 13, 5, 8, 1, 2, 1};
  std::sort(v.begin(), v.end());  // v = {1, 1, 2, 3, 5, 8, 13}
  std::sort(v.begin(), v.end(), std::greater<>());  // v = {13, 8, 5, 3, 2, 1 ,1}

• std::is_sort() can be used to check whether a range of elements is already sorted.

• Some containers like std::list provide sort() as their methods, which should be preferred to the std::sort().

5.6 Initializing a range

• STL Algorithms also provide a series of functions to fill (initialize) elements in a range. Most basically, we can use std::fill to fill a range with a given value and std::generate to fill a range with the return value of a given callable. (The callable accepts no parameter. If you want to use the original value in the container, resort to std::transform)

  And also, we can use std::iota to fill a range with sequentially increasing values (actually it’s the operator++ that gets invoked).

5.7 Using set operations on a range

• Note that set operations like std::set_union, std::set_intersection, std::set_difference and so on should be used on sorted containers (not necessarily a set, vector is ok as long as it’s sorted)

5.8 Using iterators to insert new elements in a container

• When using some STL Algorithms like std::fill_n to insert a range of elements into a container, we couldn’t use some common iterators. For example, we couldn’t use the iterator returned by std::begin(), because the following fill operation will overwrite the existing elements rather than insert. And we also couldn’t use the iterator returned by std::end(), because the compiler will complain something about out of range error.

  Yep, we can resort to the insert iterators, i.e. iterators returned by std::back_inserter(), std::front_inserter() and std::inserter().

  c++

  std::vector<int> v{ 1, 2, 3, 4, 5 };
  std::fill_n(std::inserter(v, std::next(v.begin(), 2)), 3, 0);
  // 1, 2, 0, 0, 0, 3, 4, 5

• They are all output iterators and increasing or dereferencing these iterators actually do nothing. However, upon assignment, they will invoke some methods of the container separately:

  • push_back() for std::back_insert_iterator,
  • push_front() for std::front_insert_iterator,
  • insert() for std::insert_iterator.

  So this places some limits to containers that insert iterators can work on. e.g. std::back_insert_iterator doesn’t apply to std::forward_list because it doesn’t have push_bakc() method. For the same reason. std::front_insert_iterator doesn’t apply to std::vector.

• Note that these insert iterators are preferred when inserting a range of elements instead of a single one. For the latter situation, push_back(), push_front() and insert() methods are certainly the first choice.

5.9 Writing your own random access iterator

• From input iterators to random-access iterators, more functionalities are supported:
  • Common requirements of all iterators: copy-constructible, copy-assignable, destructible and can be incremented.
  • Input iterators: support equality comparison and can be dereferenced as rvalue.
  • Output iterators: can be dereferenced as lvalue.
  • Forward iterators: can be default constructed and support multi-pass iteration.
  • Bidirectional iterators: can be decremented.
  • Random-access iterator: support arithmetic operation, offset dereference operator ([]) and inequality comparison (<, >= and so on).
• For more details, refer to the iterator doc.

5.10 Container access with non-member fucntions

• Non-member functions about the STL container access don’t only include std::begin() and std::end(), but also std::data(), std::size() and std::empty() as of C++17.

• The implement logic is simple: if the container has methods of begin() and end(), just invoke them. If it’s not the case, implement a specialization for it (such as the C-style array)

  c++

  template<class C>
  constexpr auto inline begin(C& c) -> decltype(c.begin()) {
      return c.begin();
  }
  
  template<class T, std::size_t N>
  constexpr T* inline begin(T (&array)[N]) {
      return array;
  }

Link

• https://subscription.packtpub.com/book/programming/9781786465184/5