Genericprogrammingstartswith
algorithms
Minimal requirements:
works with maximal
family of types
Am
Generic
algorithm
Lift
...
Remove an
unneeded
requirement
on the type
Start
here
Lift
A1
Lift
A0
Less specialized:
works with more
than one type
Concrete algorithm:
requires specific data type
Maximalwithrespecttowhat?
Maintain usefulness of
the algorithm make
efficiency part of the
requirements
Am
Generic
algorithm
Lift
...
Lift
A1
Lift
A0
Concrete algorithm
A Concrete Algorithm
float
max_element(float a[],
int N)
{
if (N == 0)
throw MaxElementEmptyArrayError;
int first = 0; float max = a[0];
while (++first < N)
if (max < a[first])
max = a[first];
return max;
}
A More Useful Interface
int
max_element(float a[],
int first, int last)
{
if (first == last)
return first;
int result = first;
while (++first != last)
if (a[result] < a[first])
result = first;
return result;
}
A Linked-List Counterpart
float_list_node*
max_element(float_list_node* first,
float_list_node* last)
{
if (first == last)
return first;
float_list_node* result = first;
while (first->next != last)
if (result->data < first->data)
result = first;
return result;
}
Back to the Array Version
int
max_element(float a[],
int first, int last)
{
if (first == last)
return first;
int result = first;
while (++first != last)
if (a[result] < a[first])
result = first;
return result;
}
Generalize the Element Type
template <typename E>
int
max_element(E a[],
int first, int last)
{
if (first == last)
return first;
int result = first;
while (++first != last)
if (a[result] < a[first])
result = first;
return result;
}
From Array Indexing to Pointers
template <typename T>
T*
max_element(T* first,
T* last)
{
if (first == last)
return first;
T* result = first;
while (++first != last)
if (*result < *first)
result = first;
return result;
}
Generalize from Pointers to Iterators
template <typename ForwardIterator>
ForwardIterator
max_element(ForwardIterator first,
ForwardIterator last)
{
if (first == last)
return first;
ForwardIterator result = first;
while (++first != last)
if (*result < *first)
result = first;
return result;
}
Use with any Container with appropriate iterators
int a[] = {6, 3, 7, 5};
int* ai = max_element(a, a+4);
vector<int> v(a, a+4);
vector<int>::iterator
vi = max_element([Link](), [Link]());
list<int> x(a, a+4);
list<int>::iterator
li = max_element([Link](), [Link]());
. . .
Generic
max_element algorithm
on
k = ++j
*j = 3
*k = 7
j
3 7
max_element
++i
*i
i==j
Forward
Container
Concept
max_element
Whatisaconcept?
Intension
Extension
Requirement 1
Abstraction 1
Requirement 2
.
.
.
.
Requirement N
Abstraction 2
.
.
.
Abstraction K
.
.
.
Concept
Intension
Extension
Requirement 1
Abstraction 1
Requirement 2
.
.
.
.
Requirement N
Abstraction 2
.
.
.
Abstraction K
.
.
.
An abstraction is in the Extension if and only if
it satisfies all of the requirements in the Intension
Intension
Extension
Closed plane figure
N sides (for any N)
...
Example: Polygon Concept
Intension
Must be a type
whose objects can
store other objects
(elements)
Must have an
associated iterator
type that can be
used to traverse
through the
elements.
Extension
vector<T>, for any T
deque<T> for any T
list<T> for any T
slist<T> for any T
set<T> for any T
map<T> for any T
...
Example: Container Concept
AlgorithmAworkswith
everytypeTinconceptC
Definition:analgorithmisgenericif
itworkswitheverytypeinaconcept
works:iscorrectandefficient
STL Container Concepts
Container
Associative
Container
Forward
Container
Sequence
Front
Insertion
Sequence
Reversible
Container
Back
Insertion
Sequence
Front
& Back
Insertion
Sequence
Random
Access
Container
Vector
Simple
A. C.
Set
Multiset
Sorted
A. C.
Unique
A. C.
Multiple
A. C.
Hashed
A. C.
Unique
Sorted
A. C.
Multiple
Sorted
A. C.
Unique
Hashed
A. C.
Multiple
Hashed
A. C.
Map
Multimap
H.
Set
Slist
List
Deque
See also [Link]
H.
Multiset
H.
Map
Pair
A. C.
H.
Multimap
Click on any node in the
above concept hierarchy to
see the corresponding
requirements as specified in
the SGI STL Programmers
Guide
STL Generic
Algorithms
on Forward
Containers
Requires input
iterators
Requires
forward iterators
Container
Forward
Container
Enables generic algorithms
Back
copy, for_each, equal, transform,
Enables find, merge, fill, replace,
generate, remove, unique, rotate,
Requires
bidirectional
iterators
Sequence
Front
Insertion
Sequence
Back
Insertion
Sequence
Front
& Back
Insertion
Sequence
Reversible
Container
Enables reverse, partition,
inplace_merge,
Requires
Random
random Access
access
Container
iterators
Vector
Slist
List
Deque
Enables sort,
binary_search,
random_shuffle,
STL Concepts
Container
Forward
Container
Associative
Container
Iterator
Input
Iterator
Output
Iterator
Algorithm
Input
Algorithm
Output
Algorithm
Forward
Iterator
Forward
Algorithm
Bidirectional
Bidirectional
Iterator
Algorithm
Random
Access
Iterator
Random
Access
Algorithm
Functor
Unary
Functor
Binary
Functor
Binary
Predicate
Order
Relation
Adaptor
Iterator
Adaptor
New Concepts in the Boost Graph Library
BGL Concepts
STL Concepts
Container
Graph
Incidence Adj.
Graph
Graph
Iterator
Graph
Iterator
EdgeList
Graph
Algorithm
Graph
Algorithms
Functor
Adaptor
Visitor
BFS
Visitor
DFS
Visitor
Uniform
Cost
Visitor
See also [Link]
Generic Libraries Designed and Developed Via
the Concept-Based Approach
Standard Template Library (HP, RPI, SGI)
Matrix Template Library (Indiana U.)
Boost Graph Library (Indiana U.)
Parallel Boost Graph Library (D. Gregor [RPI PhD], Indiana U.)
Boost Array Library (N. Josuttis)
Boost Multi-Array Library (Indiana U.)
Boost Basic Linear Algebra Library (J. Walter, M. Koch)
Boost Property Map Library (Indiana U.)
Boost Random Number Generator Library (J. Mauer)
Boost Threads Library (W. Kempf)
Boost Concept Checking Library (Indiana U.)
Computational Geometry Algorithms Library (H. Brnnimann,
S. Schirra, R. Veltkamp, )