Useful Class/STL in C++

These are several useful classes in C++, referring to STL. 
Source:
http://comsci.liu.edu/~murali/index.html 
http://www.yolinux.com/TUTORIALS/LinuxTutorialC++STL.html


The Standard Template Libraries (STL's) are a set of C++ template classes to provide common programming data structures and functions such as doubly linked lists (list), paired arrays (map), expandable arrays (vector), large string storage and manipulation (rope), etc. The STL library is available from the STL home page. This is also your best detailed reference for all of the STL class functions available.

STL can be categorized into the following groupings:

• Container classes:
  • Sequences:
    • vector: (this tutorial) Dynamic array of variables, struct or objects. Insert data at the end.
      (also see the YoLinux.com tutorial on using and STL list and boost ptr_list to manage pointers.)
    • deque: Array which supports insertion/removal of elements at beginning or end of array
    • list: (this tutorial) Linked list of variables, struct or objects. Insert/remove anywhere.
  • Associative Containers:
    • set (duplicate data not allowed in set), multiset (duplication allowed): Collection of ordered data in a balanced binary tree structure. Fast search.
    • map (unique keys), multimap (duplicate keys allowed): Associative key-value pair held in balanced binary tree structure.
  • Container adapters:
    • stack LIFO
    • queue FIFO
    • priority_queue returns element with highest priority.
  • String:
    • string: Character strings and manipulation
    • rope: String storage and manipulation
  • bitset: Contains a more intuitive method of storing and manipulating bits.
• Operations/Utilities:
  • iterator: (examples in this tutorial) STL class to represent position in an STL container. An iterator is declared to be associated with a single container class type.
  • algorithm: Routines to find, count, sort, search, ... elements in container classes
  • auto_ptr: Class to manage memory pointers and avoid memory leaks.

Also see the YoLinux.com GDB tutorial on dereferencing STL containers.

-1- To avoid name collision, all STL structures are wrapped in a namespace called std.  
-2- Header files that use namespaces do not have the .h extension.   For instance, the stack structure is implemented in the header file stack.  The STL string class is implemented in the header file string.  Namespace versions of the Standard C Header files, such stdio.h and string.h, are wrapped in special files with a leading c.  For example, the namespace version of the stdio.h header file is implemented in terms of the header file cstdio.  The string header file is implemented in terms of the header file cstring.

====  =======
=====[Queues]======
#incude <queue>
using namespace std;   // specify to use the standard C++ declarations
    
queue<int>  q;  // create a queue of integers
queue<String> q;    // Create a queue of strings
q.push(100); 
q.front( );      // the first item
q.pop( );  // remove the first item
q.empty( )

====[Stacks]=====
#include <stack>
using namespace std;
stack<int> q;
q.push(10);
q.empty()
q.pop();
q.top();

=====[Strings]======
http://www.yolinux.com/TUTORIALS/LinuxTutorialC++StringClass.html
string class is actually an instance of generic basic_string template class defined by the STL.  The definition of the string and the basic_string is defined in the header file string:

typedef basic_string<char> string;

The basic_string template has a length member that returns the string length.  The basic_string template has several other operators that make it act like a fundamental type.  For instance the operator == is used to test if two string are identical.  The operator != is used to test inequality.   The operator [] can be used to modify or return an element in the string.  The operators <,>,<=.>= are used to lexographicaly compare strings.  The operator + can be used to add two string togather.   Even the assignement operator is defined to copy a real C string into this string_type. 

#include <string>
using namespace std;
z.length()
strcmp
..... a lot of

STL C++ string functions:   Assuming declaration: string Var;

Function/Operation	Description
Var = string2 Var.assign("string-to-assign")	Assignment of value to string. When assigning a C "char" data type, first check if NULL to avoid failure/crash. i.e.: if( szVar ) sVar.assign( szVar ); where szVar is a C "char *" data type and sVar is of type "string".
Var.swap(string2) swap(string1,string2)	Swap with value held in string2. Function swap will exchange contents of two string class variables.
Var += string2 Var.append() Var.push_back()	Append string/characters.
Var.insert()	Insert characters
Var.erase() Var = ""	Clear string variable. No arguments necessary.
+	Concatenate
==, !=, <, <=, >, >=	Compare strings.
Var.compare(string) Var.compare( size_t pos1, size_t len, string ) const; Var.compare( size_t pos1, size_t len1, const string, size_t pos2, size_t len2 ) const;	Compare strings. Returns int: 0: if equal. -1: Not equal. 1st non matching character in Var is less in value based on ASCII table than in compare string. +1: Not equal. 1st non matching character is greater in value based on ASCII table. Where string is another STL string or null terminated C string.
Var.length()	Return length of string. No arguments necessary. The methods length(), size() and capacity() all return the same value.
Var.size()	Return length of string. No arguments necessary.
Var.capacity()	Return length of string + 1. Red Hat 7.x. Red Hat 8.0+ returns the number of characters without the "+1". Number of characters that can be held without re-allocation. No arguments necessary.
Var.max_size()	Returns a very large number. No arguments necessary.
Var.empty()	Returns 1 if an empty string. Returns 0 if not empty.
<<	Output stream
>> getline()	Input stream
Var.c_str()	Returns C string pointer. C char string is null terminated. Do not free memory using this pointer!
Var.data()	Returns C string pointer. C char string is NOT null terminated. Do not free memory using this pointer!
Var[] Var.at(integer)	Access individual characters. Return single character at specified position (integer).
Var.find(string) Var.find(string, positionFirstChar) Var.find(string, positionFirstChar, len)	Find first occurance of string or substring. Returns int position of first occurance in string. Where len is the length of the sequence to search for. Returns string::npos if not found. i.e. if(Var.find("abc") == string::npos) cout << "Not found" << endl;
Var.rfind()	Find last occurance of string or substring.
Var.find_first_of(string, position) Var.find_first_of( string, size_t position, size_t len )	Find strings and substrings. Where string is another STL string or null terminated C string. If position = 0, than start at beginning of string.
Var.find_last_of()	Find strings and substrings.
Var.find_first_not_of() Var.find_last_not_of()	Find strings and substrings.
Var.replace(pos1, len1, string) Var.replace(itterator1, itterator2, const string) Var.replace(pos1, len1, string, pos2, len2)	Replace section of string with new characters. pos2 and len2 are given when using only a substring of string. Where string is another STL string or null terminated C string.
Var.substr(pos, len)	Return substring of text given a start position in string object and length.
Var.begin() Var.end()	Iterators
Var.rbegin() Var.rend()	Reverse iterators

Note that in most cases the string functions have been overloaded to accept both string class arguments and C char variables.

====[Deques]=====

Deques, lists, maps, vectors, and sets are several templates that are classified as containers.  They are called containers as they can hold other items in them.   Items in all these containers are accessible through a special object called an iterator.  An iterator can return references to each of the items stored in the container.  Understanding the usage of an iterator in a deque exemplify there usage in other container template classes.

A deque structure in the STL implements a generic double queue that can add or remove items from either end.  The implementation is found in the deque header file.  The push_back and the push_front member methods add items to either the front or back of the deque.  The methods pop_back and pop_front are used to remove items from either the front or back of the queue.  The method empty returns true when the deque is empty and returns false otherwise.  The method front returns the first item in the front of the deque, while the method back returns the first item in the back of the deque.  The method clear can be used to empty the deque.

An iterator is an abstract object that can be used to progressively refer to each of the members of the container.  Unlike the stack and the queue, which do not have iterators operate on them, the deque has two type of iterators.  The first iterator is called a forward iterator.   This iterator can traverse the items in the deque from the front to the end.   The second form of the iterator, called the reverse iterator can traverse the deque container from the last item to the first.  The type of the iterator is defined inside the deque.  The iterator has several operators defined on it.  There extra operators make the iterator look more like a pointer object.  The increment operator (++) makes the iterator point to the next item.  The item at the iterator can be gotten by using the dereferencing operator(*).   The deque member function begin is used to return a reference to the first item when using a forward iterator.  When the forward iterator reaches a value of the deque end member method, there are no more items left to iterate.  The deque member method function rbegin us used to reference to the last item in the deque when using a reverse iterator.  When the reverse iterator reaches a value of the rend member method, there no more items to iterate.

#include <deque>
using namespace std;
deque<int> x;
x.push_back( i )   q.push_front( i )
x.empty( )
x.front ( )
x.pop_front( ); x.pop_back( );

deque<int> que; deque<int>::iterator p;
que.insert(p,11);  // Insert 11 before current item referenced by p

que.resize(10);
que.erase(que.begin()+4);

deque<int>::iterator   p;  // Create a forward iterator
for ( p=q.begin( ) ;  p != q.end ( ) ;  ++p )
          {  cout << *p << endl;  }

deque<int>::reverse_iterator   p;  // Create a reverse iterator
for ( p=q.rbegin( ) ;  p != q.rend ( ) ;  ++p )
          {  cout << *p << endl;  }

====[Lists]=====
A list is much like a deque with extra methods.  A list can be used to implement a stack, queue, or deque.  The sort method of a list will perform a stable sort of the contents of the list.  The method reverse will reverse the contents of a list.  Insertion of one list into another list can be done with the insert method.  The merge method will merge two lists into a new list.  The new list will be created by iterating through both lists at the same time and always selecting the smallest new item to insert into the new list.
The insert has several overloaded methods which always take the first argument as an interator that references a single item in the list.  The remaining argument(s) are used to reference the new items to be inserted into the list.

#include <list>
using namespace std;
list<int> lst; // Create a int list
lst.push_back(9);
lst.begin()
lst.end()
list<int>::iterator i;
i = lst.begin();
lst.sort();  // Sort the list
lst1.insert(lst1.begin(),lst2.begin(),lst2.end());     // Insert one list before the first item
lst1.insert(lst1.end(),999);     // insert 999 at end of the lst1
lst1.erase(lst1.begin());            //the first item will be removed
lst.merge(lst2);  // Merge both lists togather, The first list (1,3,5,7,9,11) is merged with the second list(2,4,6,8,10,12) to produce a final list of (1,2,3,4,5,6,7,8,9,10,11,12).


====[vector]====
#include<vector>

Constructor/Declaration:

Method/operator	Description
vector<T> v;	Vector declaration of data type "T".
vector<T> v(size_type n);	Declaration of vector containing type "T" and of size "n" (quantity).
vector<T> v(size_type n,const T& t);	Declaration of vector containing type "T", of size "n" (quantity) containing value "t". Declaration: vector(size_type n, const T& t)
vector<T> v(begin_iterator,end_iterator);	Copy of Vector of data type "T" and range begin_iterator to end_iterator. Declaration: template vector(InputIterator, InputIterator)

Size methods/operators:

Method/operator	Description
empty()	Returns bool (true/false). True if empty. Declaration: bool empty() const
size()	Number of elements of vector. Declaration: size_type size() const
resize(n, t=T())	Adjust by adding or deleting elements of vector so that its size is "n". Declaration: void resize(n, t = T())
capacity()	Max number of elements of vector before reallocation. Declaration: size_type capacity() const
reserve(size_t n)	Max number of elements of vector set to "n" before reallocation. Declaration: void reserve(size_t)
max_size()	Max number of elements of vector possible. Declaration: size_type max_size() const

Note: size_type is an unsigned integer.

Other methods/operators:

Method/operator	Description
erase() clear()	Erase all elements of vector. Declaration: void clear()
erase(iterator) erase(begin_iterator,end_iterator)	Erase element of vector. Returns iterator to next element. Erase element range of vector. Returns iterator to next element. Declarations: iterator erase(iterator pos) iterator erase(iterator first, iterator last)
= Example: X=Y()	Assign/copy entire contents of one vector into another. Declaration: vector& operator=(const vector&)
<	Comparison of one vector to another. Declaration: bool operator<(const vector&, const vector&)
==	Returns bool. True if every element is equal. Declaration: bool operator==(const vector&, const vector&)
at(index) v[index]	Element of vector. Left and Right value assignment: v.at(i)=e; and e=v.at(i); Declaration: reference operator[](size_type n)
front() v[0]	First element of vector. (Left and Right value assignment.) Declaration: reference front()
back()	Last element of vector. (Left and Right value assignment.) Declaration: reference back()
push_back(const T& value)	Add element to end of vector. Declaration: void push_back(const T&)
pop_back()	Remove element from end of vector. Declaration: void pop_back()
assign(size_type n,const T& t)	Assign first n elements a value "t".
assign(begin_iterator,end_iterator)	Replace data in range defined by iterators. Declaration:
insert(iterator, const T& t)	Insert at element "iterator", element of value "t". Declaration: iterator insert(iterator pos, const T& x)
insert(iterator pos, size_type n, const T& x)	Starting before element "pos", insert first n elements of value "x". Declaration: void insert(iterator pos, size_type n, const T& x)
insert(iterator pos, begin_iterator,end_iterator)	Starting before element "pos", insert range begin_iterator to end_iterator. Declaration: void insert(iterator pos, InputIterator f, InputIterator l)
swap(vector& v2)	Swap contents of two vectors. Declaration: void swap(vector&)

Iterator methods/operators:

Method/operator	Description
begin()	Return iterator to first element of vector. Declaration: const_iterator begin() const
end()	Return iterator to end of vector (not last element of vector but past last element) Declaration: const_iterator end() const
rbegin()	Return iterator to first element of vector (reverse order). Declaration: const_reverse_iterator rbegin() const
rend()	Return iterator to end of vector (not last element but past last element) (reverse order). Declaration: const_reverse_iterator rend() const
++	Increment iterator.
--	Decrement iterator.

---

Vector Links:

• YoLinux.com GDB tutorial on dereferencing vectors and STL containers
• SGI: vector - Detail of all vector member functions and operators available.
• Also see Boost ptr_vector - used to hold vector of pointers.

STL vector vs list function comparison:

Function	vector	list
constructor	yes	yes
destructor	yes	yes
empty()	yes	yes
size()	yes	yes
resize()	yes	yes
capacity()	yes	no
reserve()	yes	no
max_size()	yes	yes
erase()	yes	yes
clear()	yes	yes
operator=	yes	yes
operator<	yes	yes
operator==	yes	yes
operator[]	yes	no
at()	yes	no
front()	yes	yes
back()	yes	yes
push_back()	yes	yes
pop_back()	yes	yes
assign()	yes	yes
insert()	yes	yes
swap()	yes	yes
push_front()	no	yes
pop_front()	no	yes
merge()	no	yes
remove()	no	yes
remove_if()	no	yes
reverse()	no	yes
sort()	no	yes
splice()	no	yes
unique()	no	yes

♥ ¸¸.•*¨*•♫♪♪♫•*¨*•.¸¸♥