Linear Data Structures

Example Implementations

For example implementations of various linear data structures, please see the source files attached below.

STL-like Containers

The STL provides several container classes for storing items of any type.  This is accomplished using templated classes, like this:

template <typename T>
class vector {
  T *items;

For examples of implementing STL-like containers, see the attached C++ source files below.


In the STL, linear data structures like std::list and std::vector provide iterator objects, which can be used to iterate over each item in the list, like this:

for (std::vector<int>::iterator pos = v.begin(); pos != b.end(); ++pos) {
  std::cout << *pos << std::endl;

For an example implementation of an iterator, see the list.cpp code attached below.

"Auto" Arrays

C++ allows you to define an "auto array" of variable size using the stack (not the heap).  This is done like this:

int n = 5;
int array[n];

Originally, 'n' needed to be a constant or a "literal", but recent versions of C/C++ allow 'n' to be dynamic.  However, please note that this will cause the compiler to allocate your dynamic array on the stack, which is relatively small.  It is very easy to "blow the stack" this way.  In general, auto variables (arrays included) should be kept small.  Once you run out of stack, your program will crash!  You can't ask for more.

Strangely, C++ lets you define arrays this way, but not classes.  Consider this code:

template <typename T, int n>
class array {
  T data[n];

This can be used like this:

array<int, 5> as;

or like this:

const int n = 5;
array<int, n> as;

...but NOT like this:

int n = 5;
array<int, n> as;

In that last example, the size of 'n' is not constant, so it can conceivably change at run-time.  This means that the compiler cannot determine the size of the array class (and therefore can't compile the class).

For more examples, see the matrix.cpp and automat.cpp source files attached below.