Thursday, November 2, 2006

The Standard Template Library

Topics

C++ Standard Library
 

History
- C++ began a standardization process in 1989
- Standards define exact content and behavior of C++
- Standards makes it easier to...
        - port C++ programs to different platforms
        - use C++ in applications
        - teach C++
- The standardization process was completed in 1997
- Made an international standard in 1998
- The standardization process included the development of a library
- Core language and the C++ library were standardized in parallel
- Part of the standard, this became known as the C++ standard library
 

Introduction
- This library extends the core language to provide some general components
- The library leverages and uses C++'s ability to program new abstract types
- The library makes extensive use of one of C++'s "newer" features, templates
- In fact, almost all parts of the library are written as templates
- The library provides a set of common classes and interfaces
- Gives programmers a higher level of abstraction by providing...

String types

Different containers (data structures such as linked lists, dynamic arrays, ...)

Different algorithms (such as different sorting, searching algorithms)

Numeric classes (such as complex numbers)

I/O classes (we've already looked at this - C++ stream library)

Classes for internationalization support (different character sets)

General Concepts
- Fundamental concepts of C++ standard library
- Needed to work with all or most of the components

 
Namespaces

Introduction
- More and more software is written as libraries, modules, or components
- Combining user code with such software could result in a problem
- What if you named your class the same as some class contained in a library?
- What if you named a function the same as some function contained in a library?
- This would result in what's referred to as a name clash
- The feature called namespaces solves this problem
 

Usage
- A namespace groups different identifiers (names) in a named scope
- The defined names will not conflict with other names defined elsewhere

 
Example 1

#include <iostream>

using namespace std;

// Groups different identifiers under named space
namespace testlibrary
{
  class Test;
  void print();
}

// Associate class with namespace
class testlibrary::Test
{
public:
    Test();
};

testlibrary::Test::Test()
{
    cout << "Test object" << endl;
}

// Associate function with namespace
void testlibrary::print()
{
    cout << "Hello world" << endl;
}

int main()
{
  // Explicit use of namespace identifiers
  testlibrary::Test t;
  testlibrary::print();
  return 0;
}

OR

// using declarations
using testlibrary::Test;
using testlibrary::print;
int main()
{
  Test t;
  print();
  return 0;
}

OR

// using directive
// makes all names of given namespace available
using namespace testlibrary;

int main()
{
  Test t;
  print();
  return 0;
}

Output
Test object
Hello world
 

Example 2

#include <iostream>

using namespace std;

namespace ns1
{
  void print();
}

namespace ns2
{
  void print();
}

void ns1::print()
{
  cout << "Print from namespace ns1" << endl;
}

void ns2::print()
{
  cout << "Print from namespace ns2" << endl;
}

using ns2::print;

int main()
{
  print();
  return 0;
}
 

Output
Print from namespace ns2
 
 

C++ standard library namespace
- C++ standard library contains many named components
- Components are grouped under one namespace called std
- When using identifiers from the C++ standard library, one can...

1) Qualify identifier directly

#include <iostream>

int main()
{
    std::cout << "hello world" << std::endl;
    return 0;
}

2) Provide a using declaration

#include <iostream>

using std::cout;
using std::endl;

int main()
{
    cout << "hello world" << endl;
    return 0;
}

3) Provide a using directive

#include <iostream>

using namespace std;

int main()
{
    cout << "hello world" << endl;
    return 0;
}

Header Files
- Several extensions were being used before the standard (.h, .hpp, .hxx, .H)
- Standard defined headers as no longer requiring extensions in include statements
- Only defined from the point of view of program, not operating system
- Note this requirement for no extension applies only to standard header files
- Still required for the programmer's header files

#include <iostream>
#include <string>

Other general concepts

Allocators
    - Special objects to handle the allocation and deallocation of memory
    - Different memory models (shared memory, garbage collection, ...)
    - Interface to different memory models remains the same
 

Standard Template Library (STL)
- Subcomponent of the standard library
- Influenced the overall architecture of the standard library
- Standardization of common elements used by programmers
- Provides solutions to managing collections of data with modern/efficient algorithms
- Programmers benefit from innovations in area of data structures and algorithms
- Programmers don't necessarily have to know how they work
- New level of abstraction for the C++ programmer
- All components of the STL are templates - can work with any user type
- Usage avoids interoperatability problems among programmers
- Sets up a generic and common style of programming
- Avoids "reinventing the wheel"
- STL components include...

Containers
    - different methods of managing collections of objects

Iterators
    - used to step through elements of collections of objects

Algorithms
    - used to process the elements of collections
    - search, sort, modify

- Forget programming your own linked lists, stacks, trees, search algorithms!
- STL is very large, we'll look at a few of the common components
 

Containers
- Template classes to manage a collection of elements
- Different types of containers meet different programmatic needs

Sequence containers
- Collection of elements ordered by position in the list (place of insertion)
- Position in list is independent of the value of the element
- vector, list, deque

Associative containers
- Collection of elements ordered and sorted by value of the element
- Order is independent of the position in the list (place of insertion)
- set, multiset, map, multimap
 

Vector Sequence Container
- Manages elements in a dynamic array (size not known until run-time)
- Can add and remove elements from end (back) quickly
- Insertion in middle and front requires more time - all elements need to be moved
- Can randomly access elements directly

Example

#include <iostream>
#include <vector>

using namespace std;

int main()
{
  int i;          // loop counter
  vector<int> iv; // vector container of integers

  // Load container elements with values
  for( i = 10; i < 16; ++i )
    iv.push_back( i );
 

  // Print container elements
  for( i = 0; i < iv.size(); ++i )
    cout << "iv[" << i << "]: " << iv[i] << endl;
  return 0;
}

Output
iv[0]: 10
iv[1]: 11
iv[2]: 12
iv[3]: 13
iv[4]: 14
iv[5]: 15
 

- Memory allocation of container elements handled by vector class
- Created, initially, as an empty container (no elements)
- Note method to append (push) elements to end (back) of container
- Same method used in all sequence container classes
- Note size method returns number of elements in container
- Note indexing of elements (random access) with subscript operator
 
 

Deque Sequence Container
- Pronounced "deck", designed as a "double-ended queue"
- Manages elements in a dynamic array (size not known until run-time)
- Can add and remove elements from both ends (front, back) quickly
- Insertion in middle requires more time - all elements need to be moved
- Can randomly access elements directly

Example

#include <iostream>
#include <deque>

using namespace std;

int main()
{
  int i;
  deque<int> id; // deque container of integers

  // Load container elements with values at front
  for( i = 10; i < 16; ++i )
    id.push_front( i );

  // Load container elements with values at end
  for( i = 20; i < 26; ++i )
    id.push_back( i );
 

  // Print container elements
  for( i = 0; i < id.size(); ++i )
    cout << "id[" << i << "]: " << id[i] << endl;
  return 0;
}

Output
id[0]: 15
id[1]: 14
id[2]: 13
id[3]: 12
id[4]: 11
id[5]: 10
id[6]: 20
id[7]: 21
id[8]: 22
id[9]: 23
id[10]: 24
id[11]: 25
 

- Memory allocation of container elements handled by deque class
- Created, initially, as an empty container (no elements)
- Method to append (push) elements to front of container (not provided in vector)
- Note method to append (push) elements to end of container
- Note size method returns number of elements in container
- Note indexing of elements with subscript operator
 
 

List Sequence Container
- Designed as a doubly linked list of elements
- Each element in list can refer to previous element and next element in list
- Manages elements in a dynamic array (size not known until run-time)
- Can add and remove elements anywhere (front, middle, back) quickly
- Cannot randomly access elements directly (must navigate through the chain)
 

Example

#include <iostream>
#include <list>

using namespace std;

int main()
{
  int i,j;
  list<int> il;      // linked list container of integers

  // Load container elements with values at front
  for( i = 10; i < 16; ++i )
    il.push_front( i );

  // Load container elements with values at end
  for( i = 20; i < 26; ++i )
    il.push_back( i );
 

  // Print container elements
  while( !il.empty() )
    {
      cout << il.front() << endl;
      il.pop_front();
    }
  return 0;
}

Output
15
14
13
12
11
10
20
21
22
23
24
25
 

- Memory allocation of container elements handled by list class
- Created, initially, as an empty container (no elements)
- Method to append (push) elements to front of container
- Note method to append (push) elements to end of container
- Note empty() method returns false if no elements in container
- Note front() method returns first element in the list
- Note pop_front() method removes first element in the list
 
 

Iterators
- Class objects that can "iterate" or navigate over elements
- Similar to pointers, iterators "point to" elements in the list
- Typically the elements are part of another STL container
- Iterators represent positions of elements within a list
- Iterators return elements at certain positions in a list
- Each container class defines its own iterator type as a nested class
- Container classes define member methods to use the iterators for access
- Example methods include:

begin()
- Returns an iterator that represents the beginning of the elements in the list

end()
- Returns an iterator that represents the position behind the last element
- Can only be used in an equality or comparison to test end of list

++ operator
- Operator to step to the next element "pointed" to by the iterator

* operator
- Operator to return the element "pointed" to by the iterator

- Each container defines two types of iterators:

container type::iterator
- can iterate, access, and change the elements referenced by the iterator

container type::const_iterator
- can only iterate and access the elements referenced by the iterator

Example

#include <iostream>
#include <list>

using namespace std;

int main()
{
  int i,j;
  list<int> il; // linked list container of integers

  // Load container elements with values at front
  for( i = 10; i < 16; ++i )
    il.push_front( i );
 

  // Declare the iterator
  list<int>::const_iterator pos;

  // Assign the iterator to beginning of list;
  //   step through the list with the iterator
  //   print the element referenced by the iterator
  for( pos = il.begin(); pos != il.end(); ++pos )
    cout << *pos << endl;
  return 0;
}
 
 

More on Containers
- All containers have several common operations implemented as methods
- Some of these common methods include:

size()
- Returns the actual number of elements in the container

empty()
- Returns whether the container is empty or not

swap()
- Swaps data with another container

insert()
- Inserts elements into the container

erase()
- Removes elements from the container

clear()
- Removes all elements making it empty

- Some containers add their own specific methods to the common set
- The list container, for example, adds the following types of methods:

splice()
- Inserts elements from one container into another

sort()
- Sorts elements in the list

unique()
- Removes duplicate elements in the list
 
 

Algorithms
- Standard algorithms for processing elements of a collection
- Algorithms are NOT member functions of container classes
- Implemented as global functions that operate on iterators
- Types of algorithms include searching, sorting, copying, reordering
- Include header file <algorithm>
 
 

Using the STL
- STL programmers use containers, iterators, and algorithms together
- Containers contain iterators, algorithms operate on iterators...
 

Example

#include <iostream>
#include <list>
#include <algorithm>

using namespace std;

void printList( const list<int> &l )
{
  list<int>::const_iterator pos;
  cout << "List:" << endl;
  for( pos = l.begin(); pos != l.end(); ++pos )
    cout << *pos << endl;
}

int main()
{
  int i;
  list<int> il;       // linked list container of integers

  // Load container elements with values at front
  for( i = 10; i < 16; ++i )
    il.push_front( i );
  printList( il );

  // Sort the list (using list member method)
  il.sort();
  printList( il );

  // Use STL algorithm find to find an element with
  // value 12 and return an iterator to this position
  list<int>::iterator fpos;
  fpos = find( il.begin(), il.end(), 12 );

  // Insert an element at the position found
  il.insert( fpos, 101 );
  printList( il );

  // Reverse order of the list using STL algorithm
  reverse( il.begin(), il.end() );
  printList( il );
 
  return 0;
}
 

Output
List:
15
14
13
12
11
10
List:
10
11
12
13
14
15
List:
10
11
101
12
13
14
15
List:
15
14
13
12
101
11
10
 

- We can also use the STL with our own classes
- We can use an STL linked list without worrying about a next pointer!
 

Example

#include <iostream>
#include <list>

using namespace std;

class Test
{
  friend ostream &operator<<( ostream &strm, const Test &t )
  {
    strm << "Test:" << endl;
    strm << "  val: " << t.val << endl;
    return strm;
  }

private:
  int val;

public:
  Test( int v=0.0 ) { val = v; }

};

int main()
{
  int i;
  list<Test> tl;

  // Load container elements with values at front
  for( i = 10; i < 16; ++i )
    tl.push_front( Test(i) );

  // Print container elements
  list<Test>::const_iterator pos;
  for( pos = tl.begin(); pos != tl.end(); ++pos )
    cout << *pos << endl;

  return 0;
}
 

Output
Test:
  val: 15

Test:
  val: 14

Test:
  val: 13

Test:
  val: 12

Test:
  val: 11

Test:
  val: 10
 
 

Readings

Deitel & Deitel, Fourth Edition: 21.1, 22.4