C++ classes provide an excellent mechanism for creating a library of data structures.
Standard C++ includes its own built-in container class library. It's called the Standard Template Library (STL), and was developed by AlexanderStepanov and Meng Lee of Hewlett Packard.
The STL is part of the Standard C++ class library, and can be used as a standard approach to storing and processing data.
The STL contains several kinds of entities. The three most important -
- containers
- algorithms
- iterators
A container is a way that stored data is organized in memory.
For example: stacks , linked lists,arrays...
However, there are many other kinds of containers,and the STL includes the most useful. The STL containers are implemented by template classes,so they can be easily customized to hold different kinds of data.
Algorithms in the STL are procedures that are applied to containers to process their data in various ways.
For example, there are algorithms to sort, copy, search, and merge data.
Algorithms are represented by template functions. These functions are not member functions of the container classes. Rather they are standalone functions.
Indeed, one of the striking characteristics of the STL is that its algorithms are so general. You can use them not only on STL containers, but on ordinary C++ arrays and on containers you create yourself. (Containers also include member functions for more specific tasks.)
Iterators are a generalization of the concept of pointers: they point to elements in a container. You can increment an iterator, as you can a pointer, so it points in turn to each element in a container.
Iterators are a key part of the STL because they connect algorithms with containers. Think of them as a software version of cables, like the cables that connect stereo components together or a computer to its peripherals.
Containers
Basic Sequence Containers
Characteristic Advantages and Disadvantages ordinary C++
array Fixed size Quick random access (by index number) Slow to insert or erase in the middle Size cannot be changed at run time
vector =>
expandable array Quick random access (by index number)
Slow to insert or erase in the middle
Quick to insert or erase at end
list =>
Doubly linked list Quick to insert or delete at any location
Quick access to both ends
Slow random access
deque =>
like vector, but can be accessed at either end Quick random access (using index number)
Slow to insert or erase in the middle
Quick insert or erase (push and pop) at either the beginning or the end Basic Associative
Containers Characteristics
set => Stores only the key objects Only one key of each value allowed
multiset => Stores only the key objects Multiple key values allowed
map => Associates key object with value object Only one key of each value allowed
multimap => Associates key object with value object Multiple key values allowed
Algorithms
An algorithm is a function that does something to the items in a container (or containers).
Algorithms in the STL are not member functions or even friends of container classes, as they
are in earlier container libraries, but are standalone template functions.
Some Typical STL Algorithms
find => Returns first element equivalent to a specified value
count => Counts the number of elements that have a specified value
equal => Compares the contents of two containers and returns true if all corresponding elements are equal
search => Looks for a sequence of values in one container that correspond with the same sequence in another container
copy => Copies a sequence of values from one container to another (or to a different location in the same container)
swap => Exchanges a value in one location with a value in another
iter_swap => Exchanges a sequence of values in one location with a sequence of values in another location
fill => Copies a value into a sequence of locations
sort => Sorts the values in a container according to a specified ordering
merge => Combines two sorted ranges of elements to make a larger sorted range
accumulate => Returns the sum of the elements in a given range
for_each => Executes a specified function for each element in the container
Iterators
Iterators are pointer-like entities that are used to access individual data items (which are usually called elements), in a container.
Often they are used to move sequentially from element to element,a process called iterating through the container.
You can increment iterators with the ++ operator.so they point to the next element, and dereference them with the * operator to obtain the value of the element they point to.
In the STL an iterator is represented by an object of an iterator class.
Different classes of iterators must be used with different types of container.
There are three major classes of iterators:
forward, bi-directional, and random access.
Iterator Characteristics
Iterator Type Read/Write Direction Access Saved
Random access => Read and write Forward and back Random Yes
Bidirectional => Read and write Forward and back Linear Yes
Forward => Read and write Forward only Linear Yes
Output => Write only Forward only Linear No
Input => Read only Forward only Linear No
Potential Problems with the STL
The sophistication of the STL's template classes places a strain on compilers, and not all of them respond well.
Let's look at some potential problems.
First, it's sometimes hard to find errors because the compiler reports them as being deep in a header file when they're really in the class user's code.
You may need to resort to brute force methods such as commenting out one line of your code at a time to find the culprit.
Precompilation of header files, which speeds up compilation dramatically on compilers that offer it, may cause problems with the STL.
If things don't seem to be working, try turning off precompiled headers.
The STL may generate spurious compiler warnings. “Conversion may lose significant digits” is a favorite. These appear to be harmless, and can be ignored or turned off.
These minor complaints aside, the STL is a surprisingly robust and versatile system. Errors tend to be caught at compile time rather than at run time.
Examples :
// find.cpp
// finds the first object with a specified value
#include
#include //for find()
using namespace std;
int arr[] = { 11, 22, 33, 44, 55, 66, 77, 88 };
int main()
{
int* ptr;
ptr = find(arr, arr+8, 33); //find first 33
cout << "First object with value 33 found at offset "
<< (ptr-arr) << endl;
return 0;
}
The output from this program is
First object with value 33 found at offset 2.
// count.cpp
// counts the number of objects with a specified value
#include
#include //for count()
using namespace std;
int arr[] = { 33, 22, 33, 44, 33, 55, 66, 77 };
int main()
{
int n = count(arr, arr+8, 33); //count number of 33's
cout << "There are " << n << " 33's in arr." << endl;
return 0;
}
The output is
There are 3 33's in arr.