Optimized C++

Chapter 9. Optimize Searching and Sorting

There’s a way to do it better—find it.

Thomas A. Edison (1847–1931), American inventor and optimizer

C++ programs do a lot of searching. From programming language compilers to web browsers, from list controls to databases, many repeated activities have a search at the bottom of some inner loop. Searching comes up frequently on lists of hot functions in my experience. It is thus worthwhile to devote special attention to searching efficiently.

This chapter looks at searching in tables through the optimizer’s eye. I use searching as an example of a general process that a developer can use to approach the optimization task, by breaking down an existing solution into its component algorithms and data structures, then looking at each of these for opportunities to improve performance. I also evaluate some specific search methods to demonstrate the optimization process.

Most C++ developers know that the standard library container std::map can be used for looking up values that are associated with an index number or alphanumeric key string. Such associations are called key/value tables. They create a map from keys to values, hence the name of the container. Developers who know std::map remember that its performance is good in a big-O sense. This chapter explores ways to optimize the basic map-based search.

Fewer developers know that the C++ standard library’s <algorithm> header contains several iterator-based algorithms that can search sequence ...