その論文を読んでいなくても、
set::insertset次の前にアクセスする場合は、おそらくデータを追加する最も効率的な方法です。insert- 一方、セットを一度に作成する場合は、
vectorとを使用するのが最善ですsort。
- ベクター要素に次へのポインターを追加すると、並べ替えられたベクターからの削除は簡単です。
- 初期化し
next = NULLます。の場合next == NULL、要素は有効です (削除されていません)。
- 削除するには、 を設定し
next = this+1ます。
- 次に取得するには、ベクトル要素を から
this+1最初の要素 whereまで反復処理しiter->next != iter+1ます。それでif ( iter->next == NULL ) return iter; else return iter->next;
- 償却された定数時間を達成するため
(this+1)->next = iter (or) iter->nextに前に更新してください。return
- で最後にガード要素を追加し
next == thisます。これは、 ではなくvector::end、シーケンスの終わりを示します。
これが最初のドラフトです。私はそれをコーディングしました。未検証; 自由に編集するか、wiki にするよう私に依頼してください。または、バグを教えてください... これ以上の時間を費やすことは保証できません。clearソートされたバージョンでの実装は完了していません。並べerase替えられたオブジェクトを破棄しません。sorted_skip_arrayが破壊されるまで、それは起こりません。
#include <vector>
template< class T, class Alloc >
class skip_array_base {
protected:
struct node {
node *prev, *next;
T val;
node( T const &x = T() ) : prev(), next(), val(x) {}
};
typedef typename Alloc::template rebind< node >::other allocator_type;
typedef std::vector< node, allocator_type > vector_type;
typedef typename vector_type::iterator vector_iterator;
vector_type v;
skip_array_base( allocator_type const &a = allocator_type() ) : v( a ) {}
skip_array_base( skip_array_base const &in ) : v( in.v ) {}
skip_array_base( typename vector_type::size_type s,
typename vector_type::value_type const &x, allocator_type const &a )
: v( s, x, a ) {}
template< class Tcv >
struct iter : vector_iterator {
typedef T value_type;
typedef Tcv &reference;
typedef Tcv *pointer;
iter() {}
iter( vector_iterator const &in )
: vector_iterator( in ) {}
reference operator*() { return vector_iterator::operator*().val; }
pointer operator->() { return &vector_iterator::operator*().val; }
reference operator[]( typename vector_iterator::difference_type n )
{ return vector_iterator::operator[]( n ).val; }
iter &operator++() { vector_iterator::operator++(); return *this; }
iter operator++(int) { return vector_iterator::operator++(0); }
iter &operator--() { vector_iterator::operator--(); return *this; }
iter operator--(int) { return vector_iterator::operator--(0); }
iter &operator+=( typename vector_iterator::difference_type n )
{ vector_iterator::operator+=( n ); return *this; }
iter operator+( typename vector_iterator::difference_type n )
{ return vector_iterator::operator+( n ); }
iter &operator-=( typename vector_iterator::difference_type n )
{ vector_iterator::operator-=( n ); return *this; }
iter operator-( typename vector_iterator::difference_type n )
{ return vector_iterator::operator-( n ); }
};
public:
typedef typename vector_type::size_type size_type;
void swap( skip_array_base &r ) { v.swap( r.v ); }
skip_array_base &operator=( skip_array_base const &x ) {
v = x.v;
return *this;
}
size_type size() const { return v.size() - 2; }
size_type max_size() const { return v.max_size() - 2; }
bool empty() const { return v.size() > 2; }
bool operator== ( skip_array_base const &r ) const { return v == r.v; }
bool operator!= ( skip_array_base const &r ) const { return v != r.v; }
bool operator< ( skip_array_base const &r ) const { return v < r.v; }
bool operator> ( skip_array_base const &r ) const { return v > r.v; }
bool operator<= ( skip_array_base const &r ) const { return v <= r.v; }
bool operator>= ( skip_array_base const &r ) const { return v >= r.v; }
void clear() { v.erase( ++ v.begin(), -- v.end() ); }
};
template< class T, class Alloc >
class sorted_skip_array;
template< class T, class Alloc = std::allocator<T> >
class skip_array_prelim : public skip_array_base< T, Alloc > {
typedef skip_array_base< T, Alloc > base;
typedef typename base::vector_type vector_type;
using skip_array_base< T, Alloc >::v;
public:
typedef T value_type;
typedef typename Alloc::reference reference;
typedef typename Alloc::const_reference const_reference;
typedef typename base::template iter< value_type > iterator;
typedef typename base::template iter< const value_type > const_iterator;
typedef typename vector_type::difference_type difference_type;
typedef typename vector_type::size_type size_type;
typedef typename vector_type::allocator_type allocator_type;
skip_array_prelim( allocator_type const &a = allocator_type() )
: base( 2, value_type(), a ) {}
skip_array_prelim( skip_array_prelim const &in )
: base( in ) {}
skip_array_prelim( size_type s, value_type const &x = value_type(),
allocator_type const &a = allocator_type() )
: base( s + 2, x, a ) {}
template< class I >
skip_array_prelim( I first, I last,
allocator_type const &a = allocator_type(),
typename I::pointer = typename I::pointer() )
: base( 1, value_type(), a ) {
v.insert( v.end(), first, last );
v.push_back( value_type() );
}
iterator begin() { return ++ v.begin(); }
iterator end() { return -- v.end(); }
const_iterator begin() const { return ++ v.begin(); }
const_iterator end() const { return -- v.end(); }
reference operator[]( size_type n ) { return v[ n + 1 ]; }
const_reference operator[]( size_type n ) const { return v[ n + 1 ]; }
iterator insert( iterator pos, value_type const &x )
{ return v.insert( pos, x ); }
iterator insert( iterator pos, size_type n, value_type const &x )
{ return v.insert( pos, n, x ); }
template< class I >
iterator insert( iterator pos, I first, I last,
typename I::pointer = typename I::pointer() )
{ return v.insert( pos, first, last ); }
iterator erase( iterator i ) { return v.erase( i ); }
iterator erase( iterator first, iterator last )
{ return v.erase( first, last ); }
};
template< class T, class Alloc = std::allocator<T> >
class sorted_skip_array : public skip_array_base< T, Alloc > {
typedef skip_array_base< T, Alloc > base;
typedef typename base::vector_type vector_type;
typedef typename vector_type::iterator vector_iterator;
typedef typename base::node node;
using skip_array_base< T, Alloc >::v;
template< class Tcv >
struct iter : base::template iter< Tcv > {
typedef std::bidirectional_iterator_tag iterator_category;
typedef Tcv &reference;
typedef Tcv *pointer;
iter() {}
iter( vector_iterator const &x ) : base::template iter< Tcv >( x ) {}
iter &operator++() { increment< &node::next, 1 >(); return *this; }
iter operator++(int)
{ iter r = *this; increment< &node::next, 1 >(); return r; }
iter &operator--() { increment< &node::prev, -1 >(); return *this; }
iter operator--(int)
{ iter r = *this; increment< &node::prev, -1 >(); return r; }
private:
template< node *node::*link, int inc >
void increment() {
vector_iterator memo = *this; // un-consts a const_iterator
node *pen = &*( memo += inc );
while ( pen->*link && pen->*link != pen ) pen = pen->*link;
*this = iter( vector_iterator( (*memo).*link = pen ) );
}
};
public:
typedef T value_type;
typedef typename Alloc::reference reference;
typedef typename Alloc::const_reference const_reference;
typedef iter< T > iterator;
typedef iter< const T > const_iterator;
typedef typename vector_type::difference_type difference_type;
typedef typename vector_type::size_type size_type;
sorted_skip_array( skip_array_prelim<T,Alloc> &x ) {
sort( x.begin(), x.end() );
swap( x );
}
iterator begin() { return ++ iterator( v.begin() ); }
iterator end() { return iterator( -- v.end() ); }
const_iterator begin() const { return ++ const_iterator( v.begin() ); }
const_iterator end() const { return const_iterator( -- v.end() ); }
iterator erase( iterator i ) {
vector_iterator vi = i;
vi->prev = &* vi[-1];
vi->next = &* vi[1];
//vi->val->~value_type(); // don't bother with allocator rigmarole
return ++ i;
}
iterator erase( iterator first, iterator last ) {
if ( first != last ) {
vector_iterator vf = first, vl = last - 1;
vl->prev = &* vf[-1];
vf->next = &* vl[1];
}
return last;
}
};