Programming With

The Standard

Template Library

Contents:

---

1.1	Introduction
1.2	The std Namespace
1.3	std::string
1.4	std::list
1.5	std::vector
1.6	std::deque
1.7	std::set
1.8	std::map
1.9	std::stack
1.10	Conclusion
1.11	Bibliography / Recommended Reading

---

 

1.1 Introduction

---

 

 

The C programming lanugage introduced the notion of programming a computer to a large number of people. One of the biggest and most interesting parts of C was the concept of pointers. Pointers unleashed a large amount of programming idioms that are still with us today. For example, linked-lists, stacks, queues and trees can only exist with pointers. They also brought more headaches for the average programmer than could have ever been imagined, especially when the project sizes grew larger and larger. Pointers had to be consistantly checked to see if they were NULL, and the programmer had to be sure that he/she was setting those pointers to NULL.

 

Pointers are unfortunately one of the biggest problems that the language introduced, and a few people started analysising pointer usage, and how they could reduce the numbers of errors caused by them. To start with, it's worth noting that there are only a few situations where pointers are actually useful, and as you'll see most of these are due to language limitations of C...

 

1. Passing a large structure by reference into a function.

If a structure was formed such as :   typedef struct {   double DoubleArray[10];   float x,y,x;   char name[256]; } myStruct; Passing it into a function could be done in one of two ways. Firstly you could use call be value : void func( myStruct ); or you could use simulated call by reference utilising pointers : void func( myStruct* ); Calling the function by value has the problem that the entire variable is copied when being passed to the function. Not only is this slow, but it is also a waste of memory (especially considering the above structure uses over 300 bytes). So call by reference using C++ references is preferable in this situation, and pointers need not be used.

 

2. Memory Allocation

In order allocate memory in C you required a pointer to determine where the memory allocation occurred, and then access that memory afterwards. For example : int *ptr = (int*)malloc( 10 * sizeof(int) ); The above line allocate 10 integers and stores the address returned within ptr. Whilst this is not terrible, it is open for abuse. For example, there would be nothing to stop you changing the pointer to value to point somewhere completely random. This will break the application by either causing a memory leak or worse, a page fault. C++ brought with it the notion of encapsulation. This was able to provide a few mechanisms to hide away pointers until they were no longer needed for memory allocation. For example, if you needed to create a single object, you could use a singleton pattern (see design patterns by Gamma et al) :   struct Singleton {   static void Destroy() {   delete ms_pInstance; ms_pInstance = NULL; } static Singleton& GetInstance() {   if(!ms_pInstance) ms_pInstance = new Singleton; return *ms_pInstance; } private:   Singleton() {} ~Singleton() {} static Singleton* ms_pInstance; }; Singleton* Singleton::ms_pInstance = NULL;   The above code hides the pointer, constructor and destructor within the private section of the class. This prevents people deriving from the class as well as creating more than one instance. The other more powerful construct that C++ offered was that of templates. It became entirely possible to construct powerful templates for things such as lists, queues, dynamic arrays (vectors) etc. These still internally used pointers, however they were hidden away internally so that no-one could break them, or get access to them. After a while the standard template library came into existance. The best C++ programmers from around the world developed some of the most efficient and safest templates for these common constructs. This document is designed to help you understand the benefits of using them and how they save a great amount of time. Therefore, why manage your own dynamic array or lists when std::vector and std::list will do the same?

 

3. Passing a structure to a function to act upon it's data

Consider this innocent piece of code : struct vec3 {   float x,y,x; }; float length( vec3* ptr ) {   return std::sqrt((ptr->x*ptr->x) + (ptr->y*ptr->y) + (ptr->z*ptr->z) ); }; vec3 myVector; std::cout << "length is " << length(&myVector) << std::endl; This was the C way of calculating the length of a 3D vector. One of the biggest problems that becomes immediately apparent is that the function length must recieve a valid pointer address for it to work. Passing NULL into the length function would cause a fairly serious runtime error. In fact, in C++ there is absolutely no reason to do this. It can easily be replaced by a single member function :   struct vec3 {   float x,y,z; float length() {   return std::sqrt( (x*x) + (y*y) + (z*z) ); }; }; vec3 myVector; std::cout << "length is " << myVector.length() << std::endl;   Not only is this more readable, but it is also a lot safer - use it!!

 

In actual fact, it is extremely rare that you need to use a pointer anywhere in your code. People some times claim that you may need to pass an array into a function, well in that case you should be passing a reference to a std::vector. What about passing a character string they say? Well, you should be passing a std::string object instead (this doen't require a reference because it is reference counted so you gain no real benefit).

 

The Standard Template Library is there to make your life easier as a programmer so start using it. Not only is it fast, it is also bug free and extremely flexible. Have fun learning it!

 

 

 

 

1.2 The std namespace

---

 

Everything in the Standard Template Library exists within the std namespace. For those who aren’t familiar with the C++ namespace concept, I’ll present a quick overview.

 

1.2.1. Reasons for namespace use

Namespace’s are designed to prevent naming conflicts that often occurred with C. It resolves the problem by pre-fixing a name to the front of your variables and functions that helps to uniquely identify them.

 

 

1.2.2. Creating a namespace

 

---

// declare the namespace ‘name’
namespace name
{

// the integer ‘name::i’ int i;

};

// ‘i’ is not the same variable as ‘name::i’
int i;

---

 

 

1.2.3. Accessing the contents of a namespace

The scope resolution operator ( :: ) is used to get access to a variable or function that is contained within a particaular namespace.

 

---

// access i declared in the ‘name’ namespace
name::i = 5;

// access global i
i = 6;

---

 

 

1.2.4. using namespace <name>

It is possible to remove the namespace ‘name’ from the front of your functions & variables with use of the using namespace directive. An example of it’s use would be

 

---

namespace fred
{

float myValue;

};

// include the contents of the fred namespace into
// the global namespace
using namespace fred;

// This refers to fred::myValue but doesn’t need
// the scope resolution because it is now global
myValue = 10;

---

 

I have a confession, I have never written a single using namespace directive for a simple reason. See it you can spot the problem with the following code…

 

---

namespace name
{

int i;

};

int i;

using namespace name;

i = 10;

---

 

To prevent problems like the above, only ever use this in *.cpp files after all of your include’s to prevent it messing up other header and source files.

 

 

 

 

 

1.3 std::string - Easy string manipulation

---

 

 

One of the most common things that programmers need to do, and also one of the things that is most difficult in C, is string manipulation. In C, this was extremely tedious and time consuming, not to mention the amount of time wasted spent debugging and protecting against memory allocation, and out of bounds errors. The Standard Template Library removes a lot of the hassle by defining the std::string class. This wraps most of the required functionality and error checking associated with C strings into something very easy to use.

 

 

1.3.1. Some Simple String Operations

 

Probably one of the best ways to describe the string class is to look at a couple of examples of it’s usage…

 

---

#include <iostream>
#include <string>

void main()
{

// string creation and assignment from C-style strings, // note the use of the ‘=’ operator for string copying/assignment... std::string str = “Hello”; // string concatonation using += str += “ World”; // print the string std::cout << str << std::endl; // string compare operation using the ==,!=,>,<,>= or <= operators if( str == “Hello World” ) {   // use the size member function to get the length for( int i=0; i < str.size(); ++i ) {   // access individual chars using the [] operator std::cout.put( str[i] ); } // terminate the line std::cout << std::endl; }

}

---

 

The above code shows how to append string’s and characters to the string. We can also make use of the comparison operators (==,!=,>,<,>=,<=) to perform comparisons between strings. The final operator it also impliments is the array bracket ([]) operator to allow us to access the individual char’s in the string in a similar way to character strings in C.

 

There are some downsides to std::string, primarily it does not define operators to add in the standard data types such as float, int etc. If this functionality is required, you can create your own operators to do it, ie :

 

---

std::string &operator += (std::string &str,float &f)
{

char buffer[16]; sprintf(buffer,"%f",f); str += buffer; return str;

}

---

 

… Not the most ideal solution, but useful sometimes. Another solution would be to make use of std::ostrstream and build the string that way, ie

 

---

#include <strstream>
#include <iostream>
#include <string>

void main() {

// create a float variable float f = 0.098f; // create the string stream to convert the float to a text string std::ostrstream os; // place the float in the stream os << f; // assign the built up string to a new std::string object std::string s = os.str(); // print the string std::cout << s << std::endl;

}

---

1.3.2. Other Useful Member Functions

 

• Checking for an empty string

---

std::string str;

if( str.empty() ) {

// do something std::cout << "String is empty" << std::endl;

}

---

 

• Resizing the string

---

std::string str = "HELLO WORLD";

str.resize(5);

std::cout << str << std::endl;

---

 

• Returning a sub-string

---

std::string str = "HELLO WORLD";

std::cout << str.substr(4,8) << std::endl;

---

 

• Returning the number of chars in the string

---

std::string str = "HELLO WORLD";

std::cout << "size is " << str.size() << std::endl;

---

 

 

• Returning the string as a c-string (const char*)

---

std::string str = "HELLO WORLD";

const char *c_string = str.c_str();

std::cout << c_string << std::endl;

---

 

 

 

 

1.4 std::list< type >

---

 

The linked list container class std::list defines a doubly linked list that can be used commonly throughout your programs. This allows for linear traversal (in either direction) of the linked list. It allows for (virtually) free removal and insertion of elements and is defined in the header file <list> (!! NOTE: NOT <list.h> !!)

 

1.4.1. Inserting & Removing Elements

 

There are a number of ways to insert an element into a list, the following details possible methods…

---

// include the list header...
#include <iostream>

// create an integer linked list
std::list< int > someList;

// push the value 5 to the front
someList.push_front(5);

// push the value 4 to the back
someList.push_back(4);

---

 

The stl::list is instantiated in the same way as any template container class. In the above example we make a simple integer list. The push_front and push_back methods are the two commonest methods of inserting elements (inserting in the middle of the list will be covered later).

Removing elements can be done in an equally easy way...

---

// pop the element at the front
someList.pop_front();

// pop an element from the back
someList.pop_back();

---

 

1.4.2. Iterating through a list

 

Traversing a list involves the use of an iterator. This is essentually a small class that acts in a similar way to a pointer. Using ++ moves the iterator to the next element, -- moves the iterator to the previous element. Consider the following code :

 

---

// create an iterator to point to the start of the list
std::list< int >::iterator it = someList.begin();

// move the iterator on by an item until we reach the end of the list
for( ; it != someList.end(); ++it )
{

std::cout << *it << std::endl;

}

---

 

Initially, an iterator is created that references the first element in the list and a for loop is used to traverse the list. What’s of some importance here, is the terminating condition, which evaluates not-equal to the last element. This is used because it is quicker for the CPU to perform, than greater/less than tests. Use of the pre increment operator prevent’s generation of a temporary variable, unlike the post-increment operator.

1.4.3. Iterating through a list II

 

Using the iterator method above for iterating through a list is all well and good, however one of the drives of STL, is to make code more readable at a glance. 99% of the time, loops end up looking like the following pseudo-code…

 

---

// loop through the array or list...
for each element in the list
{

perform some action upon it

}

---

 

STL attempts to combat this problem with the for_each operator defined in <algorithm>. The code below shows both possible methods side by side.

 

---

#include <iostream> // the iostream includes
#include <list> // the linked list includes
#include <algorithm> // include the header that defines for_each

// the action to be performed on each item in the list
//
void PrintElement( int item ) {

std::cout << item << std::endl;

}

void main()
{

std::list< int > someList; // initialise the list // for(int i=0; i<10; ++i)   someList.push_back(i);   //------------------------------------------------------ METHOD 1 // create an iterator to point to the start of the list // std::list< int >::iterator it = someList.begin(); // move the iterator on by an item until we reach the end of the list // for( ; it != someList.end(); ++it )   std::cout << *it << std::endl;   //------------------------------------------------------ METHOD 2 // use for each to do the same as METHOD 1 above // std::for_each( someList.begin(), someList.end(), PrintElement );

}

---

 

Now for a quick bit of syntax, the first two parameters take iterators to a list (or any other STL container) that define the run of items to perform the action upon. The last parameter is the function to act upon the data. It has no restrictions on function type (ie, it can be a global function, member function etc) but it has to take a single parameter of either the type of data held, a reference to the data held (use for large structures), or a constant variation of the previous two. For example, I could have used any of the following for the function prototype :

---

void PrintElement( int item );
void PrintElement( int &item );
void PrintElement( const int item );
void PrintElement( const int &item );

---

 

So the only question left is why we would want to go to that trouble and what it can offer us. This is where the only real answer is one of improved coding style and readability. If we translate the for_each loop detailed previously, we get the following statement …

For each element between the first element and the last element, print the element

The above statement makes it clear what the intention of the loop is and why it is there. Although this example is fairly trivial, writing loops is something that is very common, often with more complex actions performed on data within those loops. By abstracting the code in this way it forces a reduction in the main bulk of your code and makes your intention far clearer than with traditional for loops. It also promotes the idea that you are programming algorithms to act upon data elements.

 

This is one construct that I personally use a lot, however, because it is firmly in the realms of coding style, it remains a choice for the programmer and what they believe to be more readable.

1.4.4. Sorting a list

 

This is where you start to see the big benefits of using STL, lets say we want to sort a list of elements in ascending order…

 

---

// sort the list in ascending order
someList.sort();

---

 

That’s it! It is worth mentioning at this point that <algorithm> defines a number of sort algorithms that apply to STL containers, however they do not work with std::list. This is the single reason why sort is a member function of std::list in this case. The sorting algorithm gives a worst case sort of N log N, where N is the number of elements in the list.

1.4.5. Copying a list

 

For some reason people have a problem when copying stl containers. For example, I have seen a number of people doing the following…

---

// the new list
std::list< int > newList;

// create an iterator to point to the start of the list
std::list< int >::iterator it = someList.begin();

// copy each item in the list
for( ; it != someList.end(); ++it )
{

newList.push_back( *it );

}

---

 

This is extremely bad ! It should always be done with the assignment operator (=). i.e.

 

---

// the new list
std::list< int > newList = someList;

---

 

Easy stuff!

 

 

 

1.4.6. Determining the size of the list

The number of elements within the list can be determined by using the size member function, ie

 

---

unsigned int elementCount = someList.size();

---

 

 

 

1.4.7. Re-sizing the list

The number of elements within the list can be set using the resize member function. The prototype for the function is as follows….

 

---

void std::list<TYPE>::resize(unsigned int num, TYPE val = TYPE());

---

 

The first parameter num is the number of elements you now want in the list. The second parameter is used only when the list needs to be increased in size and determines the value for any elements that are appended to the end of the list.

 

 

1.4.8. The erase member function:

The erase member function can be used to remove an element from anywhere in the list. The problem with erase is that it requires an iterator as it’s parameter. Whilst this is not a big deal as such, it will however invalidate the iterator after the element has been erased. This means we have to use a clever piece of con-trickerey to get around the problem with the post-increment or post-decrement operator (the only time when use of these is sensible)

Consider the following code :

 

---

void main()
{

// create an initialise a list of integers std::list<int> myList; for( int i=0; i<10; ++i )   myList.push_back(i); // iterate through the list std::list<int>::iterator it = myList.begin(); while( it != myList.end() ) {   // if the value is 5, remove the element if( *it == 5 ) {   // note the ++ operator to prevent iterator invalidation myList.erase( it++ ); } else {   // move the iterator on to the next element ++it; } }

}

---

erase can also be used to remove a run of elements. For example in the above example we could have replaced the line

---

myList.erase( it++ );

---

With a line such as...

---

myList.erase( myList.begin(), it++ );

---

which would have removed all elements from the beginning of the list, up to and including the element with the value 5.

 

1.4.9. The insert member function(s):

There are a total of three possible insert functions that are at your disposal. The three are as follows

---

iterator insert( iterator& position, T& value );
void insert( iterator& position, int number, T& value );
void insert( iterator& position, iterator& start, iterator& end );

---

 

 

The following code illustrates all three ways of inserting…

---

void PrintElement(int i) {

std::cout << i << std::endl;

}

void main()
{

// create an initialise a list of integers std::list<int> myList; // get an iterator to the start or the list std::list<int>::iterator it = myList.begin(); // insert the number 2 before the iterator position it = myList.insert( it, 2 ); // insert the number 3 into 4 positions before iterator pos 'it'. myList.insert( it, 4, 3 ); // move the iterator back 2 places --it; --it; // insert the run of values at the beginning copied from // the iterator position to the end of the list. myList.insert( myList.begin(), it, myList.end() ); // print the elements std::for_each( myList.begin(), myList.end(), PrintElement );

}

---

 

1.4.10. A General Recommendation

It is generally recommended that you use typedefs for your list types, ie :

---

typedef std::list<int> intList;

---

The reason is simple, all of the methods presented above work with another common STL container that deals with dynamic array types, std::vector. By limiting yourself to the above methods and by using a typedef instead of the specific templated definition, you can just change the typedef to switch instantly between a list or array type at the drop of a hat (with the exception of the sort member function detailed above)

 

 

 

1.5 std::vector< TYPE >

---

 

1.5.1. Sorting a vector

Sorting itself is not strictly part of the container type itself, it is something that is detailed in <algorithm>. The reason that list had it’s own specific sort member function is due to the quickest sorting algorithms requiring random access to elements – something that std::list does not provide. The sort function is defined as such:

 

---

void sort( iterator first, iterator last );
void sort( iterator first, iterator last, Predicate P );

---

 

The first prototype sorts elements in ascending order where-as the second provides a mechanism to specify a function to determine how the elements are sorted. As an example, the code below uses both functions to sort a vector in descending and ascending order.

 

---

#include <cstdlib> // stdlib.h is the C name for this! (for std::rand())
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// simple print element function for for_each
void PrintElement(const int &i) {

cout << i << " ";

}

// a simple greater than predicate
bool GreaterThan(const int& a,const int& b) {

return a>b;

}

void main()
{

// a simple vector vector<int> vec; // add 10 random numbers between 0 and 1000 to the vector for(int i=0;i<10;++i) vec.push_back( rand()%1000 ); // print the initial un-sorted array cout << "Unsorted\n"; for_each(vec.begin(),vec.end(),PrintElement); // sort the array using the custom a>b predicate sort(vec.begin(),vec.end(),GreaterThan); // print the sorted array cout << "\n\nSorted With a>b predicate\n"; for_each(vec.begin(),vec.end(),PrintElement); // sort the array using the default predicate a<b sort(vec.begin(),vec.end()); // print the sorted array cout << "\n\nSorted With Default a<b predicate\n"; for_each(vec.begin(),vec.end(),PrintElement);

}

---

 

 

1.5.2. Iterating through a vector in the same way as a C array

 

In C++, you can write code like the following

 

---

int myArray[10];
for(int i=0;i<10;++i)
{

myArray[i] = 0;

}

---

 

It would be nice if we could write code like that using vector’s, ie

---

std::vector<int> myVector;
myVector.resize(10);
for(int i=0;i<10;++i)
{

myVector [i] = 0;

}

---

 

…Well, you can! Everything above works with no real problems. The advantage though is that you can easily resize the above array, remove and insert elements etc and there is no difference in speed between the two. So why not use a vector everytime you need an array?

 

 

1.5.3. Why use an iterator then?

 

I’m sure most people prefer reading the above code as apposed to those weird iterator things. So why do we want to use an iterator? Well, the reason is this. As you should be aware, an array is merely a pointer to the first element, I could write your average array iterating code using pointer notation instead and then you would come across a loop such as this :

 

---

int myArray[10];
for(int i=0;i<10;++i)
{

*( myArray + i ) = 0;

}

---

 

This is actually what the array operator does under the surface. Each loop, we use an increment on our counter, and then we dereference the element in order to access it. However, in order to dereference an element, we use an addition to get the pointer to the correct element, and then de-reference it to access the actual data.

We can make a speed improvement here by removing the counter and using a pointer to iterate through the array. This allows you to remove the addition and is therefore a speed improement (maybe not significant on a single loop, but it starts to make a big difference in large applications), ie.

 

---

int myArray[10];

// determine the pointer position we want the loop to exit on
int *end = myArray+10;

// set a pointer it to point to the first element
int *it = myArray;

// loop until it reaches the end of the array
for( ; it < end; ++it )
{

*(it) = 0;

}

---

 

This now uses a pointer, it, to walk through each element in the array until it points to end and we exit from the loop. This has reduced the loop to merely de-reference the pointer and uses the pre-increment operator to move the pointer on to the next element. One final place where we can gain a speed improvement is by looking at the terminating condition, the less than operator can be replaced by the not-equal operator. The reason for this, is because we know that the pointer will always get to the end of the loop (end pointer) and the not-equal operator is the quickest possible CPU comparison we can do, so we end up with :

---

int myArray[10];

// determine the pointer position we want the loop to exit on
int *end = myArray+10;

// set a pointer it to point to the first element
int *it = myArray;

// loop until it reaches the end of the array
for( ; it != end; ++it )
{

*it = 0;

}

---

 

This is actually why iterator’s for vectors and lists were provided, so for our vector we can write the following (highly optimised!) code :

---

std::vector<int> myVector;
myVector.resize(10);

// create the iterator to loop through the array
std::vector<int>::iterator it = myVector.begin();

// loop until we reach the end
for( ; it != myVector.end(); ++it )
{

*it = 0;

}

---

The readability of the above isn’t amazing which is the reason why the for_each function was provided in STL. In fact, we can easily now guess what the for_each function looks like :

---

template< typename iterator, typename Function >
void for_each( const iterator begin, const iterator end, Function action )
{

for( iterator it = begin; it != end; ++it )   action( *it );

}

---

So after all of that we find that accessing an array linearly with iterator’s is infact quicker than using the array operator. So why on earth was it provided then? … The answer? Random access of elements. This is one area where using the array operator is the best method of accessing elements quickly.

There is however a down side to using the [] operator for such a purpose, the array bounds are never checked so you can still break the program if you access an invalid element. To counter this the member function, "at" was added :

---

reference at(unsigned int pos);

---

When called it acts in the same way as the array operator, except it checks the size of the array to prevent an out of bounds error. If you try to access an invalid index, it will throw an out_of_range error which you can catch and deal with appropriately, the following code illustrates it’s usage

---

#include <iostream>
#include <vector>

using namespace std;

void main()
{

// a simple vector vector<int> vec; // add 10 numbers to the vector for(int i=0;i<10;++i)   vec.push_back( i ); // surround our for loop with a try block, this in effect sets a safety // net around the code block, and allows us to throw an error before the // error actually occurs. The block stops executing and jumps to the // catch statement which deals with the error safely. try {   // try to get to element index 10 (out of range error) for(int i=0;i<11;++i)   cout << vec.at(i) << endl; } // catch the out_of_range error thrown to prevent program // termination, and carry on normally catch(out_of_range &err) {   // the error has a what member function that returns a string // that describes the error that occured   cout << "Caught the out_of_range error\n\t- " << err.what() << endl; } // just to prove the program is now continuing happily cout << "!! No harm done !!" << endl;

}

---

 

 

 

1.6 std::deque< TYPE >

---

 

The std::deque container has exactly the same interface and usage as the std::vector type, the only real differences are internal. The std::vector type works by reserving a certain amount of space which will be re-allocated when the array outgrows that capacity. When that happens, all elements are moved to a brand new chunk of memory. Insertions and deletions are quickest when they occur at the back of the array. The std::deque however is optimised for insertions and deletions at the front and back. It is more akin to the std::list type, however not as quick for elements inserted or removed from the middle of the list, where as with the std::list these are virtually free.

1.7 Advanced STL Containers

---

 

The std::deque, std::list and std::vector containers are generally thought of as the core container types that are used most often, there are however additional containers that have specific storage functionality. These are roughly built into three distinct groups

 

• Sorted Containers – those that maintain an ordered list of their contents, ie, std::set, std::multi_set

• Quick reference containers – these hold data and allow quick retrieval of specific data elements based on a unique key for the data element, ie, std::map, std::hash_map, std::multi_map

• Special Storage Containers – these are usually built on top of one of the core container types and usually restrict access in some way for special reasons, ie std::stack, std::queue, std::priority_queue

 

 

The following section will detail one container from each group. It is not really required reading, however it may be a section that is worth reading in order to be aware of what is available…

 

 

 

1.8 std::set< TYPE >

---

 

The std::set can be thought of as a permanenty ordered std::list. There are however some huge fundamental differences in the way it works !! For the most part, the interface for a set is the same as the std::list, however the std::set does not maintain a list internally, even though it may appear that way from outward appearences. For a start it stores it’s data in a tree-like structure to allow for the quick sorting of data elements. As a direct result of this it does not define pop_front, push_front, push_back or pop_back member functions. You can however use the insert and erase member functions in the same way.

 

By default, the container is ordered using the less than comparison (ie, values are ordered in ascending order). This behaviour can be changed however, but I shall deal with that later. An example of it’s usage would be the following :

 

---

#include <cstdlib> // stdlib.h is the C name for this !
#include <iostream>
#include <algorithm>
#include <set> // std::set is defined here (and std::multi_set btw)

using namespace std;

// simple print element function for for_each
void PrintElement(const int &i) {

cout << i << " ";

}

void main()
{

// create an integer set set<int> mySet; // add 10 random numbers between 0 and 1000 to the set for(int i=0;i<10;++i) {   // using insert here instead of push_back/push_front mySet.insert( rand()%1000 ); } // print the sorted set for_each(mySet.begin(),mySet.end(),PrintElement);

}

---

As mentioned earlier, it is possible to change the default ordering of the set. This is done with a function object (an empty class that overloads the function () operator). The default function object is the following :

 

---

template< typename T >
struct less
{

// the overloaded function operator for the object bool operator()(const T& x, const T& y) const {   return x < y; }

};

---

 

The above is a template class although it doesn’t nessarily have to be, for example you could provide the following struct for greater-than integer comparisons :

 

---

struct IntGreaterThan
{

// the overloaded function operator for the object bool operator()(const int& x, const int& y) const {   return x > y; }

};

---

 

… However, for the sake of generalisation, we can use the following template :

 

---

template< typename T >
struct GreaterThan
{

// the overloaded function operator for the object bool operator()(const T& x, const T& y) const {   return x > y; }

};

---

 

The following example shows how to specify this as the second template argument to the std::set< Type, Comparison = less<Type> > container:

 

---

#include <cstdlib> // stdlib.h is the C name for this !
#include <iostream>
#include <algorithm>
#include <set> // std::set is defined here (and std::multi_set btw)

using namespace std;

// a template function object for a greater than comparison
template< typename T >
struct GreaterThan {

// the overloaded function operator that performs the comparison bool operator()(const T& x, const T& y) const {   return x > y; }

};

// function to print an element, used in std::for_each
void PrintElement(const int &i) {

cout << i << " ";

}

void main()
{

// create an integer set with the GreaterThan comparison for int’s // !! NOTE !! The comparison class is the 2nd template param and the // very important space at the end of the template parameters! set<int,GreaterThan<int> > mySet; // add 10 random numbers between 0 and 1000 to the set for(int i=0;i<10;++i)   mySet.insert( rand()%1000 );   // print the sorted set for_each(mySet.begin(),mySet.end(),PrintElement);

}

---

 

 

 

1.9 std::map< TYPE >

---

 

(There is accompanying code for this section, mapExample.cpp)

 

The STL map holds a set of entries which uses a pair of data elements, the Key and the Data. The main premise of the map is to order the entries via their keys, by default this ordering is using the less-than predicate (which can be changed in the same way as the set).

 

To define a std::map, you need to provide template arguments in the following fashion :

 

---

std::map< Key, Data > myMap;

---

 

Entries within the map are held as a std::pair, the template for which looks like this :

 

---

template< typename F, typename S >
struct pair
{

F first; S second;

};

---

 

This is fairly important to bear in mind when dealing with the std::map, for a start, when inserting an element into the map you should use the std::make_pair(F,S) function, ie :

 

---

// create a map using a Key type int, and a data type of float
std::map< int, float > someCrapMap;

// create a couple of values...
int i = 1;
float f = 0.54f;

// use the make_pair function to provide a pair for the
// insert function
SomeCrapMap.insert( std::make_pair( i , f ) );

---

 

The other point to bear in mind is that the iterator’s for maps will reference one of the pairs also, so say for example we wanted to iterate the map and print the variables of the above pair using for_each, we’d have to access the first and second members of the pair as such :

 

---

// the function to print the key and the data
void PrintPair( std::pair< int, float > &Entry )
{

std::cout

<< “Key “ << Entry.first << “\nData” << Entry.second << std::endl;

}

// print all entries
std::for_each( SomeCrapMap.begin(), SomeCrapMap.end(),PrintPair);

---

If we were doing that without for_each, we would end up with something such as :

 

---

// get an iterator to the first element
std::map< int, float >::iterator it = SomeCrapMap.begin();

// print all entries
for( ; it != SomeCrapMap.end(), ++it )
{

	// using the -> to access the first and second // elements of the current pair
	std::cout	<< “Key “ << it->first << “\nData” << it->second << std::endl;

}

---

 

1.9.1. Finding a Data Element (quickly)

 

The std::map comes into it’s own when quickly trying to find data elements via the key. The find member function uses the internal tree structure to very quickly find elements for you in as many steps as the log of the number of elements (logaithmic time). The prototype is as follows :

 

---

iterator find(const Key& key);

---

 

If the element is not present, then it will return the end() iterator. When using the find member function, try and remember that it will be an iterator that references a pair, not the data element, for example :

 

---

int key = 1;

// find the pair relating to key value 1
std::map<int,float>::iterator it = SomeCrapMap.find( key );

// check to see if the element was found
if( it != SomeCrapMap.end() )
{

	// output what we found
	std::cout	<< “Found Element with Key “ << it->first << “ And data “ << it->second << std::endl;

}
else
{

// output an error message std::cerr << “Element Not Found” << std::endl;

}

---

1.10 std::stack

---

 

The std::stack is a very restricted container that only allows for insertions and removals from the top of the stack. The Container template parameter by default uses the std::deque type as it’s storage. It’s extremely rare that you ever have to change this, however it can be done if you really have to. This is very similar to the std::queue template, and both are extremely simple to use (this page details every member function).

1.10.1. Pushing a Value on the stack

 

This is easily achieved using the push member function, a simple example would be :

---

// create an integer stack
std::stack<int> myStack;

// create a value to push on the stack
int val = 10;

// push the value onto the stack
myStack.push(val);

---

 

1.10.2. Checking if the stack is empty

Unfortunately, trying to access an element on the stack when it is empty will cause a nasty error at runtime. Therefore the member function empty is provided as a quick query, and the function size is provided to return the number of elements on the stack

---

if( myStack.empty() ) {

std::cout << “The stack is empty” << std::endl;

}
else {

std::cout

<< “The stack has “ << myStack.size() << “ elements on it” << std::endl;

}

---

 

1.10.3. Checking the value currently on the stack

The code below outputs the current value on top of the stack :

 

---

if( !myStack.empty() )
{

std::cout

<< “The top value on the stack is ” << myStack.top() << std::endl;

}

---

 

1.10.4. Popping a Value from the stack

 

This is easily achieved using the pop member function, a simple example would be :

---

// pop the value from the stack
myStack.pop(val);

---

 

 

That’s it for now

---

 

That’s it from STL for the moment. This document details most of the STL functionality, however, it is a very large and ever-changing set of templates that are frequently up-dated. There are a number of areas that I haven’t touched upon, I may get around to writing a full description at some point, but in the mean time, a rough list of the top of my head include the following :

• Splicing and merging lists
• Searching Lists
• Randomly shuffling lists, and list generation
• Templated memory allocation policies
• Permutation generation
• Binders
• Numerical operations on lists

 

 

BiblioGraphy/Recommended Reading

---

 

• The C++ Programming Language, 3rd Edition – Bjarne Stroustrup
• Design Patterns – Gamma et al
• Effective C++ / More Effective C++
• Effective STL
• Modern C++ Design – Andrei Alexandreschu
• The History Of C++ - Bjarne Stroustrup
• Working With the STL
• Guru of the Week - Herb Sutter

(the first three books are available on my hard-drive as e-books, //PC9088/books)