CVector - Vector container for C89

A C89 implementation of std::vector from CPP that allows multiple data types using the same functions. Utilises #defines and void functions within structs to implement the vector container from the CPP STL from sometime around C++98/03. This implementation allows the same Vector struct and Vector function to manipulate any type of data. Some creative liberties are exercised in order for this to work.

Works by using #define to specify the data type and create a struct with function pointers and measurements, an interior struct to hold the data and helper functions that work use the #define's data type. The helper functions are then assigned to the function pointers of the vector, so you can write v->at(v, index) instead of Vector_at_int(myIntegerVector, index), greatly reducing verbosity.

Part of an ongoing series

Limitations

Iterators

In the context of C, iterators would have really limited functionality. You'd either need to call iter->next() for the next value in a for loop, or use an index with something like iter->data[i]. This removes of the major functionality of iterators, other than holding an address (references in the context of C++ don't exist in C). The accepted solution is to crudely loop through vector->at(v, i).

Lack of static functions / passing vector every time.

Unfortunately, in order to maximise compatibility, you cannot #define in one .c file and have it propagate into others without directly importing the .c file. Importing the .c file makes static functions accessible. As a result, I put all definitions in one .h file. Consequently, each defined vector's (more on that soon) helper functions are available for use public instead of accessing them through the function pointers. For consistency, safety and maintaining standards, I strongly recommend using the function pointers. Also, when using the function pointers or helper functions you must pass the vector every time. This is because there is no this-> in C, so you must provide a pointer to the vector.

Use

Basic setup

For every vector type you wish to use, you must put outside of functions and above all vector uses DEFINE_VECTOR(int) (replace with whatever type you'd like). This creates an initialisation method along all of the helper function with this type.

Once you've defined a type, do not define it again!

To create a vector:

struct Vector_int* v = vectorInit_int();

This is the only time from now on that you'll specify the type. Every time you want to call a function, you will use the vector and pass the vector to the function. Using a function:

v->example(v, restOfTheArgs);

This is used for both void methods and methods with a return. Data members can be accessed by:

v->size;

Functions

Type is replace with the DEFINE_VECTOR. Variables names can be whatever you like of course.

• void resize (struct Vector_type* v, size_t newSize);
  • Resizes the vector based on input to newSize.
  • If the size is larger than the current capacity, the vector is realloced to be bigger and new values are initialised to zero.
  • If the size is smaller than the current capacity, it will loop through initialising the vectors past the new size to zero, and then set the size and capacity to the new size. WILL NOT REALLOC FOR EFFICENCY REASONS. Call shrink_to_fit to reduce size in memory.
• int empty (const struct Vector_type* v);
  • Returns 1 if the vector has values in it, 0 if it's empty.
• void shrink_to_fit (struct Vector_type* v);
  • Reduces the memory allocation to that size and sets the capacity to the size of the vector.
• type* data (const struct Vector_type* v);
  • Returns a pointer to the data of the vector.
  • Can be used unsafely with square brackets to get pointers to values.
• type at (const struct Vector_type* v, size_t index);
  • Returns a local variable to the given index.
• type front (const struct Vector_type* v);
  • Returns a local variable to the front of the vector.
• type back (const struct Vector_type* v);
  • Returns a local variable to the back of the vector.
• void push_back (struct Vector_type* v, type inputValue);
  • Adds a new element to the end of the vector.
  • If the vector is too small, realloc is called and the capacity and allocated memory is doubled.
• void pop_back (struct Vector_type* v);
  • Initialises the last member to zero, and then reduces the size.
  • Does not dealloc anything.
• void insert (struct Vector_type* v, size_t index, type inputValue);
  • Inserts an element of value inputValue at index.
  • Pushes elements over 1 at input value. Will resize the vector 2*capacity if the vector is too small.
• void erase (struct Vector_type* v, size_t index);
  • Will erase a value at an index by overriding it with elements after it, setting the original last element to zero and decreasing the size by 1.
• void clear (struct Vector_type* v);
  • Re-initialises all values to zero for the whole capacity and sets size to zero.
• void swap (struct Vector_type* a, struct Vector_type* b);
  • Swaps the inner->data* of 2 vectors of the same type.
• void free (struct Vector_type* v);
  • Frees the inner-data*, inner struct and the struct itself.

Planned Features

• Needs insert_range
  • Currently inserting values moves them across. With every insert, its o(n) time for the values after the index to move them along. This is really inefficent. Need to copy all values after the index to a new vector, write the given range to the original vector and then append the rest of the old vector.
• Needs Iterators
  • Not very useful at this point in time, but could be useful when messing with other data structures.

Unimplemented Features

• operator[]
  • Call v->data() and use the square brackets like
  • (YOU PUT THE TYPE HERE)* data = v-> data;
  • data[i];
• Iterators
  • Beginning and end address getters. Can just use v->at(v, 0) to get the first element and v->at(v, v->size) to get the last element.
• max_size
  • Doesn't really make sense in this context as the max size is based on malloc not failing.
• reserve

That's pretty much everything according to cpp reference for std::vector when set to revision C++98/03

Sample code can be found in the main.c file