Notes on Standard Template Library ---------------------------------- What is STL ? ------------- C++ libraryof container classes, algorithms, and iterators. It is implemented using templates. Container Classes, algorithms, iterators: ---------------------------------------- e.g. vector, list, set, multiset, deque, etc. vector v(3); is a vector of 3 elements. Note that 3 is passed to vector constructor to instantiate the class. This class implements index [] operator, begin(), end(), etc v[0] = 7; v[1] = 10; v[2] = 17; reverse( v.begin(), v.end() ); // This function reverses all the // elements in that range begin-to-end. reverse() is the template function defined at global level. v.begin(), in theory, may be of type int*, or a class object, etc. The compiler generates code for reverse() only on the need basis of it's usage. (Also remember function overloading feature in C++. you can have same function taking different argtypes. you can define: float cos(float angle); double cos(double angle); ) The reverse() function here is defined something like this: template void reverse(Iterator first, Iterator last) { Iterator tmp; /* Reverse the elments using first++, last--, and assignments etc */ } The container class (e.g. vector) typically provides iterators (v.begin() and v.end()) which is a way to access its elements from global algorithms (like reverse()). An iterator is used to iterate over the elements in container class. An iterator for a container class Vector would typically be T*. Note that iterators are an interface between containers and algorithms. Algorithms typically take iterators as arguments. ***And Iterators are generalization of pointers*** Note that there is "Iterator type"(e.g. int*) and "Iterator Function" (e.g. begin() and end() ). The Iterator functions returns an Iterator type value. [ Note: In above example, Iterator need not be of a "class" type; It could be of a pointer type int* or double* for example. It could also be of a "template" type. e.g. istream or istream; istream is an input stream object processing the inputs as "int" or "float". ] More on Iterators ----------------- The algorithm may require the Iterator type to support certain operations. For example, in the above reverse function, the iterator type used should support following operations: Assume "Iterator t;" - Should be dereference'able (e.g. s = *t) - Should be incrementable, decrementable (e.g. t++ or t--) etc. There are some known classifications of iterators which explicitly documents their naming and these requirements. These are, for example, Input Iterator, Forward Iterator, Bidirectional Iterator, Random Access Iterator, Output Iterator, etc. There may be further refinements or generalization of these iterators. (For example, Input Iterator is a refinement of Trivial Iterator). The iterator requirements for the reverse function arg, is "Bidirectional Iterator". Another simple function may just require it's iterator requirment to be a "Trivial Iterator" or "Input Iterator". You can immediately look up the STL documentation to see what these requirements are before calling this function. If you are writing the algorithm, just document in the code that what your iterator requirements are. If somebody calls the algorithm with a type not confirming to the iterator requirement, compiler will flag an error. Example ------- istream_iterator iterator is an InputIterator. InputIterator is a concept. This istream_iterator is a model for that concept. Here the iterator itself is of a template type (but not necessarily in general). The istream class is used to process input from the input stream. **Iterator is a generalization of pointers.** An iterator type (i.e. instance) is just any useful class object or any pointers. By stamping it as a specific type iterator, we imply that it can be manipulated with all STL algorithms supporting this iterator type. The five iterator concepts are Output Iterator, Input Iterator, Forward Iterator, Bidirectional Iterator, and Random Access Iterator; Forward Iterator is a refinement of Input Iterator, Bidirectional Iterator is a refinement of Forward Iterator, and Random Access Iterator is a refinement of Bidirectional Iterator. (Output Iterator is related to the other four concepts, but it is not part of the hierarchy of refinement: it is not a refinement of any of the other iterator concepts, and none of the other iterator concepts are refinements of it.) STL includes utilities. There is a concept "Assignable" which means the type objects have assigment operators and copy constructors. STL includes some low-level mechanisms for allocating and deallocating memory. This is called "Allocators". STL includes a large collection of function objects, also known as functors. Just as iterators are a generalization of pointers, function objects are a generalization of functions: Unary Function (a function object that takes a single argument, i.e. one that is called as f(x)) and Binary Function (a function object that takes two arguments, f(x, y)). Function objects are an important part of generic programming because they allow abstraction not only over the types of objects, but also over the operations that are being performed. Note: what is this???? Containers: Container stores other objects. It has associated iterator type. Models of Containers define following associated types (as a type with in that class ??? ) X::value_type; typdef'ed to value type. e.g. vector; T is value_type X::iterator; typedef T *iterator; ?? X::const_iterator; X::reference; typedef T& reference; X::pointer ; typedef T *pointer; X::difference_type; typedef int difference_type; X::size_type; typedef int size_type; Folowing are valid expressions: a.begin(), a.end() /* These are iterators */ a.size(), a.empty(), a.swap(b), etc. Complexity Gurantees: begin(), end() are amortized constant time.(const time with upper limit) The copy constructor should take time linear to size. etc. For Container, the iterator type requirement is just that it should be input iterator. (very weak requirement). For Forward Container, the iterator type req is Forward iterator. The difference is like a difference between set and list. A different iteration through the container preserves the strict ordering in list. In Set, it need not be the case. Input Iterator just says that 1) you dereference to get an object; 2) can be incremented to get next iterator in seq; (though order may not be preserved exactly same in the next iteration). Forward Iterator says: 1) It is input iterator; 2) The pre,post-increment operations don't invalidate the old value; (if i==j, then ++i == ++j) So it is possible to pass through the iterators multiple times without changing the order. Reversible container: 1) It is forward Container; 2) provides bidirectional iterators; e.g. Forward iterators: begin(), end(); Reverse iterators: rbegin(), rend(); Reverse iterator type is defined and this maps ++ to --. (you increment the iterator you traverse in reverse direction!!) e.g. of such containers: vector, list Random Access container: 1) It is reversible container; 2)Provides Random Access Iterator (i.e. indexing); e.g. vector, provides [n] operator as well. Sequence Container: 1) Forward Container 2) Variable size in strict linear order 3) Supports insertion and removal of elements. (ie. supports insert(), erase() operations) e.g. vector, list, etc. Front Insertion Sequence: 1) Is a sequence 2) Could insert element at the beginning in const time; has special member function for this. e.g. front(), push_front(), pop_front(); like list, deque Back Insertion Seq: 1) seq 2) could append at back in const time; e.g. vector, list, deque Associative Contianer: 1) Is a variable-sized container 2)Elements are associated with keys 3)Supports insertion, erase(); Note: Elements are stored according to keys, so they are immutable; Usually the key is part of the element type object; Simple Associative containers have key type same as element type; (e.g. set, multiset) Unique Associative container guarantees that no 2 elements will have same key; a.erase(k) deletes all elements with key k; a.find(k) finds the element associated with key k; Pair Associative Container: 1) Assoc container 2) Value type is pair e.g. map, multi_map Sorted Assoc container: 1) Assoc container 2)stores element inside as sorted on keys; e.g. set, multi-set Multiple-Assoc container: 1) Assoc container 2) could be more than one element with the same key; e.g. multi_set, multi_map (Not set) Hashed Associative Container Elements are stored in has table. For some implementation it is much faster than sorted container; e.g. hash_set, hash_map Defines X::hasher a hash function type; The arg to that function should be X::key_type; The type X::hasher is a model of Hash Function; Note that an example hash function is an instance of hash function type X::hasher; This is also of type functor; Hash Function (Belongs to Functors category): 1)Is a Unary Function 2)hash_function(key) returns value of type size_t; Specific Container types: Examples for Sequences: -------------------------------------------------------------------- Vector By default Alloc is memory allocation function alloc(); Vector is supports const time insertion and removal at end, linear time insertion removal at beginning or in the middle; In addition to all elements supported by Random access container and Back Insertion Sequence, Vector has following new members: capacity(): Allocated memory; reserve(n): Reserve so much memory; When it is required to increase capacity it is done by default as twice current capacity; Also this invalidates the current iterators (because the pointers have changed!)Also inserting an element in middle invalidates the iterators as well. To prevent invalidation, use reserve() to preallocate as much as you want before-hand; -------------------------------------------------------------------- deque (stands for double ended queue) is same like Vector; except it supports const time for pushing and poping at the front; No support for reserve(), no guarantee for iterator preservation like in vector. supports push_front(), pop_front() functions; -------------------------------------------------------------------- list It is a doubly linked list. const time for insertion, removal at anywhere in the list. Insertion,deletion don't invalidate other iterators. (Note: slist is a single linked list.) Note that Random access capability is not there in list. list has following new members: splice() : to remove elements before a position, etc. remove(const T&): Linear in time remove_if(Predicate p); Note that p is a unary function acting on T& unique() : removes duplicate unique(BinaryPredicate P): Remove dups as defined by P(X,Y) for equality merge() : merge another list sort() : sort the elements without invalidating the iterators. Note that the global algorithm sort() does not work on lists. -------------------------------------------------------------------- slist : Singly linked list. Note that insert() and erase() is not const time-- it is linear time. so be careful. insert_after() etc is const time. -------------------------------------------------------------------- bit_vector : A typedef. Is a vector of booleans. optimized for space. similar as vector -------------------------------------------------------------------- set 1) Is sorted associative container; 2)Simple associative container (key and value are same) 3) Unique Assoc container Insertion and erasing does not invalidate other iterators. Suitable for set_union, set_difference etc set algorithms as a sorted range implementation makes it efficient. Key is the type like, int or char* etc. Compare is the function type like islessthan(X,Y); This returns 1 if X maps keys of type Key to data of type Data. It is unique, sorted, pair assoc container. i.e. value type is pair e.g. map months; ltstr is a struct type defining operator (): struct ltstr{ bool operator()(const char *s1, const char *s2) const{ return strcmp(s1, s2) < 0; } } months["january"] = 31; etc. Note that indexing operation is specific to map. (Apart from operations in Unique Sorted Associative Container and Pair Associative Container) -------------------------------------------------------------------- hash_set It is unique, hashed, simple assoc container. e.g. struct eqstr { bool operator()(const char* s1, const char* s2) const { return strcmp(s1, s2) == 0; } }; int main() { hash_set, eqstr> Set; Set.insert("kiwi"); etc. } -------------------------------------------------------------------- hash_map Similar to map -------------------------------------------------------------------- hash_multiset similar to multiset -------------------------------------------------------------------- hash_multimap similar to multimap -------------------------------------------------------------------- The default HashFcn used for hashing is hash This hash is a functor provided by STL. This template is defined only for T: char*, built-in integral types and crope and wrope?? If you want to use anyother type you can use either template specialization or use a different hash function. -------------------------------------------------------------------- Charactor Traits: Charactor Traits is provided as a class for generalized string manipulation. This is part of STL utilities. e.g. char_traits, char_traits It supports X::compare(p1, p2, n) which is a generalization of strncmp. supports eq, lt, find(generalization for strchr), etc. It is used as arg in basic_string container. -------------------------------------------------------------------- basic_string charT is either char or wchar_t; traits by default is char_traits; (encapsulates the behaviour) String is typedef'ed as basic_string; wstring is --> basic_string; Iterators may be invalidated by swap, reserve, insert, and erase, etc. int main() { string s(10u, ' '); // Create a string of ten blanks. const char* A = "this is a test"; s += A; cout << "s = " << s; reverse(s.begin(), s.end()); } -------------------------------------------------------------------- rope Ropes are a scalable string implementation. Suitable for big strings (like 10Meg). insertion is more efficient for big strings. -------------------------------------------------------------------- Adaptors: stack 1) Stack is an adaptor which provides restricted subset of a Sequence container functionality. Provides insertion, removal, inspection on top of stack; 2) By default underlying container is deque; A different type may be selected explicitly. int main() { stack S; S.push(8); assert(S.size() == 1); } -------------------------------------------------------------------- queue Default Sequence is deque. provides front(), push(), pop() operations -------------------------------------------------------------------- priority_queue You can push in any order; But larget value will be at the front. Default Sequence is vector. int main() { priority_queue Q; Q.push(1); Q.push(4); Q.push(2); Q.push(8); Q.push(5); Q.push(7); assert(Q.size() == 6); assert(Q.top() == 8); Q.pop(); assert(Q.top() == 7); Q.pop(); ... } --------------------------------------------------------------- Iterators: Generalization of pointers: Trivial Iterator: 1) may be dereferenced e.g. pointer to an object but not part of an array. May dereference, but increment, decrement may not be supported. --------------------------------------------------------------- Input Iterator: Trivial and may be incremented. Not required to be mutable. (i.e. const T* is a valid iterator). e.g. istream_iterator Note: i == j does not imply ++i == ++j; (Note that in a forward iterator, that is true. In this example, if you read from the input stream and you read it again, you get difference result.) --------------------------------------------------------------- Output Iterator: You can only store values. Nothing else is guaranteed. eg. ostream_iterator --------------------------------------------------------------- Forward Iterator: Is like an Input Iterator and may be used in multipass algorithms. i.e. i==j ==> ++i == ++j e.g. T* --------------------------------------------------------------- bidirectional iterator: 1) Forward Iterator 2) decremented as well. e.g. T* --------------------------------------------------------------- Random Access Iterator: 1) Bidirectional 2) access diff elements in const time. e.g. T*, vector::iterator --------------------------------------------------------------- What is the diff between set and list ? set is defined for unique sorted associative container. Though assoc container, key and value are same. Supported by global algo set_union, set_difference, etc. Also member fns: lower_bound, etc supported. What is map ? Map is the real associative container. e.g. dir["abcde"]= 44; etc.