LEDA, Library of Efficient Data types and Algorithm:

- Widely used commercial library of algorithms,
data structures and data types.
- containers
- graphs and graph algorithms
- computational geometry
- number types

- Long history
- Started as an academic project in 1988.
- Precedes and partly overlaps STL.

- High quality library.
- Strong theoretical basis.
- Well optimized and tested implementations.
- Continuous development and support.

- Not based on STL
- Container interface uses
*items*instead of iterators- STL conformant iterators added later

- Algorithms are not fully generic
- For example, only LEDA graphs

- Container interface uses

CGAL, Computational Geometry Algorithms Library

- Developed by several European research institutes since 1995.
- Generic algorithms for computational geometry
- convex hulls, triangulations, spatial search etc.
- 2D, 3D, dD

- Computational geometry algorithms are particularly difficult to
implement:
- handling degeneracies
- Three points on a line is a problem for many algorithms.
- CGAL algorithms can handle degeneracies.

- numerical robustness
- Intersection of two lines may not be on the line because of rounding errors.
- CGAL supports

- handling degeneracies

Some features of CGAL:

Based on STL

template <class InputIterator, class OutputIterator> OutputIterator convex_hull (InputIterator begin, InputIterator end, OutputIterator result);

Geometric kernels:

- basic objects: points, line segments, etc.
- basic primitives:
- construction: segment from two points, point as an intersection of two segments, etc.
- distances
- comparisons
- predicates:
`Are_parallel`,`Left_turn`,`Counterclockwise_in_between`, etc.

- 2D, 3D, and dD kernels
- Cartesian and homogenous coordinates

Kernels are parametrized by a number type

- built-in types, high-precision types, rationals, exact arithmetic types, interval arithmetic, lazy exact, etc.
- supports number types from other libraries: LEDA, CORE, GNU Multiple Precision

Algorithm are parametrized by optional traits:

- basic types and primitives needed by the algorithm
- default traits are derived from the kernel

STXXL, Standard Template Library for Extra Large Data Sets

STL-like algorithms and data structures for external memory computation

- vector, map, stack, priority_queue
- sort, find, for_each

stxxl::vector<double> v; // ... const unsigned M = 50*1024*1024; // use M bytes of main memory stxxl::sort (v.begin(), v.end(), std::less<double>(), M);

Can process huge volumes of data (terabytes)

Support for implementing external memory algorithms

High performance

- supports parallel disks
- overlapping I/O and computation (asynchronous I/O)
- supports pipelining
- allows (but does not require) fine control of parameters and access to low level details