Back to July Calendar

Previous Entry Next Entry→

September 28, 2005

I could do graphics, random partitions or investigate vectors....hmmm.

How about vectors?  Or do I need lists?  Let's see...

Alexander Stepanov and Meng Lee at HP are credited with developing the Standard Template Library (STL) which is a proof of concept  for generic programming with templates.  The three essential components of the STL are containers (popular templatized data structures), iterators and algorithms.  A container is a data structure capable of storing any kind of object and there are three types of these: first-class containers, adapters and near containers.

There are member functions associated with each STL container and some member functions which are common to all.  A vector is a dynamically resizable array--and these are what I'm interested in using to improve the partition code from yesterday.  Later we can find opportunities for using other containers such as  the list and the deque (double-ended queue.) 

STL iterators are similar to pointers and are used to manipulate container elements, or even simple arrays.  Algortihms are functions that do standard data processing such as sorting and comparing.  Each first-class container’s supported iterator type determines whether the container admits a particular algorithm. Iterators give access to container elements and enable many of the STL algorithms to be applied to several containers independent of the container implementation. As long as a container’s iterators support the minimum requirements of the algorithm, the algorithm can process that container’s elements. This means you can create new algorithms to handle the elements of different container types.

Here's a table of container types from chapter 21 of Deitel.

Standard Library
container class
Description
Sequence Containers  
vector
rapid insertions and deletions at back
direct access to any element
deque
rapid insertions and deletions at front or back
direct access to any element
list
doubly linked list, rapid insertion and deletion anywhere
Associative Containers  
set
rapid lookup, no duplicates allowed
multiset
rapid lookup, duplicates allowed
map
one-to-one mapping, no duplicates allowed, rapid key-based lookup
multimap
one-to-many mapping, duplicates allowed, rapid key-based lookup
Container Adapters  
stack
last-in-first-out (LIFO)
queue
first-in-first-out (FIFO)
priority_queue
highest priority element is always the first element out
Fig. 21.1 Standard Library container classes.

 

You can find this and other good info at http://ptgtraining.com/CyberClassroom/0025o8/ch21/21_01/content.htm

About Iterators

Iterators keep track of the state of particular containers on which they operate, and so need to be implemented in ways specific to the type of container, though some iterator operations are the same for all containers. The dereferencing operator (*), for example, will always dereference an iterator so that you can use the element to which it points. Likewise, the ++ operator will move the iterator to the next element.

STL first-class containers provide member functions begin() and end(), very much reminiscent of the OpenGL functions, no? Function begin() returns an iterator pointing to the first element of the container. Function end() returns an iterator pointing to the first element past the end of the container (an element that doesn’t exist). If iterator i points to a particular element, then ++i points to the “next” element and *i refers to the element pointed to by i. The iterator resulting from end() can be used only in an equality or inequality comparison to determine whether the “moving iterator” (i in this case) has reached the end of the container.

An object of type iterator refers to a container element that can be modified. A const_iterator refers to a container element that cannot be modified.

Iterators with sequences (also called ranges) can be input sequences or output sequences or in containers. 

The program of below (from Deitel) demonstrates input from the standard input (a sequence of data for input into a program), using an istream_iterator, and output to the standard output (a sequence of data for output from a program), using an ostream_iterator.  The program inputs two integers from the user at the keyboard and displays the sum of the integers.

// Fig. 21.5: fig21_05.cpp
// Demonstrating input and output with iterators.
#include <iostream>

using std::cout;
using std::cin;
using std::endl;

#include <iterator>  // ostream_iterator and istream_iterator

int main()
{
   cout << "Enter two integers: ";

   // create istream_iterator for reading int values from cin
   std::istream_iterator< int > inputInt( cin );

   int number1 = *inputInt;  // read int from standard input
   ++inputInt;               // move iterator to next input value
   int number2 = *inputInt;  // read int from standard input

   // create ostream_iterator for writing int values to cout
   std::ostream_iterator< int> outputInt( cout );

   cout << "The sum is: ";
   *outputInt = number1 + number2;  // output result to cout
   cout << endl;
   cin >> number2;
   return 0;

} // end main

If you're like me, you might be thinking, "Whoa, that's a lot of work to do something that could more easily have been done without iterators!"  And you'd be...right?  The point being that this new power will allow us to do new better things...I hope.  Here's the unsurprising output:

Enter two integers: 6354354 6574674
The sum is: 12929028

The istream_iterator extracts int values in a type-safe manner from the standard input object cin and iterator inputInt is dereferenced to read the first integer from cin and assigns that integer to number1.

Similarly, the ostream_iterator inserts int values in the standard output object cout and then an integer is output to cout by assigning to *outputInt the sum of number1 and number2.   Notice the use of the dereferencing operator * to use *outputInt as an lvalue in the assignment statement. The iterator must be incremented with ++ (both preincrement and postincrement can be used) to output another value.

The heierarchy of iterator categories used by STL is shown at right.  The weakest categories are at the top--and while this is not inheriance in the technical sense, you have all the functionality of the bidirectional type iterators in the the random access type iterators...and then some. 

Thus, containers that support random-access iterators can be used with all algorithms in the STL. Further, pointers into arrays can be used in place of iterators in most STL algorithms, including those that require random-access iterators. Shown below is a table of the iterator category supported by each of the STL containers. Note that only vectors, deques, lists, sets, multisets, maps and multimaps (i.e., the first-class containers) are traversable with iterators.

Container Type of iterator supported
Sequence containers  
   vector
random access
   deque
random access
   list
bidirectional
Associative containers  
   set
bidirectional
   multiset
bidirectional
   map
bidirectional
   multimap
bidirectional
Container adapters  
   stack
no iterators supported
   queue
no iterators supported
   priority_queue
no iterators supported

A Now a Word About Algorithms

Algophobia (al-guh-FO-bee-uh) noun

Usually having a phobia might brand you as a nut but here is a phobia that indicates you're a regular human being, if you have it. Algophobia is the fear of pain. Though the word indicates an unusual, morbid fear of pain, producing intense anxiety.

There is even an instrument called an algometer to measure pain. Now I know why they called that grueling course "algorithms" in my computer science curriculum.

We got the word from the Greek algo- (pain) and -phobia (fear).

-Anu Garg (gargATwordsmith.org)