Linear Search Algorithms

The most basic linear search is the find function. It searches a range of read iterators for a value. It returns an iterator that refers to the first matching element in the range. If find cannot find a match, it returns a copy of the end iterator. Listing 43-1 shows an example of its use. The program reads integers into a vector, searches for the value 42, and if found, changes that element to 0.

Listing 43-1.  Searching for an Integer

#include <algorithm>
#include <iostream>
 
#include "data.hpp"
 
int main()
{
  intvector data{};
  read_data(data);
  write_data(data);
  auto iter(std::find(data.begin(), data.end(), 42));
  if (iter == data.end())
    std::cout << "Value 42 not found
";
  else
  {
    *iter = 0;
    std::cout << "Value 42 changed to 0:
";
    write_data(data);
  }
}

Listing 43-2 shows the data.hpp file, which provides a few utilities for working with vectors of integers. Most of the examples in this Exploration will #include this file.

Listing 43-2.  The data.hpp File to Support Integer Data

#ifndef DATA_HPP_
#define DATA_HPP_
 
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
 
/// Convenient shorthand for a vector of integers.
typedef std::vector<int> intvector;
 
/// Convenient shorthand for an intvector's iterator.
typedef intvector::iterator intvec_iterator;
 
/// Read a series of integers from the standard input into @p data,
/// overwriting @p data in the process.
/// @param[in,out] data a vector of integers
inline void read_data(intvector& data)
{
  data.clear();
  data.insert(data.begin(), std::istream_iterator<int>(std::cin),
                            std::istream_iterator<int>());
}
 
/// Write a vector of integers to the standard output. Write all values on one
/// line, separated by single space characters, and surrounded by curly braces,
/// e.g., { 1 2 3 }.
/// @param data a vector of integers
inline void write_data(intvector const& data)
{
  std::cout << "{ ";
  std::copy(data.begin(), data.end(),
            std::ostream_iterator<int>(std::cout, " "));
  std::cout << "}
";
}
 
#endif

A companion to the find algorithm is find_if. Instead of searching for a matching value, find_if takes a predicate function or function object (from now on, I will write functor to indicate a free function, a function object, or a lambda). It calls the functor for every element in the range, until the functor returns true (or any value that can be converted automatically to true, such as a nonzero numeric value). If the functor never returns true, find_if returns the end iterator.

Every search algorithm comes in two forms. The first compares items using an operator (== for linear searches and < for binary searches). The second form uses a caller-supplied functor instead of the operator. For most algorithms, the functor is an additional argument to the algorithm, so the compiler can distinguish the two forms. In a few cases, both forms take the same number of arguments, and the library uses distinct names, because the compiler could not otherwise distinguish between the two forms. In these cases, the functor form has _if added to the name, such as find and find_if.

Suppose you want to search a vector of integers, not for a single value, but for any value that falls within a certain range. You can write a custom predicate to test a hard-coded range, but a more useful solution is to write a general-purpose functor that compares an integer against any range. Use this functor by supplying the range limits as argument to the constructor. Is this best implemented as a free function, function object, or lambda? ________________________ Because it must store state, I recommend writing a functor.

A lambda is good when you need to search for specific values, but a functor is easier if you want to write a generic comparator that can store the limits. Write the intrange functor. The constructor takes two int arguments. The function call operator takes a single int argument. It returns true, if the argument falls within the inclusive range specified in the constructor, or false, if the argument lies outside the range.

Listing 43-3 shows my implementation of intrange. As a bonus, I decided to allow the caller to specify the range limits in either order. That way, I neatly avoid the issue of error-checking and error-handling, if the caller tries to use a meaningless range, such as [10, 0].

Listing 43-3.  Functor intrange to Generate Integers in a Certain Range

#ifndef INTRANGE_HPP_
#define INTRANGE_HPP_
 
#include <algorithm>
 
/// Check whether an integer lies within an inclusive range.
class intrange
{
public:
  inline intrange(int low, int high);
  inline bool operator()(int test) const;
private:
  int const low_;
  int const high_;
};
 
/// Construct an integer range.
/// If the parameters are in the wrong order,
/// swap them to the right order.
/// @param low the lower bound of the inclusive range
/// @param high the upper bound of the inclusive range
inline intrange::intrange(int low, int high)
: low_{std::min(low, high)}, high_{std::max(low, high)}
{}
 
/// Check whether a value lies within the inclusive range.
/// @param test the value to test
inline bool intrange::operator()(int test)
const
{
  return test >= low_ and test <= high_;
}
 
#endif

The < operator form of the std::min function takes two arguments and returns the smaller. The std::max function also takes two arguments and returns the larger. Both functions compare their arguments with the < operator. As with other algorithms, you can call a functor form of both functions, passing a comparison functor to use instead of the < operator. The types of the first two arguments must be the same, and the return type matches that of the arguments. The mixmax function returns a std::pair (introduced in Exploration 15) of the minimum and maximum.

Write a test program that reads integers from the standard input and then uses find_if and intrange to find the first value that lies within the range [10, 20]. Compare your solution with mine in Listing 43-4.

Listing 43-4.  Using find_if and intrange to Find an Integer That Lies Within a Range

#include <algorithm>
#include <iostream>
 
#include "data.hpp"
#include "intrange.hpp"
 
int main()
{
  intvector data{};
  read_data(data);
  write_data(data);
  auto iter(std::find_if(data.begin(), data.end(), intrange{10, 20}));
  if (iter == data.end())
    std::cout << "No values in [10,20] found
";
  else
    std::cout << "Value " << *iter << " in range [10,20].
";
}

A few of the following examples generate random data and apply algorithms to the data. The standard library has a rich, complicated library for generating pseudo-random numbers. The details of this library are beyond the scope of this book. Only the mathematically adventuresome should crack open the details of the <random> header. For your convenience, Listing 43-5 presents the randomint.hpp header, which defines the randomint class, which generates random integers in a caller-supplied range.

Listing 43-5.  Generating Random Integers

#ifndef RANDOMINT_HPP_
#define RANDOMINT_HPP_
 
#include <algorithm>
#include <random>
 
/// Generate uniformly distributed random integers in a range.
class randomint
{
public:
  typedef std::default_random_engine::result_type result_type;
 
  /// Construct a random-number generator to produce numbers in the range [<tt>low</tt>, <tt>high</tt>].
  /// If @p low > @p high the values are reversed.
  randomint(result_type low, result_type high)
     // std::random_device uses a system-dependent generation of randomness
      // to seed the pseudo-random-number generator.
  : prng_{std::random_device{}()},
    distribution_{std::min(low, high), std::max(low, high)}
  {}
 
  /// Generate the next random number generator.
  result_type operator()()
  {
     return distribution_(prng_);
  }
 
private:
  // implementation-defined pseudo-random-number generator
  std::default_random_engine prng_;
  // Map random numbers to a uniform distribution.
  std::uniform_int_distribution<result_type> distribution_;
};
#endif

The search function is similar to find, except it searches for a matching sub-range. That is, you supply an iterator range to search and an iterator range to match. The search algorithm looks for the first occurrence of a sequence of elements that equals the entire match range. Listing 43-6 shows a silly program that generates a large vector of random integers in the range 0 to 9 and then searches for a sub-range that matches the first four digits of π.

Listing 43-6.  Finding a Sub-range That Matches the First Four Digits of π

#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <iterator>
#include <vector>
 
#include "data.hpp"
#include "randomint.hpp" 
 
int main()
{
  intvector pi{ 3, 1, 4, 1 };
  intvector data(10000);
  // The randomint functor generates random numbers in the range [0, 9]. 
 
  std::generate(data.begin(), data.end(), randomint{0, 9});
 
  auto iter(std::search(data.begin(), data.end(), pi.begin(), pi.end()));
  if (iter == data.end())
    std::cout << "The integer range does not contain the digits of pi.
";
  else
  {
    std::cout << "Easy as pi: ";
    std::copy(iter, iter+pi.size(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << '
';
  }
}

Binary Search Algorithms

The map container stores its elements in sorted order, so you can use any of the binary search algorithms, but map also has member functions that can take advantage of access to the internal structure of a map and, so, offer improved performance. Thus, the binary search algorithms are typically used on sequential containers, such as vector, when you know that they contain sorted data. If the input range is not properly sorted, the results are undefined: you might get the wrong answer; the program might crash; or something even worse might happen.

The binary_search function simply tests whether a sorted range contains a particular value. By default, values are compared using only the < operator. Another form of binary_search takes a comparison functor as an additional argument to perform the comparison.

The lower_bound function is similar to binary_search, except it returns an iterator. The iterator points to the first occurrence of the value, or it points to a position where the value belongs if you want to insert the value into the range and keep the values in sorted order. The upper_bound function is similar to lower_bound, except it returns an iterator that points to the last position where you can insert the value and keep it in sorted order. If the value is found, that means upper_bound points to one position past the last occurrence of the value in the range. To put it another way, the range [lower_bound, upper_bound]) is the sub-range of every occurrence of the value in the sorted range. As with any range, if lower_bound == upper_bound, the result range is empty, which means the value is not in the search range.

Listing 43-7 shows a variation on Listing 43-1, sorting the integer vector and searching for a value using lower_bound to perform a binary search.

Listing 43-7.  Searching for an Integer Using Binary Search

#include <algorithm>
#include <iostream>
 
#include "data.hpp"
 
int main()
{
  intvector data{};
  read_data(data);
  std::sort(data.begin(), data.end());
  write_data(data);
  intvec_iterator iter{std::lower_bound(data.begin(), data.end(), 42)};
  if (iter == data.end())
    std::cout << "Value 42 not found
";
  else
  {
    *iter = 0;
    std::cout << "Value 42 changed to 0:
";
    write_data(data);
  }
}

Only two lines changed: adding one extra line to sort the vector and changing find to lower_bound. To better understand how lower_bound and upper_bound really work, it helps to write a test program. The program reads some integers from the user into a vector, sorts the vector, and clears the I/O state bits on the standard input (std::cin.clear()), so you can enter some test values. The program then repeatedly asks for integers from the user and searches for each value using lower_bound and upper_bound. To help you understand exactly what these functions return, call the distance function to determine an iterator’s position in a vector, as follows:

intvec_iterator iter{std::lower_bound(data.begin(), data.end(), 42)};
std::cout << "Index of 42 is " << std::distance(data.begin(), iter) << '
';

The distance function (declared in <iterator>) takes an iterator range and returns the number of elements in the range. The return type is the iterator’s difference_type, which is just an integer type, although the exact type (e.g., int or long int) depends on the implementation.

Write the test program. Then run the program with the following sample input:

9 4 2 1 5 4 3 6 2 7 4

What should the program print as the sorted vector?

Fill in Table 43-1 with the expected values for the lower and upper bounds of each value. Then run the program to check your answers.

Compare your test program with mine in Listing 43-8.

Listing 43-8.  Exploring the lower_bound and upper_bound Functions

#include <algorithm>
#include <iostream>
#include <vector>
 
#include "data.hpp"
 
int main()
{
  intvector data{};
  read_data(data);
  std::sort(data.begin(), data.end());
  write_data(data);
 
  std::cin.clear();
  int test{};
  while (std::cin >> test)
  {
    intvec_iterator lb{std::lower_bound(data.begin(), data.end(), test)};
    intvec_iterator ub{std::upper_bound(data.begin(), data.end(), test)};
    std::cout << "lower bound = " << std::distance(data.begin(), lb) << '
' <<
                 "upper bound = " << std::distance(data.begin(), ub) << '
';
  }
}

When you want the lower bound and upper bound of the same range, call equal_range, which returns a pair of iterators. The first member of the pair is the lower bound, and the second is the upper bound.

Other useful linear functions include count, which takes an iterator range and value and returns the number of occurrences of the value in the range. Its counterpart count_if takes a predicate instead of a value and returns the number of times the predicate returns true.

Three more algorithms have a common pattern. They apply a predicate to every element in a range and return a bool.

• all_of(first, last, predicate) returns true if predicate(element) returns true for every element in the range [first, last].
• any_of(first, last, predicate) returns true if predicate(element) returns true for at least one element in the range [first, last].
• none_of(first, last, predicate) returns true if predicate(element) returns false for every element in the range [first, last].

You have already seen how min returns the minimum of two values. It has a partner, min_element, which takes an iterator range and returns the iterator for the minimum value in the range. Ditto for max_element. You can guess what minmax_element returns: a pair of iterators for the minimum and maximum values in the range. All three come in the usual overloaded forms: one uses the < operator, and the other takes an additional argument for a comparison predicate.

Unlike all the other algorithms, min, max, and minmax also have a form that takes a curly brace–enclosed list of values and returns the minimum, maximum, or both of those values. These are the only algorithms that take a single curly brace–enclosed list as a single argument. The only constraint is that all the values must have the same type. For example, the following

int a{1}, b{2}, c{3};
int smallest{ std::min({ a, b, c }) };

is equivalent to the traditional style of using iterators

int a{1}, b{2}, c{3};
std::vector<int> tmp{ a, b, c};
int smallest{ *std::min_element(tmp.begin(), tmp.end()) };