Standard Template Library Programmer's Guide

power functions.

template <class T, class Integer>
inline T power(T x, Integer n);
template <class T, class Integer, class MonoidOperation>
T power(T x, Integer n, MonoidOperation op);

Description

Power is generalized exponentiation: it raises the value x to the power n, where n is a non- negative integer.

The first version of power returns x raised to the nth power; that is, it returns x * x … * x , where x is repeated n times. [1] If n == 0, then it returns identity_element(multiplies<T>()).

The second version of power is just like the first except that it uses an arbitrary Monoid Operation instead of multiplies<T>, returning identity_element (op) when n == 0.

Important note: power does not assume that multiplication is commutative, but it does rely crucially on the fact that multiplication is associative. If you have defined * or MonoidOperation to be a non-associative operation, then powerwill give you the wrong answer. [2]

Definition

Defined in the standard header numeric, and in the nonstandard backward-compatibility header algo.h. This function is an SGI extension; it is not part of the C++ standard.

Requirements on types

For the first version:

• multiplies<T> is a model of Monoid Operation.

• Integer is an integral type.

For the second version:

• MonoidOperation is a model of Monoid Operation.

• T is MonoidOperation's argument type.

• n is an integral type.

Preconditions

• n >= 0.

Complexity

The number of multiplications (or, in the case of the second version, the number of applications of MonoidOperation ) is lg(n) + nu(n) where lg is the base 2 logarithm and nu(n) is the number of 1s in the binary representation of n. [3]

Example

int main() {
 cout << '2 ** 30 = ' << power(2, 30) << endl;
}

Notes

[1] This is a conceptual description of what power's return value is; it is not how power is actually implemented. If power were implemented that way then it would require n-1 multiplications, which would be grossly inefficient. Power is implemented using the 'Russian peasant algorithm', which requires only O(log n) multiplications. See section 4.6.3 of Knuth (D. E. Knuth, The Art of Computer Programming. Volume 2: Seminumerical Algorithms, Addison-Wesley, 1981) for a discussion.

[2] See the Monoid Operation requirements for a discussion of associativity.

[3] This is in fact not the minimum possible number of multiplications: it is possible to compute the fifteenth power of x using only five multiplications, but power(x, 15) uses six.

See also

Monoid Operation, multiplies, plus

Function Objects

Introduction

Category: functors

Component type: overview

Summary

A Function Object, or Functor (the two terms are synonymous) is simply any object that can be called as if it is a function. An ordinary function is a function object, and so is a function pointer; more generally, so is an object of a class that defines operator() .

Description

The basic function object concepts are Generator, Unary Function, and Binary Function: these describe, respectively, objects that can be called as f(), f(x), and f(x,y). (This list could obviously be extended to ternary function and beyond, but, in practice, no STL algorithms require function objects of more than two arguments.) All other function object concepts defined by the STL are refinements of these three.

Function objects that return bool are an important special case. A Unary Function whose return type is bool is called a Predicate, and a Binary Function whose return type is bool is called a Binary Predicate.

There is an important distinction, but a somewhat subtle one, between function objects and adaptable function objects. [1] In general, a function object has restrictions on the type of its argument. The type restrictions need not be simple, though: operator() may be overloaded, or may be a member template, or both. Similarly, there need be no way for a program to determine what those restrictions are. An adaptable function object, however, does specify what the argument and return types are, and provides nested typedefs so that those types can be named and used in programs. If a type F0 is a model of Adaptable Generator, then it must define F0::result_type. Similarly, if F1 is a model of Adaptable Unary Function then it must define F1::argument_type and F1::result_type, and if F2 is a model of Adaptable Binary Function then it must define F2::first_argument_type, F2::second_argument_type, and F2::result_type. The STL provides base classes unary_function and binary_function to simplify the definition of Adaptable Unary Functions and Adaptable Binary Functions. [2]

Adaptable function objects are important because they can be used by function object adaptors: function objects that transform or manipulate other function objects. The STL provides