Skip to content

A header only library written in C that resembles C++ std::vector more commonly known as a dynamic array

License

Notifications You must be signed in to change notification settings

NickHackman/C_Vector

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

34 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

C_Vector

test

Personal interpretation and implementation of std::vector trying to maintain generics in C, while maintaining type safety and checks done by the compiler rather than using void* only 79 lines of code

This library prefers inlined functions over macros due to their type checking and for better more descriptive function definitions for autocomplete engines, and uses macros only when completely necessary to maintain being generic

Installation

$ make install

installs headers to /usr/local/share/include/c_vector

Uninstall

$ make clean

removes headers from /usr/local/share/include/c_vector

Test

$ make test

Internal Representation

user pointer -------|
                    v
---------------------------------------------
| size | capacity | 0 | 1 | 2 | 3 | 4 | ... |
---------------------------------------------

vector[-2] = size, stored as size_t

vector[-1] = capacity, stored as size_t

then all remaining elements are of size TYPE

Allocations

if (vector == NULL) {
    new_vector = allocate 2 * sizeof(size_t) + 12 * sizeof(TYPE)
} else {
    new_vector = allocate 2 * sizeof(size_t) + 2 * capacity * sizeof(TYPE)
}
new_vector[0] = size;
new_vector[1] = new_capacity
vector = &(new_vector[2])

Initialization

int* vector = vector_init(int, 12);
char* string = vector_init(char, 32);

Functions

Function Type Time Complexity Description Example
vector_init init constant Creates a new vector with a given capacity. Not Mandatory Example
vector_push_back insert armotized constant Added a new element of TYPE to the end of the vector Example
[DEFAULT] vector_pop_back delete constant Removes the last element from the vector, doesn't decrease capacity Example
[VECTOR_SHRINK_ON_REMOVE] vector_pop_back delete armotized constant Must #define VECTOR_SHRINK_ON_REMOVE. Removes the last element, but shrinks the capacity when size == capacity / 4 Example
vector_shrink_to_fit modifier linear Reallocates vector with capacity equivalent to size Example
vector_reserve modifier linear Increases capacity to new_capacity, as long as it's greater than current capacity Example
vector_clear delete constant Sets size to 0, doesn't change capacity Example
vector_free free constant Frees the array, but not any internal malloced elements
vector_size accessor constant Returns the user seen size of the vector Example
vector_capacity accessor constant Returns the actual size of the vector Example
vector_front accessor constant Returns the first element in the vector of TYPE Example
vector_empty accessor constant Returns true if the vector is NULL or its size is 0 Example

Examples

Init

#include <stdio.h>
#include <c_vector/vector.h>
int main() {
    int* vector = vector_init(int, 101); // vector_init isn't mandatory, but is equivalent to
    // int* vector = NULL;
    // vector_reserve(vector, 101); but in 1 statement
    for (int i = 0; i < 100; i++) {
	    vector_push_back(vector, i);
    }
    printf("Capacity = %lu\n", vector_capacity(vector)); // 101
    vector_free(vector);
    return 0;
}

Push Back

#include <c_vector/vector.h>
int main() {
    int* vector = NULL;
    for (int i = 0; i < 100; i++) {
	    vector_push_back(vector, i);
    }
    vector_free(vector);
    return 0;
}

Pop Back

[DEFAULT]

#include <stdio.h>
#include <c_vector/vector.h>
int main() {
    int* vector = NULL;
    for (int i = 0; i < 100; i++) {
	    vector_push_back(vector, i);
    }
    while (vector_size(vector) > 0) {
	    printf("%d ", vector_pop_back(vector));
    }
    printf("Capacity = %lu\n", vector_capacity(vector)); // 192
    vector_free(vector);
    return 0;
}

[VECTOR_SHRINK_ON_REMOVE]

#define VECTOR_SHRINK_ON_REMOVE
#include <stdio.h>
#include <c_vector/vector.h>
int main() {
    int* vector = NULL;
    for (int i = 0; i < 100; i++) {
	    vector_push_back(vector, i);
    }
    while (vector_size(vector) > 0) {
	    printf("%d ", vector_pop_back(vector));
    }
    printf("Capacity = %lu\n", vector_capacity(vector)); // 1
    vector_free(vector);
    return 0;
}

Shrink To Fit

#include <stdio.h>
#include <c_vector/vector.h>
int main() {
    int* vector = NULL;
    for (int i = 0; i < 100; i++) {
	    vector_push_back(vector, i);
    }
    printf("Size = %lu\n", vector_size(vector)); // 100
    printf("Capacity Before Shrink = %lu\n", vector_capacity(vector)); // 192
    vector_shrink_to_fit(vector);
    printf("Capacity After Shrink = %lu\n", vector_capacity(vector)); // 100
    vector_free(vector);
    return 0;
}

Reserve

#include <stdio.h>
#include <c_vector/vector.h>
int main() {
    int* vector = NULL;
    vector_reserve(vector, 101); // prevents any allocations from push_back
    for (int i = 0; i < 100; i++) {
	    vector_push_back(vector, i);
    }
    printf("Capacity = %lu\n", vector_capacity(vector)); // 101
    vector_reserve(vector, 10); // Does nothing, 10 isn't greater than 101
    printf("Capacity = %lu\n", vector_capacity(vector)); // 101
    vector_free(vector);
    return 0;
}

Clear

#include <stdio.h>
#include <c_vector/vector.h>
int main() {
    int* vector = NULL;
    for (int i = 0; i < 100; i++) {
	    vector_push_back(vector, i);
    }
    printf("Size = %lu\n", vector_size(vector)); // 100
    vector_clear(vector);
    printf("Size = %lu\n", vector_size(vector)); // 0
    printf("Capacity = %lu\n", vector_capacity(vector)); // 192
    // Not advised
    printf("vector[100] = %d\n", vector[100]); // 99
    // Values are never cleared they are just treated as if they don't exist
    vector_free(vector);
    return 0;
}

Size

#include <stdio.h>
#include <c_vector/vector.h>
int main() {
    int* vector = NULL;
    for (int i = 0; i < 100; i++) {
	    vector_push_back(vector, i);
    }
    printf("Size = %lu\n", vector_size(vector)); // 100
    vector_free(vector);
    return 0;
}

Capacity

#include <stdio.h>
#include <c_vector/vector.h>
int main() {
    int* vector = NULL;
    for (int i = 0; i < 100; i++) {
	    vector_push_back(vector, i);
    }
    printf("Size = %lu\n", vector_capacity(vector)); // 192
    vector_free(vector);
    return 0;
}

Front

#include <stdio.h>
#include <c_vector/vector.h>
int main() {
    int* vector = NULL;
    for (int i = 0; i < 100; i++) {
	    vector_push_back(vector, i);
    }
    // Equivanlent to vector[0], but returns 0/NULL if vector == NULL or is empty
    printf("Front = %d\n", vector_front(vector)); // 0
    vector_free(vector);
    return 0;
}

Back

#include <stdio.h>
#include <c_vector/vector.h>
int main() {
    int* vector = NULL;
    for (int i = 0; i < 100; i++) {
	    vector_push_back(vector, i);
    }
    // Equivanlent to vector[vector_size(vector) - 1], but returns 0/NULL if vector == NULL or is empty
    printf("Back = %d\n", vector_back(vector)); // 99
    vector_free(vector);
    return 0;
}

Empty

#include <stdio.h>
#include <c_vector/vector.h>
int main() {
    int* vector = NULL;
    printf("Vector is empty: %d\n", vector_empty(vector)); // Vector is empty: 1
    for (int i = 0; i < 100; i++) {
	    vector_push_back(vector, i);
    }
    printf("Vector is empty: %d\n", vector_empty(vector)); // Vector is empty: 0
    vector_free(vector);
    return 0;
}

License

MIT

About

A header only library written in C that resembles C++ std::vector more commonly known as a dynamic array

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published