Class sparsetable

libCacheSim/dataStructure/sparsepp/spp.h:1785–2473

// ---------------------------------------------------------------------------
template <class T, class Alloc>
class sparsetable
{
public:
    typedef T                                             value_type;
    typedef Alloc                                         allocator_type;
    typedef sparsegroup<value_type, allocator_type>       group_type;

private:
    typedef typename Alloc::template rebind<group_type>::other group_alloc_type;
    typedef typename group_alloc_type::size_type          group_size_type;

public:
    // Basic types
    // -----------
    typedef typename allocator_type::size_type            size_type;
    typedef typename allocator_type::difference_type      difference_type;
    typedef value_type&                                   reference;
    typedef const value_type&                             const_reference;
    typedef value_type*                                   pointer;
    typedef const value_type*                             const_pointer;

    typedef group_type&                                   GroupsReference;
    typedef const group_type&                             GroupsConstReference;

    typedef typename group_type::ne_iterator              ColIterator;
    typedef typename group_type::const_ne_iterator        ColConstIterator;

    typedef table_iterator<sparsetable<T, allocator_type> >        iterator;       // defined with index
    typedef const_table_iterator<sparsetable<T, allocator_type> >  const_iterator; // defined with index
    typedef std::reverse_iterator<const_iterator>         const_reverse_iterator;
    typedef std::reverse_iterator<iterator>               reverse_iterator;

    // These are our special iterators, that go over non-empty buckets in a
    // table.  These aren't const only because you can change non-empty bcks.
    // ----------------------------------------------------------------------
    typedef Two_d_iterator<T,
                           group_type *,
                           ColIterator,
                           std::bidirectional_iterator_tag> ne_iterator;

    typedef Two_d_iterator<const T,
                           const group_type *,
                           ColConstIterator,
                           std::bidirectional_iterator_tag> const_ne_iterator;

    // Another special iterator: it frees memory as it iterates (used to resize).
    // Obviously, you can only iterate over it once, which is why it's an input iterator
    // ---------------------------------------------------------------------------------
    typedef Two_d_destructive_iterator<T,
                                       group_type *,
                                       ColIterator,
                                       std::input_iterator_tag,
                                       allocator_type>     destructive_iterator;

    typedef std::reverse_iterator<ne_iterator>               reverse_ne_iterator;
    typedef std::reverse_iterator<const_ne_iterator>         const_reverse_ne_iterator;