Transcript PowerPoint

STL: C++ Standard Library
.
Main Ideas
General
purpose: generic data structures &
algorithms, templates
Flexibility: Allows for many combinations of
algorithm-container
Simple & uniform interface:
interface through templates (not inheritence)
Efficiency
Components
Containers:
data structures
vector, list, map, set, deque
Adaptors: high-level data structure
stack, queue, priority_queue
Iterators: allow access into containers
Algorithms: base algorithms
sort, copy, search, min, max, …
Streams: input/output
String
Example
Using
STL objects to implement a simplified
version of ex2
Data structures:
 string – represent words
 map<string,vector<string> >
Associate a word with the array of words
that appear after it
Quick Facts
Vector<T>
 Implements an array of objects of type T
 Allows random-access to array
 Can grow on as needed basis
Map<KeyT,ValueT>
 “Associative Array”: maps keys to values
 Implemented as balanced binary tree
Markov-1.cpp
Extension
Same
but using k-order Markov chain
Represents the probability of a word after a
prefix of k words
Data structures:
list<string> - represent a list of objects
See Markov-k.cpp
Containers
Holds
copies of elements
Assumes Copy Ctor & operator =
The standard defines the interface, not the
implementation
Two main classes
 Sequential containers:
list, vector,....
 Associative containers:
map, multimap, set ...
Sequential Containers
Maintain
a linear sequence of objects
Types of operations
Access/insertion/deletion of
elements at the front/end of sequence
Random access to elements
Sequential Containers
list - a linked list of objects
 Efficient insertion/deletion in
front/end/middle
vector - an extendable sequence of objects
 Efficient insertion/deletion at end
 Random access
deque – double-ended queue
 Efficient insertion/deletion at front/end
 Random access
Sequential Container Interface
size(),
empty()
push_front(x), push_back(x)
front(), back()
pop_front(), pop_back()
vector & deque
operator[](int index)
Associative Containers
Maintain
a collection of keys
Requires order on keys (less-than operator)
Keys can be accessed based on their order
(Typical) Implementation:
red-black binary trees
O(log n) time for access/insert/delete
Associative Containers
Set
A set of unique keys
Map
Associate a value to key (associative array)
Unique value of each key
Multiset
Multimap
Same, but allow multiple values
Associative Containers & Order
Associative
containers use operator< as
default order
We can control order by using our own
comparison function
To understand this issue, we need to use
function object
Function Objects
A class that implements operator()
Advantages:
Use the template mechanism (class versus
function)
Enable accumulating information in the
function object
Example
template<class T>
class less {
public:
bool operator()(T& lhs, T& rhs)
{ return lhs < rhs; }
};
less<int> cmp; // declare
if( cmp(1,2) )
…
if( less<int>()(1,2) )
…
an object
Creates temporary
objects, and then
call operator()
Function Object Bases
Base
classes for the functions objects are
defined in STL.
These provide standard names for the
arguments and return types.
template<class T>
class less :
public binary_function<T, T, bool>
{
…
}
Function Object Bases
template< class Arg, class Res>
struct unary_function {
typedef Arg argument_type;
typedef Res return_type;
};
template< class Arg, class Arg2, class Res>
struct binary_function {
typedef Arg first_argument_type;
typedef Arg2 second_argument_type;
typedef Res return_type;
};
Using Comparators
template<class T, class Cmp = less<T> >
class set {
…
}
…
set<int> s1;
a new
set<int,less<int> > s2;// Creates
same type
MyComp object.
set<int,MyComp > s3;
Use given
MyComp object.
MyComp cmp;
set<int,MyComp > s4(cmp);
STL Iterators
Iterators
are allow to traverse sequences
Methods
 operator*
 operator++, and operator—
Different types of iterators - to support read,
write and random access
Containers define their own iterator types
Changing the container can invalidate the
iterator
Iterator Types
Output Input
Read
Write
Iteration
x = *i
x = *i
x = *i
x = *i
*i = x
*i = x
*i = x
++
++
++, --
==, !=
==, !=
==, !=
++,
+=,
==,
<=,
*i = x
++
Comparison
Output:
Forward Bi-directional Random
--, +, -,
-=
!=, <, >,
>=
write only and can write only once
Input: read many times each item
Forward supports both read and write
Bi-directional support also decrement
Random supports random access (just like C
pointer)
Iterators & Containers
Bidirectional iterators:
 list, map, set
Random access iterators:
vector, deque
Input/output/forward iterators:
iostreams
Iterators and Containers
T::iterator – iterator type for type T
begin() – front of the container
end() – element after last
Container C
…
Container::iterator i
for( i = C.begin(); i != C.end(); i++)
// do something with *i
Iterators & Streams
Can access iostreams through iterators:
istream_iterator<string> in(cin);
istream_iterator<string> endOfInput;
ostream_iterator<string> out(cout);
while( in != endOfInput )
{
string s = *in++;
*out++ = s;
*out++ = “ “;
}
see useStreamIterators.cpp
Sequence Adapters
Adapters
of basic containers
Very easy, but limited interface
stack<T,Seq>
provides push, pop, top, size and empty
queue<T,Seq>
also provides back
priority_queue<T,Seq,Cmp>
provides same interface as stack
uses a compare function object
Algorithms Overview
Sequence
operations
 Non modifying: for_each, find, count,
search, mismatch, equal
 Modifying: transform, copy, swap, replace,
fill, generate, remove, unique, reverse,
rotate, random_shuffle
Sorted
sequences operations
 sort, lower_bound, upper_bound,
equal_range, binary_search, merge,
includes, set_union, intersection,
difference, symmetric_difference
Algorithms
Most
STL algorithms works on sequences
Sequences are passed as two iterators:
 beginning element
 element one after last
p
q
sequence [p,q)
Algorithms
depend on iterator type
not on container type
Copy
template< class In, class Out>
Out copy(In first, In last, Out res)
{
while (first != last)
*res++ = *first++;
return res;
}
See useCopy.cpp
Non-modifying Sequence
Algorithms

In find(In first, In last, const T& val)
find the first occurence of val in the sequence

In find_if(In first, In last, Pred p)
find the first element satisfying p

I1 find_first_of(I1 f1, I1 l1, I2 f2, I2 l2)
find the first match between two sequences.

I1 search( I1 f1, I1 l1, I2 f1, I2 l2 )
search for the sequence f2...l2 inside f1..l1
Sorted Sequence Algorithms

sort(In first, In last[, class cmp])
find the first occurence of val in the sequence
In lower_bound(In first, In last,
T const & val[, class cmp])
find the first element not less than val
 bool binary_search(In first, In last,
T const & val[, class cmp])
check if val appears in the sequence
 Out merge( I1 f1, I1 l1, I2 f1, I2 l2,
Out out )

merge two sorted sequences and write the merged
sequence onto the output iterator out