42 template<
typename T>
class list {
44 static const int64_t
null = -1;
51 cell(): next(null), prev(null) {}
68 cells[free].next =
null;
70 used_cells_tail = free;
80 used_cells_tail = cells.size() - 1;
85 if (cells[used_cells_tail].prev != null)
87 if (used_cells_head == null)
99 cells[free].prev =
null;
100 used_cells_head = free;
110 used_cells_head = cells.size() - 1;
115 if (cells[used_cells_head].next != null)
117 if (used_cells_tail == null)
124 if (cells[c].prev != null)
125 cells[cells[c].prev].next = cells[c].next;
127 used_cells_head = cells[c].next;
128 if (cells[c].next != null)
129 cells[cells[c].next].prev = cells[c].prev;
131 used_cells_tail = cells[c].prev;
139 int64_t next = cells[c].next;
144 list(): used_cells_head(null), used_cells_tail(null), free_cells(null), used_cell_count(0), free_cell_count(0) {}
154 used_cells_head = used_cells_tail = free_cells =
null;
155 used_cell_count = free_cell_count = 0;
168 if (free_cell_count) {
189 if (free_cell_count) {
208 return _cell == i.
_cell;
211 return _cell != i.
_cell;
283 return iterator(
this, used_cells_head);
286 return const_iterator(
this, used_cells_head);
288 const_iterator &
end()
const {
292 return iterator(
this,
_erase(i._cell));
294 const_iterator
erase(const_iterator &i) {
295 return const_iterator(
this,
_erase(i._cell));
300 void remove(
const T &t) {
302 const_iterator i(
this, used_cells_head);
320 template<
typename T>
typename list<T>::const_iterator list<T>::end_iterator;
void __erase(int64_t c)
Definition: list.h:122
const_iterator & end() const
Definition: list.h:288
_iterator()
Definition: list.h:205
std::vector< cell > cells
Definition: list.h:54
void push_front_free_cell(const T &t)
Definition: list.h:92
iterator & operator++()
Definition: list.h:267
const_iterator()
Definition: list.h:223
int64_t _cell
Definition: list.h:203
int64_t free_cells
Definition: list.h:58
const_iterator(const list *l, int64_t c)
Definition: list.h:221
const T * operator->() const
Definition: list.h:227
T & front()
Definition: list.h:312
void reserve(uint64_t size)
Definition: list.h:149
void push_front_new_cell(const T &t)
Definition: list.h:103
const_iterator begin() const
Definition: list.h:285
void push_back(const T &t)
Definition: list.h:158
void update_used_cells_head_state()
Definition: list.h:113
void erase(int64_t c)
Definition: list.h:297
void update_used_cells_tail_state()
Definition: list.h:83
iterator & operator=(const iterator &i)
Definition: list.h:272
const_iterator erase(const_iterator &i)
Definition: list.h:294
const_iterator & operator=(const const_iterator &i)
Definition: list.h:235
void push_back_new_cell(const T &t)
Definition: list.h:73
list()
Definition: list.h:144
uint64_t used_cell_count
Definition: list.h:59
void push_front(const T &t)
Definition: list.h:179
int64_t next
Definition: list.h:48
int64_t _erase(int64_t c)
Definition: list.h:137
T data
Definition: list.h:50
void push_front(const T &t, int64_t &location)
Definition: list.h:187
iterator begin()
Definition: list.h:282
iterator()
Definition: list.h:260
list * _list
Definition: list.h:257
uint64_t size() const
Definition: list.h:146
cell()
Definition: list.h:51
bool operator==(const _iterator &i) const
Definition: list.h:207
const list * _list
Definition: list.h:220
uint64_t free_cell_count
Definition: list.h:60
const T & operator*() const
Definition: list.h:224
static const_iterator end_iterator
Definition: list.h:280
int64_t prev
Definition: list.h:49
const_iterator & operator++()
Definition: list.h:230
int64_t used_cells_tail
Definition: list.h:57
iterator erase(iterator &i)
Definition: list.h:291
int64_t used_cells_head
Definition: list.h:56
T & operator*() const
Definition: list.h:261
void push_back_free_cell(const T &t)
Definition: list.h:62
T * operator->() const
Definition: list.h:264
iterator(list *l, int64_t c)
Definition: list.h:258
T & back()
Definition: list.h:315
_iterator(int64_t c)
Definition: list.h:204
static const int64_t null
Definition: list.h:44
void push_back(const T &t, int64_t &location)
Definition: list.h:166
void clear()
Definition: list.h:152
bool operator!=(const _iterator &i) const
Definition: list.h:210