blob: 327e259f84fde389c93b14d6f49f86a761744c60 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
|
// Copyright Jean Pierre Cimalando 2018.
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE or copy at
// http://www.boost.org/LICENSE_1_0.txt)
#ifndef PL_LIST_HPP
#define PL_LIST_HPP
#include <iterator>
#include <cstddef>
/*
pl_cell: the linked list cell
*/
template <class T>
struct pl_cell;
template <class T>
struct pl_basic_cell
{
pl_cell<T> *prev, *next;
};
template <class T>
struct pl_cell : pl_basic_cell<T>
{
T value;
};
/*
pl_iterator: the linked list iterator
*/
template <class Cell>
class pl_iterator
{
public:
typedef std::bidirectional_iterator_tag iterator_category;
typedef Cell value_type;
typedef Cell &reference;
typedef Cell *pointer;
typedef std::ptrdiff_t difference_type;
pl_iterator(Cell *cell = NULL);
bool is_end() const;
Cell &operator*() const;
Cell *operator->() const;
bool operator==(const pl_iterator &i) const;
bool operator!=(const pl_iterator &i) const;
pl_iterator &operator++();
pl_iterator operator++(int);
pl_iterator &operator--();
pl_iterator operator--(int);
private:
Cell *cell_;
};
/*
pl_list: the preallocated linked list
*/
template <class T>
class pl_list
{
public:
typedef pl_cell<T> value_type;
typedef value_type *pointer;
typedef value_type &reference;
typedef const value_type *const_pointer;
typedef const value_type &const_reference;
typedef pl_iterator< pl_cell<T> > iterator;
typedef pl_iterator< const pl_cell<T> > const_iterator;
pl_list(std::size_t capacity = 0);
~pl_list();
pl_list(const pl_list &other);
pl_list &operator=(const pl_list &other);
std::size_t size() const;
std::size_t capacity() const;
bool empty() const;
iterator begin();
iterator end();
const_iterator begin() const;
const_iterator end() const;
void clear();
pl_cell<T> &front();
const pl_cell<T> &front() const;
pl_cell<T> &back();
const pl_cell<T> &back() const;
iterator insert(iterator pos, const T &x);
iterator erase(iterator pos);
void push_front(const T &x);
void push_back(const T &x);
void pop_front();
void pop_back();
iterator find(const T &x);
const_iterator find(const T &x) const;
template <class Pred> iterator find_if(const Pred &p);
template <class Pred> const_iterator find_if(const Pred &p) const;
private:
// number of cells in the list
std::size_t size_;
// number of cells allocated
std::size_t capacity_;
// array of cells allocated
pl_cell<T> *cells_;
// pointer to the head cell
pl_cell<T> *first_;
// pointer to the next free cell
pl_cell<T> *free_;
// value-less cell which terminates the linked list
pl_basic_cell<T> endcell_;
void initialize(std::size_t capacity);
pl_cell<T> *allocate(pl_cell<T> *pos);
void deallocate(pl_cell<T> *cell);
};
#include "pl_list.tcc"
#endif // PL_LIST_HPP
|