Здравствуйте Vampire, Вы писали:
V>Думал двое суток — недогнал 
Бывает
Почему-то не пришла нотификация по мылу
Конечно, полностью правильного решения не существует, в общем случае указателем может быть что угодно, и не обязательно оно преобразуется к целому типа, итп. Но если брать "обычные" указатели, и рассматривать их как целые чиселки...
Основная мысль: хранить prev ^ next, поскольку head.prev == 0 и tail.next == 0 есть откуда начать вытаскивать информацию... Думайте дальше
Здравствуйте orangy, Вы писали:
O>Задачка для развивающих мозги (взята из "ослов")
O>Написать реализацию двусвязного списка, хранящего ссылки на след. и пред. элементы в одной переменной размера указателя.
O>Подсказка в субже. Интерфейс вобщем-то любой, главное реализовать операции вставки, удаления и что-то вроде итератора.
O>Если это будет STL-like интерфейс — вообще замечательно.
O>Удачи в бою
Вот собственно сам список.
#ifndef _LIST_HPP_
#define _LIST_HPP_
#include <memory>
#include <iterator>
#include <list>
namespace dupamid
{
template<typename T, class A> class list;
template<typename T, class A> struct _ListNode;
template<typename T, class N> class _ListIter;
template<typename T, class A> class _ListBase;
template<typename T, class N>
bool operator==(const _ListIter<T, N>& lhs, const _ListIter<T, N>& rhs);
template<typename T, class N>
bool operator!=(const _ListIter<T, N>& lhs, const _ListIter<T, N>& rhs);
template<typename T, class A>
struct _ListNode
{
typedef typename A::template rebind<_ListNode>::other allocator_type;
typedef typename allocator_type::size_type size_type;
typedef A original_allocator_type;
// если надо поменять надругой целочисленный тип вмещающий указатель
typedef size_type placment_type;
_ListNode(const T& value) : value(value)
{
}
placment_type ptr;
T value;
};
template<typename T, class N>
class _ListIter : std::iterator<std::bidirectional_iterator_tag, T>
{
public:
typedef typename N::placment_type placment_type;
typedef typename T& reference;
typedef typename T* pointer;
_ListIter() : cur(NULL), next(NULL)
{
}
_ListIter& operator++()
{
N* temp = (N*)(next->ptr ^ (placment_type)cur);
cur = next;
next = temp;
return *this;
}
_ListIter& operator--()
{
N* temp = (N*)(cur->ptr ^ (placment_type)next);
next = cur;
cur = temp;
return *this;
}
_ListIter operator++(int)
{
_ListIter ret(cur, next;)
this->operator++();
return ret;
}
_ListIter operator--(int)
{
_ListIter ret(cur, next;)
this->operator--();
return ret;
}
reference operator*() const
{
return cur->value;
}
pointer operator->() const
{
return &cur->value;
}
private:
_ListIter(N* cur, N* next) : cur(cur), next(next)
{
}
friend class list<T, typename N::original_allocator_type>;
friend bool operator==(const _ListIter<T, N>& lhs, const _ListIter<T, N>& rhs);
N* cur;
N* next;
};
template<typename T, class N>
bool operator==(const _ListIter<T, N>& lhs, const _ListIter<T, N>& rhs)
{
return lhs.cur == rhs.cur;
}
template<typename T, class N>
bool operator!=(const _ListIter<T, N>& lhs, const _ListIter<T, N>& rhs)
{
return !operator==(lhs, rhs);
}
template<typename T, class A>
class _ListBase : public _ListNode<T, A>::allocator_type
{
public:
typedef _ListNode<T, A> node_type;
typedef typename node_type::allocator_type allocator_type;
typedef typename node_type::placment_type placment_type;
_ListBase(const A& a) : next((node_type*)&headNode), headNode(0), allocator_type(a)
{
}
~_ListBase()
{
clear();
}
void clear()
{
node_type* prev = (node_type*)&headNode;
node_type* cur = next;
while(cur != (node_type*)&headNode)
{
node_type* temp = (node_type*)(cur->ptr ^ (placment_type)prev);
destroy(cur);
deallocate(cur, 1);
prev = cur;
cur = temp;
}
next = (node_type*)&headNode;
headNode = 0;
}
node_type* next;
placment_type headNode;
};
template<typename T, class A = std::allocator<T> >
class list : private _ListBase<T, A>
{
public:
typedef typename A::reference reference;
typedef typename A::const_reference const_reference;
typedef _ListIter<T, typename _ListBase<T, A>::node_type> iterator;
typedef _ListIter<const T, typename _ListBase<T, A>::node_type> const_iterator;
typedef typename A::size_type size_type;
typedef typename A::difference_type difference_type;
typedef T value_type;
typedef A allocator_type;
typedef typename A::pointer pointer;
typedef typename A::const_pointer const_pointer;
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
explicit list(const A& a = A()) : _ListBase<T, A>(a)
{
}
explicit list(size_type n, const T& value = T(), const A& a = A()) : _ListBase<T, A>(a)
{
assign(n, value);
}
template <class InputIterator>
list(InputIterator first, InputIterator last, const A& a = A()) : _ListBase<T, A>(a)
{
assign(first, last);
}
list(const list<T,A>& x) : _ListBase<T, A>(x.get_allocator())
{
this->operator=(x);
}
~list()
{
}
list<T,A>& operator=(const list<T,A>& x)
{
clear();
insert(begin(), x.begin(), x.end());
return *this;
}
template <class InputIterator>
void assign(InputIterator first, InputIterator last)
{
clear();
insert(begin(), first, last);
}
void assign(size_type n, const T& value)
{
clear();
insert(begin(), n, value);
}
allocator_type get_allocator() const
{
return *this;
}
iterator begin()
{
return iterator(this->next, (typename list::node_type*)(this->next->ptr ^ (typename list::placment_type)&this->headNode));
}
iterator end()
{
return iterator((typename list::node_type*)&this->headNode, this->next);
}
const_iterator begin() const
{
return const_iterator(this->next, (typename list::node_type*)(this->next->ptr ^ (typename list::placment_type)&this->headNode));
}
const_iterator end() const
{
return const_iterator((list::node_type*)&this->headNode, this->next);
}
reverse_iterator rbegin()
{
return reverse_iterator(end());
}
const_reverse_iterator rbegin() const
{
return const_reverse_iterator(end());
}
reverse_iterator rend()
{
return reverse_iterator(begin());
}
const_reverse_iterator rend() const
{
return const_reverse_iterator(begin());
}
bool empty() const
{
return (typename list::node_type*)&this->headNode == this->next;
}
size_type size() const
{
size_type n = 0;
iterator last = end();
for(iterator i = begin(); i != last; ++i) n++;
return n;
}
using _ListBase<T, A>::max_size;
void resize(size_type sz, T c = T())
{
size_type cs = size();
if(cs < sz)
{
iterator pos = end();
while(cs < sz) pos = insert(pos, c), cs++;
}
else
{
while(cs > sz) pop_back(), cs--;
}
}
reference front()
{
return *begin();
}
const_reference front() const
{
return *begin();
}
reference back()
{
return *end();
}
const_reference back() const
{
return *end();
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_front()
{
erase(begin);
}
void push_back(const T& x)
{
insert(end(), x);
}
void pop_back()
{
erase(--end());
}
iterator insert(iterator i, const T& value)
{
typename list::node_type* temp = this->allocate(1);
try
{
this->construct(temp, value);
}
catch(...)
{
this->deallocate(temp, 1);
throw;
}
typename list::node_type* prev = (typename list::node_type*)(i.cur->ptr ^ (typename list::placment_type)i.next);
typename list::node_type* next = i.cur;
temp->ptr = (typename list::placment_type)prev ^ (typename list::placment_type)next;
prev->ptr = (prev->ptr ^ (typename list::placment_type)next) ^ (typename list::placment_type)temp;
next->ptr = (next->ptr ^ (typename list::placment_type)prev) ^ (typename list::placment_type)temp;
if(this->next == next) this->next = temp;
return iterator(temp, next);
}
void insert(iterator position, size_type n, const T& x)
{
for(size_type i = 0; i < n; i++) position = insert(position, x);
}
template <class InputIterator>
void insert(iterator position, InputIterator first, InputIterator last)
{
while(first != last) position = insert(position, *first++);
}
iterator erase(iterator i)
{
typename list::node_type* prev = (typename list::node_type*)(i.cur->ptr ^ (typename list::placment_type)i.next);
typename list::node_type* cur = i.cur;
typename list::node_type* next = i.next;
prev->ptr = (prev->ptr ^ (typename list::placment_type)cur) ^ (typename list::placment_type)next;
next->ptr = (next->ptr ^ (typename list::placment_type)cur) ^ (typename list::placment_type)prev;
this->destroy(cur);
this->deallocate(cur, 1);
if(this->next == cur) this->next = next;
return iterator(next, (typename list::node_type*)(next->ptr ^ (typename list::placment_type)prev));
}
iterator erase(iterator position, iterator last)
{
while(position != last) position = erase(position);
}
void swap(list<T,A>& x)
{
swap(this->next, x.next);
swap(this->headNode, x.headNode);
}
using _ListBase<T, A>::clear;
void splice(iterator position, list<T,A>& x);
void splice(iterator position, list<T,A>& x, iterator i);
void splice(iterator position, list<T,A>& x, iterator first, iterator last);
void remove(const T& value);
template <class Predicate>
void remove_if(Predicate pred);
void unique();
template <class BinaryPredicate>
void unique(BinaryPredicate binary_pred);
void merge(list<T,A>& x);
template <class Compare>
void merge(list<T,A>& x, Compare comp);
void sort();
template <class Compare>
void sort(Compare comp);
void reverse()
{
this->next = (typename list::node_type*)(headNode ^ (typename list::placment_type)this->next);
}
};
}
#endif // _LIST_HPP_
Пример, на котром проверял.
#include <iostream>
#include <crtdbg.h>
#include <list>
#include "List.hpp"
using namespace std;
int main()
{
_CrtSetDbgFlag(_CrtSetDbgFlag(_CRTDBG_REPORT_FLAG) | _CRTDBG_DELAY_FREE_MEM_DF | _CRTDBG_CHECK_ALWAYS_DF | _CRTDBG_LEAK_CHECK_DF);
typedef dupamid::list<int> List;
List li;
List::iterator i = li.begin();
for(int j = 0; j < 1000; j++)
i = li.insert(i, j);
li.reverse();
i = li.begin();
List::iterator end = li.end();
for(; i != end; ++i)
{
i = li.erase(i);
cout << *i << endl;
}
}
Вроде бы работает, но все сделано на скорую руку, так что ошибок может быть сколько угодно
Данный код ни в одном проекте не тестировался и может содржаеть любые ошибки Вы используете этот пример на свой страх и риск.
Не все функции стандартного std::list реализованы, не реализованные функции содержат только объявления. Эффективность класса не бралась в расчет и заведома плоха. Эта реализация list не дает гарантий по безопасности перед лицом исключений, которые требуются Стандартом.
Пример был реализован только ради собственног любопытства для полноценной реализации его нужно много дорабатывать. Как по гарантиям, так и по производительности, плюс надо до-реализовать все функции. Даже если все реализовать как надо то он все равно будет проигрывать стандартной реализации std::list по скорости, и при использовании Стандартного алокатора не будет практически давать выигрыша по памяти, так как ее убьет гранулярность кучи. Достоинтсво класс возможность использовать алокаторы с сотояниями, плюс для стандартного алокатора размер list два указателя, для пустого списка никакой динамической памяти не выделяется.
Исправлены ошибки и просто опечатки, реализованы все функции.
Эффективность все равно плохая (было бы интересно сравинить).
Реализована семантика commit-or-rollback, для всех методов кроме sort, merge и unique для этих методов зависит от предиката сравнения. Работает на MS Visual C++ .NET на 6.0 работать заставить не удалось.
Для не POD элементов список определен не совсем корректно.
Полноценной заменой std::list служит никогда не сможет так как инвалидирует указатели еще и на предыдущий элемент, надо еще учитывать его цикличность, так что может инвалидировать указатель и на первый элемент. Этот недостаток исправить на xor списке нельзя.
#ifndef _LIST_HPP_
#define _LIST_HPP_
#include <memory>
#include <iterator>
namespace dupamid
{
// forward declarations
template<typename T, class A> class xor_list;
template<typename T, class A> struct _ListNode;
template<typename T, class N> class _ListIter;
template<typename T, class N> class _ListConstIter;
template<typename T, class A> class _ListBase;
template<typename T, class N>
bool operator==(const _ListIter<T, N>& lhs, const _ListIter<T, N>& rhs);
template<typename T, class N>
bool operator!=(const _ListIter<T, N>& lhs, const _ListIter<T, N>& rhs);
// node type for xor_list
template<typename T, class A>
struct _ListNode
{
typedef typename A::template rebind<_ListNode>::other allocator_type;
typedef typename allocator_type::size_type size_type;
typedef A original_allocator_type;
// integer type holding pointer, change if not appropriate
typedef size_type placment_type;
_ListNode(const T& value) : value(value)
{
}
_ListNode* other(const _ListNode* p) const
{
return (_ListNode*)(ptr ^ (placment_type)p);
}
void link(const _ListNode* prev, const _ListNode* next)
{
ptr = (placment_type)next ^ (placment_type)prev;
}
placment_type ptr;
T value;
};
// iterator type for xor_list
template<typename T, class N>
class _ListIter : public std::iterator<std::bidirectional_iterator_tag, T>
{
private:
typedef typename N::placment_type placment_type;
typedef typename std::iterator<std::bidirectional_iterator_tag, T> iterator_base;
public:
typedef typename iterator_base::reference reference;
typedef typename iterator_base::pointer pointer;
_ListIter() : cur(NULL), next(NULL)
{
}
_ListIter& operator++()
{
N* temp = next->other(cur);
cur = next;
next = temp;
return *this;
}
_ListIter& operator--()
{
N* temp = cur->other(next);
next = cur;
cur = temp;
return *this;
}
_ListIter operator++(int)
{
_ListIter ret(*this);
this->operator++();
return ret;
}
_ListIter operator--(int)
{
_ListIter ret(*this);
this->operator--();
return ret;
}
reference operator*() const
{
return cur->value;
}
pointer operator->() const
{
return &cur->value;
}
protected:
_ListIter(N* cur, N* next) : cur(cur), next(next)
{
}
friend class xor_list<T, typename N::original_allocator_type>;
friend class _ListConstIter<T, N>;
friend bool operator==(const _ListIter<T, N>& lhs, const _ListIter<T, N>& rhs);
N* cur;
N* next;
};
// const_iterator for xor_list
template<typename T, class N>
class _ListConstIter : public _ListIter<const T, const N>
{
public:
_ListConstIter()
{
}
// for conversion from non const iterator
_ListConstIter(const _ListIter<T, N>& rhs)
: _ListIter<const T, const N>(rhs.cur, rhs.next)
{
}
private:
_ListConstIter(const N* cur, const N* next) : _ListIter<const T, const N>(cur, next)
{
}
friend class xor_list<T, typename N::original_allocator_type>;
};
template<typename T, class N>
bool operator==(const _ListIter<T, N>& lhs, const _ListIter<T, N>& rhs)
{
return lhs.cur == rhs.cur;
}
template<typename T, class N>
bool operator!=(const _ListIter<T, N>& lhs, const _ListIter<T, N>& rhs)
{
return !operator==(lhs, rhs);
}
// base class for xor_list, used for resource managment
template<typename T, class A>
class _ListBase : public _ListNode<T, A>::allocator_type
{
public:
typedef _ListNode<T, A> node_type;
typedef typename node_type::allocator_type base_type;
typedef typename node_type::allocator_type allocator_type;
typedef typename node_type::placment_type placment_type;
_ListBase(const A& a) : next((node_type*)&headNode), headNode(0), allocator_type(a)
{
}
~_ListBase()
{
clear();
}
node_type* head() const
{
return (node_type*)&headNode;
}
void clear()
{
node_type* prev = head();
node_type* cur = next;
while(cur != (node_type*)&headNode)
{
node_type* temp = cur->other(prev);
base_type::destroy(cur);
base_type::deallocate(cur, 1);
prev = cur;
cur = temp;
}
next = head();
headNode = 0;
}
node_type* next;
placment_type headNode;
};
template<class T>
struct _Empty_allocator_warp : public std::allocator<T>
{
template<class U>
struct rebind
{
typedef _Empty_allocator_warp<U> other;
};
_Empty_allocator_warp()
{
}
template<class U>
_Empty_allocator_warp(const _Empty_allocator_warp<U>& rhs)
: std::allocator<T>(rhs)
{
}
_Empty_allocator_warp& operator=(const _Empty_allocator_warp&)
{
return*this;
}
template<class U>
_Empty_allocator_warp& operator=(const _Empty_allocator_warp<U>&)
{
return*this;
}
};
// xor_list - double linked list with xor pointers storage
// insert/erase invalidate iterators on processed and previous nodes
template<typename T, class A = _Empty_allocator_warp<T> >
class xor_list : private _ListBase<T, A>
{
private:
typedef _ListBase<T, A> base_type;
typedef typename base_type::node_type node_type;
typedef typename base_type::placment_type placment_type;
using base_type::next;
using base_type::headNode;
public:
typedef typename A::reference reference;
typedef typename A::const_reference const_reference;
typedef _ListIter<T, typename _ListBase<T, A>::node_type> iterator;
typedef _ListConstIter<T, typename _ListBase<T, A>::node_type> const_iterator;
typedef typename A::size_type size_type;
typedef typename A::difference_type difference_type;
typedef T value_type;
typedef A allocator_type;
typedef typename A::pointer pointer;
typedef typename A::const_pointer const_pointer;
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
explicit xor_list(const A& a = A()) : base_type(a)
{
}
explicit xor_list(size_type n, const T& value = T(), const A& a = A()) : base_type(a)
{
iterator first = begin();
for(size_type i = 0; i < n; i++) first = ++insert(first, value);
}
template<class InputIterator>
xor_list(InputIterator first, InputIterator last, const A& a = A()) : base_type(a)
{
iterator first2 = begin();
while(first != last) first2 = ++insert(first2, *first++);
}
xor_list(const xor_list& x) : base_type(x.get_allocator())
{
iterator first = x.begin();
iterator last = x.end();
iterator first2 = begin();
while(first != last) first2 = ++insert(first2, *first++);
}
xor_list& operator=(const xor_list& x)
{
xor_list temp(x);
swap(temp);
return *this;
}
template<class InputIterator>
void assign(InputIterator first, InputIterator last)
{
xor_list temp(first, last, get_allocator());
swap(temp);
}
void assign(size_type n, const T& value)
{
xor_list temp(n, value, get_allocator());
swap(temp);
}
allocator_type get_allocator() const
{
return *this;
}
iterator begin()
{
return iterator(next, next->other(base_type::head()));
}
iterator end()
{
return iterator(base_type::head(), next);
}
const_iterator begin() const
{
return const_iterator(next, next->other(base_type::head()));
}
const_iterator end() const
{
return const_iterator(base_type::head(), next);
}
reverse_iterator rbegin()
{
return reverse_iterator(end());
}
reverse_iterator rend()
{
return reverse_iterator(begin());
}
const_reverse_iterator rbegin() const
{
return const_reverse_iterator(end());
}
const_reverse_iterator rend() const
{
return const_reverse_iterator(begin());
}
bool empty() const
{
return base_type::head() == next;
}
size_type size() const
{
size_type n = 0;
const_iterator last = end();
for(const_iterator i = begin(); i != last; ++i) n++;
return n;
}
using base_type::max_size;
void resize(size_type sz, const T& value = T())
{
size_type cs = size();
if(cs < sz)
{
xor_list temp(sz - cs, value);
splice(end(), temp);
}
else
{
while(cs > sz) pop_back(), cs--;
}
}
reference front()
{
return *begin();
}
const_reference front() const
{
return *begin();
}
reference back()
{
return *--end();
}
const_reference back() const
{
return *--end();
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_front()
{
erase(begin());
}
void push_back(const T& x)
{
insert(end(), x);
}
void pop_back()
{
erase(--end());
}
iterator insert(iterator i, const T& value)
{
node_type* temp = base_type::allocate(1);
try
{
base_type::construct(temp, value);
}
catch(...)
{
base_type::deallocate(temp, 1);
throw;
}
node_type* prev = i.cur->other(i.next);
node_type* next = i.cur;
temp->link(prev, next);
prev->link(prev->other(next), temp);
next->link(next->other(prev), temp);
if(base_type::next == next) base_type::next = temp;
return iterator(temp, next);
}
void insert(iterator position, size_type n, const T& x)
{
xor_list temp(n, x, get_allocator());
splice(position, temp);
}
template<class InputIterator>
void insert(iterator position, InputIterator first, InputIterator last)
{
xor_list temp(first, last, get_allocator());
splice(position, temp);
}
iterator erase(iterator i)
{
node_type* prev = i.cur->other(i.next);
node_type* cur = i.cur;
node_type* next = i.next;
prev->link(prev->other(cur), next);
next->link(next->other(cur), prev);
base_type::destroy(cur);
base_type::deallocate(cur, 1);
if(base_type::next == cur) base_type::next = next;
return iterator(next, next->other(prev));
}
iterator erase(iterator position, iterator last)
{
while(position != last) position = erase(position);
return position;
}
void swap(xor_list& x)
{
std::swap((typename base_type::base_type&)*this, (typename base_type::base_type&)x);
node_type* prev = base_type::head()->other(base_type::next);
node_type* next = base_type::next;
node_type* prevx = x.head()->other(x.next);
node_type* nextx = x.next;
std::swap(base_type::headNode, x.headNode);
if(next == base_type::head()) x.next = x.head();
else
{
x.next = next;
prev->link(prev->other(base_type::head()), x.head());
next->link(next->other(base_type::head()), x.head());
}
if(nextx == x.head()) base_type::next = base_type::head();
else
{
base_type::next = nextx;
prevx->link(prevx->other(x.head()), base_type::head());
nextx->link(nextx->other(x.head()), base_type::head());
}
}
using _ListBase<T, A>::clear;
void splice(iterator position, xor_list& x)
{
splice(position, x, x.begin(), x.end());
}
void splice(iterator position, xor_list& x, iterator i)
{
iterator temp = i;
splice(position, x, i, ++temp);
}
void splice(iterator position, xor_list& x, iterator first, iterator last)
{
if(first == last) return;
if(x.get_allocator() == get_allocator())
{
iterator temp = last;
--temp;
node_type* prev = first.cur->other(first.next);
node_type* next = last.cur;
prev->link(prev->other(first.cur), next);
next->link(prev, last.next);
if(x.next == first.cur) x.next = next;
if(empty())
{
base_type::head()->link(first.cur, temp.cur);
first.cur->link(base_type::head(), first.next);
temp.cur->link(temp.cur->other(temp.next), base_type::head());
base_type::next = first.cur;
}
else
{
prev = position.cur->other(position.next);
next = position.cur;
prev->link(prev->other(next), first.cur);
first.cur->link(prev, first.next);
next->link(position.next, temp.cur);
temp.cur->link(temp.cur->other(temp.next), next);
if(base_type::next == position.cur) base_type::next = first.cur;
}
}
else
{
xor_list temp(first, last, get_allocator());
splice(position, temp, temp.begin(), temp.end());
x.erase(first, last);
}
}
void remove(const T& value)
{
iterator last = end();
for(iterator i = begin(); i != last; ++i)
if(*i == value) i = erase(i);
}
template <class Predicate>
void remove_if(Predicate pred)
{
iterator last = end();
for(iterator i = begin(); i != last; ++i)
if(pred(*i)) i = erase(i);
}
void unique()
{
iterator first = begin();
iterator second = ++begin();
iterator last = end();
while(second != last)
{
if(*first == *second)
{
second = erase(second);
continue;
}
first = second;
++second;
}
}
template <class BinaryPredicate>
void unique(BinaryPredicate binary_pred)
{
iterator first = begin();
iterator second = ++begin();
iterator last = end();
while(second != last)
{
if(binary_pred(*first, *second))
{
second = erase(second);
continue;
}
first = second;
++second;
}
}
void merge(xor_list& x)
{
iterator first1 = begin();
iterator last1 = end();
iterator first2 = x.begin();
iterator last2 = x.end();
while(first1 != last1 && first2 != last2)
if(*first2 < *first1)
{
iterator temp = first2;
++temp;
splice(first1, x, first2);
first2 = temp;
}
else ++first1;
if(first2 != last2) splice(end(), x);
}
template <class Compare>
void merge(xor_list& x, Compare comp)
{
iterator first1 = begin();
iterator last1 = end();
iterator first2 = x.begin();
iterator last2 = x.end();
while(first1 != last1 && first2 != last2)
if(comp(*first2, *first1))
{
iterator temp = first2;
++temp;
splice(first1, x, first2);
first2 = temp;
}
else ++first1;
if(first2 != last2) splice(end(), x);
}
void sort()
{
if(base_type::next != base_type::head() &&
base_type::next->other(base_type::head()) != base_type::head())
{
xor_list carry;
xor_list counter[64];
int fill = 0;
while(!empty())
{
carry.splice(carry.begin(), *this, begin());
int i = 0;
while(i < fill && !counter[i].empty())
{
counter[i].merge(carry);
carry.swap(counter[i++]);
}
carry.swap(counter[i]);
if(i == fill) ++fill;
}
for(int i = 1; i < fill; i++)
counter[i].merge(counter[i-1]);
swap(counter[fill-1]);
}
}
template <class Compare>
void sort(Compare comp)
{
if(base_type::next != base_type::head() &&
base_type::next->other(base_type::head()) != base_type::head())
{
xor_list carry;
xor_list counter[64];
int fill = 0;
while(!empty())
{
carry.splice(carry.begin(), *this, begin());
int i = 0;
while(i < fill && !counter[i].empty())
{
counter[i].merge(carry, comp);
carry.swap(counter[i++]);
}
carry.swap(counter[i]);
if(i == fill) ++fill;
}
for(int i = 1; i < fill; i++)
counter[i].merge(counter[i-1], comp);
swap(counter[fill-1]);
}
}
void reverse()
{
next = base_type::head()->other(next);
}
};
}
#endif // _LIST_HPP_
Один из примеров тестирования:
#include <iostream>
#include <functional>
#include "List.hpp"
using namespace std;
template<class L>
void print(const L& l, const char* str = "")
{
cout << "----------" << str << "----------" << endl;
typename L::const_iterator last = l.end();
for(typename L::const_iterator i = l.begin(); i != last; ++i)
cout << *i << endl;
}
template<class L>
void test_sort(L& l)
{
print(l, "before sort");
l.sort(greater<int>());
print(l, "after sort");
}
int main()
{
typedef dupamid::xor_list<int> ListInt;
int a[] = { 10, 9, 8, 7, -5, 6, 5, 4, 3, 2, 1 };
ListInt l(a, a + sizeof(a)/sizeof(a[0]));
test_sort(l);
}
