STL

[jimin-kiim]

• Introduction
• container class, iterator, algorithm
• Sequence Container Operations
• Vector
• Stack
• List
• Standard Sequence Containers
• Iterators
• Algorithms

[jimin-kiim]

STL

• Standard Template Library
• included in C++ standard Library
• a set of C++ template classes to provide common programming data structures and functions

Data Structures (container class)

• expandable arrays (vector)
• doubly linked list (list)
• (priority) queue, stack, set, map ...

Functions (algorithms) on the data structures

• sort(), search(), merge(), main(), max(), swap()...
• set operations (union, difference, intersection ....)

[jimin-kiim]

Categories of STL

• container class
• iterator
• algorithm

Algorithms have ways to access any types of Containers through Iterators

Container Class

• a holder object that stores a collection of other objects with any data types(user defined or built-in)
• Sequences
  • sequential collections
  • vector, list, deque (double ended queue)
• Associative Container
  • set: collection of ordered data in a balanced BST. fast search. no duplicate data
  • map: associate key-value pair held in balanced BST
  • hash set: uses hash. fast but no order
• Container Adapters
  • implemented on top of another container
  • stack, queue, priority queue

Iterator

• similar to pointer
  • points to element of container
  • uses ++, -- and * operators
• implemented for each type of container
• elements of containers can be accessed through iterators
• provides common interface to step through the elements of any arbitrary type STL containers
• going sequentially forward iterator, going sequentially backward iterator, random access iterator

Algorithm

• header file include <algorithm>
• perform operations on STL objects (sort, search ...)
• have ways to access any types of containers through iterators
• work on any container which provides an interface by iterators

[jimin-kiim]

Sequence Container Operations

for all	for vector, deque	for list, deque
front(), back(), push_back(), pop_back(), size(), empty(), resize(int i), ==, !=, <	[ ](subscript operator), insert(p, x), erase(p), clear()	push_front(), pop_front()

[jimin-kiim]

Vector (Sequence Container class)

• dynamic array of variables, struct or objects
• elements are stored in contiguous storage locations
• able to resize itself automatically when inserting or erasing a vector element

good at

• accessing individual elements by their position index, O(1)
• iterating over the elements in any order (linear time)
• adding and removing elements from its end

declaration

#include <vector>

vector<data_type> variable_name; // static allocation
vector<data_type>* variable_name = new vector<data_type>; // dynamic allocation

member functions

member function	introduction
(constructor)	construct vector
(destructor)	destruct vector
operator=	copy vector content
begin	return iterator to beginning
end	return iterator to end
rbegin	return reverse iterator to reverse beginning
rend	return reverse iterator to reverse end
size	return size- the number of elements contained in the vector for now
max_size	return maximum size- maximum size of the capacity
resize	change size
capacity	return size of currently allocated storage capacity
empty	test whether the vector is empty
reserve	request a change in capacity
operator[]	access element
at	access element
front	access the first element
back	access the last element
assign	assign vector content
push_back	add element at the end
pop_back	delete last element
insert	insert elements
erase	erase elements
swap	swap content
clear	clear content

examples

• constructors

  vector<int> first;                                // empty vector of ints
  vector<int> x(10);                                // vector with size=10;
  vector<int> second (4,100);                       // four ints (size=4) with value 100
  vector<int> third (second.begin(),second.end());  // iterating through second
  vector<int> fourth (third);                       // a copy of third

  int myints[] = {16,2,77,29};         // using iterator constructor
  vector<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );

• accessing elements

  cout << "The contents of fifth are:";
  for (i=0; i < fifth.size(); i++)  // size function
    cout << " " << fifth[i]; // operator[]

  x[0]=7; // operator[]
  x[1]=x[0]+5;

  vector<int> myvector;
  for (int i=1; i<=5; i++) myvector.push_back(i);  // push_back function

  vector<int>::iterator it;

  cout << "myvector contains:";
  for ( it=myvector.begin() ; it != myvector.end(); it++ )  // begin function, end function
    cout << " " << *it; 

vector<int> myvector;
  int sum (0);
  myvector.push_back (100); // push_back function
  myvector.push_back (200);
  myvector.push_back (300);

  while (!myvector.empty()) // empty function
  {
    sum+=myvector.back(); // back function
    myvector.pop_back(); // pop_back function
  } 

  for (i=1; i<=10; i++) myvector.push_back(i); // push_back function
  myvector.erase (myvector.begin()+5); // erase function, begin function // erasing 6th element
  myvector.erase (myvector.begin(),myvector.begin()+3); // erasing first three elements

[jimin-kiim]

Stack

• LIFO (Last In First Out)
• header file include <stack>
• member functions
  • constructor, empty, size, top, push, pop

stack<int> mystack; 

for (int i = 0; i < 5; ++i)
    mystack.push(i); // push function 

cout << "Popping out elements...";
while (!mystack.empty()) // empty function 
{
    cout << " " << mystack.top(); // top function 
    mystack.pop(); // pop function 
}
cout << endl;

[jimin-kiim]

List

• doubly linked list
• header file include <list>
• fast access to front and back only
• adding and removing elements at any position
• member functions
  • constructor, destructor, operator=
  • begin, end, rbegin, rend
  • empty, size, max_size, resize
  • front, back
  • assign, push_front, pop_front, push_back, pop_back, insert, erase, swap, clear
  • splice, remove, remove_if, unique, merge, sort, reverse

list<int> mylist (2,100);         // two ints with a value of 100
mylist.push_front (200);  // push_front function
mylist.push_front (300);

cout << "mylist contains:";
for (list<int>::iterator it=mylist.begin(); it!=mylist.end(); ++it) // begin function, end function
  cout << " " << *it;

[jimin-kiim]

Standard Sequence Containers

[jimin-kiim]

Iterator

• iterators are a generalization of pointers, and are used much like pointers
  • represents certain position in a container
  • used to indicate elements in the sequence
  • a pair of iterators can be used to indicate a subsequence
  • behaves just like pointers
    • access element : *p, p->
    • move one unit between element : ++p, --p
    • compare iterators : ==, !=
    • assignment : =
    • navigate over elements : begin(), end()
      • begin(): points to the first element
      • end() : points to the position right behind the last element
• for each kind of container in the STL, there's an iterator type

list<int>::iterator p; 
vector<string>::iterator vp;   
deque<double>::iterator dp; 

    list<int> my_list, small, large;
    list<int>::iterator ip;

    for (int i = 1; i < 13; ++i)
    {
        my_list.push_back(i * i % 13); // push_back function
    }
    for (ip = my_list.begin(); ip != my_list.end(); ++ip) // =, begin function, !=. ++
    {
        if (*ip < 7) // *
        {
            small.push_back(*ip); // push_back function, *
        }
        else
        {
            large.push_back(*ip); // push_back function, *
        }
    }

Benefits of iterators

• can access elements of sequence container without differentiating between different container classes
  • reusability is great
  • they allow us to separate algorithms from containers
• for example, Find() function

template <class IteratorT, class T>  // function template
IteratorT Find( IteratorT begin, IteratorT end, const T& value ) 
{ 
    for ( ; begin != end ; begin++) 
        if (*begin == value) break;
    return begin; 
} 

• once defined like above, it can be used for any container that provides a suitable iterator
• it doesn't contain information about the implementation of the container, or how to move the iterator from one element to the next. these are handled by iterator itself.

[jimin-kiim]

Algorithms

• header file include <algorithm>
• sort, find, find_if, binary_search, count, min, max, swap, partition, rotate
• set_difference, set_union, set_intersection

vector<T> A;
vector<T>::iterator p,q;

sort()

sort(p,q); // sort A between p and q
sort(A.begin(), A.end()); // sort all of A

• also works with deque objects but not with list objects
• works with any random access sequence container
• guaranteed O(n log n) running time

find()

vector<T> A;
vector<T>::iterator p,q;
find(p,q,search_value);
find(A.begin(), A.end(), search_value);

• searches linearly through a sequence, and stops when an item matches the 3rd argument.
• a big limitation of find() is that it requires an exact match by value.

find_if()

vector<T> A;
vector<T>::iterator p,q;
find_if(p, q, if_statement);
find_if(A.begin(), A.end(), if_statement);