vector.h

Go to the documentation of this file.

/***************************************************************************
 *  include/stxxl/bits/containers/vector.h
 *
 *  Part of the STXXL. See http://stxxl.sourceforge.net
 *
 *  Copyright (C) 2002-2008 Roman Dementiev <[email protected]>
 *  Copyright (C) 2007-2009 Johannes Singler <[email protected]>
 *  Copyright (C) 2008-2010 Andreas Beckmann <[email protected]>
 *  Copyright (C) 2013 Timo Bingmann <[email protected]>
 *
 *  Distributed under the Boost Software License, Version 1.0.
 *  (See accompanying file LICENSE_1_0.txt or copy at
 *  http://www.boost.org/LICENSE_1_0.txt)
 **************************************************************************/

#ifndef STXXL_CONTAINERS_VECTOR_HEADER
#define STXXL_CONTAINERS_VECTOR_HEADER

#include <vector>
#include <queue>
#include <algorithm>

#include <stxxl/bits/deprecated.h>
#include <stxxl/bits/io/request_operations.h>
#include <stxxl/bits/mng/block_manager.h>
#include <stxxl/bits/mng/typed_block.h>
#include <stxxl/bits/common/tmeta.h>
#include <stxxl/bits/containers/pager.h>
#include <stxxl/bits/common/is_sorted.h>
#include <stxxl/bits/mng/buf_istream.h>
#include <stxxl/bits/mng/buf_istream_reverse.h>
#include <stxxl/bits/mng/buf_ostream.h>

STXXL_BEGIN_NAMESPACE

#define STXXL_VERBOSE_VECTOR(msg) STXXL_VERBOSE1("vector[" << static_cast<const void*>(this) << "]::" << msg)

//! \defgroup stlcont Containers
//! \ingroup stllayer
//! Containers with STL-compatible interface

//! \defgroup stlcont_vector vector
//! \ingroup stlcont
//! Vector and support classes
//! \{

template <typename SizeType, SizeType modulo2, SizeType modulo1>
class double_blocked_index
{
    typedef SizeType size_type;

    static const size_type modulo12 = modulo1 * modulo2;

    size_type pos;
    unsigned_type block1, block2, offset;

    //! \invariant block2 * modulo12 + block1 * modulo1 + offset == pos && 0 <= block1 &lt; modulo2 && 0 <= offset &lt; modulo1

    void set(size_type pos)
    {
        this->pos = pos;
        block2 = (int_type)(pos / modulo12);
        pos -= block2 * modulo12;
        block1 = (int_type)(pos / modulo1);
        offset = (int_type)(pos - block1 * modulo1);

        assert(block2 * modulo12 + block1 * modulo1 + offset == this->pos);
        assert(/* 0 <= block1 && */ block1 < modulo2);
        assert(/* 0 <= offset && */ offset < modulo1);
    }

public:
    double_blocked_index()
    {
        set(0);
    }

    double_blocked_index(size_type pos)
    {
        set(pos);
    }

    double_blocked_index(unsigned_type block2, unsigned_type block1, unsigned_type offset)
    {
        assert(/* 0 <= block1 && */ block1 < modulo2);
        assert(/* 0 <= offset && */ offset < modulo1);

        this->block2 = block2;
        this->block1 = block1;
        this->offset = offset;
        pos = block2 * modulo12 + block1 * modulo1 + offset;
    }

    double_blocked_index& operator = (size_type pos)
    {
        set(pos);
        return *this;
    }

    //pre-increment operator
    double_blocked_index& operator ++ ()
    {
        ++pos;
        ++offset;
        if (offset == modulo1)
        {
            offset = 0;
            ++block1;
            if (block1 == modulo2)
            {
                block1 = 0;
                ++block2;
            }
        }

        assert(block2 * modulo12 + block1 * modulo1 + offset == this->pos);
        assert(/* 0 <= block1 && */ block1 < modulo2);
        assert(/* 0 <= offset && */ offset < modulo1);

        return *this;
    }

    //post-increment operator
    double_blocked_index operator ++ (int)
    {
        double_blocked_index former(*this);
        operator ++ ();
        return former;
    }

    //pre-increment operator
    double_blocked_index& operator -- ()
    {
        --pos;
        if (offset == 0)
        {
            offset = modulo1;
            if (block1 == 0)
            {
                block1 = modulo2;
                --block2;
            }
            --block1;
        }
        --offset;

        assert(block2 * modulo12 + block1 * modulo1 + offset == this->pos);
        assert(/*0 <= block1 &&*/ block1 < modulo2);
        assert(/*0 <= offset &&*/ offset < modulo1);

        return *this;
    }

    //post-increment operator
    double_blocked_index operator -- (int)
    {
        double_blocked_index former(*this);
        operator -- ();
        return former;
    }

    double_blocked_index operator + (size_type addend) const
    {
        return double_blocked_index(pos + addend);
    }

    double_blocked_index& operator += (size_type addend)
    {
        set(pos + addend);
        return *this;
    }

    double_blocked_index operator - (size_type addend) const
    {
        return double_blocked_index(pos - addend);
    }

    size_type operator - (const double_blocked_index& dbi2) const
    {
        return pos - dbi2.pos;
    }

    double_blocked_index& operator -= (size_type subtrahend)
    {
        set(pos - subtrahend);
        return *this;
    }

    bool operator == (const double_blocked_index& dbi2) const
    {
        return pos == dbi2.pos;
    }

    bool operator != (const double_blocked_index& dbi2) const
    {
        return pos != dbi2.pos;
    }

    bool operator < (const double_blocked_index& dbi2) const
    {
        return pos < dbi2.pos;
    }

    bool operator <= (const double_blocked_index& dbi2) const
    {
        return pos <= dbi2.pos;
    }

    bool operator > (const double_blocked_index& dbi2) const
    {
        return pos > dbi2.pos;
    }

    bool operator >= (const double_blocked_index& dbi2) const
    {
        return pos >= dbi2.pos;
    }

    double_blocked_index& operator >>= (size_type shift)
    {
        set(pos >> shift);
        return *this;
    }

    size_type get_pos() const
    {
        return pos;
    }

    const unsigned_type & get_block2() const
    {
        return block2;
    }

    const unsigned_type & get_block1() const
    {
        return block1;
    }

    const unsigned_type & get_offset() const
    {
        return offset;
    }
};

////////////////////////////////////////////////////////////////////////////

template <
    typename ValueType,
    unsigned PageSize,
    typename PagerType,
    unsigned BlockSize,
    typename AllocStr,
    typename SizeType>
class vector;

template <typename ValueType, typename AllocStr, typename SizeType, typename DiffType,
          unsigned BlockSize, typename PagerType, unsigned PageSize>
class const_vector_iterator;

template <typename VectorIteratorType>
class vector_bufreader;

template <typename VectorIteratorType>
class vector_bufreader_reverse;

template <typename VectorIteratorType>
class vector_bufwriter;

////////////////////////////////////////////////////////////////////////////

//! External vector iterator, model of \c ext_random_access_iterator concept.
template <typename ValueType, typename AllocStr, typename SizeType, typename DiffType,
          unsigned BlockSize, typename PagerType, unsigned PageSize>
class vector_iterator
{
    typedef vector_iterator<ValueType, AllocStr, SizeType,
                            DiffType, BlockSize, PagerType, PageSize> self_type;

    typedef const_vector_iterator<ValueType, AllocStr, SizeType,
                                  DiffType, BlockSize, PagerType, PageSize> const_self_type;

    friend class const_vector_iterator<ValueType, AllocStr, SizeType,
                                       DiffType, BlockSize, PagerType, PageSize>;

public:
    //! \name Types
    //! \{

    typedef self_type iterator;
    typedef const_self_type const_iterator;

    typedef unsigned block_offset_type;
    typedef vector<ValueType, PageSize, PagerType, BlockSize, AllocStr, SizeType> vector_type;
    friend class vector<ValueType, PageSize, PagerType, BlockSize, AllocStr, SizeType>;
    typedef typename vector_type::bids_container_type bids_container_type;
    typedef typename bids_container_type::iterator bids_container_iterator;
    typedef typename bids_container_type::bid_type bid_type;
    typedef typename vector_type::block_type block_type;
    typedef typename vector_type::blocked_index_type blocked_index_type;

    typedef std::random_access_iterator_tag iterator_category;
    typedef typename vector_type::size_type size_type;
    typedef typename vector_type::difference_type difference_type;
    typedef typename vector_type::value_type value_type;
    typedef typename vector_type::reference reference;
    typedef typename vector_type::const_reference const_reference;
    typedef typename vector_type::pointer pointer;
    typedef typename vector_type::const_pointer const_pointer;

    //! \}

protected:
    blocked_index_type offset;
    vector_type* p_vector;

private:
    //! private constructor for initializing other iterators
    vector_iterator(vector_type* v, size_type o)
        : offset(o), p_vector(v)
    { }

public:
    //! constructs invalid iterator
    vector_iterator()
        : offset(0), p_vector(NULL)
    { }
    //! copy-constructor
    vector_iterator(const self_type& a)
        : offset(a.offset),
          p_vector(a.p_vector)
    { }

    //! \name Iterator Properties
    //! \{

    //! return pointer to vector containing iterator
    vector_type * parent_vector() const
    {
        return p_vector;
    }
    //! return block offset of current element
    block_offset_type block_offset() const
    {
        return static_cast<block_offset_type>(offset.get_offset());
    }
    //! return iterator to BID containg current element
    bids_container_iterator bid() const
    {
        return p_vector->bid(offset);
    }

    //! \}

    //! \name Access Operators
    //! \{

    //! return current element
    reference operator * ()
    {
        return p_vector->element(offset);
    }
    //! return pointer to current element
    pointer operator -> ()
    {
        return &(p_vector->element(offset));
    }
    //! return const reference to current element
    const_reference operator * () const
    {
        return p_vector->const_element(offset);
    }
    //! return const pointer to current element
    const_pointer operator -> () const
    {
        return &(p_vector->const_element(offset));
    }
    //! return mutable reference to element +i after the current element
    reference operator [] (size_type i)
    {
        return p_vector->element(offset.get_pos() + i);
    }

#ifdef _LIBCPP_VERSION
    //-tb 2013-11: libc++ defines std::reverse_iterator::operator[] in such a
    // way that it expects vector_iterator::operator[] to return a (mutable)
    // reference. Thus to remove confusion about the compiler error, we remove
    // the operator[] const for libc++. The const_reference actually violates
    // some version of the STL standard, but works well in gcc's libstdc++.
#else
    //! return const reference to element +i after the current element
    const_reference operator [] (size_type i) const
    {
        return p_vector->const_element(offset.get_pos() + i);
    }
#endif
    //! \}

    //! \name Relative Calculation of Iterators
    //! \{

    //! calculate different between two iterator
    difference_type operator - (const self_type& a) const
    {
        return offset - a.offset;
    }
    //! calculate different between two iterator
    difference_type operator - (const const_self_type& a) const
    {
        return offset - a.offset;
    }
    //! return iterator advanced -i positions in the vector
    self_type operator - (size_type i) const
    {
        return self_type(p_vector, offset.get_pos() - i);
    }
    //! return iterator advanced +i positions in the vector
    self_type operator + (size_type i) const
    {
        return self_type(p_vector, offset.get_pos() + i);
    }
    //! advance this iterator -i positions in the vector
    self_type& operator -= (size_type i)
    {
        offset -= i;
        return *this;
    }
    //! advance this iterator +i positions in the vector
    self_type& operator += (size_type i)
    {
        offset += i;
        return *this;
    }
    //! advance this iterator to next position in the vector
    self_type& operator ++ ()
    {
        offset++;
        return *this;
    }
    //! advance this iterator to next position in the vector
    self_type operator ++ (int)
    {
        self_type tmp = *this;
        offset++;
        return tmp;
    }
    //! advance this iterator to preceding position in the vector
    self_type& operator -- ()
    {
        offset--;
        return *this;
    }
    //! advance this iterator to preceding position in the vector
    self_type operator -- (int)
    {
        self_type tmp = *this;
        offset--;
        return tmp;
    }

    //! \}

    //! \name Comparison Operators
    //! \{

    bool operator == (const self_type& a) const
    {
        assert(p_vector == a.p_vector);
        return offset == a.offset;
    }
    bool operator != (const self_type& a) const
    {
        assert(p_vector == a.p_vector);
        return offset != a.offset;
    }
    bool operator < (const self_type& a) const
    {
        assert(p_vector == a.p_vector);
        return offset < a.offset;
    }
    bool operator <= (const self_type& a) const
    {
        assert(p_vector == a.p_vector);
        return offset <= a.offset;
    }
    bool operator > (const self_type& a) const
    {
        assert(p_vector == a.p_vector);
        return offset > a.offset;
    }
    bool operator >= (const self_type& a) const
    {
        assert(p_vector == a.p_vector);
        return offset >= a.offset;
    }

    bool operator == (const const_self_type& a) const
    {
        assert(p_vector == a.p_vector);
        return offset == a.offset;
    }
    bool operator != (const const_self_type& a) const
    {
        assert(p_vector == a.p_vector);
        return offset != a.offset;
    }
    bool operator < (const const_self_type& a) const
    {
        assert(p_vector == a.p_vector);
        return offset < a.offset;
    }
    bool operator <= (const const_self_type& a) const
    {
        assert(p_vector == a.p_vector);
        return offset <= a.offset;
    }
    bool operator > (const const_self_type& a) const
    {
        assert(p_vector == a.p_vector);
        return offset > a.offset;
    }
    bool operator >= (const const_self_type& a) const
    {
        assert(p_vector == a.p_vector);
        return offset >= a.offset;
    }

    //! \}

    //! \name Flushing Operation
    //! \{

    void block_externally_updated()
    {
        p_vector->block_externally_updated(offset);
    }

    void flush()
    {
        p_vector->flush();
    }

    //! \}
};

////////////////////////////////////////////////////////////////////////////

//! Const external vector iterator, model of \c ext_random_access_iterator concept.
template <typename ValueType, typename AllocStr, typename SizeType, typename DiffType,
          unsigned BlockSize, typename PagerType, unsigned PageSize>
class const_vector_iterator
{
    typedef const_vector_iterator<ValueType, AllocStr, SizeType, DiffType,
                                  BlockSize, PagerType, PageSize> self_type;

    typedef vector_iterator<ValueType, AllocStr, SizeType, DiffType,
                            BlockSize, PagerType, PageSize> mutable_self_type;

    friend class vector_iterator<ValueType, AllocStr, SizeType, DiffType,
                                 BlockSize, PagerType, PageSize>;

public:
    //! \name Types
    //! \{

    typedef self_type const_iterator;
    typedef mutable_self_type iterator;

    typedef unsigned block_offset_type;
    typedef vector<ValueType, PageSize, PagerType, BlockSize, AllocStr, SizeType> vector_type;
    friend class vector<ValueType, PageSize, PagerType, BlockSize, AllocStr, SizeType>;
    typedef typename vector_type::bids_container_type bids_container_type;
    typedef typename bids_container_type::iterator bids_container_iterator;
    typedef typename bids_container_type::bid_type bid_type;
    typedef typename vector_type::block_type block_type;
    typedef typename vector_type::blocked_index_type blocked_index_type;

    typedef std::random_access_iterator_tag iterator_category;
    typedef typename vector_type::size_type size_type;
    typedef typename vector_type::difference_type difference_type;
    typedef typename vector_type::value_type value_type;
    typedef typename vector_type::const_reference reference;
    typedef typename vector_type::const_reference const_reference;
    typedef typename vector_type::const_pointer pointer;
    typedef typename vector_type::const_pointer const_pointer;

    //! \}

protected:
    blocked_index_type offset;
    const vector_type* p_vector;

private:
    //! private constructor for initializing other iterators
    const_vector_iterator(const vector_type* v, size_type o)
        : offset(o), p_vector(v)
    { }

public:
    //! constructs invalid iterator
    const_vector_iterator()
        : offset(0), p_vector(NULL)
    { }
    //! copy-constructor
    const_vector_iterator(const self_type& a)
        : offset(a.offset), p_vector(a.p_vector)
    { }
    //! copy-constructor from mutable iterator
    const_vector_iterator(const mutable_self_type& a)
        : offset(a.offset), p_vector(a.p_vector)
    { }

    //! \name Iterator Properties
    //! \{

    //! return pointer to vector containing iterator
    const vector_type * parent_vector() const
    {
        return p_vector;
    }
    //! return block offset of current element
    block_offset_type block_offset() const
    {
        return static_cast<block_offset_type>(offset.get_offset());
    }
    //! return iterator to BID containg current element
    bids_container_iterator bid() const
    {
        return ((vector_type*)p_vector)->bid(offset);
    }

    //! \}

    //! \name Access Operators
    //! \{

    //! return current element
    const_reference operator * () const
    {
        return p_vector->const_element(offset);
    }
    //! return pointer to current element
    const_pointer operator -> () const
    {
        return &(p_vector->const_element(offset));
    }
    //! return const reference to element +i after the current element
    const_reference operator [] (size_type i) const
    {
        return p_vector->const_element(offset.get_pos() + i);
    }

    //! \}

    //! \name Relative Calculation of Iterators
    //! \{

    //! calculate different between two iterator
    difference_type operator - (const self_type& a) const
    {
        return offset - a.offset;
    }
    //! calculate different between two iterator
    difference_type operator - (const mutable_self_type& a) const
    {
        return offset - a.offset;
    }
    //! return iterator advanced -i positions in the vector
    self_type operator - (size_type i) const
    {
        return self_type(p_vector, offset.get_pos() - i);
    }
    //! return iterator advanced +i positions in the vector
    self_type operator + (size_type i) const
    {
        return self_type(p_vector, offset.get_pos() + i);
    }
    //! advance this iterator -i positions in the vector
    self_type& operator -= (size_type i)
    {
        offset -= i;
        return *this;
    }
    //! advance this iterator +i positions in the vector
    self_type& operator += (size_type i)
    {
        offset += i;
        return *this;
    }
    //! advance this iterator to next position in the vector
    self_type& operator ++ ()
    {
        offset++;
        return *this;
    }
    //! advance this iterator to next position in the vector
    self_type operator ++ (int)
    {
        self_type tmp_ = *this;
        offset++;
        return tmp_;
    }
    //! advance this iterator to preceding position in the vector
    self_type& operator -- ()
    {
        offset--;
        return *this;
    }
    //! advance this iterator to preceding position in the vector
    self_type operator -- (int)
    {
        self_type tmp = *this;
        offset--;
        return tmp;
    }

    //! \}

    //! \name Comparison Operators
    //! \{

    bool operator == (const self_type& a) const
    {
        assert(p_vector == a.p_vector);
        return offset == a.offset;
    }
    bool operator != (const self_type& a) const
    {
        assert(p_vector == a.p_vector);
        return offset != a.offset;
    }
    bool operator < (const self_type& a) const
    {
        assert(p_vector == a.p_vector);
        return offset < a.offset;
    }
    bool operator <= (const self_type& a) const
    {
        assert(p_vector == a.p_vector);
        return offset <= a.offset;
    }
    bool operator > (const self_type& a) const
    {
        assert(p_vector == a.p_vector);
        return offset > a.offset;
    }
    bool operator >= (const self_type& a) const
    {
        assert(p_vector == a.p_vector);
        return offset >= a.offset;
    }

    bool operator == (const mutable_self_type& a) const
    {
        assert(p_vector == a.p_vector);
        return offset == a.offset;
    }
    bool operator != (const mutable_self_type& a) const
    {
        assert(p_vector == a.p_vector);
        return offset != a.offset;
    }
    bool operator < (const mutable_self_type& a) const
    {
        assert(p_vector == a.p_vector);
        return offset < a.offset;
    }
    bool operator <= (const mutable_self_type& a) const
    {
        assert(p_vector == a.p_vector);
        return offset <= a.offset;
    }
    bool operator > (const mutable_self_type& a) const
    {
        assert(p_vector == a.p_vector);
        return offset > a.offset;
    }
    bool operator >= (const mutable_self_type& a) const
    {
        assert(p_vector == a.p_vector);
        return offset >= a.offset;
    }

    //! \}

    //! \name Flushing Operation
    //! \{

    void block_externally_updated()
    {
        p_vector->block_externally_updated(offset);
    }

    void flush()
    {
        p_vector->flush();
    }

    //! \}
};

////////////////////////////////////////////////////////////////////////////

//! External vector container. \n
//! <b>Introduction</b> to vector container: see \ref tutorial_vector tutorial. \n
//! <b>Design and Internals</b> of vector container: see \ref design_vector
//!
//! For semantics of the methods see documentation of the STL std::vector
//! \tparam ValueType type of contained objects (POD with no references to internal memory)
//! \tparam PageSize number of blocks in a page
//! \tparam PagerType pager type, \c random_pager<x> or \c lru_pager<x>, where x is the default number of pages,
//!  default is \c lru_pager<8>
//! \tparam BlockSize external block size in bytes, default is 2 MiB
//! \tparam AllocStr one of allocation strategies: \c striping , \c RC , \c SR , or \c FR
//!  default is RC
//!
//! Memory consumption: BlockSize*x*PageSize bytes
//! \warning Do not store references to the elements of an external vector. Such references
//! might be invalidated during any following access to elements of the vector
template <
    typename ValueType,
    unsigned PageSize = 4,
    typename PagerType = lru_pager<8>,
    unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType),
    typename AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY,
    typename SizeType = stxxl::uint64       // will be deprecated soon
    >
class vector
{
public:
    //! \name Standard Types
    //! \{

    //! The type of elements stored in the vector.
    typedef ValueType value_type;
    //! reference to value_type
    typedef value_type& reference;
    //! constant reference to value_type
    typedef const value_type& const_reference;
    //! pointer to value_type
    typedef value_type* pointer;
    //! constant pointer to value_type
    typedef const value_type* const_pointer;
    //! an unsigned 64-bit integral type
    typedef SizeType size_type;
    typedef stxxl::int64 difference_type;

    typedef PagerType pager_type;
    typedef AllocStr alloc_strategy_type;

    enum constants {
        block_size = BlockSize,
        page_size = PageSize,
        on_disk = -1
    };

    //! iterator used to iterate through a vector, see \ref design_vector_notes.
    typedef vector_iterator<value_type, alloc_strategy_type, size_type,
                            difference_type, block_size, pager_type, page_size> iterator;
    friend class vector_iterator<value_type, alloc_strategy_type, size_type, difference_type, block_size, pager_type, page_size>;

    //! constant iterator used to iterate through a vector, see \ref design_vector_notes.
    typedef const_vector_iterator<value_type, alloc_strategy_type,
                                  size_type, difference_type, block_size, pager_type, page_size> const_iterator;
    friend class const_vector_iterator<value_type, alloc_strategy_type, size_type, difference_type, block_size, pager_type, page_size>;
    typedef std::reverse_iterator<iterator> reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

    //! \}

    //! \name Extra Types
    //! \{

    //! vector_bufwriter compatible with this vector
    typedef vector_bufwriter<iterator> bufwriter_type;

    //! vector_bufreader compatible with this vector
    typedef vector_bufreader<const_iterator> bufreader_type;

    //! vector_bufreader compatible with this vector
    typedef vector_bufreader_reverse<const_iterator> bufreader_reverse_type;

    //! \internal
    class bid_vector : public std::vector<BID<block_size> >
    {
    public:
        typedef std::vector<BID<block_size> > super_type;
        typedef typename super_type::size_type size_type;
        typedef typename super_type::value_type bid_type;

        bid_vector(size_type sz) : super_type(sz)
        { }
    };

    typedef bid_vector bids_container_type;
    typedef typename bids_container_type::iterator bids_container_iterator;
    typedef typename bids_container_type::const_iterator const_bids_container_iterator;

    //! type of the block used in disk-memory transfers
    typedef typed_block<BlockSize, ValueType> block_type;
    //! double-index type to reference individual elements in a block
    typedef double_blocked_index<SizeType, PageSize, block_type::size> blocked_index_type;

    //! \}

private:
    alloc_strategy_type m_alloc_strategy;
    size_type m_size;
    bids_container_type m_bids;
    mutable pager_type m_pager;

    // enum specifying status of a page of the vector
    enum { valid_on_disk = 0, uninitialized = 1, dirty = 2 };
    //! status of each page (valid_on_disk, uninitialized or dirty)
    mutable std::vector<unsigned char> m_page_status;
    mutable std::vector<int_type> m_page_to_slot;
    mutable simple_vector<int_type> m_slot_to_page;
    mutable std::queue<int_type> m_free_slots;
    mutable simple_vector<block_type>* m_cache;
    file* m_from;
    block_manager* m_bm;
    bool m_exported;

    size_type size_from_file_length(stxxl::uint64 file_length) const
    {
        stxxl::uint64 blocks_fit = file_length / stxxl::uint64(block_type::raw_size);
        size_type cur_size = blocks_fit * stxxl::uint64(block_type::size);
        stxxl::uint64 rest = file_length - blocks_fit * stxxl::uint64(block_type::raw_size);
        return (cur_size + rest / stxxl::uint64(sizeof(value_type)));
    }

    stxxl::uint64 file_length() const
    {
        typedef stxxl::uint64 file_size_type;
        size_type cur_size = size();
        size_type num_full_blocks = cur_size / block_type::size;
        if (cur_size % block_type::size != 0)
        {
            size_type rest = cur_size - num_full_blocks * block_type::size;
            return file_size_type(num_full_blocks) * block_type::raw_size + rest * sizeof(value_type);
        }
        return file_size_type(num_full_blocks) * block_type::raw_size;
    }

public:
    //! \name Constructors/Destructors
    //! \{

    //! Constructs external vector with n elements.
    //!
    //! \param n Number of elements.
    //! \param npages Number of cached pages.
    vector(size_type n = 0, unsigned_type npages = pager_type().size())
        : m_size(n),
          m_bids((size_t)div_ceil(n, block_type::size)),
          m_pager(npages),
          m_page_status(div_ceil(m_bids.size(), page_size)),
          m_page_to_slot(div_ceil(m_bids.size(), page_size)),
          m_slot_to_page(npages),
          m_cache(NULL),
          m_from(NULL),
          m_exported(false)
    {
        m_bm = block_manager::get_instance();

        allocate_page_cache();

        for (size_t i = 0; i < m_page_status.size(); ++i)
        {
            m_page_status[i] = uninitialized;
            m_page_to_slot[i] = on_disk;
        }

        for (unsigned_type i = 0; i < numpages(); ++i)
            m_free_slots.push(i);

        m_bm->new_blocks(m_alloc_strategy, m_bids.begin(), m_bids.end(), 0);
    }

    //! \}

    //! \name Modifier
    //! \{

    //! swap content
    void swap(vector& obj)
    {
        std::swap(m_alloc_strategy, obj.m_alloc_strategy);
        std::swap(m_size, obj.m_size);
        std::swap(m_bids, obj.m_bids);
        std::swap(m_pager, obj.m_pager);
        std::swap(m_page_status, obj.m_page_status);
        std::swap(m_page_to_slot, obj.m_page_to_slot);
        std::swap(m_slot_to_page, obj.m_slot_to_page);
        std::swap(m_free_slots, obj.m_free_slots);
        std::swap(m_cache, obj.m_cache);
        std::swap(m_from, obj.m_from);
        std::swap(m_exported, obj.m_exported);
    }

    //! \}

    //! \name Miscellaneous
    //! \{

    //! Allocate page cache, must be called to allow access to elements.
    void allocate_page_cache() const
    {
        //  numpages() might be zero
        if (!m_cache && numpages() > 0)
            m_cache = new simple_vector<block_type>(numpages() * page_size);
    }

    //! allows to free the cache, but you may not access any element until call
    //! allocate_page_cache() again
    void deallocate_page_cache() const
    {
        flush();
        delete m_cache;
        m_cache = NULL;
    }

    //! \name Size and Capacity
    //! \{

    //! return the size of the vector.
    size_type size() const
    {
        return m_size;
    }
    //! true if the vector's size is zero.
    bool empty() const
    {
        return (!m_size);
    }

    //! Return the number of elelemtsn for which \a external memory has been
    //! allocated. capacity() is always greator than or equal to size().
    size_type capacity() const
    {
        return size_type(m_bids.size()) * block_type::size;
    }
    //! Returns the number of bytes that the vector has allocated on disks.
    size_type raw_capacity() const
    {
        return size_type(m_bids.size()) * block_type::raw_size;
    }

    /*! Reserves at least n elements in external memory.
     *
     * If n is less than or equal to capacity(), this call has no
     * effect. Otherwise, it is a request for allocation of additional \b
     * external memory. If the request is successful, then capacity() is
     * greater than or equal to n; otherwise capacity() is unchanged. In either
     * case, size() is unchanged.
     */
    void reserve(size_type n)
    {
        if (n <= capacity())
            return;

        unsigned_type old_bids_size = m_bids.size();
        unsigned_type new_bids_size = (unsigned_type)div_ceil(n, block_type::size);
        unsigned_type new_pages = div_ceil(new_bids_size, page_size);
        m_page_status.resize(new_pages, uninitialized);
        m_page_to_slot.resize(new_pages, on_disk);

        m_bids.resize(new_bids_size);
        if (m_from == NULL)
        {
            m_bm->new_blocks(m_alloc_strategy,
                             m_bids.begin() + old_bids_size, m_bids.end(),
                             old_bids_size);
        }
        else
        {
            size_type offset = size_type(old_bids_size) * size_type(block_type::raw_size);
            for (bids_container_iterator it = m_bids.begin() + old_bids_size;
                 it != m_bids.end(); ++it, offset += size_type(block_type::raw_size))
            {
                (*it).storage = m_from;
                (*it).offset = offset;
            }
            STXXL_VERBOSE_VECTOR("reserve(): Changing size of file " <<
                                 ((void*)m_from) << " to " << offset);
            m_from->set_size(offset);
        }
    }

    //! Resize vector contents to n items.
    //! \warning this will not call the constructor of objects in external memory!
    void resize(size_type n)
    {
        _resize(n);
    }

    //! Resize vector contents to n items, and allow the allocated external
    //! memory to shrink. Internal memory allocation remains unchanged.
    //! \warning this will not call the constructor of objects in external memory!
    void resize(size_type n, bool shrink_capacity)
    {
        if (shrink_capacity)
            _resize_shrink_capacity(n);
        else
            _resize(n);
    }

    //! \}

private:
    //! Resize vector, only allow capacity growth.
    void _resize(size_type n)
    {
        reserve(n);
        if (n < m_size) {
            // mark excess pages as uninitialized and evict them from cache
            unsigned_type first_page_to_evict = (unsigned_type)div_ceil(n, block_type::size * page_size);
            for (size_t i = first_page_to_evict; i < m_page_status.size(); ++i) {
                if (m_page_to_slot[i] != on_disk) {
                    m_free_slots.push(m_page_to_slot[i]);
                    m_page_to_slot[i] = on_disk;
                }
                m_page_status[i] = uninitialized;
            }
        }
        m_size = n;
    }

    //! Resize vector, also allow reduction of external memory capacity.
    void _resize_shrink_capacity(size_type n)
    {
        unsigned_type old_bids_size = m_bids.size();
        unsigned_type new_bids_size = (unsigned_type)div_ceil(n, block_type::size);

        if (new_bids_size > old_bids_size)
        {
            reserve(n);
        }
        else if (new_bids_size < old_bids_size)
        {
            unsigned_type new_pages_size = div_ceil(new_bids_size, page_size);

            STXXL_VERBOSE_VECTOR("shrinking from " << old_bids_size << " to " <<
                                 new_bids_size << " blocks = from " <<
                                 m_page_status.size() << " to " <<
                                 new_pages_size << " pages");

            // release blocks
            if (m_from != NULL)
                m_from->set_size(new_bids_size * block_type::raw_size);
            else
                m_bm->delete_blocks(m_bids.begin() + old_bids_size, m_bids.end());

            m_bids.resize(new_bids_size);

            // don't resize m_page_to_slot or m_page_status, because it is
            // still needed to check page status and match the mapping
            // m_slot_to_page

            // clear dirty flag, so these pages will be never written
            std::fill(m_page_status.begin() + new_pages_size,
                      m_page_status.end(), (unsigned char)valid_on_disk);
        }

        m_size = n;
    }

public:
    //! \name Modifiers
    //! \{

    //! Erases all of the elements and deallocates all external memory that is
    //! occupied.
    void clear()
    {
        m_size = 0;
        if (m_from == NULL)
            m_bm->delete_blocks(m_bids.begin(), m_bids.end());

        m_bids.clear();
        m_page_status.clear();
        m_page_to_slot.clear();
        while (!m_free_slots.empty())
            m_free_slots.pop();

        for (unsigned_type i = 0; i < numpages(); ++i)
            m_free_slots.push(i);
    }

    //! \name Front and Back Access
    //! \{

    //! Append a new element at the end.
    void push_back(const_reference obj)
    {
        size_type old_size = m_size;
        resize(old_size + 1);
        element(old_size) = obj;
    }
    //! Removes the last element (without returning it, see back()).
    void pop_back()
    {
        resize(m_size - 1);
    }

    //! \}

    //! \name Operators
    //! \{

    //! Returns a reference to the last element, see \ref design_vector_notes.
    reference back()
    {
        return element(m_size - 1);
    }
    //! Returns a reference to the first element, see \ref design_vector_notes.
    reference front()
    {
        return element(0);
    }
    //! Returns a constant reference to the last element, see \ref design_vector_notes.
    const_reference back() const
    {
        return const_element(m_size - 1);
    }
    //! Returns a constant reference to the first element, see \ref design_vector_notes.
    const_reference front() const
    {
        return const_element(0);
    }

    //! \}

    //! \name Constructors/Destructors
    //! \{

    //! Construct vector from a file.
    //! \param from file to be constructed from
    //! \param size Number of elements.
    //! \param npages Number of cached pages.
    //! \warning Only one \c vector can be assigned to a particular (physical) file.
    //! The block size of the vector must be a multiple of the element size
    //! \c sizeof(ValueType) and the page size (4096).
    vector(file* from, size_type size = size_type(-1), unsigned_type npages = pager_type().size())
        : m_size((size == size_type(-1)) ? size_from_file_length(from->size()) : size),
          m_bids((size_t)div_ceil(m_size, size_type(block_type::size))),
          m_pager(npages),
          m_page_status(div_ceil(m_bids.size(), page_size)),
          m_page_to_slot(div_ceil(m_bids.size(), page_size)),
          m_slot_to_page(npages),
          m_cache(NULL),
          m_from(from),
          m_exported(false)
    {
        // initialize from file
        if (!block_type::has_only_data)
        {
            std::ostringstream str;
            str << "The block size for a vector that is mapped to a file must be a multiple of the element size (" <<
                sizeof(value_type) << ") and the page size (4096).";
            throw std::runtime_error(str.str());
        }

        m_bm = block_manager::get_instance();

        allocate_page_cache();

        for (size_t i = 0; i < m_page_status.size(); ++i)
        {
            m_page_status[i] = valid_on_disk;
            m_page_to_slot[i] = on_disk;
        }

        for (unsigned_type i = 0; i < numpages(); ++i)
            m_free_slots.push(i);

        // allocate blocks equidistantly and in-order
        size_type offset = 0;
        for (bids_container_iterator it = m_bids.begin();
             it != m_bids.end(); ++it, offset += size_type(block_type::raw_size))
        {
            (*it).storage = from;
            (*it).offset = offset;
        }
        from->set_size(offset);
    }

    //! copy-constructor
    vector(const vector& obj)
        : m_size(obj.size()),
          m_bids((size_t)div_ceil(obj.size(), block_type::size)),
          m_pager(obj.numpages()),
          m_page_status(div_ceil(m_bids.size(), page_size)),
          m_page_to_slot(div_ceil(m_bids.size(), page_size)),
          m_slot_to_page(obj.numpages()),
          m_cache(NULL),
          m_from(NULL),
          m_exported(false)
    {
        assert(!obj.m_exported);
        m_bm = block_manager::get_instance();

        allocate_page_cache();

        for (size_t i = 0; i < m_page_status.size(); ++i)
        {
            m_page_status[i] = uninitialized;
            m_page_to_slot[i] = on_disk;
        }

        for (unsigned_type i = 0; i < numpages(); ++i)
            m_free_slots.push(i);

        m_bm->new_blocks(m_alloc_strategy, m_bids.begin(), m_bids.end(), 0);

        const_iterator inbegin = obj.begin();
        const_iterator inend = obj.end();
        std::copy(inbegin, inend, begin());
    }

    //! \}

    //! \name Operators
    //! \{

    //! assignment operator
    vector& operator = (const vector& obj)
    {
        if (&obj != this)
        {
            vector tmp(obj);
            this->swap(tmp);
        }
        return *this;
    }

    //! \}

    //! \name Iterator Construction
    //! \{

    //! returns an iterator pointing to the beginning of the vector, see \ref design_vector_notes.
    iterator begin()
    {
        return iterator(this, 0);
    }
    //! returns a const_iterator pointing to the beginning of the vector, see \ref design_vector_notes.
    const_iterator begin() const
    {
        return const_iterator(this, 0);
    }
    //! returns a const_iterator pointing to the beginning of the vector, see \ref design_vector_notes.
    const_iterator cbegin() const
    {
        return begin();
    }
    //! returns an iterator pointing beyond the end of the vector, see \ref design_vector_notes.
    iterator end()
    {
        return iterator(this, m_size);
    }
    //! returns a const_iterator pointing beyond the end of the vector, see \ref design_vector_notes.
    const_iterator end() const
    {
        return const_iterator(this, m_size);
    }
    //! returns a const_iterator pointing beyond the end of the vector, see \ref design_vector_notes.
    const_iterator cend() const
    {
        return end();
    }

    //! returns a reverse_iterator pointing to the end of the vector.
    reverse_iterator rbegin()
    {
        return reverse_iterator(end());
    }
    //! returns a reverse_iterator pointing to the end of the vector.
    const_reverse_iterator rbegin() const
    {
        return const_reverse_iterator(end());
    }
    //! returns a reverse_iterator pointing to the end of the vector.
    const_reverse_iterator crbegin() const
    {
        return const_reverse_iterator(end());
    }
    //! returns a reverse_iterator pointing beyond the beginning of the vector.
    reverse_iterator rend()
    {
        return reverse_iterator(begin());
    }
    //! returns a reverse_iterator pointing beyond the beginning of the vector.
    const_reverse_iterator rend() const
    {
        return const_reverse_iterator(begin());
    }
    //! returns a reverse_iterator pointing beyond the beginning of the vector.
    const_reverse_iterator crend() const
    {
        return const_reverse_iterator(begin());
    }

    //! \}

    //! \name Direct Element Access
    //! \{

    //! access the element at the given vector's offset
    reference operator [] (size_type offset)
    {
        return element(offset);
    }
    //! access the element at the given vector's offset
    const_reference operator [] (size_type offset) const
    {
        return const_element(offset);
    }

    //! access the element at the given vector's offset
    reference at(size_type offset)
    {
        assert(offset < (size_type)size());
        return element(offset);
    }
    //! access the element at the given vector's offset
    const_reference at(size_type offset) const
    {
        assert(offset < (size_type)size());
        return const_element(offset);
    }

    //! return true if the given vector offset is in cache
    bool is_element_cached(size_type offset) const
    {
        return is_page_cached(blocked_index_type(offset));
    }

    //! \}

    //! \name Modifiers
    //! \{

    //! Flushes the cache pages to the external memory.
    void flush() const
    {
        simple_vector<bool> non_free_slots(numpages());

        for (unsigned_type i = 0; i < numpages(); i++)
            non_free_slots[i] = true;

        while (!m_free_slots.empty())
        {
            non_free_slots[m_free_slots.front()] = false;
            m_free_slots.pop();
        }

        for (unsigned_type i = 0; i < numpages(); i++)
        {
            m_free_slots.push(i);
            int_type page_no = m_slot_to_page[i];
            if (non_free_slots[i])
            {
                STXXL_VERBOSE_VECTOR("flush(): flushing page " << i << " at address " <<
                                     (int64(page_no) * int64(block_type::size) * int64(page_size)));
                write_page(page_no, i);

                m_page_to_slot[page_no] = on_disk;
            }
        }
    }

    //! \}

    //! \name Constructors/Destructors
    //! \{

    ~vector()
    {
        STXXL_VERBOSE_VECTOR("~vector()");
        try
        {
            flush();
        }
        catch (io_error e)
        {
            STXXL_ERRMSG("io_error thrown in ~vector(): " << e.what());
        }
        catch (...)
        {
            STXXL_ERRMSG("Exception thrown in ~vector()");
        }

        if (!m_exported)
        {
            if (m_from == NULL) {
                m_bm->delete_blocks(m_bids.begin(), m_bids.end());
            }
            else // file must be truncated
            {
                STXXL_VERBOSE_VECTOR("~vector(): Changing size of file " <<
                                     ((void*)m_from) << " to " << file_length());
                STXXL_VERBOSE_VECTOR("~vector(): size of the vector is " << size());
                try
                {
                    m_from->set_size(file_length());
                }
                catch (...)
                {
                    STXXL_ERRMSG("Exception thrown in ~vector()...set_size()");
                }
            }
        }
        delete m_cache;
    }

    //! \}

    //! \name Miscellaneous
    //! \{

    //! Export data such that it is persistent on the file system. Resulting
    //! files will be numbered ascending.
    void export_files(std::string filename_prefix)
    {
        int64 no = 0;
        for (bids_container_iterator i = m_bids.begin(); i != m_bids.end(); ++i) {
            std::ostringstream number;
            number << std::setw(9) << std::setfill('0') << no;
            size_type current_block_size =
                ((i + 1) == m_bids.end() && m_size % block_type::size > 0) ?
                (m_size % block_type::size) * sizeof(value_type) :
                block_type::size * sizeof(value_type);
            (*i).storage->export_files((*i).offset, current_block_size, filename_prefix + number.str());
            ++no;
        }
        m_exported = true;
    }

    //! Get the file associated with this vector, or NULL.
    file * get_file() const
    {
        return m_from;
    }

    //! \}

    //! \name Capacity
    //! \{

    //! Set the blocks and the size of this container explicitly.
    //! The vector must be completely empty before.
    template <typename ForwardIterator>
    void set_content(const ForwardIterator& bid_begin, const ForwardIterator& bid_end, size_type n)
    {
        unsigned_type new_bids_size = div_ceil(n, block_type::size);
        m_bids.resize(new_bids_size);
        std::copy(bid_begin, bid_end, m_bids.begin());
        unsigned_type new_pages = div_ceil(new_bids_size, page_size);
        m_page_status.resize(new_pages, valid_on_disk);
        m_page_to_slot.resize(new_pages, on_disk);
        m_size = n;
    }

    //! Number of pages used by the pager.
    inline unsigned_type numpages() const
    {
        return m_pager.size();
    }

    //! \}

private:
    bids_container_iterator bid(const size_type& offset)
    {
        return (m_bids.begin() +
                static_cast<typename bids_container_type::size_type>
                (offset / block_type::size));
    }
    bids_container_iterator bid(const blocked_index_type& offset)
    {
        return (m_bids.begin() +
                static_cast<typename bids_container_type::size_type>
                (offset.get_block2() * PageSize + offset.get_block1()));
    }
    const_bids_container_iterator bid(const size_type& offset) const
    {
        return (m_bids.begin() +
                static_cast<typename bids_container_type::size_type>
                (offset / block_type::size));
    }
    const_bids_container_iterator bid(const blocked_index_type& offset) const
    {
        return (m_bids.begin() +
                static_cast<typename bids_container_type::size_type>
                (offset.get_block2() * PageSize + offset.get_block1()));
    }

    void read_page(int_type page_no, int_type cache_slot) const
    {
        assert(page_no < (int_type)m_page_status.size());
        if (m_page_status[page_no] == uninitialized)
            return;
        STXXL_VERBOSE_VECTOR("read_page(): page_no=" << page_no << " cache_slot=" << cache_slot);
        request_ptr* reqs = new request_ptr[page_size];
        int_type block_no = page_no * page_size;
        int_type last_block = STXXL_MIN(block_no + page_size, int_type(m_bids.size()));
        int_type i = cache_slot * page_size, j = 0;
        for ( ; block_no < last_block; ++block_no, ++i, ++j)
        {
            reqs[j] = (*m_cache)[i].read(m_bids[block_no]);
        }
        assert(last_block - page_no * page_size > 0);
        wait_all(reqs, last_block - page_no * page_size);
        delete[] reqs;
    }
    void write_page(int_type page_no, int_type cache_slot) const
    {
        assert(page_no < (int_type)m_page_status.size());
        if (!(m_page_status[page_no] & dirty))
            return;
        STXXL_VERBOSE_VECTOR("write_page(): page_no=" << page_no << " cache_slot=" << cache_slot);
        request_ptr* reqs = new request_ptr[page_size];
        int_type block_no = page_no * page_size;
        int_type last_block = STXXL_MIN(block_no + page_size, int_type(m_bids.size()));
        assert(block_no < last_block);
        int_type i = cache_slot * page_size, j = 0;
        for ( ; block_no < last_block; ++block_no, ++i, ++j)
        {
            reqs[j] = (*m_cache)[i].write(m_bids[block_no]);
        }
        m_page_status[page_no] = valid_on_disk;
        assert(last_block - page_no * page_size > 0);
        wait_all(reqs, last_block - page_no * page_size);
        delete[] reqs;
    }

    reference element(size_type offset)
    {
#ifdef STXXL_RANGE_CHECK
        assert(offset < (size_type)size());
#endif
        return element(blocked_index_type(offset));
    }

    reference element(const blocked_index_type& offset)
    {
#ifdef STXXL_RANGE_CHECK
        assert(offset.get_pos() < size());
#endif
        unsigned_type page_no = offset.get_block2();
        assert(page_no < m_page_to_slot.size());   // fails if offset is too large, out of bound access
        int_type cache_slot = m_page_to_slot[page_no];
        if (cache_slot < 0)                        // == on_disk
        {
            if (m_free_slots.empty())              // has to kick
            {
                int_type kicked_slot = m_pager.kick();
                m_pager.hit(kicked_slot);
                int_type old_page_no = m_slot_to_page[kicked_slot];
                m_page_to_slot[page_no] = kicked_slot;
                m_page_to_slot[old_page_no] = on_disk;
                m_slot_to_page[kicked_slot] = page_no;

                write_page(old_page_no, kicked_slot);
                read_page(page_no, kicked_slot);

                m_page_status[page_no] = dirty;

                return (*m_cache)[kicked_slot * page_size + offset.get_block1()][offset.get_offset()];
            }
            else
            {
                int_type free_slot = m_free_slots.front();
                m_free_slots.pop();
                m_pager.hit(free_slot);
                m_page_to_slot[page_no] = free_slot;
                m_slot_to_page[free_slot] = page_no;

                read_page(page_no, free_slot);

                m_page_status[page_no] = dirty;

                return (*m_cache)[free_slot * page_size + offset.get_block1()][offset.get_offset()];
            }
        }
        else
        {
            m_page_status[page_no] = dirty;
            m_pager.hit(cache_slot);
            return (*m_cache)[cache_slot * page_size + offset.get_block1()][offset.get_offset()];
        }
    }

    // don't forget to first flush() the vector's cache before updating pages externally
    void page_externally_updated(unsigned_type page_no) const
    {
        // fails if offset is too large, out of bound access
        assert(page_no < m_page_status.size());
        // "A dirty page has been marked as newly initialized. The page content will be lost."
        assert(!(m_page_status[page_no] & dirty));
        if (m_page_to_slot[page_no] != on_disk) {
            // remove page from cache
            m_free_slots.push(m_page_to_slot[page_no]);
            m_page_to_slot[page_no] = on_disk;
            STXXL_VERBOSE_VECTOR("page_externally_updated(): page_no=" << page_no << " flushed from cache.");
        }
        else {
            STXXL_VERBOSE_VECTOR("page_externally_updated(): page_no=" << page_no << " no need to flush.");
        }
        m_page_status[page_no] = valid_on_disk;
    }

    void block_externally_updated(size_type offset) const
    {
        page_externally_updated(
            (unsigned_type)(offset / (block_type::size * page_size))
            );
    }

    void block_externally_updated(const blocked_index_type& offset) const
    {
        page_externally_updated(offset.get_block2());
    }

    const_reference const_element(size_type offset) const
    {
        return const_element(blocked_index_type(offset));
    }

    const_reference const_element(const blocked_index_type& offset) const
    {
        unsigned_type page_no = offset.get_block2();
        assert(page_no < m_page_to_slot.size());   // fails if offset is too large, out of bound access
        int_type cache_slot = m_page_to_slot[page_no];
        if (cache_slot < 0)                        // == on_disk
        {
            if (m_free_slots.empty())              // has to kick
            {
                int_type kicked_slot = m_pager.kick();
                m_pager.hit(kicked_slot);
                int_type old_page_no = m_slot_to_page[kicked_slot];
                m_page_to_slot[page_no] = kicked_slot;
                m_page_to_slot[old_page_no] = on_disk;
                m_slot_to_page[kicked_slot] = page_no;

                write_page(old_page_no, kicked_slot);
                read_page(page_no, kicked_slot);

                return (*m_cache)[kicked_slot * page_size + offset.get_block1()][offset.get_offset()];
            }
            else
            {
                int_type free_slot = m_free_slots.front();
                m_free_slots.pop();
                m_pager.hit(free_slot);
                m_page_to_slot[page_no] = free_slot;
                m_slot_to_page[free_slot] = page_no;

                read_page(page_no, free_slot);

                return (*m_cache)[free_slot * page_size + offset.get_block1()][offset.get_offset()];
            }
        }
        else
        {
            m_pager.hit(cache_slot);
            return (*m_cache)[cache_slot * page_size + offset.get_block1()][offset.get_offset()];
        }
    }

    bool is_page_cached(const blocked_index_type& offset) const
    {
        unsigned_type page_no = offset.get_block2();
        assert(page_no < m_page_to_slot.size());   // fails if offset is too large, out of bound access
        int_type cache_slot = m_page_to_slot[page_no];
        return (cache_slot >= 0);                  // on_disk == -1
    }
};

template <
    typename ValueType,
    unsigned PageSize,
    typename PagerType,
    unsigned BlockSize,
    typename AllocStr,
    typename SizeType>
inline bool operator == (stxxl::vector<ValueType, PageSize, PagerType, BlockSize,
                                       AllocStr, SizeType>& a,
                         stxxl::vector<ValueType, PageSize, PagerType, BlockSize,
                                       AllocStr, SizeType>& b)
{
    return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin());
}

template <
    typename ValueType,
    unsigned PageSize,
    typename PagerType,
    unsigned BlockSize,
    typename AllocStr,
    typename SizeType>
inline bool operator != (stxxl::vector<ValueType, PageSize, PagerType, BlockSize,
                                       AllocStr, SizeType>& a,
                         stxxl::vector<ValueType, PageSize, PagerType, BlockSize,
                                       AllocStr, SizeType>& b)
{
    return !(a == b);
}

template <
    typename ValueType,
    unsigned PageSize,
    typename PagerType,
    unsigned BlockSize,
    typename AllocStr,
    typename SizeType>
inline bool operator < (stxxl::vector<ValueType, PageSize, PagerType, BlockSize,
                                      AllocStr, SizeType>& a,
                        stxxl::vector<ValueType, PageSize, PagerType, BlockSize,
                                      AllocStr, SizeType>& b)
{
    return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
}

template <
    typename ValueType,
    unsigned PageSize,
    typename PagerType,
    unsigned BlockSize,
    typename AllocStr,
    typename SizeType>
inline bool operator > (stxxl::vector<ValueType, PageSize, PagerType, BlockSize,
                                      AllocStr, SizeType>& a,
                        stxxl::vector<ValueType, PageSize, PagerType, BlockSize,
                                      AllocStr, SizeType>& b)
{
    return b < a;
}

template <
    typename ValueType,
    unsigned PageSize,
    typename PagerType,
    unsigned BlockSize,
    typename AllocStr,
    typename SizeType>
inline bool operator <= (stxxl::vector<ValueType, PageSize, PagerType, BlockSize,
                                       AllocStr, SizeType>& a,
                         stxxl::vector<ValueType, PageSize, PagerType, BlockSize,
                                       AllocStr, SizeType>& b)
{
    return !(b < a);
}

template <
    typename ValueType,
    unsigned PageSize,
    typename PagerType,
    unsigned BlockSize,
    typename AllocStr,
    typename SizeType>
inline bool operator >= (stxxl::vector<ValueType, PageSize, PagerType, BlockSize,
                                       AllocStr, SizeType>& a,
                         stxxl::vector<ValueType, PageSize, PagerType, BlockSize,
                                       AllocStr, SizeType>& b)
{
    return !(a < b);
}

////////////////////////////////////////////////////////////////////////////

// specialization for stxxl::vector, to use only const_iterators
template <typename ValueType, typename AllocStr, typename SizeType, typename DiffType,
          unsigned BlockSize, typename PagerType, unsigned PageSize>
bool is_sorted(
    stxxl::vector_iterator<ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize> first,
    stxxl::vector_iterator<ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize> last)
{
    return is_sorted_helper(
        stxxl::const_vector_iterator<ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize>(first),
        stxxl::const_vector_iterator<ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize>(last));
}

template <typename ValueType, typename AllocStr, typename SizeType, typename DiffType,
          unsigned BlockSize, typename PagerType, unsigned PageSize, typename StrictWeakOrdering>
bool is_sorted(
    stxxl::vector_iterator<ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize> first,
    stxxl::vector_iterator<ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize> last,
    StrictWeakOrdering comp)
{
    return is_sorted_helper(
        stxxl::const_vector_iterator<ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize>(first),
        stxxl::const_vector_iterator<ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize>(last),
        comp);
}

////////////////////////////////////////////////////////////////////////////

template <typename VectorBufReaderType>
class vector_bufreader_iterator;

/*!
 * Buffered sequential reader from a vector using overlapped I/O.
 *
 * This buffered reader can be used to read a large sequential region of a
 * vector using overlapped I/O. The object is created from an iterator range,
 * which can then be read to using operator<<(), or with operator*() and
 * operator++().
 *
 * The interface also fulfills all requirements of a stream. Actually most of
 * the code is identical to stream::vector_iterator2stream.
 *
 * Note that this buffered reader is inefficient for reading small ranges. This
 * is intentional, as one can just use operator[] on the vector for that.
 *
 * See \ref tutorial_vector_buf
 */
template <typename VectorIterator>
class vector_bufreader : public noncopyable
{
public:
    //! template parameter: the vector iterator type
    typedef VectorIterator vector_iterator;

    //! value type of the output vector
    typedef typename vector_iterator::value_type value_type;

    //! block type used in the vector
    typedef typename vector_iterator::block_type block_type;

    //! type of the input vector
    typedef typename vector_iterator::vector_type vector_type;

    //! block identifier iterator of the vector
    typedef typename vector_iterator::bids_container_iterator bids_container_iterator;

    //! construct output buffered stream used for overlapped reading
    typedef buf_istream<block_type, bids_container_iterator> buf_istream_type;

    //! construct an iterator for vector_bufreader (for C++11 range-based for loop)
    typedef vector_bufreader_iterator<vector_bufreader> bufreader_iterator;

    //! size of remaining data
    typedef typename vector_type::size_type size_type;

protected:
    //! iterator to the beginning of the range.
    vector_iterator m_begin;

    //! internal "current" iterator into the vector.
    vector_iterator m_iter;

    //! iterator to the end of the range.
    vector_iterator m_end;

    //! buffered input stream used to overlapped I/O.
    buf_istream_type* m_bufin;

    //! number of blocks to use as buffers.
    unsigned_type m_nbuffers;

    //! allow vector_bufreader_iterator to check m_iter against its current value
    friend class vector_bufreader_iterator<vector_bufreader>;

public:
    //! Create overlapped reader for the given iterator range.
    //! \param begin iterator to position were to start reading in vector
    //! \param end iterator to position were to end reading in vector
    //! \param nbuffers number of buffers used for overlapped I/O (>= 2*D recommended)
    vector_bufreader(vector_iterator begin, vector_iterator end,
                     unsigned_type nbuffers = 0)
        : m_begin(begin), m_end(end),
          m_bufin(NULL),
          m_nbuffers(nbuffers)
    {
        m_begin.flush(); // flush container

        if (m_nbuffers == 0)
            m_nbuffers = 2 * config::get_instance()->disks_number();

        rewind();
    }

    //! Create overlapped reader for the whole vector's content.
    //! \param vec vector to read
    //! \param nbuffers number of buffers used for overlapped I/O (>= 2*D recommended)
    vector_bufreader(const vector_type& vec, unsigned_type nbuffers = 0)
        : m_begin(vec.begin()), m_end(vec.end()),
          m_bufin(NULL),
          m_nbuffers(nbuffers)
    {
        m_begin.flush(); // flush container

        if (m_nbuffers == 0)
            m_nbuffers = 2 * config::get_instance()->disks_number();

        rewind();
    }

    //! Rewind stream back to begin. Note that this recreates the buffered
    //! reader and is thus not cheap.
    void rewind()
    {
        m_iter = m_begin;
        if (empty()) return;

        if (m_bufin) delete m_bufin;

        // find last bid to read
        bids_container_iterator end_bid = m_end.bid() + (m_end.block_offset() ? 1 : 0);

        // construct buffered istream for range
        m_bufin = new buf_istream_type(m_begin.bid(), end_bid, m_nbuffers);

        // skip the beginning of the block, up to real beginning
        vector_iterator curr = m_begin - m_begin.block_offset();

        for ( ; curr != m_begin; ++curr)
            ++(*m_bufin);
    }

    //! Finish reading and free buffered reader.
    ~vector_bufreader()
    {
        if (m_bufin) delete m_bufin;
    }

    //! Return constant reference to current item
    const value_type& operator * () const
    {
        return *(*m_bufin);
    }

    //! Return constant pointer to current item
    const value_type* operator -> () const
    {
        return &(*(*m_bufin));
    }

    //! Advance to next item (asserts if !empty()).
    vector_bufreader& operator ++ ()
    {
        assert(!empty());
        ++m_iter;
        ++(*m_bufin);

        if (UNLIKELY(empty())) {
            delete m_bufin;
            m_bufin = NULL;
        }

        return *this;
    }

    //! Read current item into variable and advance to next one.
    vector_bufreader& operator >> (value_type& v)
    {
        v = operator * ();
        operator ++ ();

        return *this;
    }

    //! Return remaining size.
    size_type size() const
    {
        assert(m_begin <= m_iter && m_iter <= m_end);
        return (size_type)(m_end - m_iter);
    }

    //! Returns true once the whole range has been read.
    bool empty() const
    {
        return (m_iter == m_end);
    }

    //! Return vector_bufreader_iterator for C++11 range-based for loop
    bufreader_iterator begin()
    {
        return bufreader_iterator(*this, m_begin);
    }

    //! Return vector_bufreader_iterator for C++11 range-based for loop
    bufreader_iterator end()
    {
        return bufreader_iterator(*this, m_end);
    }
};

////////////////////////////////////////////////////////////////////////////

/*!
 * Adapter for vector_bufreader to match iterator requirements of C++11
 * range-based loop construct.
 *
 * Since vector_bufreader itself points to only one specific item, this
 * iterator is merely a counter facade. The functions operator*() and
 * operator++() must only be called when it is in _sync_ with the bufreader
 * object. This is generally only the case for an iterator constructed with
 * begin() and then advanced with operator++(). The class checks this using
 * asserts(), the operators will fail if used wrong.
 *
 * See \ref tutorial_vector_buf
 */
template <typename VectorBufReaderType>
class vector_bufreader_iterator
{
public:
    //! The underlying buffered reader type
    typedef VectorBufReaderType vector_bufreader_type;

    //! Value type of vector
    typedef typename vector_bufreader_type::value_type value_type;

    //! Use vector_iterator to reference a point in the vector.
    typedef typename vector_bufreader_type::vector_iterator vector_iterator;

protected:
    //! Buffered reader used to access elements in vector
    vector_bufreader_type& m_bufreader;

    //! Use vector_iterator to reference a point in the vector.
    vector_iterator m_iter;

public:
    //! Construct iterator using vector_iterator
    vector_bufreader_iterator(vector_bufreader_type& bufreader, const vector_iterator& iter)
        : m_bufreader(bufreader), m_iter(iter)
    { }

    //! Return constant reference to current item
    const value_type& operator * () const
    {
        assert(m_bufreader.m_iter == m_iter);
        return m_bufreader.operator * ();
    }

    //! Return constant pointer to current item
    const value_type* operator -> () const
    {
        assert(m_bufreader.m_iter == m_iter);
        return m_bufreader.operator -> ();
    }

    //! Make bufreader advance to next item (asserts if !empty() or if iterator
    //! does not point to current).
    vector_bufreader_iterator& operator ++ ()
    {
        assert(m_bufreader.m_iter == m_iter);
        m_bufreader.operator ++ ();
        m_iter++;
        return *this;
    }

    //! Equality comparison operator
    bool operator == (const vector_bufreader_iterator& vbi) const
    {
        assert(&m_bufreader == &vbi.m_bufreader);
        return (m_iter == vbi.m_iter);
    }

    //! Inequality comparison operator
    bool operator != (const vector_bufreader_iterator& vbi) const
    {
        assert(&m_bufreader == &vbi.m_bufreader);
        return (m_iter != vbi.m_iter);
    }
};

////////////////////////////////////////////////////////////////////////////

/*!
 * Buffered sequential reverse reader from a vector using overlapped I/O.
 *
 * This buffered reader can be used to read a large sequential region of a
 * vector _in_reverse_ using overlapped I/O. The object is created from an
 * iterator range, which can then be read to using operator<<(), or with
 * operator*() and operator++(), where ++ actually goes to the preceding
 * element.
 *
 * The interface also fulfills all requirements of a stream. Actually most of
 * the code is identical to stream::vector_iterator2stream.
 *
 * Note that this buffered reader is inefficient for reading small ranges. This
 * is intentional, as one can just use operator[] on the vector for that.
 *
 * See \ref tutorial_vector_buf
 */
template <typename VectorIterator>
class vector_bufreader_reverse : public noncopyable
{
public:
    //! template parameter: the vector iterator type
    typedef VectorIterator vector_iterator;

    //! value type of the output vector
    typedef typename vector_iterator::value_type value_type;

    //! block type used in the vector
    typedef typename vector_iterator::block_type block_type;

    //! type of the input vector
    typedef typename vector_iterator::vector_type vector_type;

    //! block identifier iterator of the vector
    typedef typename vector_iterator::bids_container_iterator bids_container_iterator;

    //! construct output buffered stream used for overlapped reading
    typedef buf_istream_reverse<block_type, bids_container_iterator> buf_istream_type;

    //! size of remaining data
    typedef typename vector_type::size_type size_type;

protected:
    //! iterator to the beginning of the range.
    vector_iterator m_begin;

    //! internal "current" iterator into the vector.
    vector_iterator m_iter;

    //! iterator to the end of the range.
    vector_iterator m_end;

    //! buffered input stream used to overlapped I/O.
    buf_istream_type* m_bufin;

    //! number of blocks to use as buffers.
    unsigned_type m_nbuffers;

public:
    //! Create overlapped reader for the given iterator range.
    //! \param begin iterator to position were to start reading in vector
    //! \param end iterator to position were to end reading in vector
    //! \param nbuffers number of buffers used for overlapped I/O (>= 2*D recommended)
    vector_bufreader_reverse(vector_iterator begin, vector_iterator end,
                             unsigned_type nbuffers = 0)
        : m_begin(begin), m_end(end),
          m_bufin(NULL),
          m_nbuffers(nbuffers)
    {
        m_begin.flush(); // flush container

        if (m_nbuffers == 0)
            m_nbuffers = 2 * config::get_instance()->disks_number();

        rewind();
    }

    //! Create overlapped reader for the whole vector's content.
    //! \param vec vector to read
    //! \param nbuffers number of buffers used for overlapped I/O (>= 2*D recommended)
    vector_bufreader_reverse(const vector_type& vec, unsigned_type nbuffers = 0)
        : m_begin(vec.begin()), m_end(vec.end()),
          m_bufin(NULL),
          m_nbuffers(nbuffers)
    {
        m_begin.flush(); // flush container

        if (m_nbuffers == 0)
            m_nbuffers = 2 * config::get_instance()->disks_number();

        rewind();
    }

    //! Rewind stream back to begin. Note that this recreates the buffered
    //! reader and is thus not cheap.
    void rewind()
    {
        m_iter = m_end;
        if (empty()) return;

        if (m_bufin) delete m_bufin;

        // find last bid to read
        bids_container_iterator end_bid = m_end.bid() + (m_end.block_offset() ? 1 : 0);

        // construct buffered istream_reverse for range
        m_bufin = new buf_istream_type(m_begin.bid(), end_bid, m_nbuffers);

        // skip to beginning of reverse sequence.
        stxxl::int_type endoff = m_end.block_offset();
        if (endoff == 0) {
            // nothing to skip
        }
        else {
            // else, let ifstream_reverse skip last elements at end of block,
            // up to real end
            for ( ; endoff != block_type::size; endoff++)
                ++(*m_bufin);
        }
    }

    //! Finish reading and free buffered reader.
    ~vector_bufreader_reverse()
    {
        if (m_bufin) delete m_bufin;
    }

    //! Return constant reference to current item
    const value_type& operator * () const
    {
        return *(*m_bufin);
    }

    //! Return constant pointer to current item
    const value_type* operator -> () const
    {
        return &(*(*m_bufin));
    }

    //! Advance to next item (asserts if !empty()).
    vector_bufreader_reverse& operator ++ ()
    {
        assert(!empty());
        --m_iter;
        ++(*m_bufin);

        if (UNLIKELY(empty())) {
            delete m_bufin;
            m_bufin = NULL;
        }

        return *this;
    }

    //! Read current item into variable and advance to next one.
    vector_bufreader_reverse& operator >> (value_type& v)
    {
        v = operator * ();
        operator ++ ();

        return *this;
    }

    //! Return remaining size.
    size_type size() const
    {
        assert(m_begin <= m_iter && m_iter <= m_end);
        return (size_type)(m_iter - m_begin);
    }

    //! Returns true once the whole range has been read.
    bool empty() const
    {
        return (m_iter == m_begin);
    }
};

////////////////////////////////////////////////////////////////////////////

/*!
 * Buffered sequential writer to a vector using overlapped I/O.
 *
 * This buffered writer can be used to write a large sequential region of a
 * vector using overlapped I/O. The object is created from an iterator range,
 * which can then be written to using operator << (), or with operator * () and
 * operator ++ ().
 *
 * The buffered writer is given one iterator in the constructor. When writing,
 * this iterator advances in the vector and will \b enlarge the vector once it
 * reaches the end(). The vector size is doubled each time; nevertheless, it is
 * better to preinitialize the vector's size using stxxl::vector::resize().
 *
 * See \ref tutorial_vector_buf
 */
template <typename VectorIterator>
class vector_bufwriter : public noncopyable
{
public:
    //! template parameter: the vector iterator type
    typedef VectorIterator iterator;

    //! type of the output vector
    typedef typename iterator::vector_type vector_type;

    //! value type of the output vector
    typedef typename iterator::value_type value_type;

    //! block type used in the vector
    typedef typename iterator::block_type block_type;

    //! block identifier iterator of the vector
    typedef typename iterator::bids_container_iterator bids_container_iterator;

    //! iterator type of vector
    typedef typename iterator::iterator vector_iterator;
    typedef typename iterator::const_iterator vector_const_iterator;

    //! construct output buffered stream used for overlapped writing
    typedef buf_ostream<block_type, bids_container_iterator> buf_ostream_type;

protected:
    //! internal iterator into the vector.
    vector_iterator m_iter;

    //! iterator to the current end of the vector.
    vector_const_iterator m_end;

    //! boolean whether the vector was grown, will shorten at finish().
    bool m_grown;

    //! iterator into vector of the last block accessed (used to issue updates
    //! when the block is switched).
    vector_const_iterator m_prevblk;

    //! buffered output stream used to overlapped I/O.
    buf_ostream_type* m_bufout;

    //! number of blocks to use as buffers.
    unsigned_type m_nbuffers;

public:
    //! Create overlapped writer beginning at the given iterator.
    //! \param begin iterator to position were to start writing in vector
    //! \param nbuffers number of buffers used for overlapped I/O (>= 2D recommended)
    vector_bufwriter(vector_iterator begin,
                     unsigned_type nbuffers = 0)
        : m_iter(begin),
          m_end(m_iter.parent_vector()->end()),
          m_grown(false),
          m_bufout(NULL),
          m_nbuffers(nbuffers)
    {
        if (m_nbuffers == 0)
            m_nbuffers = 2 * config::get_instance()->disks_number();

        assert(m_iter <= m_end);
    }

    //! Create overlapped writer for the vector's beginning
    //! \param vec vector to write
    //! \param nbuffers number of buffers used for overlapped I/O (>= 2D recommended)
    vector_bufwriter(vector_type& vec,
                     unsigned_type nbuffers = 0)
        : m_iter(vec.begin()),
          m_end(m_iter.parent_vector()->end()),
          m_grown(false),
          m_bufout(NULL),
          m_nbuffers(nbuffers)
    {
        if (m_nbuffers == 0)
            m_nbuffers = 2 * config::get_instance()->disks_number();

        assert(m_iter <= m_end);
    }

    //! Finish writing and flush output back to vector.
    ~vector_bufwriter()
    {
        finish();
    }

    //! Return mutable reference to item at the position of the internal
    //! iterator.
    value_type& operator * ()
    {
        if (UNLIKELY(m_iter == m_end))
        {
            // iterator points to end of vector -> double vector's size

            if (m_bufout) {
                // fixes issue with buf_ostream writing invalid blocks: when
                // buf_ostream::current_elem advances to next block, flush()
                // will write to block beyond bid().end.
                if (m_iter.block_offset() != 0)
                    m_bufout->flush(); // flushes overlap buffers

                delete m_bufout;
                m_bufout = NULL;

                if (m_iter.block_offset() != 0)
                    m_iter.block_externally_updated();
            }

            vector_type& v = *m_iter.parent_vector();
            if (v.size() < 2 * block_type::size) {
                v.resize(2 * block_type::size);
            }
            else {
                v.resize(2 * v.size());
            }
            m_end = v.end();
            m_grown = true;
        }

        assert(m_iter < m_end);

        if (UNLIKELY(m_bufout == NULL))
        {
            if (m_iter.block_offset() != 0)
            {
                // output position is not at the start of the block, we
                // continue to use the iterator initially passed to the
                // constructor.
                return *m_iter;
            }
            else
            {
                // output position is start of block: create buffered writer

                m_iter.flush(); // flush container

                // create buffered write stream for blocks
                m_bufout = new buf_ostream_type(m_iter.bid(), m_nbuffers);
                m_prevblk = m_iter;

                // drop through to normal output into buffered writer
            }
        }

        // if the pointer has finished a block, then we inform the vector that
        // this block has been updated.
        if (UNLIKELY(m_iter.block_offset() == 0)) {
            if (m_prevblk != m_iter) {
                m_prevblk.block_externally_updated();
                m_prevblk = m_iter;
            }
        }

        return m_bufout->operator * ();
    }

    //! Advance internal iterator.
    vector_bufwriter& operator ++ ()
    {
        // always advance internal iterator
        ++m_iter;

        // if buf_ostream active, advance that too
        if (LIKELY(m_bufout != NULL)) m_bufout->operator ++ ();

        return *this;
    }

    //! Write value to the current position and advance the internal iterator.
    vector_bufwriter& operator << (const value_type& v)
    {
        operator * () = v;
        operator ++ ();

        return *this;
    }

    //! Finish writing and flush output back to vector.
    void finish()
    {
        if (m_bufout)
        {
            // must finish the block started in the buffered writer: fill it with
            // the data in the vector
            vector_const_iterator const_out = m_iter;

            while (const_out.block_offset() != 0)
            {
                m_bufout->operator * () = *const_out;
                m_bufout->operator ++ ();
                ++const_out;
            }

            // inform the vector that the block has been updated.
            if (m_prevblk != m_iter) {
                m_prevblk.block_externally_updated();
                m_prevblk = m_iter;
            }

            delete m_bufout;
            m_bufout = NULL;
        }

        if (m_grown)
        {
            vector_type& v = *m_iter.parent_vector();
            v.resize(m_iter - v.begin());

            m_grown = false;
        }
    }
};

////////////////////////////////////////////////////////////////////////////

//! External vector type generator.
//!
//! \tparam ValueType element type of contained objects (POD with no references to internal memory)
//! \tparam PageSize number of blocks in a page, default: \b 4 (recommended >= D)
//! \tparam CachePages number of pages in cache, default: \b 8 (recommended >= 2)
//! \tparam BlockSize external block size \a B in bytes, default: <b>2 MiB</b>
//! \tparam AllocStr parallel disk allocation strategies: \c striping, RC, SR, or FR. default: \b RC.
//! \tparam Pager pager type: \c random or \c lru, default: \b lru.
//!
//! \warning Do not store references to the elements of an external vector. Such references
//! might be invalidated during any following access to elements of the vector
template <
    typename ValueType,
    unsigned PageSize = 4,
    unsigned CachePages = 8,
    unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType),
    typename AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY,
    pager_type Pager = lru
    >
struct VECTOR_GENERATOR
{
    typedef typename IF<Pager == lru,
                        lru_pager<CachePages>, random_pager<CachePages> >::result PagerType;

    typedef vector<ValueType, PageSize, PagerType, BlockSize, AllocStr> result;
};

//! \}

STXXL_END_NAMESPACE

namespace std {

template <
    typename ValueType,
    unsigned PageSize,
    typename PagerType,
    unsigned BlockSize,
    typename AllocStr,
    typename SizeType>
void swap(stxxl::vector<ValueType, PageSize, PagerType, BlockSize, AllocStr, SizeType>& a,
          stxxl::vector<ValueType, PageSize, PagerType, BlockSize, AllocStr, SizeType>& b)
{
    a.swap(b);
}

} // namespace std

#endif // !STXXL_CONTAINERS_VECTOR_HEADER
// vim: et:ts=4:sw=4