Programming Language Concepts Using C and C++/Parameterized Types

Achieving reuse through inheritance may at times lead to an explosion in the number of classes. Consider defining stacks of different types. Using the inheritance approach, we would start out with defining an abstract class containing the attributes common to all stacks and get people to derive their specialized stack classes from this class. Problem with this approach is—since operation signatures are type dependent—not much can be reused.

class AbstractStack { virtual bool empty(void) const = 0; } // end of class AbstractStack class StdntStk : public AbstractStack { public: bool peek(Student&) const; bool pop(Student&); void push(Student); virtual bool empty(void) const; ... private: ... } // end of class StdntStk

A stack of Shape objects using a similar implementation technique would mean all occurrences of Student must be replaced with Shape, which leaves very little room for reuse. Way out of this is defining a stack of something that can be interpreted as a stack of anything. In C/C++, that something is void*; in Java and C#, it is the root class Object.

Example: Genericness in pre-1.5 Java.

public interface IStack { public Object peek() throws StackEmpty; public Object pop() throws StackEmpty; public void push(Object newItem); public boolean isEmpty(); } // end of interface IStack public class GenericStack implements IStack { public Object peek() throws StackEmpty { ... } public Object pop() throws StackEmpty { ... } public void push(Object newItem) { ... } public boolean isEmpty() { ... } ... ... } // end of class GenericStack

In this pre-1.5 Java implementation we can create and use stacks of various types without having to rewrite the functionality in different classes. This solution has a serious flaw, though. Users of GenericStack are responsible for correct use of the class. Errors such as pushing a Shape onto a stack of Students are tolerated by the compiler and cannot be caught before run-time. After all, both classes are derived from Object and their objects are in that aspect alike.

So we need to take another step for achieving reuse without sacrificing type safety. The answer is provided by introducing a new feature into the language: parameterized types. Using parameterized types we can get higher levels of reuse by collapsing a base class and a number of derived classes into a single class without compromising type safety. Instead of having an abstract class and various specialized classes deriving from this abstract class, we now have a single parameterized class.

Example: Generic classes in Java.

public interface IStack<V> { public V peek() throws StackEmpty; public V pop() throws StackEmpty; public void push(V newItem); public boolean isEmpty(); } // end of interface IStack<V> public class Stack<V> implements IStack<V> { public V peek() throws StackEmpty { ... } public V pop() throws StackEmpty { ... } public void push(V newItem) { ... } public boolean isEmpty() { ... } ... ... } // end of class Stack<V>

Replacing inheritance in the first scenario with parameterized types in the final scenario might make you think parameterized types and inheritance are alternatives to each other. That would be wrong, though. These two features are actually complementary reuse tools: while inheritance is used to express the is-a relation between classes found at different levels of the class hierarchy, parameterized types are used to group classes found at the same level. In other words, inheritance—since it adds a new level—is "vertical", whereas parameterized types—since they work by collapsing classes at the same level—are "horizontal".

Complex Imaginary Integer Natural Rational Real ComplexVector, IntegerVector, RealVector, ... ...

Without inheritance and parameterized types we have a collection of types that can be related to each other with composition and association.

Object Complex Real Rational Integer Natural Imaginary Vector<V>

Thanks to inheritance [and polymorphism] we organize these types into a hierarchy that better reflects our perception of them. After all, aren't real numbers actually complex numbers with no imaginary part? Aren't rational numbers real numbers that can be expressed as the ratio of two integers? ... This is further strengthened by the use of parameterized types. In math, we never speak of vectors with different content type as different concepts; there is only one definition for vector.

Note that the use of a collection type in the previous presentation is not by chance. Genericness is generally regarded as parameterization of collection types. But many times we need to reuse the functionality of a single function working on a parameterized type. Generic algorithms—such as accumulate, count_if, for_each, inner_product, min_element, random_shuffle, and so on—implemented as part of the standard library are examples to this.

Template Compilation Models edit

Once a parametric type is implemented it is typically used by indefinitely many clients. This means the same module will have to be re-used to create objects of indefinitely many types. Well, not really! At least not so in the C++ world.

Separation Compilation Model edit

In the separation compilation model, template file is compiled and this compiled file is supplied to the clients. Given the diversity of object file formats and instruction sets, for a language like C++ this seems to be a rather elusive option.

A first attempt at solving this problem dictates the implementer to maintain a separate object module for each platform. Given the possibility of multiple platforms coexisting in the same company or clients willing to switch to/add a new platform, this option turns out to be a maintenance nightmare.

Interoperability between various platforms is made possible by adapting a common file format and compiling the source module into intermediate code. This scheme is used by languages like Java and C#, where the clients, regardless of the platform, use intermediate code equivalent of the source module. Needless to say this technique is not well-suited to C++. Therefore the separation compilation model is not widely implemented by C++ compilers.

With the separation compilation model, the class template definition and the definitions of its inline member functions are placed in a header file, whereas the definitions of the member functions that are not inline and static data members are placed in a program text file. With this model, the definitions for a class template and its members are organized in the same way we organize the definitions of non-template classes and their members.

Genericness in Java

In an environment where the separation compilation model is supported, we need to make some changes in our code.

Example: C++ code a la separation compilation model.

export template <class ItemType> class Stack { friend ... public: ... private: ... }; // end of class Stack<ItemType>

Implementation of member function definitions that are not inline are moved into a file named, say StackTemplate.cxx.

You may choose to use a more selective version of the export keyword.

Example: Selective export.

template <class ItemType> class Stack { friend ... public: ... private: ... }; // end of class Stack<ItemType> template <class T> bool Stack<T>:: empty(void) {...} ...


export template <class Type> bool Stack<Type>:: peek(Type& value) {...} export template <class Type> bool Stack<Type>:: pop (Type& value) {...} export template<class Type> void Stack<Type>:: push(Type value) {...}

Inclusion Compilation Model edit

In the inclusion compilation model, the definition of the member functions and static members of class templates must be included in every file in which they are instantiated.

Definition: The act of using a parameterized type is called instantiation.

There are some drawbacks in providing the definitions for the members of a class template in a header file. The member function definitions may be quite large and may describe implementation details that the user may want to ignore or that we, as implementers, may want to hide from our users. Moreover, compiling the same template definitions across multiple files can add to the compile-time of our programs unnecessarily. The separation compilation model, if available, allows us to separate the class template interface (that is, the class template definition) from its implementation (that is, the definitions of its member functions and static data members).

Interface / Implementation edit


#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;

namespace  CSE224 {
  namespace DS {

Here is where we begin the definition of our class template. The list surrounded by ‘<’ and ‘>’ includes the template parameter list, which can have a combination of type parameters and non-type parameters.

A template type parameter consists of the keyword class or the keyword typename followed by an identifier. In a template parameter list, both keywords have the same meaning. They indicate that the parameter name that follows represents a built-in or user-defined type. In this case, our single parameter represents the type of information held in the stack.

A template non-type parameter consists of an ordinary parameter declaration. A non-type parameter indicates that the parameter name represents a potential value. This value represents a constant in the class template definition.

Example: A generic buffer containing as many as a given number of objects.

template <class ItemType, int size> class Buffer; ... Buffer<int, 5> buf; // A buffer of 5 ints.

    template <class ItemType>
    class Stack {

Notice the explicit template argument following the function name. This syntax is used to specify that the friend declaration refers to an instantiation of the function template. That is, there is a one-to-one mapping between the instantiations of the class template and its friend. In our case, the only friend of Stack<T> is operator<<(ostream&, const Stack<T>&); no other overloaded definitions for the shift operator has any special access rights.

There are two other types of friend declarations that may appear within a class.

  • Many-to-one: Friend class/function is declared to be friend to all instantiations of the class template. For example,

template <class T> class ClassName { friend void functionName(Formal-Par-List); ... };

declares functionName to be friend to all ClassName instantiations.
  • One-to-many: For each instantiation of the class template, all instantiations of friend class/functions are friends. For example,

template <class T> class ClassName { template <class U> friend void functionName(..., Par<U>, ...); ... };

declares all instantiations of functionName to be friends to each instantiation of ClassName.

      friend ostream& operator<< <ItemType>(ostream&, const Stack<ItemType>&);

The following constructor definition is equivalent to Stack(int cap = 1) { _stack.reserve(cap); }. In both cases, a Stack object is constructed with a capacity of cap. But, there is a subtle difference. This is due to the execution order of constructors. Before the execution of an object’s constructor, all of its base class default constructors and member object default constructors are invoked. So, any updates you make to a member object in the constructor body will probably override the value provided in the relevant constructor. That may sometimes turn out to be a little costly. We may end up initializing the same object twice for different initial values. (Technically, it is not initialization that we do inside the constructor body but assignment.) For instance, the above code will work as follows:

  1. Stack constructor is called.
  2. Before entering the constructor body, the default vector constructor for _stack is called. This will create a vector of size and capacity both equal to 0.
  3. The body of the Stack constructor is executed. This will, depending on the value of the parameter, adjust the initial capacity of the vector object with the parameter and probably resize it.

In this scenario, we end up creating a vector object and having to resize it. Member initialization list provides us with a way to remove this source of inefficiency. Instead of calling the default constructors, we may pass arguments to the constructors and create the object with the required properties. The compiler in such a case will call the relevant constructor.

The below constructor definition will work as follows:

  1. Constructor of Stack is called.
  2. Before entering the constructor body, _stack object is created by calling the relevant vector constructor. The cap parameter passed to the Stack constructor is further passed as an argument to the vector constructor. This will basically create a vector with an initial capacity equal to cap, which is what we did inside the constructor body in the first version.
      Stack(int cap = 1 ) : _stack(cap) { }

Note the difference between the signature of the first two functions and the last one. Since the result is returned in their sole parameter the first two declare call-by-reference parameters. Because we do not have such a requirement the last function, on the other hand, declares a call-by-value parameter. As is explained in the Object-Based Programming chapter, this could also be accomplished by the following declaration.

void push(const ItemType&);

      bool peek(ItemType&);
      bool pop(ItemType&);
      void push(ItemType);
      bool empty(void);


vector is one of the abstract container types provided by the C++ standard library. Like an array, it holds an ordered collection of elements of a single type. It is represented in a contiguous area of memory, which makes random access possible. Unlike an array, however, size of a vector can grow dynamically. When the vector needs to grow itself, it allocates additional storage capacity beyond its immediate need—it holds this storage in reserve. You can try the following to see how a vector grows in your system.


#include <vector> #include <iostream> using namespace std; int main(void) { int cap; vector<int> vec; cout << "Initial size = " << vec.size() << '\t' << "Initial capacity = " << vec.capacity() << "Maximum size = " << vec.max_size() << endl; cout << "Enter the maximum capacity: "; cin >> cap; for (int i = 0, prev_cap = vec.capacity(); i < cap; i++) { vec.push_back(i); int cur_cap = vec.capacity(); if (prev_cap == cur_cap) continue; prev_cap = cur_cap; cout << "Size = " << vec.size() << '\t' << "New capacity = " << cur_cap << endl; } // end of for (int i = 0; i < cap; i++) return(0); } /* end of int main(void) */

Note the difference between size() and capacity(). capacity() returns the maximum number of elements that a vector object can hold before it needs to regrow itself. On the other hand, size() returns the number of elements currently held in the vector. (push_back() inserts an element to the back of the container.)

Other major container types provided by the C++ standard library are list, deque, map, and set. For more check the Container Types section.

      vector<ItemType> _stack;
}; // end of class Stack<ItemType>

Whoops! What have we got here? Definition of a class member function inside a header file?!. It certainly goes against the information hiding principle! Unfortunately, we cannot avoid it in this case. This is a consequence of the way templates are supported by C++ compilers. For more on this, check the Template Compilation Models section.

    template <class Type>
    bool Stack<Type>::
    peek(Type& value) {
      if (empty()) return false;

Sometimes we want the user of a container data type to be able to access, one at a time, each and every component in the container. For an array, it would be very simple: start from the first component and each time you want to move on to the next component proceed by increasing the index value by one; for a linked list all you have to do is to follow the link to the next component; for a sequential file issuing a read operation will do the job. Although the way you achieve is different the idea of traversing an ADT is an abstract operation common to many of them. In object-oriented programming languages such an operation is provided by means of iterators.[1]

Definition: An iterator is an auxiliary data structure created with the sole purpose of permitting access to the values in a container through a sequence of simple operations, while hiding from the user of the iterator the actual implementation of these operators.

In C++, an iterator is defined to be a "pointer" to the component’s data type. begin() and end() are used to locate the beginning and end of the container, respectively. Along with an iterator used to traverse the container in the forward direction, one can also have a reverse iterator, an iterator that starts traversal from the last component and moves toward the beginning. For such an iterator, rbegin() and rend() methods are used to locate the two ends of the container.

Insert iterator figure here

For a forward iterator, ++ accesses the next element in the container, while it accesses the previous component in the case of a reverse iterator. Using * to dereference the iterator yields the contents of component currently being visited. (Do not forget that the iterator is in fact a pointer!)

Next line defines a reverse iterator on the vector and sets it to point to the last component.

      vector<Type>::reverse_iterator iter = _stack.rbegin();
      value = *iter; 

    } // end of bool Stack<Type>::peek(Type&)

Each and every class template member function definition must be preceded by the template keyword and the template parameter list.

Parameter names stay in scope throughout the definition of the following class or the member function. That’s why we can use different names for the same parameter.

    template <class T>
    bool Stack<T>::
    pop(T& value) {
      if (empty()) return false;

      vector<T>::reverse_iterator iter = _stack.rbegin();
      value = *iter; 

    } // end of bool Stack<T>::pop(T&)

    template<class Type>
    void Stack<Type>::
    push(Type value) { _stack.push_back(value); }

    template <class Type>
    bool Stack<Type>::
    empty(void) { return(_stack.empty()); }

    template <class Type>
    ostream& operator<<(ostream& os, const Stack<Type>& rhs) {
      os << "( " << rhs._stack.size() << " )";

In order to avoid modifications being made through an iterator we can define constant iterators. Any attempt to modify components of the underlying vector through these iterators will be caught by the compiler.

Note this applies only to attempts made using these iterators. Making modifications using other means or even other non-constant iterators is still a possibility.

      vector<Type>::const_iterator iter = rhs._stack.begin();
      vector<Type>::const_iterator iend = rhs._stack.end();
      if (iter == iend) {
       cout << "EMPTY\n";
      } // end of if (iter == iend)

      os << "(bot: ";
      while(iter != iend) {
        os << *iter << " ";
      } // end of while (iter != iend)
      os << " :top )\n";

    } // end of ostream& operator<<(ostream&, const Stack<Type>&)
  } // end of namespace DS
} // end of namespace CSE224

Test Program edit

#include <iostream>
using namespace std;

#include "math/Complex"
using CSE224::Math::Complex;
#include "ds/StackTemplate"
using CSE224:DS::Stack;

int main(void) {

Next two lines are examples to instantiation of our class template. As a result of elaborating these statements compiler, or the compiler-linker pair, will synthesize code required for two classes. In order to convince yourself about this add lines that defines and uses a stack of a different type and observe the increase in size of the resulting executable.

  Stack<double> dstack;
  Stack<Complex> cstack;

  cout << cstack;
  cout << dstack << endl;

  int d;
  for (d = 1; d <= 15; d++) {
    Complex num = Complex(d, 2 * d);
  } // end of for (d = 1; d <= 15; d++)
  cout << cstack;
  cout << dstack << endl;

  for (d = 1; d <= 10; d++) {
    double dval;
    Complex cval;
  } // end of for (d = 1; d <= 10; d++)
  cout << cstack;
  cout << dstack << endl;

  for (d = 1; d <= 10; d++) {
    double dval;
    Complex cval;
  } // end of for (d = 1; d <= 10; d++)
  cout << cstack;
  cout << dstack << endl;

} // end of int main(void)

Container Types edit

Container types supported by the Standard Template Library (STL) can be divided into two: linear containers (sequences), which hold an ordered collection of elements, and non-linear containers, which support efficient query and retrieval of an element. The former includes the list, vector, and deque classes while the latter group map and set. One can also add the restricted list classes priority_queue, stack and queue to the former group.

In addition to the basic relational operators, functions creating iterators, and container-specific operations, all container types conform to the Orthodoz Canonical Form and support clear(), empty(), max_size(), swap(container), size(). Functionality offered by a particular class is brought in by an #include directive that takes the container type as the file name.

Sequences (Linear Containers) edit

STL supports three types of sequences: deque, list, and vector. All capable of dynamically adjusting their sizes, vector is designed to be a random-access container, list is the typical linked structure, and deque provides a cross between the two.

Two important operations supported by the linear containers are insertion and deletion of items. Named insert and erase, these operations make use of iterators. insert can be used in three ways. The first version returns an iterator to the element that has just been added while the others return void.

  • seq.insert(itr, val): Inserts val before the position indicated by the iterator passed in the first argument. Note, since end() locates the iterator beyond the container, seq.insert(seq.end(), val) inserts val to the end of seq.
  • seq.insert(itr, no_of_ins, val): Inserts val as many as no_of_ins times before the position indicated by the iterator passed in the first argument.
  • seq.insert(itr, from_st_itr, from_end_itr): Inserts a closed-open range of values delimited by the second and third arguments before the position indicated by the iterator passed in the first argument. For instance, seq.insert(seq.end(), arr, arr + 4) inserts the first four elements of arr to the end of seq.

Similarly, erase can be used in two ways. Both versions return an iterator that shows the element after the last erased element.

  • seq.erase(itr): Removes the item indicated by the iterator passed in the argument.
  • seq.erase(st_itr, end_itr): Removes all items of seq delimited by the range specified in the arguments. The special case where all items of the container is removed can also be accomplished by the clear function.

Two functions, both special to list, remove elements that have a certain property.

  • lst.remove(val): Removes all elements of the list that are equal to val.
  • lst.remove_if(unary_pred): Removes all elements of lst that satisfy the unary predicate—actually, a function object impersonating as a bool-returning function—provided as its sole argument.

Shorthands are provided for some of the more commonly used invocations of insert and erase. These are given below.

seq.insert(seq.end(), val) seq.push_back(val) seq.insert(seq.begin(), val) seq.push_front(val) seq.erase(--seq.end()) seq.pop_back() seq.erase(seq.begin()) seq.pop_front()

Given the cost of item insertion/removal due to shifting, it is no surprise that vector does not support pop_front and push_front.

The two ends of the sequence are accessed by means of the back and front functions.

Sequence types and their operations
Operation deque list vector
assign, swap
at, []
back, front
begin, end, rbegin, rend
capacity, reserve
max_size, resize, size
pop_back, push_back
pop_front, push_front
remove, remove_if

Observe that the container-specific functions reflect the nature of the underlying sequence. Thanks to their random-access support both vector and deque have functions, at and [], for accessing elements using index values. Since list and deque increase their size by one as new items are inserted, neither supports capacity and reserve.

Signatures of the list-specific functions along with what they do are given below. Wherever required bin_pred, a binary predicate, is used in determining the ordering criterion utilized in the algorithm.

  • lst.merge(sec_lst) & lst.merge(sec_lst, bin_pred): Merges sec_lst into the list, both of which are sorted. If not given ordering is done by <.
  • lst.sort(void) & lst.sort(bin_pred): Sorts the list. If not given ordering is done by <.
  • lst.splice(itr, sec_lst): Inserts sec_lst into lst at the location given by the iterator in the first argument.
  • lst.splice(itr, sec_lst, st_itr, end_itr = lst.end()): In addition to inserting sec_lst this version removes all elements at locations between st_itr and end_itr.
  • lst.unique(void) & lst.unique(bin_pred): Removes all consecutive duplicates in the list. If not given equality of consecutive elements are tested using ==.

Container Adapters edit

In addition to the sequence types mentioned in the previous section, STL provides support for three restricted lists by means of adapter classes. These classes and their operations are given in the table below. Note that iterator creating functions, which would enable us to access and modify each and every element in the relevant data structure, are not in the table.

Operation priority_queue queue stack

Associative (Non-linear) Containers edit

STL supports two types of associative containers: map and set. The former is used as a fast lookup structure relating a key with a value, whereas the latter is used to implement the mathematical notion of sorted sets.

Neither container type allows duplicates: it is not possible to relate a particular key with more than one value; a set cannot contain more than one copy of an object. In case duplicates are required one should use multimap and multiset, which are map and set with the no-duplicates criterion removed.

Operation map set
begin, end, rbegin, rend
key_comp, value_comp
lower_bound, upper_bound
max_size, size

Fundamental operations supported are insert, erase, and find.

  • map.insert(pair) & set.insert(val): Inserts key-value pair/val only if it does not exist in the map/set. This function returns an iterator-success pair, where the iterator part indicates the location of insertion and the success part describes whether the operation has successfully been inserted or not.
  • assoc_cntnr.insert(st_itr, end_itr): Inserts all items found in [st_itr, end_itr).
  • map.insert(itr, pair) & set.insert(itr, val): Inserts pair/val after the location indicated by itr and returns an iterator to the item just inserted. Note the location of insertion passed is just a suggestion.
  • assoc_cntnr.erase(itr): Erases the element indicated by itr.
  • assoc_cntnr.erase(st_itr, end_itr): Erases all elements in the range between st_itr and end_itr.
  • map.erase(key) & set.erase(val): Erases all elements that have the value key/val. This function returns the number of entries deleted, which can be zero or one in a map or set whereas in a multimap or multiset it can be more than one.
  • map.find(key) & set.find(val): Returns an iterator to the related entry in the map/set if it exists. Otherwise, it returns an iterator to the end of the container.

As in the vector and deque classes one can also use the subscript operator ([]) for finding and inserting an entry in a map. One should however be aware of the differences. First of all, both insert and find provide means for flagging unsuccessful operations. As a result of looking up a non-existing key in the map, find returns an iterator to the end of the map without making any modification in the map, whereas [] makes an entry relating the key with a default value. Also, thanks to the second version, insert enables multiple entries to be inserted in a single application of the function while this is limited to one in the case of [].

Example: Fundamental operations on maps.

#include <map> #include <string> ... ... pair<string, string> initial_entries[] = { make_pair("bilgisayar", "computer"), make_pair("donanim", "hardware"), make_pair("yazilim", "software") }; string words[] = {"komutsal", "yordamsal", "birimsel", "nesne-temelli", "nesne-yonelimli"}; string meanings[] = {"imperative", "procedural", "modular", "object-based", "object-oriented"};

Next line creates a map and initializes it with the contents of the array named initial_entries.

map<string, string> par_dict(initial_entries, initial_entries + 3);

Next for-loop populates the map with five more entries.

for (int i = 0; i < 5; i++) par_dict[words[i]] = meanings[i];

Next line attempts to insert an already existing key, which causes the value in the second part of the pair returned from insert to set to false.

pair<map<string, string>::iterator, bool> result = par_dict.insert(map<string, string>::value_type(words[4], meanings[4])); if (!result.second) cout << "Last entry (" << words[4] << ") in the map" << endl; pair<string, string> last_entries[] = { make_pair("yazici", "printer"), make_pair("tarayici", "scanner"), make_pair("klavye", "keyboard") };

Next application of insert inserts three key-value pairs found in last_entries into par_dict.

par_dict.insert(last_entries, last_entries + 3); string searched_word; cout << "Enter a word to be looked up in the dictionary: "; cin >> searched_word;

If you enter a word that happens to be missing in our map, next line will return an iterator to the end of the map, meaning the lookup did not return a value. Otherwise, it returns an iterator to the relevant entry, which is a key-value pair.

map<string, string>::iterator itr = par_dict.find(searched_word); string meaning = (itr == par_dict.end()) ? Word not found : itr->second; cout << Meaning of << searched_word << is << meaning << endl;

In case a non-existing key is looked up in the map, using the [] operator instead of find will cause an entry to be made for the key in question. The corresponding value inserted assumes the default of the second part's type.

cout << "Meaning of " << searched_word << " is " << par_dict[searched_word] << endl; itr = par_dict.find(searched_word); meaning = (itr == par_dict.end()) ? "Word not found" : itr->second; cout << "Meaning of " << searched_word << " is " << meaning << endl; par_dict.erase(searched_word); ...

Other operations applicable on an associative container include the following.

  • assoc_cntnr.count(key/val): Returns the number of occurrences of key/val as the key part of the entries in the map or in the set.
  • assoc_cntnr.equal_range(key/val): Returns a pair of iterators that has key as its part of the key-value pair or val as the element value.
  • assoc_cntnr.lower_bound(key/val) & assoc_cntnr.upper_bound(key/val): Returns an iterator to the smallest value that is greater-or-equal to (greater than) key/val.

Generic Functions in STL edit

Strength of the seemingly thin interface offered by different container types is augmented by the use of generic functions of STL. These functions make heavy use of iterators for expressing the boundaries of the container. Instead of accumulate(container, init_val), which would sum up the elements of container, we have accumulate(st_itr, end_itr, init_val), which sums up the elements in [st_itr, end_itr). The second version is more flexible in that it enables us to apply the generic function not only on the whole container but also on a part of it. In some functions, further specialization can be provided by passing a function object to be applied on the elements of the container.

Example: Applying a generic function on a part of a container.
Inclusion of algorithm and numeric are required for accumulate. functional is required for multiplies.

#include <algorithm> #include <functional> #include <numeric> ... int int_arr[] = {-1, 1, 3 , 5, 7, 9, 11}; int int_vec(int_arr, int_arr + 7);

Next line sums up all elements, except for the first and the last, of int_arr and stores the result in sum.

int sum = accumulate(int_arr + 1, int_arr + 6, 0);

Next application of accumulate finds the product of all elements in int_vec.

int product = accumulate(int_vec.begin(), int_vec.end(), 1, multiplies<int>()); ...

A helpful hint in dealing with the complexity of the generic functions in STL is the naming of functions that take predicates. For instance, count(st_itr, end_itr, val) returns the number of elements in [st_itr, end_itr) equal to val. Conditional form of this function, count_if(st_itr, end_itr, pred), basically does the same thing: it returns the number of elements in [st_itr, end_itr) that satisfy pred. Other functions that come with a conditional form are given below.

  • find(st_itr, end_itr, val): Returns an iterator for the first occurrence of val in the range delimited by st_itr and end_itr. If val is not found end_itr is returned.
  • remove(st_itr, end_itr, val): Removes all elements in [st_itr, end_itr) that are equal to val. Note neither versions—that is, remove and remove_if—do any actual deletion from the underlying container. As elements that do not satisfy the (explicitly or implicitly stated) criterion are seen, they are moved to the front of the current container. Any actual deletion is meant to take place upon application of an erase following either one of remove or remove_if. Both functions return an iterator to a position that comes as many as the number of removed elements before the end.
Example: Peculiarity of remove and remove_if.

... int int_arr[] = {-1, 1, 3, 5, 1, 9, 11}; vector<int> int_vec(int_arr, int_arr + 7);

Next line "removes" all elements in int_vec that are equal to 1. Upon execution of remove, int_vec will have {-1, 3, 5, 9, 11, 9, 11} as its content. The returned iterator will be pointing at the second 9. In order to actually complete the deletion, we must execute an erase.

vector<int>::iterator first_one = remove(int_vec.begin(), int_vec.end(), 1); int_vec.erase(first_one, int_vec.end()); list<int> int_list(int_arr, int_arr + 7); list<int>::iterator first_less5 = remove_if(int_list.begin(), int_list.end(), bind2nd(less<int>(), 5)); int_list.erase(first_less5, int_list.end()); ... replace(st_itr, end_itr, val, new_val): Replaces all occurrences of val in [st_itr, end_itr) with new_val.

Another useful way to figure out more about generic functions in STL is to spot those functions that work their magic on a copy of the original container. Such functions have copy somewhere in their names. For instance, remove_copy moves those values in the original container that do not satisfy the stated criterion to another container and returns an iterator to the end of the resulting container. Other functions working in a similar fashion include remove_copy_if, replace_copy, replace_copy_if, reverse & reverse_copy, rotate & rotate_copy, and unique & unique_copy.

Example: Copying functions.

... vector<int> copy_vec; copy_vec.resize(5); remove_copy(int_vec.begin(), int_vec.end(), copy_vec.begin(), 1); list<int> copy_list; copy_list.resize(3); remove_copy_if(int_list.begin(), int_list.end(), copy_list.begin(), bind2nd(less<int>(), 5)); ...

One other group of functions involve generalizations of certain container-specific functions. For instance, while lst.merge(sec_lst) & lst.merge(sec_lst, bin_pred) merges two sorted lists, generic function merge merges any two sorted containers. Other functions in this group include count, equal_range, lower_bound, upper_bound, merge, remove, remove_if, reverse, sort, swap, and unique.

Example: Using the generalized versions of container-specific functions.

... int int_arr[] = {2, -1, 2, -2, 2, -3}; vector<int> int_vec(int_arr, int_arr + 6);

If -1 occurs in int_vec, next two lines insert 0 right before the first occurrence of -1. Otherwise, o is inserted at the end of int_vec.

vector<int>::iterator first_one = find(int_vec.begin(), int_vec.end(), -1); int_vec.insert(first_one, 0);

The following definition create a list using the contents of the vector in reverse order.

list<int> int_list(int_vec.rbegin(), int_vec.rend());

Next three lines delete all items in between the first and second occurrences of 2, including the 2's. Notice—since there is no random access support—unlike in vectors and deques, we cannot use iterator arithmetic [that is, we cannot use + and -] while using list iterators. Hence is the use of -- following a ++.

list<int>::iterator first_two = find(int_vec.begin(), int_vec.end(), 2); list<int>::iterator second_two = find(++first_two, int_vec.end(), 2); int_vec.erase(--first_two, ++second_two);

Next three lines find the third smallest item in a deque created from a previously created list. Note we can now use iterator arithmetic.

deque<int> int_deque(int_list.begin(), int_list.end()); sort(int_deque.begin(), int_deque.end()); int third_smallest = *(int_deque.begin() + 2);

Next four lines merge two sorted sequences into a single one. Observe that the resulting sorted sequence is populated starting from its end. Note also the list, initially created empty, is later resized to take as many as one more than the total number of elements. In the process, each slot is initialized to -100.

list<int> merged_list; merged_list.resize(int_deque.size() + int_vec.size() + 1, -100); sort(int_vec.begin(), int_vec.end()); merge(int_deque.begin(), int_deque.end(), int_vec.begin(), int_vec.end(), merged_list.rbegin()); ...

Yet another group comprises the classical higher-order functions: accumulate, find, for_each, and transform. These functions do the equivalent of reduce, filter, foreach, and map functions provided in functional programming languages.


... int int_arr[] = {0, 1, 2, 3, 4, 5}; list<int> int_list(int_arr, int_arr + 6); void dump_element(int elmt) { cout << elem << ' ';} int negate_value(int val) { return -val; }

Next line processes all elements in the range by applying the dump_element function to each element. Passing another function in the third argument will change the side effect created by for_each.

for_each(copy_lst.begin(), copy_lst.end(), dump_element);

transform maps a given sequence to another. Nature of the mapping is determined by the last argument, which can be a unary or a binary function. The result is stored into the sequence whose starting point is given in the third argument.

transform(copy_lst.begin(), copy_lst.end(), copy_lst.begin(), negate_value); ...

Finally, one can also utilize generic functions that treat a container as a set or a heap, respectively. In the former group, we have set_difference, set_intersection, set_symmetric_difference, and set_union. The latter group includes make_heap, pop_heap, push_heap, and sort_heap functions. Set functions take two pairs of iterators to delimit the containers to work on and an iterator pointing at the starting location of the resulting set. On the other hand, heap functions take a single pair of iterators to determine the container. All functions—set or heap—come in two flavors: one that assumes < is used as the ordering criterion in forming the container and one that takes an extra function that may serve the same purpose.

pop_heap and push_heap
Given a container—say [first, last)—with the heap property, pop_heap swaps the first and last items in the container and reorganizes [first, last-1), by means of downheaping, so as to preserve the heap property for [first, last-1). Similarly,given a container—say [first, last)—whose subsequence [first, last-1) has the heap property, push_heap inserts the item in position last-1 into the container by means of upheaping, so that we get the whole container to satisfy the heap property.

Function Objects edit

An intuitive notion lacking in C++, like almost any other imperative language, is the treatment of functions as first-class values. It's not possible to pass around and return functions; one must resort to using pointer-to-functions, instead. This section offers an alternative solution to this by introducing function objects, objects that look like functions. Instead of using functions we use instances of a class that overloads the function call operator.

Definition: A function object is an instance of a class that overloads the function call operator. Function call operator encapsulates what normally would be encapsulated as a function.

Following a selection of standard function objects supported by C++, we provide an application of the concept in simulating local functions.

Interface edit


#include <ostream>
using namespace std;

namespace CSE224 {
  namespace Math {
    class Polynomial {
      friend ostream& operator<<(ostream&, const Polynomial&);

      Polynomial(double con = 0.0, double fir = 0.0, double sec = 0.0) : _con(con), _fir(fir), _sec(sec) { }

Thanks to the simple structure of Polynomial objects—only primitive type fields—we do not have to write a copy constructor or an assignment operator. Behavior of the compiler-provided default will suffice. Add to this the fact that we don't acquire any outside resources, it becomes clear we don't need to provide a destructor function, either.

But the assignment operator is still there and will serve to assign both Polynomials and doubles to a Polynomial object. What makes this magic work is the implicit conversion of a double to a Polynomial object. If you take a closer look at the previous constructor, you’ll see that we can create a Polynomial object by simply passing a single double value. Compiler will take this as a conversion tool and use for double-to-Polynomial conversions. So, anywhere a Polynomial is required but a double is used compiler will silently convert the double value to a Polynomial object. In doing so it will use the constructor listed above.

This [implicit conversion] takes away our freedom of ordering the arguments sent to the constructor. Say, we change its semantics so that the first parameter stands for the coefficient of the second-degree component, the second the coefficient of the first-degree component and the last the constant. This arrangement has a rather unexpected consequence. Take a look at the following C++ fragment:

... Polynomial c; ... c = 3.0; // 1 ...

The double value 3.0 is converted to a Polynomial using the relevant constructor and 3x^2 will be assigned to c. Very unlikely what we really wanted!

     // Polynomial(const Polynomial& existing_pol);
     // ~Polynomial(void);
     // Polynomial& operator=(const Polynomial&);

Given the above explanations, one may think that the following friend declaration is superfluous. Well, not really! Because the object the message is sent to is not implicitly converted.

      friend bool operator==(double, Polynomial&);
      bool operator==(const Polynomial&);

Next line is a declaration that will make Polynomial objects look like functions, which will give an illusion of functions being treated as first-class citizens. This is achieved through overloading the function call operator.

      double operator()(double x);

Thanks to the implicit conversion mentioned above, we no longer have to have three functions to overload the + operator; two will be enough.

      Polynomial operator+(const Polynomial&); 
      friend Polynomial operator+(double, Polynomial&);
      Polynomial& operator+=(const Polynomial&);

      Polynomial operator-(const Polynomial&);
      friend Polynomial operator-(double, Polynomial&);
      Polynomial& operator-=(const Polynomial&);

      double _sec, _fir, _con;
    }; // end of class Polynomial
  } // end of namespace Math
} // end of namespace CSE224

Implementation edit

#include "math/Polynomial"

namespace CSE224 {
  namespace Math {

This is what makes instances of Polynomial function objects: operator() is overloaded to return the value of the polynomial at a given point.

    double Polynomial::
    operator()(double x) {
      return(_sec * x * x + _fir * x + _con);
    } // end of double Polynomial::operator()(const double)

    bool Polynomial::
    operator==(const Polynomial& rhs) {
      if (_sec != rhs._sec) return false;
      else if (_fir != rhs._fir) return false;
      else if (_con != rhs._con) return false;
        else return true;
    } // end of equality-test operator

    bool operator==(double lhs, Polynomial& rhs) {
      return(rhs._sec == 0 && rhs._fir == 0 && rhs._con == lhs);
    } // end of bool operator==(double, Polynomial&)

    Polynomial Polynomial::
    operator+(const Polynomial& rhs) {
      Polynomial res_pol;

      res_pol._sec = _sec + rhs._sec;
      res_pol._fir = _fir + rhs._fir;
      res_pol._con = _con + rhs._con;

      return res_pol;
    } // end of Polynomial Polynomial::operator+(const Polynomial)

    Polynomial operator+(double lhs, Polynomial& rhs) {
      Polynomial res_pol;

      res_pol._sec = rhs._sec;
      res_pol._fir = rhs._fir;
      res_pol._con = lhs + rhs._con;

      return res_pol;
    } // end of Polynomial operator+(double, Polynomial&)

    Polynomial& Polynomial::
    operator+=(const Polynomial& rhs) {
      _sec += rhs._sec;
      _fir += rhs._fir;
      _con += rhs._con;

      return (*this);
    } // end of Polynomial& Polynomial::operator+=(const Polynomial)

    Polynomial Polynomial::
    operator-(const Polynomial& rhs) {
      Polynomial res_pol;

      res_pol._sec = _sec - rhs._sec;
      res_pol._fir = _fir - rhs._fir;
      res_pol._con = _con - rhs._con;

      return res_pol;
    } // end of Polynomial Polynomial::operator-(const Polynomial)

    Polynomial operator-(double lhs, Polynomial& rhs) {
      Polynomial res_pol;

      res_pol._sec = -rhs._sec;
      res_pol._fir = -rhs._fir;
      res_pol._con = lhs - rhs._con;

      return res_pol;
    } // end of Polynomial operator-(double, Polynomial&)

    Polynomial& Polynomial::
    operator-=(const Polynomial& rhs) {
      _sec -= rhs._sec;
      _fir -= rhs._fir;
      _con -= rhs._con;

      return (*this);
    } // end of Polynomial& Polynomial::operator-=(const Polynomial&)

    ostream& operator<<(ostream& os, const Polynomial& rhs) {
      if (rhs._sec != 0) os << rhs._sec << "x^2 ";

      if (rhs._fir != 0) {
        if (rhs._sec != 0) os << "+ ";
        os << rhs._fir << "x ";
      } // end of if (rhs._fir != 0)

      if (rhs._con != 0) {
        if (rhs._sec != 0 || rhs._fir != 0) os << "+ ";
        os << rhs._con;
      } else if (rhs._fir == 0 && rhs._sec == 0) os << "0";

    } // end of ostream& operator<<(ostream&, const Polynomial&)
  } // end of namespace Math
} // end of namespace CSE224

Test Program edit

#include <iostream>
using namespace std;

#include "math/Polynomial"
using namespace CSE224::Math;

int main(void) {
  cout << "Creating c1 and initializing it with 1... ";
  Polynomial c1 = 1.0;
  cout << "c1: " << c1 << endl;
  cout << "Creating c2 and initializing it with 2... ";
  Polynomial c2(2.0);
  cout << "c2: " << c2 << endl;
  cout << "Creating c3 and initializing it with an anonymous object that has a value of 3... ";
  Polynomial c3 = Polynomial(3.0);
  cout << "c3: " << c3 << endl;
  cout << "Creating c4... It is automatically initialized with 0... ";
  Polynomial c4;
  cout << "c4: " << c4 << endl;
  cout << "Assigning 4 to c4..." << endl;
  c4 = 4.0;
  cout << "Creating c5... It is automatically initialized with 0... ";
  Polynomial c5;
  cout << "c5: " << c5 << endl;
  cout << "Assigning c4 to c5..." << endl;
  c5 = c4;
  cout << "c1: " << c1 << ", c2: " << c2 << ", c3: " << c3
       << ", c4: " << c4 << ", c5: " << c5 <<endl;

  cout << endl << "Testing compound assignment..." << endl;
  cout << "Adding 1 to c1... "; c1 += 1.0;
  cout << "c1: " << c1 << endl;
  cout << "Subtracting 1 from c3... "; c3 -= 1.0;
  cout << "c3: " << c3 << endl;
  cout << endl << "Testing the equality test operator..." << endl;
  cout << "c3 == c1? ";
  if (c3 == c1) cout << "Yes" << endl;
    else cout << "Something wrong with the equality test operator" << endl;
  cout << "c2 == 2? ";
  if (c2 == 2) cout << "Yes" << endl;
    else cout << "Something wrong with the equality test operator" << endl;
  cout << "4.0 == c4? ";
  if (4.0 == c4) cout << "Yes" << endl;
    else cout << "Something wrong with the equality test operator" << endl;
  cout << "c5 == c4? ";
  if (c5 == c4) cout << "Yes" << endl;
    else cout << "Something wrong with the equality test operator" << endl;

  cout << endl << "Creating f and initializing it with 4x + 3... ";
  Polynomial f(3.0, 4.0);
  cout << "f: " << f << endl;
  cout << "Creating g and initializing it with 3x^2 + 2x + 1... ";
  Polynomial g(1, 2, 3);
  cout << "g: " << g << endl;
  cout << "Creating h and initializing it with 2 + f - g + 4... ";

Now that a double value is implicitly converted to a Polynomial—remember the first constructor—following assignment can be seen as addition of four Polynomials.[2] Assuming left-to-right, sequential evaluation; 2.0—a polynomial that has 0.0 as the coefficient of first and second order terms—is added to f, to the result of which is added the Polynomial g. Finally, 4.0 is added to the temporary value obtained from the summation of the first three terms.

  Polynomial h = 2.0 + f - g + 4.0;
  cout << "h: " << h << endl;
  cout << "Using function object... ";

Note the following—although it looks more like calling functions—is an application of the function call operator defined in Polynomial.

  cout << "f(g(2)) = " << f(g(2)) << ", h(3) = " << h(3) << endl;

  cout << endl << "Creating j(on the heap) and k; j is initialized with 0 while k with 1" << endl;
  Polynomial *j = new Polynomial, k = 1;
  cout << "h: " << h << ", j: " << *j << ", k: " << k << endl;
  cout << "Subtracting 2x^2 + x from h, adding h to k, and assigning k to j..." << endl;
  *j = k += h -= Polynomial(0.0, 1.0, 2.0);
  cout << "h: " << h << ", j: " << *j << ", k: " << k << endl;
  delete j;

  return 0;
} // end of int main(void)

Running the Test Program edit

gxx –c Polynomial.cxx↵ # Using DJGPP-gxx gxx –o Polynomial_Test.exe Polynomial_Test.cxx Polynomial.o↵ Polynomial_Test↵ Creating c1 and initializing it with 1... c1: 1 Creating c2 and initializing it with 2... c2: 2 Creating c3 and initializing it with an anonymous object that has a value of 3... c3: 3 Creating c4... It is automatically initialized with 0... c4: 0 Assigning 4 to c4... Creating c5... It is automatically initialized with 0... c5: 0 Assigning c4 to c5... c1: 1, c2: 2, c3: 3, c4: 4, c5: 4 Testing compound assignment... Adding 1 to c1... c1: 2 Subtracting 1 from c3... c3: 2 Testing the equality test operator... c3 == c1? Yes c2 == 2? Yes 4.0 == c4? Yes c5 == c4? Yes Creating f and initializing it with 4x + 3... f: 4x + 3 Creating g and initializing it with 3x^2 + 2x + 1... g: 3x^2 + 2x + 1 Creating h and initializing it with 2 + f - g + 4... h: -3x^2 + 2x + 8 Using function object... f(g(2)) = 71, h(3) = -13 Creating j(on the heap) and k; j is initialized with 0 while k with 1 h: -3x^2 + 2x + 8, j: 0, k: 1 Subtracting 2x^2 + x from h, adding h to k, and assigning k to j... h: -5x^2 + 1x + 8, j: -5x^2 + 1x + 9, k: -5x^2 + 1x + 9

#include <iostream>
#include <string>
#include <vector>
using namespace std;

template<class T>
class Filter {
  virtual bool operator()(T) = 0;
}; // end of (abstract) class Filter

class EvennessFilter : public Filter<int> {
  virtual bool operator()(int num) { return(num % 2 == 0); }
}; // end of class EvennessFilter

class NamesWithNLettersFilter : public Filter<string> {
  NamesWithNLettersFilter(unsigned int n = 1) { _n = n; }
  virtual bool operator()(string name) { return(name.length() == _n); }

  unsigned int _n;
}; // end of class NamesWithFourLetters

template<class T, class FilterType>
vector<T> filt(vector<T> vec, FilterType f) {
  vector<T> filtered_vec;
  for (int i = 0; i < vec.size(); i++)
    if (f(vec[i])) filtered_vec.push_back(vec[i]);

  return filtered_vec;
} // end of vector<T> filt(vector<T>, FilterType)

int main(void) {
  int int_arr[] = { 1, 3, 2, 4, 0, 7, -12, -13};
  vector<int> int_vec(int_arr, int_arr + 8);
  vector<int> filtered_numbers = filt(int_vec, EvennessFilter());
  for (int i = 0; i < filtered_numbers.size(); i++)
    cout << filtered_numbers[i] << '\t';
  cout << endl;

  string str_arr[] = { string("Ali"), string("Veli"), string("Fatma"), string("Asiye") };
  vector<string> str_vec(str_arr, str_arr + 4);
  unsigned int len;
  cout << "No of characters: "; cin >> len;
  vector<string> filtered_names = filt(str_vec, NamesWithNLettersFilter(len));
  for (int i = 0; i < filtered_names.size(); i++)
    cout << filtered_names[i] << '\t';
  cout << endl;

  return 0;
} /* end of int main(void) */

Predefined Function Objects edit

Predefined function objects are generally used in coordination with generic functions in STL, which are a bunch of function templates whose implementations require assistance from their users. To give an example, sort requires a function object that is used for comparison purposes; if not passed such an object, it uses the less-than operator of the underlying type, which means you should implement the less-than operator. Passing different function objects for the same underlying type can be used to modify the ordering criterion used.[3]

Arithmetic Function Objects edit

The predefined arithmetic function objects support addition (plus<T>), subtraction (minus<T>), multiplication (multiplies<T>), division (divides<T>), modulus (modulus<T>), and negation (negate<T>).

Example: Arithmetic function objects.

#include <functional> #include <numeric> ... int odd_numerals[] = {1, 3, 5, 7, 9}; int product, summation;

pr_obj is a function object that "multiplies" both of its arguments. What is meant by multiplication is determined by the type parameter passed to the multiplies class.

multiplies<int> pr_obj; ...

The first two arguments to accumulate provide the boundaries for the data set to be traversed. Third argument holds the initial value of the operation. The final argument is the function object that will be used inside accumulate by sending it the function call operator.

summation = accumulate(&odd_numerals[0], &odd_numerals[4], 0, plus<int>()); product = accumulate(&odd_numerals[0], &odd_numerals[4], 1, pr_obj);

At this point, summation and product will be holding 25 and 945, respectively.


Relational Function Objects edit

The predefined relational function objects are equality (equal_to<T>), inequality (not_equal_to<T>), greater than (greater<T>), greater than or equal (greater_equal<T>), less than (less<T>), less than or equal (less_equal<T>).

Example: Relational function objects.

#include <algorithm> #include <functional> ...

What follows is the definition of a very simple function object class.

class less_than_x { public: less_than_x(int x) { _x = x; } bool operator()(int rhs) { return rhs < _x; } private: int _x; }; ... int nums[] = {-2, 1, -13, 5, 7, 9}; int lessthan5 = 0, negatives = 0, positives = 0;

count_if returns the number of items in the container that satisfies the predicate passed in the third argument. bind2nd is a so-called adapter that can be used to specialize and extend function objects. It basically converts the binary function object passed in its first argument into a unary function object. In our example, it is used to make the comparison with zero. not1 (together with not2), another adapter, reverses the truth value of a predicate function object.

positives = count_if(&nums[0], &nums[6], bind2nd(greater_equal<int>(), 0)); negatives = count_if(&nums[0], &nums[6], not1(bind2nd(greater_equal<int>(), 0)));

In addition to predefined function objects, you can pass user-defined function objects. Our example involves a predicate function object that has an effect similar to that of a binder: it causes the comparison to be made with a particular integer.

lessthan5 = count_if(&nums[0], &nums[6], less_than_x(5)); ...

Logical Function Objects edit

The logical function objects supported are and (logical_and<T>), or (logical_or<T>), and the negation (logical_not<T>) functions.

Example: Logical function objects.

#include <functional> ... double dnums[] = { 2.0, -3.5, 3.3, 4.5, -2.0, 0.0 }; sort(&dnums[0], &dnums[6]); logical_or<bool> boolOr; if (boolOr(binary_search(&dnums[0], &dnums[6], 0.0), binary_search(&dnums[0], &dnums[6], 10.0))) cout << "Found either one of 1 or 10" << endl; int i1 = 1, mask = 0; logical_and<int> intAnd; if (intAnd(i1, mask)) cout << "Unmasked"; else cout << "Masked"; ...

Simulating Local Functions edit

Local classes together with function objects can be used to simulate local functions. Using local classes provides protection from outside the current function whereas overriding the function call operator complements this by giving a sense of using functions.

#include <iostream>
using namespace std;

quicksort() is a function template that we can use to instantiate functions that sort specific type of data, which is determined at the point of calling the function. On line 56 of the current program, for instance, a call using an array of ints is being made, which means the compiler or the compiler-linker pair will synthesize a version of the following function that takes an array of ints.

template <class Elmt_Type>
void quicksort(Elmt_Type *arr, int l, int r) {
  class Pivot {
    int operator()(Elmt_Type *arr, int lb, int ub) {
      Elmt_Type v = arr[lb];
      int i = lb, j = ub + 1;

      do {

Note comparison of the current array element with the first element of the array slice means we must make sure the less-than operator of the component type is implemented.

        do { j--; } while (j != i && v < arr[j]);
        if (i == j) break;
        do { i++; } while (i != j && arr[i] < v);
        if (i == j) break;
        Elmt_Type tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
      } while (i <= j);
      if (j != lb) {
        Elmt_Type tmp = arr[lb];
        arr[lb] = arr[j];
        arr[j] = tmp;
      } // end of if (j != lb)

      return j;
    } // end of int operator(Elmt_Type*, int, int)
  }; // end of (local) class Pivot

  Pivot pivot;
  int i = pivot(arr, l, r);

  if (l < i - 1) quicksort(arr, l, i – 1);
  if (i + 1 < r) quicksort(arr, i + 1, r);
} // end of void quicksort()

int main(void) {
  int *array;

  cout << "Enter number of items in the sequence: ";
  int no_of_items;
  cin >> no_of_items;

  array = new int[no_of_items];
  for (int i = 0; i < no_of_items; i++)
    array[i] = i;

random_shuffle() randomly reorders the elements of an iterable container marked off by its first and second arguments. In other words, this function comes up with a permutation of the range marked with its arguments. It should be noted the range is closed-open. That is, the first argument is included in the range while the second argument is excluded.

Note there is a second version of this function that takes a random number generator as its third argument, which is used in the process of shuffling the elements.

  random_shuffle(&array[0], &array[no_of_items]);

  cout << "Shuffled (Initial) sequence: " << endl;
  for (int i = 0; i < no_of_items; i++)
    cout << array[i] << " ";
  cout << endl;

  quicksort(array, 0, no_of_items – 1);

  cout << "Sorted seqeunce: " << endl;
  for (int i = 0; i < no_of_items; i++)
    cout << array[i] << " ";

  delete[] array;

  return 0;
} // end of int main(void)

Notes edit

  1. Observe the similarity between iterators and generators. A generator—a random number generator, for instance—computes the next component in the sequence, whereas in the case of an iterator the next component is already there. In other words a generator finds the next component using computation-in-time while an iterator does it using computation-in-space.
  2. For pedagogical purposes, we assume the expression is evaluated sequentially from left to right. In reality, evaluation can be carried out in any order; sub-expressions can even be re-ordered by the compiler. That is; we may end up with an addition of two doubles and three Polynomials.
  3. This is very much like the Comparable and Comparator interfaces found in Java, where implementation of the former is meant to provide the natural order and the latter is used to provide alternative ordering criteria.