A closer look into STL

We’ve already had an introduction about STL. Having learnt about data structures you will be in a better position to appreciate the use of STL. Data structures are used frequently by programmers for various applications. Every programmer could keep creating his own model of the data structure and use them in his application. But the idea of OOP is reuse. Since data structures are used frequently it was felt that creating a common standard would greatly benefit programmers. This led to the development of STL. The programmer can reuse the existing code and need not waste time in developing the data structures or algorithms (like sorting and searching).

How STL was developed?

An example might help you appreciate the concept behind development of STL. Let us suppose that we want to write 2 algorithms: one for sorting and one for searching. Let us say that we want to operate on two data types: integers and float. Sorting and searching is not applied to a single element. We will be needing a sequence of elements and let us restrict ourselves to arrays and linked lists.

Thus we are attempting to write programs to:

They have to work on 2 containers:

The data types we will use are:

So, how many codes do you think we have to write? We’d have to write 2*2*2 (2 algorithms * 2 data structures * 2 data types = 8) sets of codes. The combinations would be:

  1. Searching an array of integers
  2. Searching an array of float
  3. Searching a linked list of integers
  4. Searching a linked list of float

Similarly you’ll need to have 4 more codings for sorting. The problem with the above methodology is that our basic algorithm is going to be the same things. It’s only the data types and data structures that will vary. To reduce on this template functions were created. With template functions we could use the same function across any data type. Thus the data type factor was eliminated from the equation and the number of codings needed was reduced to 4 (2 algorithms * 2 data structures). The next logical step was to write code that could be used across different containers. This would mean that ultimately you only need to write an algorithm for each operation and needn’t worry about what data structure was used. This is the basis for STL.

STL was developed by Stepanovs and Ming Lee and it has been drafted into the standard ANSI C++ standards. Hence all C++ compilers (the latest ones) will support STL.

We have already dealt with the terms used in STL: containers, iterators and algorithms. We use pointers to access objects in C++. When using STL we use iterators instead of pointers. Containers are basically the data structures, a few of which we have already discussed. They are designed as template classes and can be used to hold any data type. Containers can be divided into different categories:Text Box: forward Text Box: bidirectional Text Box: random access Text Box: output Text Box: input

  1. Sequence containers
  2. Associative containers
  3. Container Adapters
  4. Specialized/ Near containers

There are 3 types of sequence containers namely vectors, lists and deque. Algorithms are used to perform some operation on the elements held within these containers. These algorithms are implemented as functions and whenever you want to use them you will usually have to pass iterators to the function. For example by passing 2 iterators we can specify the elements on which we want the algorithm to act upon.

There are 5 types of iterators:

  1. Input - used to read elements from a container. They can move in only the forward direction (i.e. from the first element to the last) and they can pass only once through the container.
  2. Output - used to write elements to a container. They are similar to input iterators.
  3. Forward - they are a combination of the input and output iterators. They can be used to pass multiple times through the container.
  4. Bidirection - they have the properties of the forward iterator and they can be used to move in the backward direction also.
  5. Random access - They have the properties of the bidirectional iterator and also permit random access of container elements.

There is a hierarchy for the 5 types of iterators and the ones at the top of the hierarchy are considered ‘weaker’ than those at the bottom of the hierarchy. The lower levels in the hierarchy support all the functions that are performed by the ones above it (thus they are stronger than the ones above them).

 

 

 

 

 

 

 

Containers and iterators are related. Every type of container will support particular types of iterators. Also each container has a set of member functions and some of these functions will return iterators.

The following member functions are a few of the common functions available in almost all STL containers (including vectors).

Function/operators

Use

bool empty( )

Returns true if container is empty.

size_type size( )

Returns the number of elements present in the container.

void clear( )

Clears the contents of the container.

const_pointer/pointer begin( )

Returns reference to the first element of the container.

const_pointer/pointer end( )

Returns a reference to the end of the container.

reverse_iterator rbegin( )

Returns a reverse iterator.

reverse_iterator rend( )

Returns a reverse iterator.

erase( )

Used to erase a particular element or a range of elements (needs to be passed iterator arguments).

Overloaded operators = =,<,<=,>,>=

All return a Boolean value depending on the result of comparison.

Overloaded assignment operator =

Used to assign one container to another.

Note: Italics denote the return data type of the functions.

We’ll use some of the overloaded operators in programs to illustrate their working.

Some of the return data type might appear to be new. These are actually typedef’s which have already been defined. Some typical typedefs you might encounter in STL are:

Typedef

Description

size_type

Data type used to count the number of elements in a container.

const_iterator

An iterator that can be used to only read elements of a container.

reverse_iterator

This is used to pass through a container in the reverse order (from the last element to the first).

const_reverse_iterator

A constant reverse iterator used for reading the elements of the container in reverse order.

Next we’ll take a look at each of the container types in a little more detail.

Learn about Sequence Containers (Vectors)

Go back to Contents page 2.

Copyright © 2004 Sethu Subramanian All rights reserved.