Zimmer CSCI 330
Standard Template Library
Template Class - created with at least one class parameter, a symbol that serves as a placeholder for a specific data type.
Example:
A program has a stack of ints and a stack of chars: s1, s2
Right now we would need two different stack ADT’s each incorporating a different data type being “stacked” (an int stack, and a char stack):
StackIntClass s1;
StackCharClass s2;
Instead, we would like to just have one ADT but create two different stack variables and indicate in the declaration the data type to use in the stack.
StackClass<int> s1;
StackClass<char> s2;
08/24/15 1
Zimmer CSCI 330
// ORIGINAL stackClass.h
class StackClass
{
public:
StackClass(int max); // max is stack size.
StackClass(); // Default size is 500.
~StackClass(); // Destructor
void MakeEmpty();
bool IsEmpty() const;
bool IsFull() const;
void Push(int item);
void Pop(int& item);
private:
int top;
int maxStack; // Max stack items.
int* items; // ptr to dyn alloc stack
};
Becomes:
// NEW stackClass.h
template <class ItemType>
class StackClass
{
public:
StackClass(int max); // max is stack size.
StackClass(); // Default size is 500.
~StackClass(); // Destructor
void MakeEmpty();
bool IsEmpty() const;
bool IsFull() const;
void Push(ItemType item);
void Pop(ItemType & item);
private:
int top;
int maxStack; // Max stack items ItemType * items; // ptr to dyn alloc stack
};
08/24/15 1
Zimmer CSCI 330
08/24/15 1
Zimmer CSCI 330
// ORIGINAL stackClass.cpp
StackClass::StackClass()
{
maxStack = 500;
top = -1;
items = new int[500];
}
StackClass::StackClass(int max)
{
maxStack = max;
top = -1;
items = new int[max];
}
StackClass::~StackClass()
{
delete[ ] items;
}
void StackClass::MakeEmpty()
{
top = -1;
}
bool StackClass::IsEmpty() const
{
return (top == -1);
}
bool StackClass::IsFull() const
{
return (top == maxStack - 1);
}
void StackClass::Push(int newItem)
{
if (top <maxStack-1)
{
top++;
items[top] = newItem;
}
}
void StackClass::Pop(int& item)
{
if (top > -1)
{
item = items[top];
top--;
}
}
Becomes:
// NEW stackClass.cpp
template<class ItemType>
StackClass<ItemType>::StackClass()
{
maxStack = 500;
top = -1;
items = new ItemType [maxStack];
}
template<class ItemType>
StackClass<ItemType>::StackClass(int max)
{
maxStack = max;
top = -1;
items = new ItemType [max];
}
template<class ItemType>
StackClass<ItemType>::~StackClass()
{ delete[ ] items;}
template<class ItemType>
void StackClass<ItemType>::MakeEmpty()
{ top = -1; }
template<class ItemType>
bool StackClass<ItemType>::IsEmpty() const
{
return (top == -1);
}
template<class ItemType>
bool StackClass<ItemType>::IsFull() const
{ return (top == maxStack - 1); }
template<class ItemType>
void StackClass<ItemType>::
Push(ItemType newItem)
{
if (top <maxStack-1)
{
top++;
items[top] = newItem;
}
}
template<class ItemType>
void StackClass<ItemType>::
Pop(ItemType& item)
{
if (top > -1)
{
item = items[top];
top--;
}
}
08/24/15 1
Zimmer CSCI 330
Function Style Parameters
· Template must have at least one class parameter (may have more)
· May have function style parameters whose data type is built in or user defined
· separate parameters by commas
StackClass<int,5 s1;
StackClass<char,12 s2;
08/24/15 1
Zimmer CSCI 330
Becomes:
// NEW stackClass.h
template <class ItemType, int max>
class StackClass
{
public:
StackClass(); // Default size is max.
~StackClass(); // Destructor
void MakeEmpty();
bool IsEmpty() const;
bool IsFull() const;
void Push(ItemType item);
void Pop(ItemType & item);
private:
int top;
ItemType * items; // ptr to dyn alloc stack
};
Becomes:
// NEW stackClass.cpp
template<class ItemType, int max>
StackClass<ItemType, max>::StackClass()
{
top = -1;
items = new ItemType [max];
}
template<class ItemType, int max>
StackClass<ItemType, max>::~StackClass()
{ delete[ ] items; }
template<class ItemType, int max>
void StackClass<ItemType, max>::MakeEmpty()
{ top = -1; }
template<class ItemType, int max>
bool StackClass<ItemType, max>::IsEmpty() const
{
return (top == -1);
}
template<class ItemType, int max>
bool StackClass<ItemType, max>::IsFull() const
{
return (top == max - 1);
}
template<class ItemType, int max>
void StackClass<ItemType, max>::
Push(ItemType newItem)
{
if (top <max-1)
{
top++;
items[top] = newItem;
}
}
template<class ItemType, int max>
void StackClass<ItemType, max>::
Pop(ItemType& item)
{
if (top > -1)
{
item = items[top];
top--;
}
}
08/24/15 1
Zimmer CSCI 330
Assertions
· Is a condition that must be true at a certain point in the program
· Can be used for debugging
· Must include cassert header file
· #define NDEBUG will disable asserts
//#define NDEBUG
#include <cassert>
…
cout < "enter a number - not zero";
cin > num;
assert (num!=0); // program halts and prints msg if num is 0
x = 5/num;
…
If assert fails then the following is output:
Assertion failed: num!=0, file xxx.cpp, line yyy
STL - Standard Template Library
· Data structures already created
· Dynamic implementation that grows and shrinks as needed
· Contribute to programming ease, robustness, storage efficiency
· STL is extensible - can be added to
· Need to include proper header files
3 Components:
Containers - collection of objects (data structure)
Sequential data structures: (accessed by position)
· vector - array that grows and shrinks (supports fast random access)
· deque – (double ended queue) array with efficient insertions/deletions at the ends
· list - bidirectional linked list (supports fast insert & deletion)
Sequential container adaptors
· stack – LIFO
· queue – FIFO
· priority_queue – priority managed queue
Associative data structures: (accessed by a key)
· set - collection of nonduplicate keys
· multiset - set that allows duplicate keys
· map - collection of nonduplicate elements with access by a key
· multimap - map that allows duplicates
Algorithms - functions for processing containers contents
· copy
· sort
· search
· merge
· permute
Iterators - mechanism for accessing the objects in the container one at a time
Sequential Containers:
#include <vector>
#include <list>
#include <deque>
vector<string> svec; //empty vector to hold strings
list<int> ilist; // empty list to hold integers
deque<StudentClass> students; // empty deque for StudentClass
Basic Operations:
c.empty( ) returns true if container is empty, false otherwise
c.size( ) returns number of elements in the container
c.push_back(e) adds element with value e to the end of the container
c.push_front(e) adds element with value e to the front of the container (only valid for list or deque)
c[i] subscripts an element in the container (only valid for vector and deque) (Can only subscript if elements exist)
Examples: (vec1.cpp)
vector<string> v1 ;
v1.push_back(“hello”);
v1.push_back(“there”);
v1.push_back(“world”);
cout < v1.size( ); // prints 3
cout < v1[0] < v1[1] < v1[2] ; // prints out the three strings
Iterators:
· allows to examine and navigate through the elements in a container
· two iterator types that are common to all containers:
§ iterator
§ const_iterator
· two member functions for all containers that return an iterator:
c.begin( ) returns a pointer to the first element
c.end( ) sentinel value - returns a pointer to element just beyond the end of the container (not really an existing element)
Iterator Operations:
*iter Dereference the iterator to get to the element
iter->mem dereference iterator and fetch the member named mem
++iter increment iterator to reference next element
iter ++
--iter decrement iterator to reference the previous element
iter--
iter1 == iter2 check whether iterators are referring to same element
iter1!= iter2 check whether iterators are referring to different elements
>,<,<=,>= (these 4 relational op only valid for vector & deque)
iter+n reference element n elements from iter (only
iter – n supported by vector & deque)
Examples: (vec2.cpp)
vector<string> :: iterator iter;
vector<string>:: const_iterator c_iter;
iter = v1.begin( );
cout < *iter;
c_iter = v1.begin( );
cout < *c_iter;
*iter = “hi”; // OK
*c_iter = “Good bye”; // Error – can’t change element pointer to by const iterator
cout < iter->length( ); // calls length( ) for string pointed to by iterator
Container Constructors: (vec3.cpp)
vector<int> v1; // create an empty container
vector<int> v2(4, 15); // create v2 with 4 el each with initial value of 15
(sequential containers only)
vector<int> v3 (v2); // create v3 as a copy of v2
vector<int> v4(8); // create v4 with 8 elements initialized
(sequential containers only)
vector<int>::iterator b = v2.begin( );
vector<int>:: iterator e = b+2;
vector<int> v5(b, e); // create v5 with a copy of elements from b to e ( not including e)
Constraints on types that a container holds
· element type must support assignment
· element type must be able to copy objects of that type (copy constructor)
Examples:
class Foo
{ public:
Foo(int i) { data = i; };
…
};
vector <Foo> empty; // OK: no need for a default constructor
vector<Foo> bad(10); // error: no default constructor
vector<Foo> ok(10,1); // OK: each element initialize to 1 by parameterized constructor
More Container Operations
c.insert(p , t) inserts element t before the element referred to by p. Returns an iterator referring to the new element
c.insert(p,n,t) inserts n copies of t before element referred to by p.
Returns void
c.insert(p,b,e) inserts copies of the elements from b to (not including e)
before the element pointed to by p. Returns void.
c.erase(p) removes the element referred to by p
c.erase(b,e) removes the elements from b to e
c.clear( ) removes all elements
c.pop_back( ) removes the last element
c.pop_front( ) removes the first element(only for list & deque)
Examples: (vec4.cpp)
vector<string> v1 ;
v1.push_back(“hello”);
v1.push_back(“there”);
v1.push_back(“world”);
v1.insert(v1.begin( ), v1.begin( ), v1.end( ));
vector<string>:: iterator iter;
iter = v1.begin( ) +1;
v1.insert(iter, “hello”);
iter = v1.begin( ) +2;
v1.insert(iter,5,”hi”);
iter = v1.begin( )+7;
v1.erase(iter);
// VECTORs (vec5.cpp)
#include <iostream>
#include <vector>
using namespace std;
int main( )
{
vector<char> v;
char ch;
int i;
cout < "Enter 10 characters: ";
for (i = 1; i<=10; i++)
{
cin.get(ch);
v.insert(v.begin( ), ch); // inserts at the beginning
}
v.insert(v.begin( ), '('); // inserts ( in front of first character
v.insert(v.end( ), ')'); // inserts ) at the end of vector
cout < " Size = " < v.size()< endl;
cout < "Vector is ";
for (i=0; i< v.size(); i++)
cout < v[i];
cout < endl;
v.erase(v.begin( )); // removes first character
cout < " Size = " < v.size()< endl;
cout < "Vector is ";
for (i=0; i< v.size(); i++)
cout < v[i];
cout < endl;
return 0;
}
08/24/15 1
Zimmer CSCI 330
// LISTs (list.cpp)
#include <iostream>
#include <list>
using namespace std;
int main( )
{
list<char> l;
char ch;
int i;
list<char>::const_iterator x;
// can't change the container
list<char>::iterator y;
// can change the container
cout < "Enter 10 characters: ";
for (i = 1; i<=10; i++)
{
cin.get(ch);
l.insert(l.end( ), ch); // inserts at the end
}
l.insert(l.begin( ), '(');
// inserts ( in front of first character
l.insert(l.end( ), ')');
// inserts ) at the end of vector
cout < " Size = " < l.size()< endl;
cout < "list is ";
x = l.begin();
while (x != l.end())
{
cout < *x;
x++;
}
cout < endl<endl;
l.erase(l.begin( )); // removes first character
cout < "removed first char"<endl;
cout < " Size = " < l.size()< endl;
cout < "list is ";
x = l.begin();
while (x != l.end())
{
cout < *x;
x++;
}
cout < endl<endl;
l.reverse( ); // reverses the list
cout < "reverse list"<endl;
cout < "list is: ";
x = l.begin();
y = l.begin();
for (i=0; i< l.size(); i++)
{
cout < *x;
*y = 'Z';
x++;
y++;
}
cout < endl <endl;
cout < "list is after changed: ";
x = l.begin();
for (i=0; i< l.size(); i++)
{
cout < *x;
x++;
}
cout < endl<endl;
return 0;
08/24/15 1
Zimmer CSCI 330
08/24/15 1
Zimmer CSCI 330
Associative Containers:
#include <map>
#include <set>
#include <mutimap>
#include <mutiset>
set – used to store a collection of distinct values
ex: all words used in a document
map – used to store pairs of values (key and value pairs)
ex: all words used in a document along with their counts
Companion library type:
#include <utility>
pair – creates a data type of two values(data members: first, second)
make_pair(v1, v2) – creates and returns a pair datatype that has a pair(v1,v2)
– v1 & v2 datatypes are implied
Examples: (pair.cpp)
08/24/15 1
Zimmer CSCI 330
pair<string, string> author1 ("Randy", "Pausch");
cout < "Author 1: ";
cout < author1.first <" "
<author1.second<endl<endl;
pair<string,string> author2;
string fname, lname;
cout < "Enter author name: ";
cin > fname > lname ;
author2 = make_pair(fname, lname);
cout < "Author 2: ";
cout < author2.first <" "
<author2.second<endl<endl;
typedef pair<string, string> AuthorType;
AuthorType author3("James", "Joyce");
AuthorType author4;
author4 = make_pair("Robin","Cook");
cout < "Author 3: ";
cout < author3.first <" "
<author3.second<endl<endl;
cout < "Author 4: ";
cout < author4.first <" "
<author4.second<endl<endl;
return 0;
}
08/24/15 1
Zimmer CSCI 330
Associative containers:
do not have: front, push_front, pop_front, back, push_back, pop_back
do have: insert, erase, clear
elements are ordered by key – irrespective of the order added
Examples: (map1.cpp)
string word;
map<string, int> word_count;
// word_count["the"] = 1; // if it exists it is modified,
//if it is new it is added
// cout < word_count["the"]<endl;
cout < "Enter some words, q when done:" <endl;
cin>word;
while(word != "q")