STL – Know It Better

STL? Before proceeding, first of all we should know that what does it stands
for?
In fact, STL – is Standard Template Library. C++ programmers have benefited
from it a lot.

What is Standard Template Library?

It is general purpose C++ library of algorithms and data structures, conceived by Alexandor Stepanov and Meng Lee. It is part of standard ANSI/ISO c++ library. It is called so since it is implemented by c++ template mechanism. The STL is a generic library, means that its components are heavily parameterized.

It contains of container classes, generic algorithms and similar things that can greatly simplify many programming task in c++. STL include the classes vector,list,deque,set,multiset,map,multimap,hash_set,hash_multiset,hash_map,hash_multimap.Each of these classes is a template and can be instantiated to contain any type of object. Now for eg lets see how vector is used. We can use the vector in much the same way as you would use an ordinary C array. But remember that vector eliminates the chore of managing dynamic m/y allocation by hand.

Eg
vector v(3); // Declare a vector of 3 elements.
v[0] = 7;
v[1] = v[0] + 3;
v[2] = v[0] + v[1]; // v[0] == 7, v[1] == 10, v[2] == 17

Container classes -are the classes used to hold objects of any particular type. We can say that their purpose is to contain other objects.

How can we traverse and access objects within container?

See, traversing containers and accessing objects within containers is made possible with iterators.Infact, iterators are an abstraction of pointers. They are used to link a container with algorithm.
Generic Algorithms- are a collection of routines that can be used to perform common operations on container classes. The operations can be of any type say sorting, which is a very common operation.

Why are they called generic?

-It is a common question which comes in one mind that why do we call it generic and the answer is quite simple-i.e since they are independent
of the container class used and the data type of the objects held in those container classes.

See, if you have understood about STL so far, then it wouldn’t be tough to understand similarity b/w it and
array. Although I have given brief introduction of container classes, algorithms,and iterators ,they are dealed in more detailed later). STL provide container classes that can be used to hold objects in the same way as array can be used to hold objects. However , container classes can handle all sizing and m/y allocation issues ,i.e we can’t write past the end of container classes like you can with an array.

Container classes can contain utility methods such as empty(), clear() and size() that can simplify programming up to a large extent. Infact, there are many other methods for various purposes like insertion, deletion etc.

How can container classes be implemented?

They can be implemented as class templates.

Is it necessary to understand class templates to use STL?
Not, exactly. But if you want to understand more about design of this library you will need this information.

Types of container
-Sequence
-Associative

Sequence containers are meant to hold a collection of objects of one type in a linear sequence. This is similar to an array. STL provides three sequence containers:
vector, deque, list.

The three different sequence containers all have different time and space complexities for their different operations:
C array vector deque list
Insert/erase at start n/a linear constt constt
Insert/erase at end n/a constt constt constt
Insert/erase in middle n/a linear linear constt
Access first element constt constt constt constt
Access last element constt constt constt constt
Access middle element constt constt constt linear
Overhead none low medium high

1) Vector-provides random access retrievals of objects at any position in const time.
-somewhat like arrays but more flexible. They can grow and shrink as needed.
-are composed of single block of sequential m/y, just like C vectors.
-can be indexed using [] notation.
-several constructors available for vector class.
-Default constructor builds an empty vector.
-inefficiency:overflow condition can cause a complete copy
-m/y extended in multi-object blocks.
-m/y is freed when the vector object is destroyed.

To use vectors you must include the vector header file. The std namespace is also needed in order to have access to the names used in the STL for the classes and functions. If you want to use any of the algorithms provided by the STL, you also need to include the algorithm header. Remember that these algorithms are separate from the functions provided by the vector container class itself.

#include
#include
#include
using namespace std;
Now you may be thinking how can one create a vector.It s quite simple and straightforward. To create a vector one uses something like the following. Note the use of int in angle brackets to specify that we want a vector of integers. The name of the vector is Num and it starts out with size 8.
vector Num(6);
We can then use indexing to access individual items in the Num vector. For example, we can assign an item to the 0-th vector slot as follows:
Num[0] = 7;

2) deque-This class also provides random access retrievals of objects at any positions in const time. The insertions and deletions at both the front and end of a deque are optimized and occur in const time.

– Deques are composed of fixed-size multi-object blocks of memory with a "map" block -Memory is freed when the vector object is destroyed.
-Use when objects are inserted/removed primarily at the end or the beginning.
-Inefficiency: no complete copies, but operator[] is a bit slower.

3) List -This unlike previous classes doesn’t support random access retrievals. Retrievals require linear time. This is because lists are implemented with an underlying doubly linked –list structure. A doubly linked –list is a series of nodes with each node containing the address of its previous node as well as the next node. Infact, each node of a doubly linked list has two pointers, one “previous” pointer gets you to previous element and the “next” ptr to next. Insertions and deletions at any pt are efficient and occur in const time.
-Insertion and deletion in middle of vectors and lists and at the beginning of vectors require other elements to be moved. This is why they require linear time.
-Lists are composed prev-object-next blocks.
-Objects are allocated from same-type static private pool.
-Memory isn’t freed until every member of the class is destroyed.
-No operator[].
-Inefficiency: highest overhead

Apart from above containers ,ordinary arrays and string class can also be considered sequence containers.

Container Adaptors

Container adaptors take sequence containers as their type arguments, for example:
stack < vector < int > > a;
Stack
-Use with vector (best), deque, or list (bad choice)
-The stack class is technically a container adaptor that utilizes some underlying container (by default, a dequeue, a double-ended queue) to hold its data. This container adaptor, however, keeps the programmer from accessing the data in many of the ways that the underlying container supports; only reasonable types of stack access are allowed.

-Basic interface:

bool empty();
size_type size();
value_type& top();
const value_type& top();
void push(const value_type&);
void pop();

Queue

-Use with deque, or list. (Vector works, but its extremely inefficient)

Associative containers-They support the construction of hashes and sets. A set is a collections of keys. These can help us know whether a particular object is present or not. A hash is a collection of key, value
pairs. Each value may be inserted by key and located by its key. All of these containers are sorted.
-They are implemented using Red-Black trees.
-objects are allocated from same type static private pool.
-Memory isn’t freed until every member of the class is destroyed.
Types of associative containers:
1)set-hold unique keys of any type.
-fast retrieval of keys and tests for presence of particular keys.
-ordered.
-duplication of keys not allowed.
2)multiset-this also holds key but they need not be unique.
3)map-It is a hash. Stores object of one type, the values, in a sorted order based on objects of another type, the keys.
-The map class (My personal feeling) is one of the best classes provided and its my favorite too.
-Dynamically expandable
-Duplication of keys not allowed.

-only limitation is m/y of your system.
-can be indexed by anything you choose: char,int ,string or even the class you define. You just need to define the way to comparing them.
-Another imp feature is that they sort your data by the index for you. So can
you guess the advantage of it? If not let me tell you. The advantage is that you do not have to perform bubble-sort, or any sort !It does it for you.

Creating an instance of a map

A map can be instantiated with the following parameters.

map "instance name";

Key: the data element you are going to use to index the map with.

Data: what is being stored. i.e. any primitive or class you want, even user defined classes.

Compare: the comparison function where the key type are the two arguments to the function. true is returned when the 1st element is less than the second element, otherwise false is returned.

4) Multimap-allows storage of values based on keys. The keys may be duplicated.

Generic Algorithms:

They provide functions that implements many common programming tasks in an efficient manner. Many of the algorithms have overloaded function signatures. That is, they have versions that take diff numbers and/or types of arguments .Many of generic algos perform some type of comparison or test as they execute. For instance, count function returns the
no. of elements equal to some value. Many of the algos have versions that take a function or function object as a operator, (), overloaded. These functions or function object usually take one or two parameters and return a Boolean or true/false value. A function that returns a Boolean value is also called a predicate.
Also, STL provides built-in function objects via the functional include file.

Iterators:

See, I gave a one line definition on iterators, but I think many may be still be wondering what it exactly
is. Let me explain you a little bit further. Iterators are:
-modelled after standard C pointers.
– the interface that the STL generic algorithms use to work with any container!
Types of iterators:
Random Access Iterators
Most closely resembles the standard C pointer.
Bidirectional Iterators
Use to traverse containers in either direction.
Forward Iterators
Use to traverse containers in one direction only.
Input Iterators
Can only read elements, and in the forward direction only.
Output Iterators
Can only write elements.

Other parts of the STL

If you understand algorithms, iterators, and containers, then you understand almost everything there is to know about the STL. The STL does, however, include several other types of components. What I feel is that
you must have got a lot of idea about STL. Now lets see some other type of components.
First, the STL includes several utilities: very basic concepts and functions that are used in many different parts of the library.
Second, the STL includes some low-level mechanisms for allocating and deallocating memory. Allocators are very specialized, and you can safely ignore them for almost all purposes.
Now you may be thinking why do we need allocators? isn’t it?
Allocators are required in environments with multiple memory models (16 bit PCs).

Allocators may also be useful for fixed-memory applications, OO database interfaces, and parallel processing.

Finally, the STL includes a large collection of function objects, also known as functors.

Function Objects

Just as iterators are a generalization of pointers, function objects are a generalization of functions: a function object is anything that you can call using the ordinary function call syntax.
-They work by overloading operator().
-Function objects take the place of function pointers in traditional C programming.
-Also useful when functions need to encapsulate data.
-Very useful for generating needed functions on-the-fly.

Built-in function objects
Function Object Type Return
:Arithmetic function objects (there are more but I am including only few)
plus binary arg1 + arg2
minus binary arg1 – arg2
times binary arg1 * arg2
:Comparison function objects (there are more but iam including only few)
equal_to binary arg1 == arg2
not_equal_to binary arg1 != arg2
greater binary arg1 > arg2
less binary arg1 < arg

Function adaptors

Function adaptors take function objects and mutate their application.

Some of the built in Function adaptors are not1,not2, etc.

I sincerely hopes that information shared herein gives you knowledge and know STL better.