# LEDA

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

LEDA Tutorial

# CGAL

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

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

Example

# STXXL

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