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 pre1.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 pre1.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 Student
s are tolerated by the compiler and cannot be caught before runtime. 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 isa 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".

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

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  edit source]Once a parametric type is implemented it is typically used by indefinitely many clients. This means the same module will have to be reused to create objects of indefinitely many types. Well, not really! At least not so in the C++ world.
Separation Compilation Model
[edit  edit source]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 wellsuited 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 nontemplate classes and their members.
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. 


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. 



Inclusion Compilation Model
[edit  edit source]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 compiletime 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  edit source]#ifndef STACKTEMPLATE_HXX
#define STACKTEMPLATE_HXX
#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 nontype 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 builtin or userdefined type. In this case, our single parameter represents the type of information held in the stack.
A template nontype parameter consists of an ordinary parameter declaration. A nontype 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>
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 onetoone 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.
 Manytoone: 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(FormalParList); ... };
 declares functionName to be friend to all
ClassName
instantiations.
 Onetomany: 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>&);
public:
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:
Stack
constructor is called. Before entering the constructor body, the default
vector
constructor for_stack
is called. This will create avector
of size and capacity both equal to 0.  The body of the
Stack
constructor is executed. This will, depending on the value of the parameter, adjust the initial capacity of thevector
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:
 Constructor of
Stack
is called.  Before entering the constructor body,
_stack
object is created by calling the relevantvector
constructor. Thecap
parameter passed to theStack
constructor is further passed as an argument to thevector
constructor. This will basically create avector
with an initial capacity equal tocap
, 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 callbyreference parameters. Because we do not have such a requirement the last function, on the other hand, declares a callbyvalue parameter. As is explained in the ObjectBased 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);
private:
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 objectoriented 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.
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;
return(true);
} // 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;
_stack.pop_back();
return(true);
} // 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 nonconstant 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";
return(os);
} // end of if (iter == iend)
os << "(bot: ";
while(iter != iend) {
os << *iter << " ";
iter++;
} // end of while (iter != iend)
os << " :top )\n";
return(os);
} // end of ostream& operator<<(ostream&, const Stack<Type>&)
} // end of namespace DS
} // end of namespace CSE224
#endif
Test Program
[edit  edit source]#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 compilerlinker 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);
cstack.push(num);
dstack.push(d);
} // end of for (d = 1; d <= 15; d++)
cout << cstack;
cout << dstack << endl;
for (d = 1; d <= 10; d++) {
double dval;
Complex cval;
cstack.pop(cval);
dstack.pop(dval);
} // end of for (d = 1; d <= 10; d++)
cout << cstack;
cout << dstack << endl;
for (d = 1; d <= 10; d++) {
double dval;
Complex cval;
cstack.pop(cval);
dstack.pop(dval);
} // end of for (d = 1; d <= 10; d++)
cout << cstack;
cout << dstack << endl;
return(0);
} // end of int main(void)
Container Types
[edit  edit source]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 nonlinear 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 containerspecific 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  edit source]STL supports three types of sequences: deque
, list
, and vector
. All capable of dynamically adjusting their sizes, vector
is designed to be a randomaccess 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)
: Insertsval
before the position indicated by the iterator passed in the first argument. Note, sinceend()
locates the iterator beyond the container,seq.insert(seq.end(), val)
insertsval
to the end ofseq
.seq.insert(itr, no_of_ins, val)
: Insertsval
as many asno_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 closedopen 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 ofarr
to the end ofseq
.
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 ofseq
delimited by the range specified in the arguments. The special case where all items of the container is removed can also be accomplished by theclear
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 toval
.lst.remove_if(unary_pred)
: Removes all elements oflst
that satisfy the unary predicate—actually, a function object impersonating as abool
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.
Operation  deque

list

vector


assign , swap

✔  ✔  ✔ 
at , []

✔  ✘  ✔ 
back , front

✔  ✔  ✔ 
begin , end , rbegin , rend

✔  ✔  ✔ 
capacity , reserve

✘  ✘  ✔ 
clear

✔  ✔  ✔ 
empty

✔  ✔  ✔ 
erase

✔  ✔  ✔ 
insert

✔  ✔  ✔ 
max_size , resize , size

✔  ✔  ✔ 
merge

✘  ✔  ✘ 
pop_back , push_back

✔  ✔  ✘ 
pop_front , push_front

✔  ✔  ✘ 
remove , remove_if

✘  ✔  ✘ 
reverse

✘  ✔  ✘ 
sort

✘  ✔  ✘ 
splice

✘  ✔  ✘ 
unique

✘  ✔  ✘ 
Observe that the containerspecific functions reflect the nature of the underlying sequence. Thanks to their randomaccess 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)
: Mergessec_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)
: Insertssec_lst
intolst
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 insertingsec_lst
this version removes all elements at locations betweenst_itr
andend_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  edit source]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


back

✘  ✔  ✘ 
empty

✔  ✔  ✔ 
front

✘  ✔  ✘ 
pop

✔  ✔  ✔ 
push

✔  ✔  ✔ 
size

✔  ✔  ✔ 
top

✔  ✘  ✔ 
Associative (Nonlinear) Containers
[edit  edit source]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 noduplicates criterion removed.
Operation  map

set


[]

✔  ✘ 
begin , end , rbegin , rend

✔  ✔ 
clear

✔  ✔ 
count

✔  ✔ 
empty

✔  ✔ 
equal_range

✔  ✔ 
erase

✔  ✔ 
find

✔  ✔ 
insert

✔  ✔ 
key_comp , value_comp

✔  ✔ 
lower_bound , upper_bound

✔  ✔ 
max_size , size

✔  ✔ 
swap

✔  ✔ 
Fundamental operations supported are insert
, erase
, and find
.
map.insert(pair)
&set.insert(val)
: Inserts keyvaluepair
/val
only if it does not exist in themap
/set
. This function returns an iteratorsuccess 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)
: Insertspair
/val
after the location indicated byitr
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 byitr
.assoc_cntnr.erase(st_itr, end_itr)
: Erases all elements in the range betweenst_itr
andend_itr
.map.erase(key)
&set.erase(val)
: Erases all elements that have the valuekey
/val
. This function returns the number of entries deleted, which can be zero or one in amap
orset
whereas in amultimap
ormultiset
it can be more than one.
map.find(key)
&set.find(val)
: Returns an iterator to the related entry in themap
/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 nonexisting 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", "nesnetemelli", "nesneyonelimli"}; string meanings[] = {"imperative", "procedural", "modular", "objectbased", "objectoriented"};
Next line creates a map
and initializes it with the contents of the array namedinitial_entries
.map<string, string> par_dict(initial_entries, initial_entries + 3);
Next for
loop populates themap
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 keyvalue pairs found inlast_entries
intopar_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 themap
, meaning the lookup did not return a value. Otherwise, it returns an iterator to the relevant entry, which is a keyvalue 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 nonexisting 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 ofkey
/val
as the key part of the entries in themap
or in theset
.assoc_cntnr.equal_range(key/val)
: Returns a pair of iterators that haskey
as its part of the keyvalue pair orval
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 greaterorequal to (greater than)key
/val
.
Generic Functions in STL
[edit  edit source]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
andnumeric
are required foraccumulate
.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 insum
.int sum = accumulate(int_arr + 1, int_arr + 6, 0);
Next application of accumulate
finds the product of all elements inint_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 ofval
in the range delimited byst_itr
andend_itr
. Ifval
is not foundend_itr
is returned.remove(st_itr, end_itr, val)
: Removes all elements in [st_itr
,end_itr
) that are equal toval
. Note neither versions—that is,remove
andremove_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 anerase
following either one ofremove
orremove_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
andremove_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 to1
. Upon execution ofremove
,int_vec
will have{1, 3, 5, 9, 11, 9, 11}
as its content. The returned iterator will be pointing at the second9
. In order to actually complete the deletion, we must execute anerase
.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 containerspecific 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 containerspecific functions. ... int int_arr[] = {2, 1, 2, 2, 2, 3}; vector<int> int_vec(int_arr, int_arr + 6);
If 1
occurs inint_vec
, next two lines insert0
right before the first occurrence of 1. Otherwise,o
is inserted at the end ofint_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 the2
's. Notice—since there is no random access support—unlike invector
s anddeque
s, 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 higherorder functions: accumulate
, find
, for_each
, and transform
. These functions do the equivalent of reduce
, filter
, foreach
, and map
functions provided in functional programming languages.
Example: ... 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 byfor_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, last1), by means of downheaping, so as to preserve the heap property for [first, last1). Similarly,given a container—say [first, last)—whose subsequence [first, last1) has the heap property, push_heap inserts the item in position last1 into the container by means of upheaping, so that we get the whole container to satisfy the heap property.

Function Objects
[edit  edit source]An intuitive notion lacking in C++, like almost any other imperative language, is the treatment of functions as firstclass values. It's not possible to pass around and return functions; one must resort to using pointertofunctions, 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  edit source]#ifndef POLYNOMIAL_HXX
#define POLYNOMIAL_HXX
#include <ostream>
using namespace std;
namespace CSE224 {
namespace Math {
class Polynomial {
friend ostream& operator<<(ostream&, const Polynomial&);
public:
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 compilerprovided 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 Polynomial
s and double
s 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
toPolynomial
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 seconddegree component, the second the coefficient of the firstdegree 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 firstclass 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&);
private:
double _sec, _fir, _con;
}; // end of class Polynomial
} // end of namespace Math
} // end of namespace CSE224
#endif
Implementation
[edit  edit source]#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 equalitytest 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";
return(os);
} // end of ostream& operator<<(ostream&, const Polynomial&)
} // end of namespace Math
} // end of namespace CSE224
Test Program
[edit  edit source]#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 Polynomial
s.^{[2]} Assuming lefttoright, 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  edit source]gxx –c Polynomial.cxx↵ # Using DJGPPgxx 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 {
public:
virtual bool operator()(T) = 0;
}; // end of (abstract) class Filter
class EvennessFilter : public Filter<int> {
public:
virtual bool operator()(int num) { return(num % 2 == 0); }
}; // end of class EvennessFilter
class NamesWithNLettersFilter : public Filter<string> {
public:
NamesWithNLettersFilter(unsigned int n = 1) { _n = n; }
virtual bool operator()(string name) { return(name.length() == _n); }
private:
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  edit source]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 lessthan operator of the underlying type, which means you should implement the lessthan operator. Passing different function objects for the same underlying type can be used to modify the ordering criterion used.^{[3]}
Arithmetic Function Objects
[edit  edit source]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. 


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.


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.


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


Relational Function Objects
[edit  edit source]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. 


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

count_if returns the number of items in the container that satisfies the predicate passed in the third argument. bind2nd is a socalled 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.


In addition to predefined function objects, you can pass userdefined 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. 

Logical Function Objects
[edit  edit source]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. 


Simulating Local Functions
[edit  edit source]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 int
s is being made, which means the compiler or the compilerlinker pair will synthesize a version of the following function that takes an array of int
s.
template <class Elmt_Type>
void quicksort(Elmt_Type *arr, int l, int r) {
class Pivot {
public:
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 lessthan 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 closedopen. 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  edit source] ↑ 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 computationintime while an iterator does it using computationinspace.
 ↑ For pedagogical purposes, we assume the expression is evaluated sequentially from left to right. In reality, evaluation can be carried out in any order; subexpressions can even be reordered by the compiler. That is; we may end up with an addition of two
double
s and threePolynomial
s.  ↑ This is very much like the
Comparable
andComparator
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.