303 lines
7.6 KiB
C++
303 lines
7.6 KiB
C++
#include <memory>
|
|
#include <vector>
|
|
#include <iterator>
|
|
|
|
template<size_t chunkSize>
|
|
class FixedAllocator {
|
|
private:
|
|
static const int count_chunks = 16;
|
|
static inline std::vector<void*> free;
|
|
public:
|
|
[[nodiscard]] static void* allocate() {
|
|
if (free.empty()) {
|
|
char* tmp = static_cast<char*>(malloc(chunkSize * count_chunks));
|
|
for (int i = 0; i < count_chunks; ++i) free.push_back(reinterpret_cast<void*>(tmp + i * chunkSize));
|
|
}
|
|
void* tmp = free.back();
|
|
free.pop_back();
|
|
return tmp;
|
|
}
|
|
|
|
static void deallocate(void* p) noexcept {
|
|
free.push_back(p);
|
|
}
|
|
};
|
|
|
|
template<size_t x, size_t end>
|
|
[[nodiscard]] void* genius_allocate_fixed_allocator(size_t n) {
|
|
if (x == n) {
|
|
return FixedAllocator<x>::allocate();
|
|
} else {
|
|
if constexpr (x < end) {
|
|
return genius_allocate_fixed_allocator<x + 1, end>(n);
|
|
}
|
|
}
|
|
|
|
return nullptr;
|
|
}
|
|
|
|
template<typename T>
|
|
class FastAllocator {
|
|
public:
|
|
using value_type = T;
|
|
FastAllocator() = default;
|
|
|
|
template<typename U>
|
|
FastAllocator(const FastAllocator<U>&) {}
|
|
|
|
template<typename U>
|
|
FastAllocator& operator=(const FastAllocator<U>&) const { return *this; }
|
|
|
|
[[nodiscard]] T* allocate(size_t n) {
|
|
if (n * sizeof(T) > big_block_ || n > 1)
|
|
return static_cast<T*>(std::malloc(n * sizeof(T)));
|
|
else {
|
|
return static_cast<T*>(genius_allocate_fixed_allocator<sizeof(T), big_block_>(sizeof(T) * n));
|
|
// return static_cast<T*>(FixedAllocator<sizeof(T)>().allocate());
|
|
}
|
|
}
|
|
|
|
void deallocate(T* p, size_t n) noexcept {
|
|
if (n * sizeof(T) > 48 || n > 1)
|
|
free(p);
|
|
else
|
|
return FixedAllocator<sizeof(T)>().deallocate(p);
|
|
}
|
|
private:
|
|
static const size_t big_block_ = 48;
|
|
};
|
|
|
|
template<class T, class U>
|
|
bool operator==(const FastAllocator<T>& a, const FastAllocator<U>& b) {
|
|
return &a == &b;
|
|
}
|
|
|
|
template<class T, class U>
|
|
bool operator!=(const FastAllocator<T>& a, const FastAllocator<U>& b) {
|
|
return &a != &b;
|
|
}
|
|
|
|
template<typename T, typename Allocator=std::allocator<T>>
|
|
class List {
|
|
private:
|
|
class Node;
|
|
|
|
template<bool is_const>
|
|
class base_iterator;
|
|
public:
|
|
using iterator = base_iterator<false>;
|
|
using const_iterator = base_iterator<true>;
|
|
using reverse_iterator = std::reverse_iterator<iterator>;
|
|
using const_reverse_iterator = std::reverse_iterator<const_iterator>;
|
|
|
|
explicit List(const Allocator& alloc = Allocator()) : alloc_(alloc) {
|
|
AllocateEnd();
|
|
}
|
|
|
|
List(size_t count, const T& value, const Allocator& alloc = Allocator()) : alloc_(alloc) {
|
|
AllocateEnd();
|
|
|
|
for (size_t i = 0; i < count; ++i) {
|
|
Node* tmp = alloc_.allocate(1);
|
|
alloc_traits_::construct(alloc_, tmp, value);
|
|
Link(end_->l, tmp);
|
|
}
|
|
size_ = count;
|
|
}
|
|
|
|
List(size_t count, const Allocator& alloc = Allocator()) : alloc_(alloc) {
|
|
AllocateEnd();
|
|
|
|
for (size_t i = 0; i < count; ++i) {
|
|
Node* tmp = alloc_.allocate(1);
|
|
alloc_traits_::construct(alloc_, tmp);
|
|
Link(end_->l, tmp);
|
|
}
|
|
size_ = count;
|
|
}
|
|
|
|
List(const List& another) {
|
|
alloc_ = alloc_traits_::select_on_container_copy_construction(another.alloc_);
|
|
AllocateEnd();
|
|
for (const T& i: another) {
|
|
Node* tmp = alloc_.allocate(1);
|
|
alloc_traits_::construct(alloc_, tmp, i);
|
|
Link(end_->l, tmp);
|
|
}
|
|
size_ = another.size();
|
|
}
|
|
|
|
List(List&&) = default;
|
|
|
|
List& operator=(const List& another) {
|
|
if (this == &another) return *this;
|
|
if (alloc_traits_::propagate_on_container_copy_assignment::value && alloc_ != another.alloc_) {
|
|
alloc_ = another.alloc_;
|
|
}
|
|
|
|
auto it1 = begin();
|
|
auto it2 = another.begin();
|
|
for (size_t i = 0; i < std::min(another.size(), size()); ++i) {
|
|
*it1 = *it2;
|
|
++it1;
|
|
++it2;
|
|
}
|
|
if (another.size() > size()) {
|
|
while (size() != another.size()) {
|
|
push_back(*it2);
|
|
++it2;
|
|
}
|
|
} else {
|
|
while (size() != another.size()) {
|
|
pop_back();
|
|
}
|
|
}
|
|
|
|
return *this;
|
|
}
|
|
|
|
List& operator= (List&&) = default;
|
|
|
|
~List() {
|
|
while (end_ != end_->r) {
|
|
erase(iterator(end_->r));
|
|
}
|
|
alloc_.deallocate(end_, 1);
|
|
}
|
|
|
|
Allocator get_allocator() {
|
|
return alloc_;
|
|
}
|
|
|
|
void push_back(const T& value) {
|
|
insert(end(), value);
|
|
}
|
|
|
|
void push_front(const T& value) {
|
|
insert(begin(), value);
|
|
}
|
|
|
|
void pop_back() {
|
|
erase(std::prev(end()));
|
|
}
|
|
|
|
void pop_front() {
|
|
erase(begin());
|
|
}
|
|
|
|
size_t size() const { return size_; }
|
|
|
|
iterator begin() { return iterator(end_->r); }
|
|
iterator end() { return iterator(end_); }
|
|
|
|
const_iterator begin() const { return const_iterator(end_->r); }
|
|
const_iterator end() const { return const_iterator(end_); }
|
|
|
|
const_iterator cbegin() const { return const_iterator(end_->r); }
|
|
const_iterator cend() const { return const_iterator(end_); }
|
|
|
|
reverse_iterator rbegin() { return reverse_iterator(end()); }
|
|
reverse_iterator rend() { return reverse_iterator(begin()); }
|
|
|
|
const_reverse_iterator rbegin() const { return const_reverse_iterator(cend()); }
|
|
const_reverse_iterator rend() const { return const_reverse_iterator(cbegin()); }
|
|
|
|
const_reverse_iterator crbegin() const { return const_reverse_iterator(cend()); }
|
|
const_reverse_iterator crend() const { return const_reverse_iterator(cbegin()); }
|
|
|
|
void insert(const_iterator it, const T& value) {
|
|
Node* tmp = alloc_.allocate(1);
|
|
std::allocator_traits<decltype(alloc_)>::construct(alloc_, tmp, value);
|
|
Link(const_cast<Node*>(std::prev(it).it), tmp);
|
|
++size_;
|
|
}
|
|
|
|
void erase(const_iterator it) {
|
|
Node* tmp = const_cast<Node*>(it.it);
|
|
tmp->l->r = tmp->r;
|
|
tmp->r->l = tmp->l;
|
|
std::allocator_traits<decltype(alloc_)>::destroy(alloc_, tmp);
|
|
alloc_.deallocate(tmp, 1);
|
|
--size_;
|
|
}
|
|
|
|
private:
|
|
|
|
void AllocateEnd() {
|
|
end_ = alloc_.allocate(1);
|
|
end_->l = end_;
|
|
end_->r = end_;
|
|
}
|
|
|
|
void Link(Node* l, Node* x) {
|
|
Node* r = l->r;
|
|
x->l = l;
|
|
x->r = r;
|
|
l->r = x;
|
|
r->l = x;
|
|
}
|
|
|
|
template<bool is_const>
|
|
class base_iterator {
|
|
friend List;
|
|
std::conditional_t<is_const, const Node*, Node*> it;
|
|
using U = std::conditional_t<is_const, const T, T>;
|
|
public:
|
|
|
|
using iterator_category = std::bidirectional_iterator_tag;
|
|
using value_type = U;
|
|
using pointer = U*;
|
|
using reference = U&;
|
|
using difference_type = int;
|
|
|
|
base_iterator() : it(nullptr) {}
|
|
base_iterator(Node* v) { it = v; }
|
|
|
|
base_iterator(const base_iterator&) = default;
|
|
operator base_iterator<true>() { return base_iterator<true>(it); }
|
|
|
|
U& operator*() const { return it->value; }
|
|
U* operator->() const { return &it->value; }
|
|
base_iterator& operator++()& {
|
|
it = it->r;
|
|
return *this;
|
|
}
|
|
base_iterator operator++(int)& {
|
|
base_iterator tmp = *this;
|
|
it = it->r;
|
|
return tmp;
|
|
}
|
|
base_iterator& operator--()& {
|
|
it = it->l;
|
|
return *this;
|
|
}
|
|
base_iterator operator--(int)& {
|
|
base_iterator tmp = *this;
|
|
it = it->l;
|
|
return tmp;
|
|
}
|
|
|
|
friend bool operator==(base_iterator first, base_iterator second) { return first.it == second.it; }
|
|
|
|
friend bool operator!=(base_iterator first, base_iterator second) { return first.it != second.it; }
|
|
|
|
base_iterator& operator=(const base_iterator<false>& another) {
|
|
it = another.it;
|
|
return *this;
|
|
}
|
|
};
|
|
|
|
struct Node {
|
|
Node* l = nullptr;
|
|
Node* r = nullptr;
|
|
T value;
|
|
Node() = default;
|
|
Node(const T& value) : value(value) {}
|
|
Node& operator=(const Node& another) { value = another.value; }
|
|
};
|
|
typename std::allocator_traits<Allocator>::template rebind_alloc<Node> alloc_;
|
|
using alloc_traits_ = std::allocator_traits<decltype(alloc_)>;
|
|
Node* end_ = nullptr;
|
|
size_t size_ = 0;
|
|
};
|