A planar triangulation of a set of points is a maximal set of triangles whose vertices are located on the initial points. In order to represent and manipulate a triangulation, we usually use a graph to encode the relationships between the vertices (points) of the triangulation, the faces (triangles), and eventually the edges (line segments). For example, a triangle has 3 adjacent triangles, and thus a face in the associated graph will store 3 pointers (or iterators) to other faces, it will also store 3 pointers to adjacent vertices, and a vertex stores the coordinates of the point as well as a pointer (or iterator) to one of its incident faces.
We would like to store the associated graph in a class which would follow the standard container adapters design as much as possible, so that we can use the standard containers to store the faces and vertices.
When manipulating the associated graph, we require that the time to create and delete objects (faces, vertices) be amortized constant, whereever they appear in the iterator sequence. The STL list provides this functionality, however it is not very compact in memory, since each node of the list usually stores 2 additional pointers for the iterator requirements.
The goal of the project is to design and implement an STL-like Container which will feature a smaller memory footprint than the STL list, while still providing the properties of interest for this graph application (and probably most graphs). This container should try (as much as possible) to provide the requirements of standard containers and iterators. The tasks include: