Implementations
C++
#include <cstddef>
#include <memory>
template <typename T> class ArrayDeque {
private:
std::allocator<T> alloc_;
T *array_ = nullptr;
std::size_t start_ = 0;
// WARN: end_ is not needed and you CANNOT do it without a size_
// end can be computed from size but not the other way around
std::size_t size_ = 0;
std::size_t capacity_ = 0;
// INFO: normalise to 0 whenever you grow
void ensure_capacity_(std::size_t min_capacity) {
if (capacity_ >= min_capacity)
return;
T *new_array = alloc_.allocate(min_capacity);
for (std::size_t i = 0; i < size_; i++) {
std::size_t old_i = (start_ + i) % capacity_;
std::construct_at(new_array + i, std::move(array_[old_i]));
std::destroy_at(array_ + old_i);
}
if (array_) {
alloc_.deallocate(array_, capacity_);
}
array_ = new_array;
capacity_ = min_capacity;
start_ = 0;
}
inline std::size_t end_() {
// WARN: rem this div by 0 guard
if (!capacity_)
return 0;
return (start_ + size_) % capacity_;
}
public:
ArrayDeque() = default;
~ArrayDeque() {
clear();
if (array_) {
alloc_.deallocate(array_, capacity_);
}
};
// delete copy ctor
ArrayDeque(const ArrayDeque &) = delete;
// and copy assignment ctor
// INFO: this is to avoid assingment and then double frees
ArrayDeque &operator=(const ArrayDeque &) = delete;
// INFO: also note that you don't need to specify var name when deleting
// though you CAN specify. You can do this in GENERAL for funcs actually
//
// INFO: deleting these also deleted impl move ctors ( even defining
// would've done so )
// call dtors on all elems
void clear() {
for (std::size_t i = 0; i < size_; i++) {
std::size_t at = (start_ + i) % capacity_;
std::destroy_at(array_ + at);
}
start_ = size_ = 0;
}
// push and pop - copy ctors
void push_back(const T &elem) {
if (size_ == capacity_)
ensure_capacity_(2 * capacity_ + 1);
std::construct_at(array_ + end_(), elem);
size_++;
}
void pop_back() {
// assumes size > 0
std::size_t last = (start_ + size_ - 1) % capacity_;
std::destroy_at(array_ + last);
size_--;
}
void push_front(const T &elem) {
if (size_ == capacity_)
ensure_capacity_(2 * capacity_ + 1);
start_ = (start_ - 1 + capacity_) % capacity_;
std::construct_at(array_ + start_, elem);
size_++;
}
void pop_front() {
std::destroy_at(array_ + start_);
start_ = (start_ + 1) % capacity_;
size_--;
}
// front, back is similer
T &front() { return array_[start_]; }
const T &front() const { return array_[start_]; }
};Java
import java.util.Iterator;
import java.util.NoSuchElementException;
final class ArrayDeque<T> implements Iterable<T> {
private Object[] array;
private int start;
private int size;
private int capacity;
// no need to specify a ctor or dtor
public int size() {
return size;
}
private void ensureCapacity(int minCapacity) {
if (capacity >= minCapacity)
return;
var new_array = new Object[minCapacity];
for (int i = 0; i < size; i++) {
int old_i = (start + i) % capacity;
new_array[i] = array[old_i];
// INFO: you don't need array[i] = null, that'll be handledby gc
}
array = new_array;
capacity = minCapacity;
start = 0;
}
// push and pop
public void pushBack(T val) {
if (size == capacity)
ensureCapacity(2 * capacity + 1);
int at = (start + size) % capacity;
array[at] = val;
size++;
}
public T popBack() {
int end = (start + size - 1) % capacity;
T val = (T) array[end];
array[end] = null; // INFO: you NEED it, case where rv is discarded
size--;
return val;
}
public void pushFront(T val) {
if (size == capacity)
ensureCapacity(2 * capacity + 1);
start = (start - 1 + capacity) % capacity;
array[start] = val; // NOTE: no need opf cast here as Object is higher type
size++;
}
// INFO: this is what you do to ignore warnings - very much needed in code
// but since it's the same everywhere I skip
@SuppressWarnings("unchecked")
public T popFront() {
T val = (T) array[start];
array[start] = null; // mark for deletion
size--;
start = (start + 1) % capacity;
return val;
}
// front and back are trivial
@Override
public Iterator<T> iterator() {
return new Iterator<>() {
private int index = 0;
@Override
public boolean hasNext() {
return index < size;
}
@Override
public T next() {
if (!hasNext())
throw new NoSuchElementException();
// WARN: don't forget to index++
int at = (start + index++) % capacity;
return (T) array[at];
}
};
}
}Notes
cpp
- it’s just resizable array + a start pointer
- you NEED capacity handling ( not expose though ) to allow for deque amortised complexities of O(1)s
- an std::move by itself does not do anything except casting
- don’t do a = construct_at(a,…), it’s a redundant op, just construct is fine
IMP
- DO NOT traverse from start to end, instead loop over 0 to size always and then get the logical start and end.
- Remt that array_ + i is the pointer and array_[i] is the actual reference to element. When you destroy/construct u need a pointer, when you move you don’t
The state
- front
- size
- capacity
you DON’t store end
How to think of std::alloc
an alloc_.allocate makes → mem to reserver correctly aligned RAW mem constuct at → turns it into a real object destroy make it a RAW meme again and then dealloc release it.
Rule of 5
if your class owns mem and needs one of
- dtor
- copy ctor, copy assng ctor
- move ctor, move assing ctor
Then think about all 5
lang
- no move but having a copy ctor does a copy on std::move
Rules on ctors
If you declare any copy operation, move operations are not auto-generated. If you declare any move operation, copy operations are deleted unless you declare them yourself. If you declare a destructor, move operations are not auto-generated. Copy constructor and copy assignment are separate. Move constructor and move assignment are separate.
java
- if a is some obj, and a = b ( other obj ) then this makes older a to be eligible for deletion by gc