Implementations

C

#include <stddef.h>
#include <stdlib.h>
#include <string.h>
 
typedef struct {
	unsigned char *data;
	size_t size;
	size_t capacity;
	size_t elem_size;
} Array;
 
/// initialise
void array_init(Array *array, size_t elem_size) {
	*array =
	    (Array){.data = NULL, .size = 0, .capacity = 0, .elem_size = elem_size};
}
 
/// free
void array_free(Array *array) {
	free(array->data);
	array_init(array, 0);
}
 
/// get
const void *array_get(const Array *array, size_t index) {
	return (const void *)(array->data + index * array->elem_size);
}
 
/// set
void array_set(Array *array, size_t index, const void *elem) {
	void *dest = (void *)(array->data + array->elem_size * index);
	memcpy(dest, elem, array->elem_size);
}
 
// resize = change size only ( unless growing )
int array_resize(Array *array, size_t size) {
	if (size > array->capacity) {
		// need to grow
		size_t new_cap = 2 * size + 1;
		unsigned char *mem_loc =
		    realloc(array->data, array->elem_size * new_cap);
		if (mem_loc == NULL)
			return 0;
		array->data = mem_loc;
		array->capacity = new_cap;
	}
 
	array->size = size;
	return 1;
}
 
// reserve = guarantee atleast "new_capacity" capacity
int array_reserve(Array *array, size_t new_capacity) {
	// don't refactor to new_capacity > array -> capacity like size
	// size is ALWAYS set, capacity ONLY increases
	if (new_capacity <= array->capacity)
		return 0;
	unsigned char *mem_loc =
	    realloc(array->data, new_capacity * array->elem_size);
	if (mem_loc == NULL)
		return 0;
	array->data = mem_loc;
	array->capacity = new_capacity;
	return 1;
}
 
// push
int array_push(Array *array, const void *elem) {
	// this handles the zero size case
	if (array->size == array->capacity &&
	    !array_reserve(array, array->capacity * 2 + 1)) {
		return 0;
	}
	unsigned char *mem_loc = array->data + array->elem_size * array->size;
	memcpy(mem_loc, elem, array->elem_size);
	array->size++;
	return 1;
}
 
// pop
int array_pop(Array *array, void *out) {
	if (array->size == 0)
		return 0;
	array->size--;
	if (out) {
		unsigned char *mem_loc = array->data + array->size * array->elem_size;
		memcpy(out, mem_loc, array->elem_size);
	}
 
	return 1;
}
 
/*
 * WARN:
 * there are OVERLFLOW issues on multiplcation. Can be improved to use overflow
 * detection - to check if a * b overflows ( b!=0 && a > UINT_MAX / b )
 *
 * INFO:
 * NEWS TO ME: signed integer overflow is UB
 * unsigned overflow is well-defined
 *
 * WARN:
 * any get pointers are invalidated when you realloc - remember that
 *
 * WARN:
 * Assumes elements are "trivially copyable in C++ sense". Problem would be
 * structs holding pointers and then both copy and orignal believng they OWN
 * that pointer's memory
 */

C++

/*
 * dynamic array in c++
 *
 * Needed?
 *   - length, capacity
 *   - overload index operators []
 *   - push_back, pop_back
 *   - reserve
 *   - size
 *   - capacity
 */
#include <cstddef>
#include <initializer_list>
#include <type_traits>
#include <utility>
 
template <typename T> class DynamicArray {
 
  private:
	T *data_ = nullptr;
	std::size_t size_ = 0;
	std::size_t capacity_ = 0;
 
	// INFO: class level asserts will reject immediately if T does not satisfy
	// all of these, even if you NEVER use a func that needs the particular prop
	// Ideally, you put them in funcs where they belong
	static_assert(std::is_default_constructible_v<T>,
	              "DynamicArray requires default-constructible T");
	static_assert(std::is_copy_assignable_v<T>,
	              "DynamicArray requires copy-assignable T");
	static_assert(std::is_move_assignable_v<T>,
	              "DynamicArray requires move-assignable T");
	static_assert(std::is_destructible_v<T>,
	              "DynamicArray requires destructible T");
 
  public:
	DynamicArray(std::initializer_list<T> elems)
	    : size_(elems.size()), capacity_(2 * size_ + 1) {
		reserve(capacity_);
		for (const T &elem : elems) {
			push_back(elem);
		}
	}
 
	DynamicArray() = default;
 
	~DynamicArray() { delete[] data_; }
 
	std::size_t capacity() { return capacity_; }
	std::size_t size() { return size_; }
 
	T &operator[](std::size_t index) { return data_[index]; }
	const T &operator[](const std::size_t index) const { return data_[index]; }
 
	void reserve(std::size_t new_capacity) {
		if (new_capacity <= capacity_)
			return;
 
		T *new_data = new T[new_capacity];
		for (std::size_t i = 0; i < size_; i++) {
			new_data[i] = std::move(data_[i]);
		}
 
		delete[] data_; // noop in case this is nullptr
 
		data_ = new_data;
		capacity_ = new_capacity;
	}
 
	void resize(std::size_t new_size) {
		if (new_size > capacity_) {
			reserve(new_size);
		}
		size_ = new_size;
	}
 
	void push_back(const T &elem) {
		if (size_ == capacity_) {
			reserve(2 * capacity_ + 1);
		}
 
		data_[size_++] = elem;
	}
 
	T &back() { return data_[size_ - 1]; }
 
	const T &back() const { return data_[size_ - 1]; }
 
	void pop_back() { size_--; }
};
 
/*
 * WARN: WHAT ASSUMPTIONS DO WE HAVE ON T HERE?
 * - for doing new T[size_] it must be DEFAULT constructible
 * - for ownership transfer in reserve, moveable
 * - for delete => has destructor
 * - for push_back, copy assignable
 */

C++ (second implementation)

#include <cstddef>
#include <memory>
 
template <typename T> class DynamicArray {
  private:
	std::allocator<T> alloc_;
	T *data_ = nullptr;
	std::size_t size_ = 0;
	std::size_t capacity_ = 0;
 
  public:
	DynamicArray() = default;
 
	// INFO: you destroy size_ and dealloc capacity_
 
	~DynamicArray() {
		clear(); // call all dtors on elems
		if (data_) {
			alloc_.deallocate(data_, capacity_);
		}
	}
 
	// skip back, and operator[]
	// and size() and capacity()
 
	void clear() {
		for (std::size_t i = 0; i < size_; i++) {
			std::destroy_at(data_ + i);
		}
		// keep the capacity
		size_ = 0;
	}
 
	void reserve(std::size_t new_capacity) {
		if (capacity_ >= new_capacity)
			return;
 
		T *new_data = alloc_.allocate(new_capacity);
 
		for (std::size_t i = 0; i < size_; i++) {
			std::construct_at(new_data + i, std::move(data_[i]));
			std::destroy_at(data_ + i);
		}
 
		// INFO: you can have allocated memory with no size, those are
		// separate now
		if (data_) {
			alloc_.deallocate(data_, capacity_);
		}
 
		data_ = new_data;
		capacity_ = new_capacity;
	}
 
	// INFO: you would also want a move based push bac
	void push_back(const T &elem) {
		if (size_ == capacity_) {
			reserve(2 * capacity_ + 1);
		}
 
		std::construct_at(data_ + size_++, elem); // in move you'll move this
	}
 
	void pop_back() { std::destroy_at(data_ + --size_); }
 
	void resize(std::size_t new_size) {
		// previously for any size less than capacity we just set it as the
		// new size
 
		// with this you NEED to destroy
 
		if (new_size < size_) {
			// WARN:looks hamrless but this can unerflow FOREVER when i which
			// is unsigned reaches 0 and now becoes too large
			// for (std::size_t i = size_ - 1; i >= new_size; i--) {
			for (std::size_t i = new_size; i < size_; i++) {
				std::destroy_at(data_ + i);
			}
 
			size_ = new_size;
			return;
		}
 
		// you ALSO need to call ctor after allocating mem if needed
		if (new_size > capacity_) {
			reserve(new_size);
		}
 
		for (std::size_t i = size_; i < new_size; i++) {
			std::construct_at(data_ + i); // default construc
		}
 
		size_ = new_size;
	}
};

Java

import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Objects;
 
// https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/Iterator.html
// https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/lang/Iterable.html
// look at the abstract methods o know what to implement
 
class DynamicArray<T> implements Iterable<T> {
    private Object[] array = new Object[0];
    private int size;
    // an array in java knows it's size so you don't need
    // a capacity
 
    public int size() {
        return size;
    }
 
    public int capacity() {
        return array.length;
    }
 
    @Override
    public Iterator<T> iterator() {
        // magic syntax here is "anonymous class interface"
        // equivalent to
        // private class MyIter implements Iterator<T>
        // and then this body being a return new MyIter()
        //
        // read as - Iterator<T> is an interface you cannot
        // create objects of it
        // this magic syntax is implement on interface and
        // extends on classes
        // ANYTHING you add is an override
        // the brace are very much part of the syntax
        return new Iterator<T>() {
            private int index = 0;
 
            public boolean hasNext() {
                // this would have closure
                return index < size;
            }
 
            public T next() {
                if (!hasNext()) {
                    throw new NoSuchElementException();
                }
 
                return get(index++);
            }
        };
    }
 
    // get and set
    T get(int index) {
        // the array's size ( aka capacity ) is diff from
        // the logical size of the class
        // which is why you need checkIndex
        // it would've still thrown normally if you were out of
        // capacity
        Objects.checkIndex(index, size);
        return (T) array[index];
    }
 
    // this pattern of returning the old value is java's
    // standard list.set behavior
    T set(int index, T val) {
        Objects.checkIndex(index, size);
        T old = (T) array[index];
        array[index] = val;
        return old;
    }
 
    // INFO: JUICE next
    void ensureCapacity(int minCapacity) {
        if (minCapacity <= array.length)
            return;
 
        // following cpp behav here
        // the additional slots are null - you don't need
        // a default constructible object here
        // in java any reference type can be null
        // but same not possible in cpp so you would've done
        // ptrs there ( or force a default constructible impl )
        array = Arrays.copyOf(array, minCapacity);
    }
 
    void resize(int newSize) {
        ensureCapacity(newSize * 2 + 1);
 
        // above is noop if newSize is cap which follow < size
        // need discard existing for gc - this just sets
        // newSize (inc) to size (ex) to null
        if (newSize < size) {
            Arrays.fill(array, newSize, size, null);
        }
 
        size = newSize;
    }
 
    // push and pop
    void add(T value) {
        ensureCapacity(2 * size + 1);
        array[size++] = value;
    }
 
    T removeLast() {
        if (size == 0) {
            throw new NoSuchElementException();
        }
 
        T value = (T) array[--size];
        array[size] = null; // for gc
        return value;
    }
}

Notes

c

Essential c api needed

void *malloc(size_t size);
void free(void *_Nullable p);
void *calloc(size_t n, size_t size);
void *realloc(void *_Nullable p, size_t size);
void *reallocarray(void *_Nullable p, size_t n, size_t size);

Why `unsinged char` pointer and not a `void`?

This is because arithemetic is easier on unsiged char*. You cannot do arithemetic with void* and you will NEED to cast it.

Refer: https://stackoverflow.com/questions/3523145/pointer-arithmetic-for-void-pointer-in-c

In practice, this is impl dependent but NOT in standard.

As for why unsigned? C and C++ standard DO NOT define char as signed or unsigned and it’s impl dependent. It only says that signed char is signed and unsigned char is unsigned.

Struct quick guide ( C specific )

Normal struct

struct Array{
    int x
};
 
//home/ init can only be with struct prefix
struct Array a = {.x = 10}

Typedef struct

typedef struct P{
    // ...
} P;
 
// this'll allow both use P directly and use struct P directly

Anon struct

typedef struct{
    int x;
} Array
// this forces you to do
Array a = {.x = 10}
// cannot do struct Array at all

Which ones to use?

I like the anon struct syntax, use that by default.

Conventions

even if type is same, define on separate lines
null vs nullptr

How does free know what to free?

free is meant to be used on memory allocated via malloc. This memory is more than what the raw mem should be as malloc impls also write some metadata with free uses.

Rem

size_t comes from stdlib.h
c does not has function overloading and no default args as well
There is no Array arr{} type zero init in C. You do a Array arr = {0}
In my case doing a Array arr = {.elem_size = sizeof(int)} will zero init the other members but a func is nicer still.
C does not have a nullptr before C23 which is very recent.
pointer to free can be null and it’ll be a noop.
rem calloc as clear allocation.
realloc behavior as malloc and free ( what cases )
memcpy MUST not overlap else it’s a UB. In that case memmove is used.
when using size_t, never check for size < 0 as not possible, it’s unsigned.
you cannot just memcpy into a pointer, you need to malloc on heap to mark it occupied.
use string.h instead of memory.h
intended use ( since get pointers are invalid on realloc ) is to use indexes just like you would do with a vector ( iterators are invalidated )

Pitfalls

I was making a new_array and thinking of return type as void*. That’s wrong as you need an Array*
api naming - prefix with array. So you have all fucntions as array_...
On the new_array, I was trying to make a CONSTRUCTOR type func and have it return an Array*. That’s not a good api since you MUST allocate this small struct ont he heap. You cannot allocate on stack locally and return a pointer as that’s dangling. If you do want that it’ll have to be return type as Array.
API DESIGN - think go like. Functions modify the struct, not create it. So you always have the first arg as Array* for consistency.
API design on set shoult not MALLOC, instead take a pointer. This way you do not have a hidden malloc free contract and pop can’t fail.

memory alloc

cpp

size_t vs std::size_t

They are the same but used std::size_t as more modern needs #include<cstddef>

Challenges with a generic implementation

A type T, may for example string hold internally some different memory. A trivial copy would make it so that both will share the same memory and have possible double free bugs. An ideal realloc performs “move” to transfer ownership but this means you need to iterate and cannot just operate on raw memory.

I had codex benchmark runs, here are the results. C was faster ~3x for trivial types. For large growths, it used by default C used mmap ( mremap ) which does not extend bu asks kernel to remap pages. But since mem was mostly, a forced extenstion extended in place and was faster.

what is new[] ad delete[]

array version of new and delete.

int *arr = new int[10]
delete[] arr

both need to pair exactly.

new = malloc + constructor delete = free + destructor

A note on operator overloading

cpp understands [] as special. You can also call obj.operator[](index) as the direct explicit form.

On the need of two T& and const T&

If you write const DynamicArra<int> c then you cannot use c[index] as cannot call non const function from a const object.

allocating mem

malloc and std::malloc are same, use the later. None call constructor.
::operator new(100) is raw bytes but throws std::bad_alloc and needs to be freed via operator delete. C++ idiomatic way to allocate raw mem. Fixes some alignment related UBs.
new and delete ⇒ above + calls ctor and dtor
operator is used with placement new so once you alloc bytes and do a static_cast to the type then to call constructo use new (pointer_va) T(args...). This just creates a real object at that memory

initializer list or inside body

class X{
    Foo f;
 
    X() : f(10);
 
    vs X(){
        f = Foo(10);
    }
}

the first one would just call Foo(10) but the other one would have the Foo f default constructed and then later in body have it assigned.

std::allocator api

std::allocator<T> alloc
 
T* p = alloc.allocate(n); // n T objects allocated, 0 constructed
 
// ctor and dtor
std::construct_at(p+index, args...)
std::destroy_at(p+index)
 
// dealloc
alloc.deallocate(p,n)

destroy does not dealloc on it’s own.

Rem

init T* array to be nullptr so that delete is say. Else it would delete operate on random stuff in mem
std::nullptr and nullptr are same, use the later one.
rem to make the const one as a const function
move is in utility
you can’t mix allocator api and say using delete[] inside of dtor. apis must match.
if you’re moving a const, it’s a silent copy

java

Lang

no private scope, default it package private ( like go )
java apparently does NOT use prefixes for naming privates
an array in java is an object reference and is default constructed to be null

A note on java inits

a “field” get’s default init first
super gets called
field inits are run ( so inline object = so and so )
constructor body runs

In cpp, it’s like

1. Base classes constructed
2. Member fields initialized
   - using constructor initializer list if provided
   - otherwise using default **member initializer** ( aka "field initializer" )
   - otherwise default-initialized
3. Constructor body runs

Lest I Forget

Dynamic Array

Implementations

C

C++

C++ (second implementation)

Java

Notes

c

Essential c api needed

Why `unsinged char` pointer and not a `void`?

Struct quick guide ( C specific )

Normal struct

Typedef struct

Anon struct

Which ones to use?

Conventions

How does free know what to free?

Rem

Pitfalls

cpp

size_t vs std::size_t

Challenges with a generic implementation

what is new[] ad delete[]

A note on operator overloading

On the need of two T& and const T&

allocating mem

initializer list or inside body

std::allocator api

Rem

java

Lang

A note on java inits

Lest I Forget

Dynamic Array

Implementations

C

C++

C++ (second implementation)

Java

Notes

c

Essential c api needed

Why unsinged char* pointer and not a void*?

Struct quick guide ( C specific )

Normal struct

Typedef struct

Anon struct

Which ones to use?

Conventions

How does free know what to free?

Rem

Pitfalls

cpp

size_t vs std::size_t

Challenges with a generic implementation

what is new[] ad delete[]

A note on operator overloading

On the need of two T& and const T&

allocating mem

initializer list or inside body

std::allocator api

Rem

java

Lang

A note on java inits

Why `unsinged char` pointer and not a `void`?