#define _LIBCXX_LIST_
#include <cstddef>
+#include "allocator"
+#include "stdexcept"
+#include "utility"
namespace std {
namespace _bits {
-template <class T> class list_iterator;
+template <class ListType, class T> class list_iterator;
template <class T> class list_item;
}
-template <class T>
+template <class T, class Alloc = allocator<T> >
class list
{
- friend class ::std::_bits::list_iterator<T>;
-
typedef ::std::_bits::list_item<T> item_type;
+ typedef ::std::_bits::list_item<const T> const_item_type;
+ friend class ::std::_bits::list_iterator<list, T>;
+
+ typedef typename Alloc::template rebind<item_type>::other item_allocator;
+public:
+ typedef T value_type;
+ typedef Alloc allocator_type;
+ typedef typename allocator_type::reference reference;
+ typedef typename allocator_type::const_reference const_reference;
+ typedef typename allocator_type::pointer pointer;
+ typedef typename allocator_type::const_pointer const_pointer;
+ typedef _bits::list_iterator<list,T> iterator;
+ typedef _bits::list_iterator<list,const T> const_iterator;
+ typedef int difference_type;
+ typedef size_t size_type;
+
+private:
+ item_allocator m_item_allocator;
+ allocator_type m_allocator;
item_type *m_start;
item_type *m_end;
+ size_type m_item_count;
+
public:
- typedef T value_type;
- typedef value_type& reference;
- typedef const value_type& const_reference;
- typedef _bits::list_iterator<value_type> iterator;
- typedef _bits::list_iterator<const value_type> const_iterator;
-
- list():
+ list(const allocator_type& alloc = allocator_type()):
+ m_item_allocator(),
+ m_allocator(alloc),
m_start(0), m_end(0)
{
}
- list(size_t n, const value_type& val = value_type());
+ list(size_t n, const value_type& val = value_type(), const allocator_type& alloc = allocator_type()):
+ list()
+ {
+ assign(n, val);
+ }
list(const list& x);
~list() {
clear();
list& operator =(const list& x);
iterator begin() {
- return iterator(m_start);
+ return iterator(*this, m_start);
}
const_iterator begin() const {
- return const_iterator(m_start);
+ return const_iterator(*this, m_start);
}
iterator end() {
- return iterator(0);
+ return iterator(*this, 0);
}
const_iterator end() const {
- return const_iterator(0);
+ return const_iterator(*this, 0);
}
bool empty() const {
return !m_start;
}
- size_t size() const;
- size_t max_size() const;
+ size_t size() const {
+ return m_item_count;
+ }
+ size_t max_size() const {
+ return (size_type)-1 / sizeof(item_type);
+ }
- T& front();
- const T& front() const;
- T& back();
- const T& back() const;
+ T& front() {
+ return m_start->value;
+ }
+ const T& front() const {
+ return m_start->value;
+ }
+ T& back() {
+ return m_end->value;
+ }
+ const T& back() const {
+ return m_end->value;
+ }
+
+ void assign(size_type n, const value_type& val) {
+ clear();
+ for( size_t i = 0; i < n; i ++ )
+ {
+ push_back(val);
+ }
+ }
+
+ void push_front(const value_type& val) {
+ insert(front(), val);
+ }
+ void pop_front() {
+ erase(front());
+ }
+ void push_back(const value_type& val) {
+ insert(end(), val);
+ }
+ void pop_back() {
+ erase(end());
+ }
+
+ template <class... Args>
+ iterator emplace(iterator position, Args&&... args) {
+ item_type *newi = m_item_allocator.allocate(1);
+ m_allocator.construct(&newi->value, ::std::forward<Args>(args)...);
+ return insert_item(position, newi);
+ }
+
+ iterator insert(iterator position, const value_type& val) {
+ item_type *newi = m_item_allocator.allocate(1);
+ m_allocator.construct(&newi->value, val);
+ return insert_item(position, newi);
+ }
+ void insert(iterator position, size_type n, const value_type& val) {
+ for( size_type i = 0; i < n; i ++ )
+ {
+ position = insert(position, val);
+ }
+ }
+ iterator erase(iterator position) {
+ if( position == end() ) {
+ }
+ else {
+ item_type *oldi = position.m_cur;
+ ++ position;
+
+ if(oldi->prev)
+ oldi->prev->next = oldi->next;
+ else
+ m_start = oldi->next;
+ if(oldi->next)
+ oldi->next->prev = oldi->prev;
+ else
+ m_end = oldi->prev;
+
+ m_item_count --;
+ m_allocator.destroy(&oldi->value);
+ m_item_allocator.deallocate(oldi, 1);
+ }
+ return position;
+ }
void clear() {
while( m_start ) {
m_start = m_start->next;
delete item;
}
+ m_item_count = 0;
+ }
+
+ void splice(iterator position, list& x) {
+ splice(position, x, x.begin(), x.end());
+ }
+ void splice(iterator position, list& x, iterator i) {
+ splice(position, x, i, x.end());
+ }
+ void splice(iterator position, list& x, iterator first, iterator last);
+
+private:
+ class _equal
+ {
+ const value_type& m_val;
+ public:
+ _equal(const value_type& val):
+ m_val(val)
+ {
+ };
+ bool operator() (const value_type& v1)
+ {
+ return m_val == v1;
+ }
+ };
+public:
+ void remove(const value_type& val) {
+ remove_if(_equal(val));
+ }
+ template <class Predicate> void remove_if(Predicate pred) {
+ for( iterator it = begin(); it != end(); )
+ {
+ if( pred(*it) )
+ it = erase(it);
+ else
+ ++ it;
+ }
+ }
+
+ void unique();
+ template <class BinaryPredicate> void unique(BinaryPredicate binary_pred);
+
+ void merge(list& x);
+ template <class Compare> void merge(list& x, Compare comp);
+
+ void sort();
+ template <class Compare> void sort(Compare comp);
+
+ void reverse() throw();
+private:
+ iterator insert_item(iterator position, item_type *newi) {
+ m_item_count ++;
+ if( m_start == 0 ) {
+ newi->next = 0;
+ newi->prev = m_end;
+ m_start = newi;
+ m_end = newi;
+ return end();
+ }
+ if( position == end() ) {
+ newi->next = 0;
+ newi->prev = m_end;
+ //assert(m_end);
+ m_end->next = newi;
+ m_end = newi;
+ }
+ else if( position == begin() ) {
+ newi->next = m_start;
+ newi->prev = 0;
+ //assert(m_start);
+ m_start->prev = newi;
+ m_start = newi;
+ }
+ else {
+ newi->prev = position.m_cur->prev;
+ newi->next = position.m_cur;
+ position.m_cur->prev->next = newi;
+ position.m_cur->prev = newi;
+ }
+ return ++iterator(*this, newi);
}
};
template <class T>
struct list_item
{
+ typedef T value_type;
list_item<T> *next;
list_item<T> *prev;
- T value;
+ value_type value;
};
-template <class T>
+template <class ListType, class T>
class list_iterator//:
//public bidirectional_iterator_tag;
{
- friend class list<T>;
-
- list_item<T> *cur;
+ const ListType* m_list;
+ list_item<T> *m_cur;
+ friend ListType;
public:
+ list_iterator(const list_iterator& x):
+ m_list(x.m_list),
+ m_cur (x.m_cur)
+ {
+ }
+ list_iterator& operator=(const list_iterator& x) {
+ m_list = x.m_list;
+ m_cur = x.m_cur;
+ }
+
bool operator == (const list_iterator& other) const {
- return cur == other.cur;
+ return m_cur == other.m_cur;
}
bool operator != (const list_iterator& other) const {
- return cur != other.cur;
+ return !(*this == other);
}
T& operator * () {
- return cur->value;
+ return m_cur->value;
}
T& operator -> () {
- return cur->value;
+ return m_cur->value;
}
list_iterator& operator ++ () {
- cur = cur->next;
+ if(!m_cur)
+ throw ::std::logic_error("list iterator ++ on end");
+ m_cur = m_cur->next;
+ return *this;
}
list_iterator& operator -- () {
- cur = cur->prev;
+ if( m_cur == m_list->m_start )
+ throw ::std::logic_error("list iterator -- on start");
+ if(!m_cur)
+ m_cur = m_list->m_end;
+ else
+ m_cur = m_cur->prev;
+ return *this;
}
-
+
private:
- list_iterator(list_item<T> *item):
- cur(item)
+ list_iterator(const ListType& list, list_item<T> *item):
+ m_list(&list),
+ m_cur(item)
{
}
};
git.ucc.asn.au / tpg / acess2.git / blobdiff
UCC git Repository :: git.ucc.asn.au