Skip to content

Instantly share code, notes, and snippets.

@skyzh

skyzh/_Deque_README.md

Last active May 3, 2019 10:19
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save skyzh/2597b532ad191036ae4a6dc785859e5b to your computer and use it in GitHub Desktop.
Save skyzh/2597b532ad191036ae4a6dc785859e5b to your computer and use it in GitHub Desktop.
Download ZIP
Deque for Data Structure homework
Raw
_Deque_README.md

Deque

LinkedList implementation

https://gist.github.com/SkyZH/2597b532ad191036ae4a6dc785859e5b#file-deque_sqrt_vector-cpp

O(n) access, O(1) insert & remove

RingBuffer implementation

https://gist.github.com/SkyZH/2597b532ad191036ae4a6dc785859e5b/#file-deque_ring_buffer-cpp

O(1) access, O(n) insert & remove

Sqrt Vector implementation (Accepted answer)

https://gist.github.com/SkyZH/2597b532ad191036ae4a6dc785859e5b/#file-deque_sqrt_vector-cpp

O(sqrt(n)) access, O(sqrt(n)) insert & remove

Chunk Vector implementation

https://gist.github.com/SkyZH/2597b532ad191036ae4a6dc785859e5b/#file-deque_vector_chunk-cpp

O(n/chunk_size) access, O(n) insert & move

Raw
deque_accepted_sqrt_vector_without_cache.hpp
#ifndef SJTU_DEQUE_HPP
#define SJTU_DEQUE_HPP
#include "exceptions.hpp"
#include "utility.hpp"
#include <cstddef>
#include <memory>
#include <vector>
#include <iostream>
namespace sjtu {
template<class T>
class deque {
private:
static const int INSERT_GC_THRESHOLD = 10000;
static const int REMOVE_GC_THRESHOLD = 10000;
template<class U>
class Vector {
static const int min_chunk_size = 512;
friend deque;
U *buffer;
int _size, _cap;
std::allocator<U> alloc;
bool full() { return _size == _cap; }
static int fit(int min_cap) {
int s = min_chunk_size;
while (s < min_cap) s <<= 1;
return s;
}
void expand_to(int new_cap) {
U *new_buffer = alloc.allocate(new_cap);
memcpy(new_buffer, buffer, sizeof(U) * _size);
alloc.deallocate(buffer, _cap);
_cap = new_cap;
buffer = new_buffer;
}
void shrink_if_small() {
if (_cap >= (min_chunk_size << 2) && (_size << 2) < _cap) expand_to(_cap >> 2);
}
void expand_if_full() {
if (!full()) return;
expand_to(_cap << 1);
}
U *get_buffer() {
return buffer;
}
public:
Vector(int cap = min_chunk_size) : _size(0), _cap(cap) {
buffer = alloc.allocate(_cap);
}
Vector(const Vector &that) : _size(that._size), _cap(that._cap) {
buffer = alloc.allocate(_cap);
for (int i = 0; i < that._size; i++) alloc.construct(buffer + i, that[i]);
}
Vector &operator=(const Vector &that) {
if (this == &that) return *this;
for (int i = 0; i < _size; i++) alloc.destroy(buffer + i);
alloc.deallocate(buffer, _cap);
_cap = that._cap;
_size = that._size;
buffer = alloc.allocate(_cap);
for (int i = 0; i < that._size; i++) alloc.construct(buffer + i, that[i]);
return *this;
}
int size() const { return _size; }
void insert(int pos, const U &x) {
expand_if_full();
if (pos != _size) memmove(buffer + pos + 1, buffer + pos, (_size - pos) * sizeof(U));
alloc.construct(buffer + pos, x);
++_size;
}
void erase(int pos) {
alloc.destroy(buffer + pos);
if (pos != _size - 1) memmove(buffer + pos, buffer + pos + 1, (_size - pos - 1) * sizeof(U));
--_size;
shrink_if_small();
}
void clear() {
for (int i = 0; i < _size; i++) alloc.destroy(buffer + i);
_size = 0;
}
~Vector() {
for (int i = 0; i < _size; i++) alloc.destroy(buffer + i);
alloc.deallocate(buffer, _cap);
}
U &operator[](int pos) { return buffer[pos]; }
const U &operator[](int pos) const { return buffer[pos]; }
};
int _size;
Vector<Vector<T> > x;
private:
template<typename Tx, typename Tq>
class base_iterator {
protected:
friend deque;
Tq *q;
mutable Tx *elem;
int pos;
base_iterator(Tq *q, const int &pos) : q(q), pos(pos), elem(NULL) {}
bool owns(Tq *q) const { return q == this->q; }
void check_owns(Tq *q) const { if (!owns(q)) throw invalid_iterator(); }
template<typename _This>
static _This &valid(_This *self) {
if (!self->q) throw invalid_iterator();
self->q->throw_if_out_of_bound(self->pos, true);
return *self;
}
base_iterator &construct() {
elem = nullptr;
return valid<base_iterator>(this);
}
const base_iterator &construct() const {
elem = nullptr;
return valid<const base_iterator>(this);
}
public:
base_iterator(const base_iterator &that) = default;
base_iterator() : base_iterator(nullptr, 0) {}
/**
* return a new iterator which pointer n-next elements
* even if there are not enough elements, the behaviour is **undefined**.
* as well as operator-
*/
base_iterator operator+(const int &n) const { return base_iterator(q, pos + n).construct(); }
base_iterator operator-(const int &n) const { return base_iterator(q, pos - n).construct(); }
// return th distance between two iterator,
// if these two iterators points to different vectors, throw invaild_iterator.
int operator-(const base_iterator &rhs) const {
construct();
check_owns(rhs.q);
return pos - rhs.pos;
}
base_iterator &operator+=(const int &n) { return *this = base_iterator(q, pos + n).construct(); }
base_iterator &operator-=(const int &n) { return *this = base_iterator(q, pos - n).construct(); }
base_iterator operator++(int) {
auto _ = *this;
++(*this);
return _;
}
base_iterator &operator++() {
++pos;
return construct();
}
base_iterator operator--(int) {
auto _ = *this;
--(*this);
return _;
}
base_iterator &operator--() {
--pos;
return construct();
}
Tx &operator*() const {
if (!elem) elem = &q->access(pos);
return *elem;
}
Tx *operator->() const noexcept {
if (!elem) elem = &q->access(pos);
return elem;
}
bool operator==(const base_iterator &rhs) const { return rhs.q == q && rhs.pos == pos; }
bool operator!=(const base_iterator &rhs) const { return !(*this == rhs); }
};
private:
void init() {
_size = 0;
x.insert(0, Vector<T>());
}
void throw_if_out_of_bound(int pos, bool include_end = false) const {
if (include_end && pos == size()) return;
if (pos < 0 || pos >= size()) throw index_out_of_bound();
}
template<typename _This, typename Tx>
static Tx &access(_This *self, int pos) {
self->throw_if_out_of_bound(pos);
int _pos = pos;
int i = self->find_at(pos);
return self->x[i][pos];
}
T &access(int pos) { return access<deque, T>(this, pos); }
const T &access(int pos) const { return access<const deque, const T>(this, pos); }
void split_chunk(int chunk) {
int split_size = x[chunk].size() >> 1;
x.insert(chunk, Vector<T>(Vector<T>::fit(x[chunk]._size)));
auto &chk_a = x[chunk];
auto &chk_b = x[chunk + 1];
memcpy(chk_a.buffer, chk_b.buffer, sizeof(T) * split_size);
chk_a._size = split_size;
memmove(chk_b.buffer, chk_b.buffer + split_size, sizeof(T) * (chk_b._size - split_size));
chk_b._size -= split_size;
}
void merge_chunk(int chunk) {
auto &chk_a = x[chunk];
auto &chk_b = x[chunk + 1];
chk_a.expand_to(Vector<T>::fit(chk_a._size + chk_b._size));
memcpy(chk_a.buffer + chk_a._size, chk_b.buffer, sizeof(T) * chk_b._size);
chk_a._size += chk_b._size;
chk_b._size = 0;
x.erase(chunk + 1);
}
bool should_split(int total_size) { return total_size >= 16 && total_size * total_size > _size * 8; }
bool should_merge(int total_size) { return total_size * total_size * 64 <= _size; }
int find_at(int &pos) const {
int i = 0, _pos = pos, tmp;
if (_pos <= _size >> 1) {
while (_pos >= (tmp = x[i]._size)) {
if (tmp == 0) {
++i;
continue;
}
_pos -= tmp;
++i;
}
} else {
i = x._size - 1;
_pos = _size - _pos;
while (_pos > (tmp = x[i]._size)) {
if (tmp == 0) {
--i;
continue;
}
_pos -= tmp;
--i;
}
_pos = x[i]._size - _pos;
}
pos = _pos;
return i;
}
int find_at_allow_end(int &pos) const {
int i = 0, _pos = pos, tmp;
if (_pos <= _size >> 1) {
while (_pos > (tmp = x[i].size())) {
_pos -= tmp;
++i;
}
} else {
i = x.size() - 1;
_pos = _size - _pos;
while (i != 0 && _pos >= (tmp = x[i].size())) {
_pos -= tmp;
--i;
}
_pos = x[i].size() - _pos;
}
pos = _pos;
return i;
}
int insert_at(int pos, const T &value) {
throw_if_out_of_bound(pos, true);
int __pos = pos;
int i = find_at_allow_end(pos);
x[i].insert(pos, value);
++_size;
if (should_split(x[i].size())) split_chunk(i);
if (rand() < INSERT_GC_THRESHOLD) gc();
return __pos;
}
public:
void gc() {
clear_zero();
for (int i = 0; i < x.size(); i++) {
if (should_split(x[i].size())) {
split_chunk(i);
++i;
}
}
for (int i = 0; i < x.size() - 1; i++) {
if (should_merge(x[i].size() + x[i + 1].size())) {
merge_chunk(i);
--i;
}
}
}
private:
void clear_zero() {
if (x.size() <= 1) return;
for (int i = 0; i < x.size() - 1; i++) {
if (x[i].size() == 0) {
x.erase(i);
}
}
}
int remove_at(int pos) {
throw_if_out_of_bound(pos);
int __pos = pos;
int i = find_at(pos);
x[i].erase(pos);
--_size;
if (i != x.size() - 1) {
if (should_merge(x[i].size() + x[i + 1].size())) merge_chunk(i);
} else {
if (x.size() > 1 && x[i].size() == 0) x.erase(i);
}
if (rand() < REMOVE_GC_THRESHOLD) gc();
return __pos;
}
public:
typedef base_iterator<T, deque> iterator;
typedef base_iterator<const T, const deque> const_iterator;
/**
* Constructors
*/
deque() {
_size = 0;
init();
}
/**
* Deconstructor
*/
~deque() {}
/**
* access specified element with bounds checking
* throw index_out_of_bound if out of bound.
*/
T &at(const size_t &pos) { return access(pos); }
const T &at(const size_t &pos) const { return access(pos); }
T &operator[](const size_t &pos) { return access(pos); }
const T &operator[](const size_t &pos) const { return access(pos); }
/**
* access the first element
* throw container_is_empty when the container is empty.
*/
const T &front() const { return access(0); }
/**
* access the last element
* throw container_is_empty when the container is empty.
*/
const T &back() const { return access(size() - 1); }
/**
* returns an iterator to the beginning.
*/
iterator begin() { return iterator(this, 0); }
const_iterator cbegin() const { return const_iterator(this, 0); }
/**
* returns an iterator to the end.
*/
iterator end() { return iterator(this, size()); }
const_iterator cend() const { return const_iterator(this, size()); }
/**
* checks whether the container is empty.
*/
bool empty() const { return _size == 0; }
/**
* returns the number of elements
*/
size_t size() const { return _size; }
/**
* clears the contents
*/
void clear() {
x.clear();
init();
}
/**
* inserts elements at the specified locat on in the container.
* inserts value before pos
* returns an iterator pointing to the inserted value
* throw if the iterator is invalid or it point to a wrong place.
*/
iterator insert(iterator pos, const T &value) {
pos.check_owns(this);
return iterator(this, insert_at(pos.pos, value));
}
/**
* removes specified element at pos.
* removes the element at pos.
* returns an iterator pointing to the following element, if pos pointing to the last element, end() will be returned.
* throw if the container is empty, the iterator is invalid or it points to a wrong place.
*/
iterator erase(iterator pos) {
pos.check_owns(this);
return iterator(this, remove_at(pos.pos));
}
/**
* adds an element to the end
*/
void push_back(const T &value) { insert_at(size(), value); }
/**
* removes the last element
* throw when the container is empty.
*/
void pop_back() { remove_at(size() - 1); }
/**
* inserts an element to the beginning.
*/
void push_front(const T &value) { insert_at(0, value); }
/**
* removes the first element.
* throw when the container is empty.
*/
void pop_front() { remove_at(0); }
void debug() const {
std::cerr << _size << "(" << x.size() << "): ";
for (int i = 0; i < x.size(); i++) std::cerr << x[i].size() << "/" << x[i]._cap << " ";
std::cerr << "\n";
}
};
}
#endif
Raw
deque_fenwick_tree_vector.hpp
#ifndef SJTU_DEQUE_HPP
#define SJTU_DEQUE_HPP
#include "exceptions.hpp"
#include "utility.hpp"
#include <cstddef>
#include <memory>
#include <vector>
#include <iostream>
#define LSB(i) ((i) & -(i))
namespace sjtu {
template<class T>
class deque {
private:
static const int INSERT_GC_THRESHOLD = 10000;
static const int REMOVE_GC_THRESHOLD = 10000;
template<class U>
class Vector {
static const int min_chunk_size = 512;
friend deque;
U *buffer;
int _size, _cap;
std::allocator<U> alloc;
bool full() { return _size == _cap; }
static int fit(int min_cap) {
int s = min_chunk_size;
while (s < min_cap) s <<= 1;
return s;
}
void expand_to(int new_cap) {
U *new_buffer = alloc.allocate(new_cap);
memcpy(new_buffer, buffer, sizeof(U) * _size);
alloc.deallocate(buffer, _cap);
_cap = new_cap;
buffer = new_buffer;
}
void shrink_if_small() {
if (_cap >= (min_chunk_size << 2) && (_size << 2) < _cap) expand_to(_cap >> 2);
}
void expand_if_full() {
if (!full()) return;
expand_to(_cap << 1);
}
U *get_buffer() {
return buffer;
}
public:
Vector(int cap = min_chunk_size) : _size(0), _cap(cap) {
buffer = alloc.allocate(_cap);
}
Vector(const Vector &that) : _size(that._size), _cap(that._cap) {
buffer = alloc.allocate(_cap);
for (int i = 0; i < that._size; i++) alloc.construct(buffer + i, that[i]);
}
Vector &operator=(const Vector &that) {
if (this == &that) return *this;
for (int i = 0; i < _size; i++) alloc.destroy(buffer + i);
alloc.deallocate(buffer, _cap);
_cap = that._cap;
_size = that._size;
buffer = alloc.allocate(_cap);
for (int i = 0; i < that._size; i++) alloc.construct(buffer + i, that[i]);
return *this;
}
int size() const { return _size; }
void insert(int pos, const U &x) {
expand_if_full();
if (pos != _size) memmove(buffer + pos + 1, buffer + pos, (_size - pos) * sizeof(U));
alloc.construct(buffer + pos, x);
++_size;
}
void erase(int pos) {
alloc.destroy(buffer + pos);
if (pos != _size - 1) memmove(buffer + pos, buffer + pos + 1, (_size - pos - 1) * sizeof(U));
--_size;
shrink_if_small();
}
void clear() {
for (int i = 0; i < _size; i++) alloc.destroy(buffer + i);
_size = 0;
}
~Vector() {
for (int i = 0; i < _size; i++) alloc.destroy(buffer + i);
alloc.deallocate(buffer, _cap);
}
U &operator[](int pos) { return buffer[pos]; }
const U &operator[](int pos) const { return buffer[pos]; }
};
int _size;
Vector< Vector<T> > x;
private:
template<typename Tx, typename Tq>
class base_iterator {
protected:
friend deque;
Tq *q;
mutable Tx *elem;
int pos;
base_iterator(Tq *q, const int &pos) : q(q), pos(pos), elem(NULL) {}
bool owns(Tq *q) const { return q == this->q; }
void check_owns(Tq *q) const { if (!owns(q)) throw invalid_iterator(); }
template<typename _This>
static _This &valid(_This *self) {
if (!self->q) throw invalid_iterator();
self->q->throw_if_out_of_bound(self->pos, true);
return *self;
}
base_iterator &construct() {
elem = nullptr;
return valid<base_iterator>(this);
}
const base_iterator &construct() const {
elem = nullptr;
return valid<const base_iterator>(this);
}
public:
base_iterator(const base_iterator &that) = default;
base_iterator() : base_iterator(nullptr, 0) {}
/**
* return a new iterator which pointer n-next elements
* even if there are not enough elements, the behaviour is **undefined**.
* as well as operator-
*/
base_iterator operator+(const int &n) const { return base_iterator(q, pos + n).construct(); }
base_iterator operator-(const int &n) const { return base_iterator(q, pos - n).construct(); }
// return th distance between two iterator,
// if these two iterators points to different vectors, throw invaild_iterator.
int operator-(const base_iterator &rhs) const {
construct();
check_owns(rhs.q);
return pos - rhs.pos;
}
base_iterator &operator+=(const int &n) { return *this = base_iterator(q, pos + n).construct(); }
base_iterator &operator-=(const int &n) { return *this = base_iterator(q, pos - n).construct(); }
base_iterator operator++(int) {
auto _ = *this;
++(*this);
return _;
}
base_iterator &operator++() {
++pos;
return construct();
}
base_iterator operator--(int) {
auto _ = *this;
--(*this);
return _;
}
base_iterator &operator--() {
--pos;
return construct();
}
Tx &operator*() const {
if (!elem) elem = &q->access(pos);
return *elem;
}
Tx *operator->() const noexcept {
if (!elem) elem = &q->access(pos);
return elem;
}
bool operator==(const base_iterator &rhs) const { return rhs.q == q && rhs.pos == pos; }
bool operator!=(const base_iterator &rhs) const { return !(*this == rhs); }
};
public:
class Cache {
public:
const static int MAX_CACHE_SIZE = 4096;
unsigned int A[MAX_CACHE_SIZE];
int sum(int i) const {
++i;
int sum = 0;
while (i > 0) {
sum += A[i];
i -= LSB(i);
}
return sum;
}
void add(int i, int k, int _size) {
++i;
while (i < MAX_CACHE_SIZE) {
A[i] += k;
i += LSB(i);
}
}
void rebuild(const deque& q) {
memset(A, 0, sizeof A);
int __size = q.x.size();
for (int i = 0; i < __size; i++) {
add(i, q.x[i].size(), __size);
}
}
void debug(int n) const {
for (int i = 0; i < n; i++) {
std::cerr << this->sum(i) << " ";
}
std::cerr << std::endl;
}
Cache() {
memset(A, 0, sizeof A);
}
} map_cache;
private:
void init() {
_size = 0;
x.insert(0, Vector<T>());
}
void throw_if_out_of_bound(int pos, bool include_end = false) const {
if (include_end && pos == size()) return;
if (pos < 0 || pos >= size()) throw index_out_of_bound();
}
template<typename _This, typename Tx>
static Tx &access(_This *self, int pos) {
self->throw_if_out_of_bound(pos);
int _pos = pos;
int i = self->find_at(pos);
return self->x[i][pos];
}
T &access(int pos) { return access<deque, T>(this, pos); }
const T &access(int pos) const { return access<const deque, const T>(this, pos); }
void split_chunk(int chunk) {
int split_size = x[chunk].size() >> 1;
x.insert(chunk, Vector<T>(Vector<T>::fit(x[chunk]._size)));
auto &chk_a = x[chunk];
auto &chk_b = x[chunk + 1];
memcpy(chk_a.buffer, chk_b.buffer, sizeof(T) * split_size);
chk_a._size = split_size;
memmove(chk_b.buffer, chk_b.buffer + split_size, sizeof(T) * (chk_b._size - split_size));
chk_b._size -= split_size;
}
void merge_chunk(int chunk) {
auto &chk_a = x[chunk];
auto &chk_b = x[chunk + 1];
chk_a.expand_to(Vector<T>::fit(chk_a._size + chk_b._size));
memcpy(chk_a.buffer + chk_a._size, chk_b.buffer, sizeof(T) * chk_b._size);
chk_a._size += chk_b._size;
chk_b._size = 0;
x.erase(chunk + 1);
}
bool should_split(int total_size) { return total_size >= 16 && total_size * total_size > _size * 8; }
bool should_merge(int total_size) { return total_size * total_size * 64 <= _size; }
int find_at(int &pos) const {
if (pos == 0) return 0;
if (pos >= _size - 1) {
pos = x[x.size() - 1].size() + pos - _size;
return x.size() - 1;
}
int L = 0, R = x.size();
int M = 0;
while (L < R) {
M = (L + R) >> 1;
if (map_cache.sum(M - 1) <= pos) {
L = M + 1;
} else {
R = M;
}
}
--L;
pos -= map_cache.sum(L - 1);
return L;
}
int find_at_allow_end(int &pos) const {
if (pos == 0) return 0;
if (pos >= _size - 1) {
pos = x[x.size() - 1].size() + pos - _size;
return x.size() - 1;
}
int L = 0, R = x.size();
int M = 0;
while (L < R) {
M = (L + R) >> 1;
if (map_cache.sum(M - 1) < pos) {
L = M + 1;
} else {
R = M;
}
}
--L;
pos -= map_cache.sum(L - 1);
return L;
}
int insert_at(int pos, const T &value) {
throw_if_out_of_bound(pos, true);
int __pos = pos;
int i = find_at_allow_end(pos);
x[i].insert(pos, value);
map_cache.add(i, 1, x.size() + 1);
++_size;
if (should_split(x[i].size())) {
split_chunk(i);
map_cache.rebuild(*this);
}
if (rand() < INSERT_GC_THRESHOLD) {
gc();
map_cache.rebuild(*this);
}
return __pos;
}
void gc() {
clear_zero();
for (int i = 0; i < x.size(); i++) {
if (should_split(x[i].size())) {
split_chunk(i);
++i;
}
}
for (int i = 0; i < x.size() - 1; i++) {
if (should_merge(x[i].size() + x[i + 1].size())) {
merge_chunk(i);
--i;
}
}
}
void clear_zero() {
if (x.size() <= 1) return;
for (int i = 0; i < x.size() - 1; i++) {
if (x[i].size() == 0) {
x.erase(i);
}
}
}
int remove_at(int pos) {
throw_if_out_of_bound(pos);
int __pos = pos;
int i = find_at(pos);
x[i].erase(pos);
map_cache.add(i, -1, x.size() + 1);
--_size;
if (i != x.size() - 1) {
if (should_merge(x[i].size() + x[i + 1].size())) {
merge_chunk(i);
map_cache.rebuild(*this);
}
}
if (x.size() > 1 && x[i].size() == 0) {
x.erase(i);
map_cache.rebuild(*this);
}
if (rand() < REMOVE_GC_THRESHOLD) {
gc();
map_cache.rebuild(*this);
}
return __pos;
}
public:
typedef base_iterator<T, deque> iterator;
typedef base_iterator<const T, const deque> const_iterator;
/**
* Constructors
*/
deque() {
_size = 0;
init();
}
/**
* Deconstructor
*/
~deque() {}
/**
* access specified element with bounds checking
* throw index_out_of_bound if out of bound.
*/
T &at(const size_t &pos) { return access(pos); }
const T &at(const size_t &pos) const { return access(pos); }
T &operator[](const size_t &pos) { return access(pos); }
const T &operator[](const size_t &pos) const { return access(pos); }
/**
* access the first element
* throw container_is_empty when the container is empty.
*/
const T &front() const { return access(0); }
/**
* access the last element
* throw container_is_empty when the container is empty.
*/
const T &back() const { return access(size() - 1); }
/**
* returns an iterator to the beginning.
*/
iterator begin() { return iterator(this, 0); }
const_iterator cbegin() const { return const_iterator(this, 0); }
/**
* returns an iterator to the end.
*/
iterator end() { return iterator(this, size()); }
const_iterator cend() const { return const_iterator(this, size()); }
/**
* checks whether the container is empty.
*/
bool empty() const { return _size == 0; }
/**
* returns the number of elements
*/
size_t size() const { return _size; }
/**
* clears the contents
*/
void clear() {
x.clear();
init();
}
/**
* inserts elements at the specified locat on in the container.
* inserts value before pos
* returns an iterator pointing to the inserted value
* throw if the iterator is invalid or it point to a wrong place.
*/
iterator insert(iterator pos, const T &value) {
pos.check_owns(this);
return iterator(this, insert_at(pos.pos, value));
}
/**
* removes specified element at pos.
* removes the element at pos.
* returns an iterator pointing to the following element, if pos pointing to the last element, end() will be returned.
* throw if the container is empty, the iterator is invalid or it points to a wrong place.
*/
iterator erase(iterator pos) {
pos.check_owns(this);
return iterator(this, remove_at(pos.pos));
}
/**
* adds an element to the end
*/
void push_back(const T &value) { insert_at(size(), value); }
/**
* removes the last element
* throw when the container is empty.
*/
void pop_back() { remove_at(size() - 1); }
/**
* inserts an element to the beginning.
*/
void push_front(const T &value) { insert_at(0, value); }
/**
* removes the first element.
* throw when the container is empty.
*/
void pop_front() { remove_at(0); }
void debug() const {
std::cerr << _size << "(" << x.size() << "): ";
for (int i = 0; i < x.size(); i++) std::cerr << x[i].size() << "/" << x[i]._cap << " ";
std::cerr << "\n";
}
};
}
#endif
Raw
deque_linkedlist.cpp
#ifndef SJTU_DEQUE_HPP
#define SJTU_DEQUE_HPP
#include "exceptions.hpp"
#include <cstddef>
#include <list>
#include <vector>
#include <iostream>
namespace sjtu {
template<class T>
class deque {
private:
static const int min_chunk_size = 64;
int _size;
struct Node {
Node *prev, *next;
Node(Node *prev = NULL, Node *next = NULL) : prev(prev), next(next) {}
virtual ~Node() {}
} *head, *tail;
struct Chunk {
Node *head, *tail;
int chunk_size;
Chunk *prev, *next;
Chunk(Node *head, Node *tail, int chunk_size = 0, Chunk *prev = NULL, Chunk *next = NULL) :
head(head), tail(tail), chunk_size(chunk_size), prev(prev), next(next) {}
} *chunk_head, *chunk_tail;
struct Wrapper : public Node {
T x;
Wrapper(const T &x, Node *prev = NULL, Node *next = NULL) : Node(prev, next), x(x) {}
};
bool empty_chunk() const { return chunk_head->next == chunk_tail; }
void construct() {
head = new Node;
tail = new Node;
head->next = tail;
tail->prev = head;
chunk_head = new Chunk(head, head, 1);
chunk_tail = new Chunk(tail, tail, 1);
chunk_head->next = chunk_tail;
chunk_tail->prev = chunk_head;
_size = 0;
}
template<typename U>
void _destroy(U *head) {
U *ptr = head;
while (ptr) {
U *tmp = ptr->next;
delete ptr;
ptr = tmp;
}
}
template<typename U>
U *remove_node(U *node) {
node->next->prev = node->prev;
U *tmp = node->prev->next = node->next;
delete node;
return tmp;
}
void destroy() {
_destroy<Node>(head);
_destroy<Chunk>(chunk_head);
_size = 0;
}
void copy_from(const deque &that) {
const Node *that_ptr = that.head->next;
while (that_ptr != that.tail) {
const Wrapper *that_wrapper = dynamic_cast<const Wrapper *>(that_ptr);
push_back(that_wrapper->x);
that_ptr = that_ptr->next;
}
_size = that._size;
}
void throw_if_empty() const {
if (empty()) throw container_is_empty();
}
template<typename T_x, typename T_Node, typename T_Wrapper, typename T_Chunk>
class base_iterator {
protected:
friend deque;
const deque *q;
T_Chunk *chunk;
T_Node *node;
base_iterator(const deque *q, T_Chunk *chunk, T_Node *node) : q(q), chunk(chunk), node(node) {}
int distance_to_head() const {
T_Node *ptr = node;
T_Chunk *chk = chunk;
int d = 0;
while (ptr != q->head) {
if (ptr == chk->head) {
chk = chk->prev;
d += chk->chunk_size;
ptr = chk->head;
} else {
ptr = ptr->prev;
++d;
}
}
return d;
}
inline void move_backward() {
if (node == chunk->head) chunk = chunk->prev;
node = node->prev;
if (node == q->head) throw index_out_of_bound();
}
inline void move_forward() {
if (node == chunk->tail) chunk = chunk->next;
node = node->next;
if (node == NULL) throw index_out_of_bound();
}
public:
/**
* return a new iterator which pointer n-next elements
* even if there are not enough elements, the behaviour is **undefined**.
* as well as operator-
*/
base_iterator operator+(const int &n) const {
base_iterator that(*this);
that += n;
return that;
}
base_iterator operator-(const int &n) const {
return *this + (-n);
}
// return th distance between two iterator,
// if these two iterators points to different vectors, throw invaild_iterator.
int operator-(const base_iterator &rhs) const {
if (rhs.q != this->q) throw invalid_iterator();
return this->distance_to_head() - rhs.distance_to_head();
}
base_iterator &operator+=(const int &n) {
int i = n;
while (i > 0) {
if (node == chunk->head && i >= chunk->chunk_size) {
i -= chunk->chunk_size;
chunk = chunk->next;
if (!chunk) throw index_out_of_bound();
node = chunk->head;
} else {
this->move_forward();
--i;
}
}
while (i < 0) {
if (node == chunk->tail && i >= chunk->chunk_size) {
i -= chunk->chunk_size;
chunk = chunk->prev;
if (chunk == q->chunk_head) throw index_out_of_bound();
node = chunk->tail;
} else {
this->move_backward();
++i;
}
}
return *this;
}
base_iterator &operator-=(const int &n) {
return *this += (-n);
}
/**
* iter++
*/
base_iterator operator++(int) {
base_iterator that(*this);
++*this;
return that;
}
/**
* ++iter
*/
base_iterator &operator++() {
this->move_forward();
return *this;
}
/**
* iter--
*/
base_iterator operator--(int) {
base_iterator that(*this);
--*this;
return that;
}
/**
* --iter
*/
base_iterator &operator--() {
this->move_backward();
return *this;
}
/**
* TODO *it
*/
T_x &operator*() const {
if (node == q->tail) throw index_out_of_bound();
return dynamic_cast<T_Wrapper *>(node)->x;
}
/**
* TODO it->field
*/
T_x *operator->() const noexcept { return &(dynamic_cast<T_Wrapper *>(node)->x); }
/**
* a operator to check whether two iterators are same (pointing to the same memory).
*/
bool operator==(const base_iterator &rhs) const { return q == rhs.q && node == rhs.node; }
/**
* some other operator for iterator.
*/
bool operator!=(const base_iterator &rhs) const { return !(*this == rhs); }
};
typedef base_iterator<T, Node, Wrapper, Chunk> _iterator;
typedef base_iterator<const T, const Node, const Wrapper, const Chunk> _const_iterator;
public:
class const_iterator;
class iterator : public _iterator {
protected:
friend deque;
friend const_iterator;
iterator(const deque *q, Chunk *chunk, Node *node) : _iterator(q, chunk, node) {}
public:
iterator() : iterator(NULL, NULL, NULL) {}
iterator(const _iterator &that) : iterator(that.q, that.chunk, that.node) {}
};
class const_iterator : public _const_iterator {
private:
friend deque;
const_iterator(const deque *q, const Chunk *chunk, const Node *node) : _const_iterator(q, chunk, node) {}
public:
const_iterator() : const_iterator(NULL, NULL, NULL) {}
const_iterator(const iterator &that) : const_iterator(that.q, that.chunk, that.node) {}
const_iterator(const _const_iterator &that) : const_iterator(that.q, that.chunk, that.node) {}
};
private:
Chunk *split_chunk(Chunk *chunk, Node *pos) {
if (should_split(chunk->chunk_size)) {
int split_loc = chunk->chunk_size / 2;
Node *split_node = chunk->head;
bool pos_found_in_left = false;
for (int i = 0; i < split_loc; i++) {
if (split_node == pos) pos_found_in_left = true;
split_node = split_node->next;
}
Chunk *left = new Chunk(chunk->head, split_node->prev, split_loc, chunk->prev);
Chunk *right = new Chunk(split_node, chunk->tail, chunk->chunk_size - left->chunk_size, left,
chunk->next);
left->next = right;
chunk->prev->next = left;
chunk->next->prev = right;
delete chunk;
if (pos_found_in_left) return left; else return right;
} else return chunk;
}
iterator _insert_before(Chunk *chunk, Node *pos, const T &x) {
Node *tmp = new Wrapper(x, pos->prev, pos);
pos->prev->next = tmp;
pos->prev = tmp;
if (empty_chunk()) {
chunk = new Chunk(tmp, tmp, 1, chunk_head, chunk_tail);
chunk_head->next = chunk;
chunk_tail->prev = chunk;
} else {
if (chunk == chunk_tail) {
chunk = chunk->prev;
chunk->tail = tmp;
}
++chunk->chunk_size;
if (pos == chunk->head) chunk->head = tmp;
chunk = split_chunk(chunk, tmp);
}
++_size;
return iterator(this, chunk, tmp);
}
bool should_split(int chunk_size) { return chunk_size >= min_chunk_size && chunk_size * chunk_size > _size; }
Chunk *merge_chunk(Chunk *left) {
if (left->next == chunk_tail) return left;
Chunk *right = left->next;
if (!should_split(left->chunk_size + right->chunk_size)) {
Chunk *chunk = new Chunk(left->head, right->tail, left->chunk_size + right->chunk_size, left->prev,
right->next);
left->prev->next = chunk;
right->next->prev = chunk;
delete left;
delete right;
return chunk;
}
return left;
}
iterator _remove_at(Chunk *chunk, Node *pos) {
if (pos == tail) throw invalid_iterator();
Node *next = remove_node(pos);
if (chunk->head == pos && chunk->tail == pos) {
chunk->prev->next = chunk->next;
chunk->next->prev = chunk->prev;
Chunk *tmp = chunk->next;
delete chunk;
chunk = tmp;
} else if (chunk->head == pos) {
chunk->head = next;
--chunk->chunk_size;
chunk = merge_chunk(chunk);
} else if (chunk->tail == pos) {
chunk->tail = next->prev;
--chunk->chunk_size;
chunk = chunk->next;
} else {
--chunk->chunk_size;
chunk = merge_chunk(chunk);
}
--_size;
return iterator(this, chunk, next);
}
public:
/**
* TODO Constructors
*/
deque() { construct(); }
deque(const deque &other) {
construct();
copy_from(other);
}
/**
* TODO Deconstructor
*/
~deque() { destroy(); }
/**
* TODO assignment operator
*/
deque &operator=(const deque &other) {
if (this == &other) return *this;
destroy();
construct();
copy_from(other);
return *this;
}
/**
* access specified element with bounds checking
* throw index_out_of_bound if out of bound.
*/
T &at(const size_t &pos) { return *(begin() + pos); }
const T &at(const size_t &pos) const { return *(cbegin() + pos); }
T &operator[](const size_t &pos) { return at(pos); }
const T &operator[](const size_t &pos) const { return at(pos); }
/**
* access the first element
* throw container_is_empty when the container is empty.
*/
const T &front() const {
throw_if_empty();
return *(cbegin());
}
/**
* access the last element
* throw container_is_empty when the container is empty.
*/
const T &back() const {
throw_if_empty();
return *(--cend());
}
/**
* returns an iterator to the beginning.
*/
iterator begin() { return iterator(this, chunk_head->next, head->next); }
const_iterator cbegin() const { return const_iterator(this, chunk_head->next, head->next); }
/**
* returns an iterator to the end.
*/
iterator end() { return iterator(this, chunk_tail, tail); }
const_iterator cend() const { return const_iterator(this, chunk_tail, tail); }
/**
* checks whether the container is empty.
*/
bool empty() const { return head->next == tail; }
/**
* returns the number of elements
*/
size_t size() const { return _size; }
/**
* clears the contents
*/
void clear() {
destroy();
construct();
}
/**
* inserts elements at the specified locat on in the container.
* inserts value before pos
* returns an iterator pointing to the inserted value
* throw if the iterator is invalid or it point to a wrong place.
*/
iterator insert(iterator pos, const T &value) {
if (pos.q != this) throw invalid_iterator();
return _insert_before(pos.chunk, pos.node, value);
}
/**
* removes specified element at pos.
* removes the element at pos.
* returns an iterator pointing to the following element, if pos pointing to the last element, end() will be returned.
* throw if the container is empty, the iterator is invalid or it points to a wrong place.
*/
iterator erase(iterator pos) {
throw_if_empty();
if (pos.q != this) throw invalid_iterator();
return _remove_at(pos.chunk, pos.node);
}
/**
* adds an element to the end
*/
void push_back(const T &value) {
_insert_before(chunk_tail, tail, value);
}
/**
* removes the last element
* throw when the container is empty.
*/
void pop_back() {
throw_if_empty();
_remove_at(chunk_tail->prev, tail->prev);
}
/**
* inserts an element to the beginning.
*/
void push_front(const T &value) {
_insert_before(chunk_head->next, head->next, value);
}
/**
* removes the first element.
* throw when the container is empty.
*/
void pop_front() {
throw_if_empty();
_remove_at(chunk_head->next, head->next);
}
void debug() {
Chunk *chunk = chunk_head->next;
int i = 0;
while (chunk != chunk_tail) {
Node *ptr = chunk->head;
std::cout << "chunk " << i++ << "(" << chunk->chunk_size << "): ";
while (ptr->prev != chunk->tail) {
std::cout << dynamic_cast<Wrapper *>(ptr)->x << " ";
ptr = ptr->next;
}
std::cout << std::endl;
chunk = chunk->next;
}
if (empty_chunk()) std::cout << "EMPTY" << std::endl;
std::cout << std::endl;
}
};
}
#endif
Raw
deque_ring_buffer.cpp
#ifndef SJTU_DEQUE_HPP
#define SJTU_DEQUE_HPP
#include "exceptions.hpp"
#include <cstddef>
#include <memory>
#include <cstring>
#include <cstdlib>
namespace sjtu {
template<class T>
class deque {
private:
static const int default_cap = 1024;
T *ring_buffer;
int _front, _rear, cap;
int _size;
std::allocator<T> alloc;
int _real_pos(const int &pos) const {
int pos_b = pos + _front;
int pos_a = pos + _front - cap;
return pos_a >= 0 ? pos_a : pos_b;
}
int _next_pos(int pos) const {
if (pos == cap - 1) return 0; else return pos + 1;
}
int _prev_pos(int pos) const {
if (pos > 0) return pos - 1; else return cap - 1;
}
inline bool wrap() const { return _rear < _front; }
inline bool full() const { return _next_pos(_rear) == _front; }
T &access(const size_t &pos) {
if (pos >= size()) throw index_out_of_bound();
else
return ring_buffer[_real_pos(pos)];
}
const T &access(const size_t &pos) const {
if (pos >= size()) throw index_out_of_bound();
else return ring_buffer[_real_pos(pos)];
}
void expand() {
T *new_buffer = alloc.allocate(cap * 2);
int _size = size();
if (wrap()) {
memcpy(new_buffer, ring_buffer + _front, (cap - _front) * sizeof(T));
memcpy(new_buffer + (cap - _front), ring_buffer, _rear * sizeof(T));
} else {
memcpy(new_buffer, ring_buffer + _front, (_rear - _front) * sizeof(T));
}
alloc.deallocate(ring_buffer, cap);
ring_buffer = new_buffer;
cap *= 2;
_front = 0;
_rear = _size;
}
void throw_if_empty() const { if (empty()) throw container_is_empty(); }
void expand_if_full() { if (full()) expand(); }
inline void mem_replace(T *a, const T *b) {
memcpy(a, b, sizeof(T));
}
void _swap_backward(int from, int target) {
while (from != target) {
int prev = _prev_pos(from);
mem_replace(ring_buffer + from, ring_buffer + prev);
from = prev;
}
}
void swap_backward(int from, int target) {
if (target == from) return;
if (target < from) {
memmove(ring_buffer + target + 1, ring_buffer + target, sizeof(T) * (from - target));
} else {
memmove(ring_buffer + 1, ring_buffer, sizeof(T) * from);
memcpy(ring_buffer, ring_buffer + cap - 1, sizeof(T));
memmove(ring_buffer + target + 1, ring_buffer + target, sizeof(T) * (cap - target - 1));
}
}
void _swap_forward(int from, int target) {
while (from != target) {
int next = _next_pos(from);
mem_replace(ring_buffer + from, ring_buffer + next);
from = next;
}
}
void swap_forward(int from, int target) {
if (target == from) return;
if (target > from) {
memmove(ring_buffer + from, ring_buffer + from + 1, sizeof(T) * (target - from));
} else {
memmove(ring_buffer + from, ring_buffer + from + 1, sizeof(T) * (cap - from - 1));
memcpy(ring_buffer + cap - 1, ring_buffer, sizeof(T));
memmove(ring_buffer, ring_buffer + 1, sizeof(T) * target);
}
}
int insert_before(const int &pos, const T &x) {
if (pos < 0 || pos > size()) throw index_out_of_bound();
expand_if_full();
int target = 0;
if (pos < size() / 2) {
target = _prev_pos(_real_pos(pos));
_front = _prev_pos(_front);
swap_forward(_front, target);
} else {
target = _real_pos(pos);
swap_backward(_rear, target);
_rear = _next_pos(_rear);
}
++_size;
alloc.construct(ring_buffer + target, x);
return pos;
}
int remove_at(const int &pos) {
throw_if_empty();
if (pos < 0 || pos >= size()) throw index_out_of_bound();
int target = _real_pos(pos);
alloc.destroy(ring_buffer + target);
if (pos < size() / 2) {
swap_backward(target, _front);
_front = _next_pos(_front);
} else {
_rear = _prev_pos(_rear);
swap_forward(target, _rear);
}
--_size;
return pos;
}
void construct() {
_front = _rear = _size = 0;
cap = default_cap;
ring_buffer = alloc.allocate(cap);
}
void destroy() {
while (_front != _rear) {
alloc.destroy(ring_buffer + _front);
_front = _next_pos(_front);
}
alloc.deallocate(ring_buffer, cap);
}
void copy_from(const deque &q) {
_front = _rear = _size = 0;
cap = q.cap;
ring_buffer = alloc.allocate(cap);
_size = _rear = q.size();
for (int i = 0; i < q.size(); i++) {
alloc.construct(ring_buffer + i, q[i]);
}
}
private:
template<typename Tx, typename Tq>
class base_iterator {
protected:
friend deque;
Tq *q;
int pos;
base_iterator(Tq *q, const int &pos) : q(q), pos(pos) {
if (!q) return;
if (pos < 0 || pos > q->size()) throw index_out_of_bound();
}
bool owns(Tq *q) const { return q == this->q; }
void check_owns(Tq *q) const { if (!owns(q)) throw invalid_iterator(); }
public:
base_iterator(const base_iterator &that) = default;
base_iterator() : base_iterator(NULL, 0) {}
/**
* return a new iterator which pointer n-next elements
* even if there are not enough elements, the behaviour is **undefined**.
* as well as operator-
*/
base_iterator operator+(const int &n) const { return base_iterator(q, pos + n); }
base_iterator operator-(const int &n) const { return base_iterator(q, pos - n); }
// return th distance between two iterator,
// if these two iterators points to different vectors, throw invaild_iterator.
int operator-(const base_iterator &rhs) const {
check_owns(rhs.q);
return pos - rhs.pos;
}
base_iterator &operator+=(const int &n) { return *this = base_iterator(q, pos + n); }
base_iterator &operator-=(const int &n) { return *this = base_iterator(q, pos - n); }
base_iterator operator++(int) {
auto _ = *this;
++(*this);
return _;
}
base_iterator &operator++() {
++pos;
if (pos < 0 || pos > q->size()) throw index_out_of_bound();
return *this;
}
base_iterator operator--(int) {
auto _ = *this;
--(*this);
return _;
}
base_iterator &operator--() {
--pos;
if (pos < 0 || pos > q->size()) throw index_out_of_bound();
return *this;
}
Tx &operator*() const { if (q) return q->access(pos); else throw invalid_iterator(); }
Tx *operator->() const noexcept { return &(q->access(pos)); }
bool operator==(const base_iterator &rhs) const { return rhs.q == q && rhs.pos == pos; }
bool operator!=(const base_iterator &rhs) const { return !(*this == rhs); }
};
public:
typedef base_iterator<T, deque> iterator;
typedef base_iterator<const T, const deque> const_iterator;
/**
* Constructors
*/
deque() { construct(); }
deque(const deque &other) { copy_from(other); }
/**
* Deconstructor
*/
~deque() { destroy(); }
/**
* assignment operator
*/
deque &operator=(const deque &other) {
if (this == &other) return *this;
destroy();
copy_from(other);
return *this;
}
/**
* access specified element with bounds checking
* throw index_out_of_bound if out of bound.
*/
T &at(const size_t &pos) { return access(pos); }
const T &at(const size_t &pos) const { return access(pos); }
T &operator[](const size_t &pos) { return access(pos); }
const T &operator[](const size_t &pos) const { return access(pos); }
/**
* access the first element
* throw container_is_empty when the container is empty.
*/
const T &front() const { return access(0); }
/**
* access the last element
* throw container_is_empty when the container is empty.
*/
const T &back() const { return access(size() - 1); }
/**
* returns an iterator to the beginning.
*/
iterator begin() { return iterator(this, 0); }
const_iterator cbegin() const { return const_iterator(this, 0); }
/**
* returns an iterator to the end.
*/
iterator end() { return iterator(this, size()); }
const_iterator cend() const { return const_iterator(this, size()); }
/**
* checks whether the container is empty.
*/
bool empty() const { return _front == _rear; }
/**
* returns the number of elements
*/
size_t size() const { return _size; }
/**
* clears the contents
*/
void clear() {
destroy();
construct();
}
/**
* inserts elements at the specified locat on in the container.
* inserts value before pos
* returns an iterator pointing to the inserted value
* throw if the iterator is invalid or it point to a wrong place.
*/
iterator insert(const iterator &pos, const T &value) {
pos.check_owns(this);
return iterator(this, insert_before(pos.pos, value));
}
/**
* removes specified element at pos.
* removes the element at pos.
* returns an iterator pointing to the following element, if pos pointing to the last element, end() will be returned.
* throw if the container is empty, the iterator is invalid or it points to a wrong place.
*/
iterator erase(const iterator &pos) {
pos.check_owns(this);
return iterator(this, remove_at(pos.pos));
}
/**
* adds an element to the end
*/
void push_back(const T &value) {
expand_if_full();
alloc.construct(ring_buffer + _rear, value);
_rear = _next_pos(_rear);
++_size;
}
/**
* removes the last element
* throw when the container is empty.
*/
void pop_back() {
throw_if_empty();
_rear = _prev_pos(_rear);
alloc.destroy(ring_buffer + _rear);
--_size;
}
/**
* inserts an element to the beginning.
*/
void push_front(const T &value) {
expand_if_full();
_front = _prev_pos(_front);
alloc.construct(ring_buffer + _front, value);
++_size;
}
/**
* removes the first element.
* throw when the container is empty.
*/
void pop_front() {
throw_if_empty();
alloc.destroy(ring_buffer + _front);
_front = _next_pos(_front);
--_size;
}
/*
void debug() {
for (int i = _front; i != _rear; i = _next_pos(i)) std::cout << ring_buffer[i] << " ";
std::cout << std::endl;
}
*/
};
}
#endif
Raw
deque_sqrt_vector.cpp
#ifndef SJTU_DEQUE_HPP
#define SJTU_DEQUE_HPP
#include "exceptions.hpp"
#include "utility.hpp"
#include <cstddef>
#include <memory>
#include <vector>
#include <iostream>
namespace sjtu {
template<class T>
class deque {
private:
static const int INSERT_GC_THRESHOLD = 10000;
static const int REMOVE_GC_THRESHOLD = 10000;
template<class U>
class Vector {
static const int min_chunk_size = 512;
friend deque;
U *buffer;
int _size, _cap;
std::allocator<U> alloc;
bool full() { return _size == _cap; }
static int fit(int min_cap) {
int s = min_chunk_size;
while (s < min_cap) s <<= 1;
return s;
}
void expand_to(int new_cap) {
U *new_buffer = alloc.allocate(new_cap);
memcpy(new_buffer, buffer, sizeof(U) * _size);
alloc.deallocate(buffer, _cap);
_cap = new_cap;
buffer = new_buffer;
}
void shrink_if_small() {
if (_cap >= (min_chunk_size << 2) && (_size << 2) < _cap) expand_to(_cap >> 2);
}
void expand_if_full() {
if (!full()) return;
expand_to(_cap << 1);
}
U *get_buffer() {
return buffer;
}
public:
Vector(int cap = min_chunk_size) : _size(0), _cap(cap) {
buffer = alloc.allocate(_cap);
}
Vector(const Vector &that) : _size(that._size), _cap(that._cap) {
buffer = alloc.allocate(_cap);
for (int i = 0; i < that._size; i++) alloc.construct(buffer + i, that[i]);
}
Vector &operator=(const Vector &that) {
if (this == &that) return *this;
for (int i = 0; i < _size; i++) alloc.destroy(buffer + i);
alloc.deallocate(buffer, _cap);
_cap = that._cap;
_size = that._size;
buffer = alloc.allocate(_cap);
for (int i = 0; i < that._size; i++) alloc.construct(buffer + i, that[i]);
return *this;
}
int size() const { return _size; }
void insert(int pos, const U &x) {
expand_if_full();
if (pos != _size) memmove(buffer + pos + 1, buffer + pos, (_size - pos) * sizeof(U));
alloc.construct(buffer + pos, x);
++_size;
}
void erase(int pos) {
alloc.destroy(buffer + pos);
if (pos != _size - 1) memmove(buffer + pos, buffer + pos + 1, (_size - pos - 1) * sizeof(U));
--_size;
shrink_if_small();
}
void clear() {
for (int i = 0; i < _size; i++) alloc.destroy(buffer + i);
_size = 0;
}
~Vector() {
for (int i = 0; i < _size; i++) alloc.destroy(buffer + i);
alloc.deallocate(buffer, _cap);
}
U &operator[](int pos) { return buffer[pos]; }
const U &operator[](int pos) const { return buffer[pos]; }
};
class Cache {
static const int cache_size = 512;
static const unsigned cache_size_mask = 511;
pair<int, void *> cache[cache_size];
bool valid[cache_size];
public:
int hash(const int &idx) { return idx & cache_size_mask; }
Cache() {
expire();
}
Cache(const Cache &that) {
expire();
}
Cache &operator=(const Cache &that) {
if (this == &that) return *this;
expire();
return *this;
}
template<typename U>
void put(const int &idx, U *entry) {
int _idx = hash(idx);
valid[_idx] = true;
cache[_idx].first = idx;
cache[_idx].second = reinterpret_cast<void *>(entry);
}
template<typename U>
void put(const int &idx, const U *entry) {
int _idx = hash(idx);
valid[_idx] = true;
cache[_idx].first = idx;
cache[_idx].second = const_cast<void *>(reinterpret_cast<const void *>(entry));
}
template<typename U>
U *get(const int &idx) {
int _idx = hash(idx);
if (!valid[_idx]) return nullptr;
if (cache[_idx].first != idx) return nullptr;
return reinterpret_cast<U *>(cache[_idx].second);
}
void expire() {
memset(valid, 0, sizeof(valid));
}
};
mutable Cache index_cache;
int _size;
Vector<Vector<T> > x;
private:
template<typename Tx, typename Tq>
class base_iterator {
protected:
friend deque;
Tq *q;
mutable Tx *elem;
int pos;
base_iterator(Tq *q, const int &pos) : q(q), pos(pos), elem(NULL) {}
bool owns(Tq *q) const { return q == this->q; }
void check_owns(Tq *q) const { if (!owns(q)) throw invalid_iterator(); }
template<typename _This>
static _This &valid(_This *self) {
if (!self->q) throw invalid_iterator();
self->q->throw_if_out_of_bound(self->pos, true);
return *self;
}
base_iterator &construct() {
elem = nullptr;
return valid<base_iterator>(this);
}
const base_iterator &construct() const {
elem = nullptr;
return valid<const base_iterator>(this);
}
public:
base_iterator(const base_iterator &that) = default;
base_iterator() : base_iterator(nullptr, 0) {}
/**
* return a new iterator which pointer n-next elements
* even if there are not enough elements, the behaviour is **undefined**.
* as well as operator-
*/
base_iterator operator+(const int &n) const { return base_iterator(q, pos + n).construct(); }
base_iterator operator-(const int &n) const { return base_iterator(q, pos - n).construct(); }
// return th distance between two iterator,
// if these two iterators points to different vectors, throw invaild_iterator.
int operator-(const base_iterator &rhs) const {
construct();
check_owns(rhs.q);
return pos - rhs.pos;
}
base_iterator &operator+=(const int &n) { return *this = base_iterator(q, pos + n).construct(); }
base_iterator &operator-=(const int &n) { return *this = base_iterator(q, pos - n).construct(); }
base_iterator operator++(int) {
auto _ = *this;
++(*this);
return _;
}
base_iterator &operator++() {
++pos;
return construct();
}
base_iterator operator--(int) {
auto _ = *this;
--(*this);
return _;
}
base_iterator &operator--() {
--pos;
return construct();
}
Tx &operator*() const {
if (!elem) elem = &q->access(pos);
return *elem;
}
Tx *operator->() const noexcept {
if (!elem) elem = &q->access(pos);
return elem;
}
bool operator==(const base_iterator &rhs) const { return rhs.q == q && rhs.pos == pos; }
bool operator!=(const base_iterator &rhs) const { return !(*this == rhs); }
};
private:
void init() {
_size = 0;
x.insert(0, Vector<T>());
}
void throw_if_out_of_bound(int pos, bool include_end = false) const {
if (include_end && pos == size()) return;
if (pos < 0 || pos >= size()) throw index_out_of_bound();
}
template<typename _This, typename Tx>
static Tx &access(_This *self, int pos) {
self->throw_if_out_of_bound(pos);
Tx *elem = self->index_cache.template get<Tx>(pos);
if (elem) return *elem;
int _pos = pos;
int i = self->find_at(pos);
elem = &self->x[i][pos];
self->index_cache.put(_pos, elem);
return self->x[i][pos];
}
T &access(int pos) { return access<deque, T>(this, pos); }
const T &access(int pos) const { return access<const deque, const T>(this, pos); }
void split_chunk(int chunk) {
int split_size = x[chunk].size() >> 1;
x.insert(chunk, Vector<T>(Vector<T>::fit(x[chunk]._size)));
auto &chk_a = x[chunk];
auto &chk_b = x[chunk + 1];
memcpy(chk_a.buffer, chk_b.buffer, sizeof(T) * split_size);
chk_a._size = split_size;
memmove(chk_b.buffer, chk_b.buffer + split_size, sizeof(T) * (chk_b._size - split_size));
chk_b._size -= split_size;
}
void merge_chunk(int chunk) {
auto &chk_a = x[chunk];
auto &chk_b = x[chunk + 1];
chk_a.expand_to(Vector<T>::fit(chk_a._size + chk_b._size));
memcpy(chk_a.buffer + chk_a._size, chk_b.buffer, sizeof(T) * chk_b._size);
chk_a._size += chk_b._size;
chk_b._size = 0;
x.erase(chunk + 1);
}
bool should_split(int total_size) { return total_size >= 16 && total_size * total_size > _size * 8; }
bool should_merge(int total_size) { return total_size * total_size * 64 <= _size; }
int find_at(int &pos) const {
int i = 0, _pos = pos, tmp;
if (_pos <= _size >> 1) {
while (_pos >= (tmp = x[i]._size)) {
if (tmp == 0) {
++i;
continue;
}
_pos -= tmp;
++i;
}
} else {
i = x._size - 1;
_pos = _size - _pos;
while (_pos > (tmp = x[i]._size)) {
if (tmp == 0) {
--i;
continue;
}
_pos -= tmp;
--i;
}
_pos = x[i]._size - _pos;
}
pos = _pos;
return i;
}
int find_at_allow_end(int &pos) const {
int i = 0, _pos = pos, tmp;
if (_pos <= _size >> 1) {
while (_pos > (tmp = x[i].size())) {
_pos -= tmp;
++i;
}
} else {
i = x.size() - 1;
_pos = _size - _pos;
while (i != 0 && _pos >= (tmp = x[i].size())) {
_pos -= tmp;
--i;
}
_pos = x[i].size() - _pos;
}
pos = _pos;
return i;
}
int insert_at(int pos, const T &value) {
throw_if_out_of_bound(pos, true);
int __pos = pos;
int i = find_at_allow_end(pos);
x[i].insert(pos, value);
++_size;
if (should_split(x[i].size())) split_chunk(i);
if (rand() < INSERT_GC_THRESHOLD) gc();
index_cache.expire();
return __pos;
}
public:
void gc() {
clear_zero();
for (int i = 0; i < x.size(); i++) {
if (should_split(x[i].size())) {
split_chunk(i);
++i;
}
}
for (int i = 0; i < x.size() - 1; i++) {
if (should_merge(x[i].size() + x[i + 1].size())) {
merge_chunk(i);
--i;
}
}
}
private:
void clear_zero() {
if (x.size() <= 1) return;
for (int i = 0; i < x.size() - 1; i++) {
if (x[i].size() == 0) {
x.erase(i);
}
}
}
int remove_at(int pos) {
throw_if_out_of_bound(pos);
int __pos = pos;
int i = find_at(pos);
x[i].erase(pos);
--_size;
if (i != x.size() - 1) {
if (should_merge(x[i].size() + x[i + 1].size())) merge_chunk(i);
} else {
if (x.size() > 1 && x[i].size() == 0) x.erase(i);
}
if (rand() < REMOVE_GC_THRESHOLD) gc();
index_cache.expire();
return __pos;
}
public:
typedef base_iterator<T, deque> iterator;
typedef base_iterator<const T, const deque> const_iterator;
/**
* Constructors
*/
deque() {
_size = 0;
init();
}
/**
* Deconstructor
*/
~deque() {}
/**
* access specified element with bounds checking
* throw index_out_of_bound if out of bound.
*/
T &at(const size_t &pos) { return access(pos); }
const T &at(const size_t &pos) const { return access(pos); }
T &operator[](const size_t &pos) { return access(pos); }
const T &operator[](const size_t &pos) const { return access(pos); }
/**
* access the first element
* throw container_is_empty when the container is empty.
*/
const T &front() const { return access(0); }
/**
* access the last element
* throw container_is_empty when the container is empty.
*/
const T &back() const { return access(size() - 1); }
/**
* returns an iterator to the beginning.
*/
iterator begin() { return iterator(this, 0); }
const_iterator cbegin() const { return const_iterator(this, 0); }
/**
* returns an iterator to the end.
*/
iterator end() { return iterator(this, size()); }
const_iterator cend() const { return const_iterator(this, size()); }
/**
* checks whether the container is empty.
*/
bool empty() const { return _size == 0; }
/**
* returns the number of elements
*/
size_t size() const { return _size; }
/**
* clears the contents
*/
void clear() {
x.clear();
init();
}
/**
* inserts elements at the specified locat on in the container.
* inserts value before pos
* returns an iterator pointing to the inserted value
* throw if the iterator is invalid or it point to a wrong place.
*/
iterator insert(iterator pos, const T &value) {
pos.check_owns(this);
return iterator(this, insert_at(pos.pos, value));
}
/**
* removes specified element at pos.
* removes the element at pos.
* returns an iterator pointing to the following element, if pos pointing to the last element, end() will be returned.
* throw if the container is empty, the iterator is invalid or it points to a wrong place.
*/
iterator erase(iterator pos) {
pos.check_owns(this);
return iterator(this, remove_at(pos.pos));
}
/**
* adds an element to the end
*/
void push_back(const T &value) { insert_at(size(), value); }
/**
* removes the last element
* throw when the container is empty.
*/
void pop_back() { remove_at(size() - 1); }
/**
* inserts an element to the beginning.
*/
void push_front(const T &value) { insert_at(0, value); }
/**
* removes the first element.
* throw when the container is empty.
*/
void pop_front() { remove_at(0); }
void debug() const {
std::cerr << _size << "(" << x.size() << "): ";
for (int i = 0; i < x.size(); i++) std::cerr << x[i].size() << "/" << x[i]._cap << " ";
std::cerr << "\n";
}
};
}
#endif
Raw
deque_vector_chunk.cpp
#ifndef SJTU_DEQUE_HPP
#define SJTU_DEQUE_HPP
#include "exceptions.hpp"
#include <cstddef>
#include <cstring>
#include <cstdlib>
namespace sjtu
{
template <class T>
class deque
{
private:
friend class iterator;
static const unsigned chunk_size = 512; // cannot be 1 otherwise there'd be something wrong with iterator
struct Chunk
{
T *data;
Chunk *prev;
Chunk *next;
std::allocator<T> allocator;
/* TODO: write our own allocator */
Chunk(Chunk *prev = NULL, Chunk *next = NULL) : prev(prev),
next(next)
{
data = allocator.allocate(chunk_size);
}
Chunk(const Chunk &other) = delete;
static Chunk *construct_from(const Chunk &other, int data_begin, int data_end)
{
Chunk *chunk = new Chunk;
for (int i = data_begin; i < data_end; i++)
chunk->allocator.construct(chunk->data + i, other.data[i]);
return chunk;
}
void destruct_range(int data_begin, int data_end)
{
for (int i = data_begin; i < data_end; i++)
allocator.destroy(data + i);
}
~Chunk() { allocator.deallocate(data, chunk_size); }
} * head, *tail;
T *chunk_head, *chunk_tail;
void destruct()
{
Chunk *ptr = head;
while (ptr->prev)
ptr = ptr->prev;
bool is_in_range = false;
while (ptr)
{
Chunk *tmp = ptr->next;
int data_begin = 0;
int data_end = chunk_size;
if (ptr == head)
{
data_begin = chunk_head - head->data;
is_in_range = true;
}
if (ptr == tail)
data_end = chunk_tail - tail->data;
if (is_in_range)
ptr->destruct_range(data_begin, data_end);
if (ptr == tail)
is_in_range = false;
delete ptr;
ptr = tmp;
}
}
void copy_from(const deque &other)
{
Chunk *ptr = other.head;
Chunk *prev = NULL;
while (ptr)
{
int data_begin = 0;
int data_end = chunk_size;
if (ptr == other.head)
data_begin = other.chunk_head - other.head->data;
if (ptr == other.tail)
data_end = other.chunk_tail - other.tail->data;
Chunk *cur = Chunk::construct_from(*ptr, data_begin, data_end);
cur->prev = prev;
if (prev)
prev->next = cur;
else
this->head = cur;
prev = cur;
ptr = ptr->next;
}
this->tail = prev;
this->chunk_head = this->head->data + (other.chunk_head - other.head->data);
this->chunk_tail = this->tail->data + (other.chunk_tail - other.tail->data);
}
void create_new()
{
tail = head = new Chunk;
chunk_head = chunk_tail = head->data;
}
void append_chunk()
{
if (!tail->next)
tail->next = new Chunk(tail);
tail = tail->next;
}
void prepend_chunk()
{
if (!head->prev)
head->prev = new Chunk(NULL, head);
head = head->prev;
}
void shrink_tail_chunk()
{
Chunk *tmp = tail->prev;
delete tail;
tail = tmp;
tail->next = NULL;
}
void shrink_head_chunk()
{
Chunk *tmp = head->next;
delete head;
head = tmp;
head->prev = NULL;
}
void throw_when_empty() const
{
if (this->empty())
throw container_is_empty();
}
public:
class const_iterator;
class iterator
{
private:
friend deque<T>;
void debug(const char *msg) const
{
fprintf(stderr, "%s: chunk %x at %d\n", msg, chunk, pos - chunk->data);
}
bool is_at_the_end() const { return pos == chunk->data + chunk_size; }
int distance_to_head() const
{
Chunk *ptr = q->head;
int chunk_cnt = 0;
while (ptr != chunk)
{
++chunk_cnt;
ptr = ptr->next;
}
int head_offset = q->chunk_head - q->head->data;
int tail_offset = pos - chunk->data;
return tail_offset + chunk_cnt * chunk_size - head_offset;
};
protected:
deque *q;
Chunk *chunk;
T *pos;
iterator(deque *q, Chunk *chunk, T *pos) : q(q), chunk(chunk), pos(pos) {}
void move_chunk(int i)
{
if (i == 0)
return;
int offset = pos - chunk->data;
while (i > 0)
{
--i;
if (!chunk->next)
{
if (chunk == q->tail && offset == 0)
{
offset = chunk_size;
}
else
throw index_out_of_bound();
}
else
chunk = chunk->next;
}
while (i < 0)
{
++i;
if (!chunk->prev)
{
throw index_out_of_bound();
}
chunk = chunk->prev;
}
pos = chunk->data + offset;
}
void move_forward(int i)
{
if (i == 0)
return;
while (i < 0)
{
++i;
if (pos == chunk->data)
{
if (!chunk->prev)
throw index_out_of_bound();
chunk = chunk->prev;
pos = chunk->data + chunk_size;
}
--pos;
if (chunk == q->head && pos < q->chunk_head)
throw index_out_of_bound();
}
while (i > 0)
{
--i;
++pos;
if (pos == chunk->data + chunk_size)
{
if (chunk != q->tail)
{
if (!chunk->next)
throw index_out_of_bound();
chunk = chunk->next;
pos = chunk->data;
}
}
if (chunk == q->tail && pos > q->chunk_tail)
throw index_out_of_bound();
}
}
public:
/** constructors **/
iterator() : q(NULL), chunk(NULL), pos(NULL) {}
iterator(const iterator &other) : iterator(other.q, other.chunk, other.pos) {}
/**
* return a new iterator which pointer n-next elements
* even if there are not enough elements, the behaviour is **undefined**.
* as well as operator-
*/
iterator operator+(const int &n) const
{
iterator that(*this);
if (n > 0)
{
if (n <= chunk_size)
that.move_forward(n);
else
{
that.move_forward(n % chunk_size);
that.move_chunk(n / chunk_size);
}
}
else if (n < 0)
{
if (n >= -chunk_size)
that.move_forward(n);
else
{
that.move_forward(-(int)((-n) % chunk_size));
that.move_chunk(-(int)((-n) / chunk_size));
}
}
return that;
}
iterator operator-(const int &n) const { return this->operator+(-n); }
// return th distance between two iterator,
// if these two iterators points to different vectors, throw invaild_iterator.
int operator-(const iterator &rhs) const
{
if (rhs.q != this->q)
throw invalid_iterator();
return this->distance_to_head() - rhs.distance_to_head();
}
iterator operator+=(const int &n)
{
this->move_forward(n);
return *this;
}
iterator operator-=(const int &n)
{
this->move_forward(-n);
return *this;
}
/**
* iter++
*/
iterator operator++(int)
{
iterator that(*this);
this->move_forward(1);
return that;
}
/**
* ++iter
*/
iterator &operator++()
{
this->move_forward(1);
return *this;
}
/**
* iter--
*/
iterator operator--(int)
{
iterator that(*this);
this->move_forward(-1);
return that;
}
/**
* --iter
*/
iterator &operator--()
{
this->move_forward(-1);
return *this;
}
/**
* *it
*/
T &operator*() const
{
if (chunk == q->tail && pos == q->chunk_tail)
throw index_out_of_bound();
return *pos;
}
/**
* it->field
*/
T *operator->() const noexcept { return pos; }
/**
* a operator to check whether two iterators are same (pointing to the same memory).
*/
bool operator==(const iterator &rhs) const
{
return (q == rhs.q) && (chunk == rhs.chunk) && (pos == rhs.pos);
}
bool operator==(const const_iterator &rhs) const
{
return (q == rhs.q) && (chunk == rhs.chunk) && (pos == rhs.pos);
}
/**
* some other operator for iterator.
*/
bool operator!=(const iterator &rhs) const { return !(*this == rhs); }
bool operator!=(const const_iterator &rhs) const { return !(*this == rhs); }
};
class const_iterator
{
// it should has similar member method as iterator.
// and it should be able to construct from an iterator.
private:
friend deque<T>;
bool is_at_the_end() { return pos == chunk->data + chunk_size; }
int distance_to_head() const
{
Chunk *ptr = q->head;
int chunk_cnt = 0;
while (ptr != chunk)
{
++chunk_cnt;
ptr = ptr->next;
}
int head_offset = q->chunk_head - q->head->data;
int tail_offset = pos - chunk->data;
return tail_offset + chunk_cnt * chunk_size - head_offset;
};
void move_chunk(int i)
{
if (i == 0)
return;
int offset = pos - chunk->data;
while (i > 0)
{
--i;
if (!chunk->next)
{
if (chunk == q->tail && offset == 0)
{
offset = chunk_size;
}
else
throw index_out_of_bound();
}
else
chunk = chunk->next;
}
while (i < 0)
{
++i;
if (!chunk->prev)
{
throw index_out_of_bound();
}
chunk = chunk->prev;
}
pos = chunk->data + offset;
}
void move_forward(int i)
{
if (i == 0)
return;
while (i < 0)
{
++i;
if (pos == chunk->data)
{
if (!chunk->prev)
throw index_out_of_bound();
chunk = chunk->prev;
pos = chunk->data + chunk_size;
}
--pos;
if (chunk == q->head && pos < q->chunk_head)
throw index_out_of_bound();
}
while (i > 0)
{
--i;
++pos;
if (pos == chunk->data + chunk_size)
{
if (chunk != q->tail)
{
if (!chunk->next)
throw index_out_of_bound();
chunk = chunk->next;
pos = chunk->data;
}
}
if (chunk == q->tail && pos > q->chunk_tail)
throw index_out_of_bound();
}
}
protected:
const deque *q;
const Chunk *chunk;
const T *pos;
const_iterator(const deque *q, const Chunk *chunk, const T *pos) : q(q), chunk(chunk), pos(pos) {}
public:
const_iterator(const const_iterator &other) : const_iterator(other.q, other.chunk, other.pos) {}
const_iterator(const iterator &other) : const_iterator(other.q, other.chunk.other.pos) {}
const_iterator() {}
/**
* return a new iterator which pointer n-next elements
* even if there are not enough elements, the behaviour is **undefined**.
* as well as operator-
*/
const_iterator operator+(const int &n) const
{
const_iterator that(*this);
if (n > 0)
{
that.move_forward(n % chunk_size);
that.move_chunk(n / chunk_size);
}
else if (n < 0)
{
/* TODO: is chunk_size is 1, then move_forward is always called with 0, which may cause exception */
that.move_forward(-(int)((-n) % chunk_size));
that.move_chunk(-(int)((-n) / chunk_size));
}
return that;
}
const_iterator operator-(const int &n) const { return this->operator+(-n); }
// return th distance between two iterator,
// if these two iterators points to different vectors, throw invaild_iterator.
int operator-(const const_iterator &rhs) const
{
if (rhs.q != this->q)
throw invalid_iterator();
return this->distance_to_head() - rhs.distance_to_head();
}
/**
* *it
*/
const T &operator*() const
{
if (chunk == q->tail && pos == q->chunk_tail)
throw index_out_of_bound();
return *pos;
}
/**
* it->field
*/
const T *operator->() const noexcept { return this->pos; }
bool operator==(const iterator &rhs) const
{
return (q == rhs.q) && (chunk == rhs.chunk) && (pos == rhs.pos);
}
bool operator==(const const_iterator &rhs) const
{
return (q == rhs.q) && (chunk == rhs.chunk) && (pos == rhs.pos);
}
/**
* some other operator for iterator.
*/
bool operator!=(const iterator &rhs) const { return !(*this == rhs); }
bool operator!=(const const_iterator &rhs) const { return !(*this == rhs); }
const_iterator operator+=(const int &n)
{
this->move_forward(n);
return *this;
}
const_iterator operator-=(const int &n)
{
this->move_forward(-n);
return *this;
}
/**
* iter++
*/
const_iterator operator++(int)
{
iterator that(*this);
this->move_forward(1);
return that;
}
/**
* ++iter
*/
const_iterator &operator++()
{
this->move_forward(1);
return *this;
}
/**
* iter--
*/
const_iterator operator--(int)
{
iterator that(*this);
this->move_forward(-1);
return that;
}
/**
* --iter
*/
const_iterator &operator--()
{
this->move_forward(-1);
return *this;
}
};
/**
* constructors
*/
deque() { create_new(); }
deque(const deque &other) { this->copy_from(other); }
/**
* deconstructor
*/
~deque() { this->destruct(); }
/**
* assignment operator
*/
deque &operator=(const deque &other)
{
if (this == &other)
return *this;
this->destruct();
this->copy_from(other);
return *this;
}
/**
* access specified element with bounds checking
* throw index_out_of_bound if out of bound.
*/
T &at(const size_t &pos) { return *(begin() + pos); }
const T &at(const size_t &pos) const { return *(cbegin() + pos); }
T &operator[](const size_t &pos) { return this->at(pos); }
const T &operator[](const size_t &pos) const { return this->at(pos); }
/**
* access the first element
* throw container_is_empty when the container is empty.
*/
const T &front() const
{
throw_when_empty();
return *chunk_head;
}
/**
* access the last element
* throw container_is_empty when the container is empty.
*/
const T &back() const
{
throw_when_empty();
return *(chunk_tail - 1);
}
/**
* returns an iterator to the beginning.
*/
iterator begin() { return iterator(this, head, chunk_head); }
const_iterator cbegin() const { return const_iterator(this, head, chunk_head); }
/**
* returns an iterator to the end.
*/
iterator end() { return iterator(this, tail, chunk_tail); }
const_iterator cend() const { return const_iterator(this, tail, chunk_tail); }
/**
* checks whether the container is empty.
*/
bool empty() const
{
if (head == tail && chunk_head == chunk_tail)
return true;
else
return false;
}
/**
* returns the number of elements
*/
size_t size() const { return cend() - cbegin(); }
/**
* clears the contents
*/
void clear()
{
this->destruct();
this->create_new();
}
/**
* inserts elements at the specified locat on in the container.
* inserts value before pos
* returns an iterator pointing to the inserted value
* throw if the iterator is invalid or it point to a wrong place.
*/
iterator insert(iterator pos, const T &value)
{
if (pos == end())
{
push_back(value);
return end() - 1;
}
push_back(value);
iterator cur = end();
--cur;
while (cur != pos)
{
iterator next = cur;
--cur;
std::swap_ranges(next.pos, next.pos + 1, cur.pos);
}
return pos;
}
/**
* removes specified element at pos.
* removes the element at pos.
* returns an iterator pointing to the following element, if pos pointing to the last element, end() will be returned.
* throw if the container is empty, the iterator is invalid or it points to a wrong place.
*/
iterator erase(iterator pos)
{
iterator lst = end();
--lst;
iterator cur = pos;
while (cur != lst)
{
iterator prev = cur;
++cur;
std::swap_ranges(prev.pos, prev.pos + 1, cur.pos);
}
pop_back();
return pos;
}
/**
* adds an element to the end
*/
void push_back(const T &value)
{
if (chunk_tail - tail->data == chunk_size)
{
append_chunk();
chunk_tail = tail->data;
}
tail->allocator.construct(chunk_tail, value);
++chunk_tail;
}
/**
* removes the last element
* throw when the container is empty.
*/
void pop_back()
{
throw_when_empty();
--chunk_tail;
tail->allocator.destroy(chunk_tail);
if (chunk_tail - tail->data == 0)
{
if (head != tail)
{
shrink_tail_chunk();
chunk_tail = tail->data + chunk_size;
}
}
}
/**
* inserts an element to the beginning.
*/
void push_front(const T &value)
{
if (chunk_head - head->data == 0)
{
prepend_chunk();
chunk_head = head->data + chunk_size;
}
--chunk_head;
head->allocator.construct(chunk_head, value);
}
/**
* removes the first element.
* throw when the container is empty.
*/
void pop_front()
{
throw_when_empty();
head->allocator.destroy(chunk_head);
++chunk_head;
if (chunk_head - head->data == chunk_size)
{
if (head == tail)
{
chunk_head = chunk_tail = head->data;
}
else
{
shrink_head_chunk();
chunk_head = head->data;
}
}
}
void debug()
{
Chunk *ptr = head;
while (ptr)
{
for (int i = 0; i < chunk_size; i++)
fprintf(stderr, "%d ", ptr->data[i]);
ptr = ptr->next;
}
fprintf(stderr, "\n");
}
};
} // namespace sjtu
#endif
Raw
test7_with_clock.cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include "deque.hpp"
#include "exceptions.hpp"
/***************************/
bool need_to_check_throw = 1;
bool good_complexity = 1;//if the complexity is N^2, change to 0
int N = good_complexity ? 300000 : 1000;
/***************************/
class T{
private:
int x;
public:
T(int x):x(x){}
int num()const {return x;}
void change(int y){
x = y;
}
};
bool operator == (const T &a, const T &b){
return a.num() == b.num();
}
bool operator != (const T &a, const T &b){
return a.num() != b.num();
}
sjtu::deque<T> q;
std::deque<T> stl;
sjtu::deque<T>::iterator it_q;
std::deque<T>::iterator it_stl;
sjtu::deque<T>::const_iterator _it_q;
std::deque<T>::const_iterator _it_stl;
bool equal(){
if(q.size() != stl.size()) return 0;
if(q.empty() != stl.empty()) return 0;
int cnt = 0;
for(it_q = q.begin(), it_stl = stl.begin(); it_q != q.end() || it_stl != stl.end(); it_q++, it_stl++){
if(*it_q != *it_stl) {
printf("cnt = %d\n",cnt);
return 0;
}
cnt++;
}
return 1;
}
void test1(){
printf("test1: push & pop ");
for(int i=1;i<=N;i++){
if(i % 10 <= 3) q.push_back(T(i)), stl.push_back(T(i));else
if(i % 10 <= 7) q.push_front(T(i)), stl.push_front(T(i));else
if(i % 10 <= 8) q.pop_back(), stl.pop_back();else
if(i % 10 <= 9) q.pop_front(), stl.pop_front();
}
if(!equal()){puts("Wrong Answer");return;}
while (!q.empty()){
q.pop_back();
stl.pop_back();
}
puts("Accept");
}
void test2(){
printf("test2: at & [] & front & back ");
int flag = 0;
try{
int t = q.front().num();
}catch(...){flag ++;}
try{
int t = q.back().num();
}catch(...){flag ++;}
if(flag != 2 && need_to_check_throw){puts("Wrong Answer");return;}
for(int i=1;i<=N;i++){
if(i % 10 <= 3) q.push_back(T(i)), stl.push_back(T(i));else
if(i % 10 <= 7) q.push_front(T(i)), stl.push_front(T(i));else
if(i % 10 <= 8) q.pop_back(), stl.pop_back();else
if(i % 10 <= 9) q.pop_front(), stl.pop_front();
}
flag = 0;
try{
int t = (q.at(q.size() + 100)).num();
}catch(...){flag = 1;}
if(flag != 1 && need_to_check_throw){puts("Wrong Answer");return;}
int num = q.size();
for(int i=0;i<100;i++)
{
int t = rand() % num;
if(q[t] != stl[t] || q.at(t) != stl.at(t)){puts("Wrong Answer");return;}
}
if(q.front() != stl.front() || q.back() != stl.back()){puts("Wrong Answer");return;}
puts("Accept");
}
void test3(){
printf("test3: itetator operation ");
int num = q.size();
for(int i =1 ; i <= 1000; i++)
{
int t1 = rand() % num;
int t2 = rand() % num;
if(*(q.begin() + t1) != *(stl.begin() + t1)){puts("Wrong Answer");return;}
if(t2 && *(q.end() - t2) != *(stl.end() - t2)){puts("Wrong Answer");return;}
if((q.begin() + t1) - (q.begin() + t2) != (t1 - t2)){puts("Wrong Answer");return;}
}
if((q.begin() + num) != q.end()) {puts("Wrong Answer");return;}
if((q.end() - num) != q.begin()) {puts("Wrong Answer");return;}
bool flag=0;
sjtu::deque<T> other;
try{
int t = q.begin() - other.begin();
}catch(...){
flag=1;
}
if(!flag && need_to_check_throw) {puts("Wrong Answer");return;}
it_q = q.begin();
it_stl = stl.begin();
for(int i=1;i<=10;i++){
int t = rand() % (num / 10);
it_q += t;
it_stl += t;
if(*it_q != *it_stl) {puts("Wrong Answer");return;}
if(it_q -> num() != it_stl -> num()) {puts("Wrong Answer");return;}
}
it_q = --q.end();
it_stl = --stl.end();
if(*it_q != *it_stl) {puts("Wrong Answer");return;}
for(int i=1;i<10;i++){
int t = rand() % (num / 10);
it_q -= t;
it_stl -= t;
if(*it_q != *it_stl) {puts("Wrong Answer");return;}
it_q -> change(t);;
it_stl -> change(t);
if(*it_q != *it_stl) {puts("Wrong Answer");return;}
}
if(!equal()) {puts("Wrong Answer");return;}
if (!(q.begin() + 10 == q.begin() +5 + 6 - 1)) {puts("Wrong Answer");return;}
sjtu::deque<T> pp;
if(q.end() == pp.end()){puts("Wrong Answer");return;}
int t = rand() % (q.size() - 1);
it_q = q.begin() + t;
it_stl = stl.begin() + t;
const sjtu::deque<T>::iterator it_q_const(++it_q);
const std::deque<T>::iterator it_stl_const(++it_stl);
if(*it_q_const != *it_stl_const){puts("Wrong Answer");return;}
if(it_q_const -> num() != it_stl_const -> num()){puts("Wrong Answer");return;}
it_q_const -> change(t);
it_stl_const -> change(t);
if(!equal()){puts("Wrong Answer");return;}
puts("Accept");
}
void test4(){
printf("test4: const_itetator operation ");
const sjtu::deque<T> _q(q);
const std::deque<T> _stl(stl);
int num = _q.size();
for(int i =1 ; i <= 1000; i++)
{
int t1 = rand() % num;
int t2 = rand() % num;
if(*(_q.cbegin() + t1) != *(_stl.cbegin() + t1)){puts("Wrong Answer");return;}
if(t2 && *(_q.cend() - t2) != *(_stl.cend() - t2)){puts("Wrong Answer");return;}
if((_q.cbegin() + t1) - (_q.cbegin() + t2) != (t1 - t2)){puts("Wrong Answer");return;}
}
if((_q.cbegin() + num) != _q.cend()) {puts("Wrong Answer");return;}
if((_q.cend() - num) != _q.cbegin()) {puts("Wrong Answer");return;}
_it_q = _q.cbegin();
_it_stl = _stl.cbegin();
for(int i=1;i<=10;i++){
int t = rand() % (num / 10);
_it_q += t;
_it_stl += t;
if(*_it_q != *_it_stl) {puts("Wrong Answer");return;}
if(_it_q -> num() != _it_stl -> num()) {puts("Wrong Answer");return;}
}
_it_q = --_q.cend();
_it_stl = --_stl.cend();
if(*_it_q != *_it_stl) {puts("Wrong Answer");return;}
if (!(_q.cbegin() + 10 == _q.cbegin() +5 + 6 - 1)) {puts("Wrong Answer");return;}
puts("Accept");
}
void test5(){
printf("test5: erase & insert ");
for(int i=1;i<=sqrt(N) && q.size()>=10;i++)
{
int t = rand() % (q.size() - 3);
it_q = q.begin() + t;
it_stl = stl.begin() + t;
it_q = q.erase(it_q);
it_stl = stl.erase(it_stl);
it_q = q.erase(it_q);
it_stl = stl.erase(it_stl);
it_q -> change(t);
it_stl -> change(t);
}
if(!equal()) {puts("Wrong Answer");return;}
it_q = q.erase(q.end() - 1);
it_stl = stl.erase(stl.end() - 1);
if(it_q != q.end()){puts("Wrong Answer");return;}
for(int i = 1; i <= sqrt(N); i++)
{
int t = rand() % q.size();
it_q = q.begin() + t;
it_stl = stl.begin() + t;
it_q = q.insert(it_q, T(t));
it_stl = stl.insert(it_stl, T(t));
it_q = q.insert(it_q, T(t + 1));
it_stl = stl.insert(it_stl, T(t + 1));
}
it_q = q.begin();
it_stl = stl.begin();
for(int i=1;i<=sqrt(N);i++)
{
it_q = q.insert(it_q, T(i));
it_stl = stl.insert(it_stl, T(i));
}
it_q = q.insert(q.end(), T(23333));
it_stl = stl.insert(stl.end(),T(23333));
if(it_q != q.end() - 1){puts("Wrong Answer");return;}
if(!equal()) {puts("Wrong Answer");return;}
puts("Accept");
}
void test6(){
printf("test6: clear & copy & assignment ");
sjtu::deque<T> p(q), r;
r = q;
q.clear();
if(!q.empty() || q.size() != 0 || q.begin()!=q.end()){puts("Wrong Answer");return;}
q=q=q;
if(!q.empty() || q.size() != 0 || q.begin()!=q.end()){puts("Wrong Answer");return;}
for(int i=1;i<=100;i++)
{
int t = rand() % p.size();
p.push_back(T(t));
p.insert(p.begin() + t, T(t));
r.push_back(T(t));
r.insert(r.begin() + t, T(t));
stl.push_back(T(t));
stl.insert(stl.begin() + t, T(t));
}
q = p;
p.clear();
q=q=q=q;
if(!equal()) {puts("Wrong Answer");return;}
q.clear();
q = r;
r.clear();
q=q=q=q;
if(!equal()) {puts("Wrong Answer");return;}
puts("Accept");
}
double print_clock() {
static clock_t start = std::clock();
double duration;
duration = ( std::clock() - start ) / (double) CLOCKS_PER_SEC;
start = std::clock();
return duration;
}
double print_clock_2() {
static clock_t start = std::clock();
double duration;
duration = ( std::clock() - start ) / (double) CLOCKS_PER_SEC;
start = std::clock();
return duration;
}
void test7(){
printf("test7: complexity ");
int num = 500000;
static sjtu::deque<T> q;
print_clock();
print_clock_2();
std::cout << std::endl;
for(int i = 0; i < num; i++) {
q.push_front(T(i));
}
std::cout << "push_front " << print_clock() << std::endl;
for(int i = 0; i < num; i++) {
q.pop_front();
}
std::cout << "pop_front " << print_clock() << std::endl;
for(int i = 0; i < num; i++) {
q.push_back(T(i));
}
std::cout << "push_back " << print_clock() << std::endl;
for(int i = 0; i < num; i++) {
q.pop_back();
}
std::cout << "pop_back " << print_clock() << std::endl;
for(int i = 0; i < num;i++){
if(i % 10 <= 3) q.push_back(T(i));else
if(i % 10 <= 7) q.push_front(T(i));else
if(i % 10 <= 8) q.pop_back();else
if(i % 10 <= 9) q.pop_front();
}
std::cout << "random_operation " << print_clock() << std::endl;
int test_num = 5000000;
it_q = q.begin() + q.size() - 10;
for(int i = 0; i < test_num; i++)
{
int tmp = (*it_q).num();
tmp = it_q -> num();
if(i % (test_num / 10) == 0) it_q = q.begin() + rand() % q.size();
}
std::cout << "random_access " << print_clock() << std::endl;
for(int i = 0; i < N; i++){
it_q = q.begin() + rand() % q.size();
q.insert(it_q, T(rand()));
}
std::cout << "random_insert " << print_clock() << std::endl;
for(int i = 0; i < N; i++){
it_q = q.begin() + rand() % q.size();
q.erase(it_q);
}
std::cout << "random_erase " << print_clock() << std::endl;
for(int i = 0; i < N; i++){
int tmp = q[rand() % q.size()].num();
tmp = q.at(rand() % q.size()).num();
}
std::cout << "random_call " << print_clock() << std::endl;
if(good_complexity){
q.clear();
for(int i=0;i<4000000;i++) {
q.push_back(i);
}
std::cout << "push_back " << print_clock() << std::endl;
while (q.size()>2010){
if(rand() % 2) q.pop_front();
else q.pop_back();
}
std::cout << "pop_back_front " << print_clock() << std::endl;
int tmp;
for(int i=0;i<2000000;i++){
tmp = q[2000].num();
tmp = q[1000].num();
}
std::cout << "static_access " << print_clock() << std::endl;
}
puts("Accept");
std::cout << "total: " << print_clock_2() << std::endl;
}
int main(){
srand(time(NULL));
puts("test start:");
print_clock();
test1();//push & pop
test2();//at & [] & front & back
test3();//iterator operation
test4();//const_iterator operation
test5();//erase & insert
test6();//clear & copy & assignment
std::cout << "test 1-6 " << print_clock() << std::endl;
test7();//complexity
test7();//complexity
test7();//complexity
test7();//complexity
test7();//complexity
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment