Financial Instrument Pricing Using C++, 2nd Edition

CHAPTER 18STL Algorithms Part II

18.1 Introduction and Objectives

In this chapter we continue with our discussion of the STL algorithms that we introduced in Chapter 17. In particular, we discuss the following major algorithm categories:

• Mutating algorithms: these algorithms change the order of elements (and not their values) in a range by assigning and swapping their values in some way. Example: reverse the order of elements in a container.
• Sorting algorithms: these are special mutating algorithms because they change the order of elements in a range. When choosing a particular sorting algorithm we must take complexity into account. Example: sort a container using heapsort. This algorithm has O(nlog n) complexity.
• Sorted range algorithms: sorted range algorithms require that the range on which they operate be sorted according to their sorting criterion. Example: process the sorted union of two ranges.
• Numeric algorithms: these algorithms combine numeric elements in different ways. Although this category only contains four algorithms they can be used by providing them with many kinds of functions, thus allowing developers to customise them. Example: compute the inner product of two ranges or the inner product of two containers.

As in Chapter 17, we discuss the intent of each category and we describe its algorithms using compact examples. We also show the output produced by each algorithm in order to help us understand the code. This chapter can be used as a reference; you ...