STL (Standard Template Library) Part1

The STL provides a ready-made set of common classes for C++, such as containers and associative arrays, that can be used with any built-in type and with any user-defined type that supports some elementary operations (such as copying and assignment). STL algorithms are independent of containers, which significantly reduces the complexity of the library.



The STL achieves its results through the use of templates. This approach provides compile-time polymorphism that is often more efficient than traditional run-time polymorphism. Modern C++ compilers are tuned to minimize any abstraction penalty arising from heavy use of the STL.

The STL was created as the first library of generic algorithms and data structures for C++, with four ideas in mind: generic programming, abstractness without loss of efficiency, the Von Neumann computation model, and value semantics.



The C++ STL provides programmers with the constructs, grouped into three categories namely:



Sequences:

C++ Vectors

C++ Lists

C++ Double-Ended Queues



Container Adapters:

C++ Stacks

C++ Queues

C++ Priority Queues



Associative Containers:

C++ Bitsets

C++ Maps

C++ Multimaps

C++ Sets

C++ Multisets



Containers

The STL contains sequence containers and associative containers. The standard sequence containers include vector, deque and list. The standard associative containers are set, multiset, map and multimap.



Vector:

a dynamic array, like C array (i.e., capable of random access) with the ability to automatically resize itself when inserting or erasing an object. Inserting and removing an element to/from back of the vector at the end takes amortized constant time. Inserting and erasing at the beginning or in the middle is linear in time.

A specialization for type bool exists, which optimizes for space by storing bool values as bits.



List

a doubly-linked list; elements are not stored in contiguous memory. Opposite performance from a vector. Slow lookup and access (linear time), but once a position has been found, quick insertion and deletion (constant time).



Deque(double ended queue):

a vector with insertion/erase at the beginning or end in amortized constant time, however lacking some guarantees on iterator validity after altering the deque.

Associative containers - unordered collections



set:

a sorted set; inserting/erasing elements in a set does not invalidate iterators pointing in the set. Provides set operations union, intersection, difference, symmetric difference and test of inclusion. Type of data must implement comparison operator < title="Self-balancing binary search tree" href="http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree">self-balancing binary search tree.



multiset:

same as a set, but allows duplicate elements.



map:

a sorted associative array; allows mapping from one data item (a key) to another (a value). Type of key must implement comparison operator <>

multimap:

same as a map, but allows duplicate keys.



hash_set, hash_multiset, hash_map, hash_multimap:

similar to a set, multiset, map, or multimap, respectively, but implemented using a hash table; keys are not sorted, but a hash function must exist for key type. These containers are not part of the C++ Standard Library, but are included in SGI's STL extensions, and are included in common libraries such as the GNU C++ Library in the __gnu_cxx namespace. These are scheduled to be added to the C++ standard as part of TR1, with the slightly different names of unordered_set, unordered_multiset, unordered_map and unordered_multimap.



Bitset:

stores series of bits similar to a fixed-sized vector of bools. Also optimizes for space



Valarray:

another C-like array like vector, but is designed for high speed numerics at the expense of some programming ease and general purpose use. It has many features that make it ideally suited for use with vector processors in traditional vector supercomputers and SIMD units in consumer-level scalar processors, and also ease vector mathematics programming even in scalar computers.



STL Function Objects

If you separate the two words function and object, you already know each one on its own. If you are already a programmer—which we assume at this point—you know the meaning of each one in regard to software engineering:



· A function is the typical way of getting a particular job done in C++ programs; in other words, it defines the execution flow of a specific operation. It usually has one defined entry and one defined exit point. There have been many debates on whether there should only be one or several exit point(s); however, this does not matter in regard to this article.



· An object refers to the concrete creation of a datatype that takes up a certain amount of space at a specific memory location. The term object is interchangeable with the term instance which, in this regard, means the same.



A function object extends the characteristics of regular functions by using object-oriented C++ features such as generic prgoramming and abstraction. Thus, they can be referred to as smart functions that provide several advantages over regular functions:



· Function objects can have member functions as well as member attributes. Thus, they can carry a state that even can be different at the same time.



· Due to their nature, function objects can be initialized before their usage.



· Opposed to regular functions that can only have different types if their signatures differs, function objects can have different types even with the same signature; this ensures the type safety of the C++ language. If you provide a function object as the sorting criteria for a collection, it is guaranteed that you cannot assign, combine, or compare collections with a different sorting criteria.



· Function objects are usually faster than regular functions.



Links:



The C++ Standard Library -

http://books.google.com/books?hl=en&id=n9VEG2Gp5pkC&dq=STL&printsec=frontcover&source=web&ots=Rdf6qk68OT&sig=FoQUpvp1Mom_CvnSWXoodfjHm_o&sa=X&oi=book_result&resnum=12&ct=result

STL Pocket Reference -

http://books.google.com/books?id=NYTjffiMxr4C&pg=PA1&dq=STL&sig=ACfU3U0lb8BcN6HmiCHJhRyCAbs1hkzv4A#PPA3,M1

Using the STL: The C++ Standard Template Library -

http://books.google.com/books?id=yOebRChQI3EC&printsec=frontcover&dq=STL&sig=ACfU3U28ZhUwJoLOiopoea3FYtbBFM0Kiw#PPR12,M1

Standard Template Library Overview - http://www.sgi.com/tech/stl/table_of_contents.html



STL - http://en.wikipedia.org/wiki/Standard_Template_Library



C++ Template Library - http://www.cppreference.com/cppstl.html



Functor (or) Function Objects - http://www.codeguru.com/cpp/cpp/cpp_mfc/stl/article.php/c11449/



Functors - http://artins.org/ben/programming/mactechgrp-artin-cpp-functors.pdf



STL Algorithms -

http://www.infosys.tuwien.ac.at/Research/Component/tutorial/prw432.htm