# Sparse Storage

## Map Array

#### Description

The templated class `map_array<I, T>` implements a simple std::map-like associative container as a sorted array.

#### Example

    #include <boost/numeric/ublas/storage_sparse.hpp>

    int main () {
        using namespace boost::numeric::ublas;
        map_array<int, double> a (3);
        for (unsigned i = 0; i < a.size (); ++ i) {
            a [i] = i;
            std::cout << a [i] << std::endl;
        }
    }

#### Definition

Defined in the header storage_sparse.hpp.

#### Template parameters

Parameter | Description | Default
--- | --- | ---
`I` | The type of index stored in the array. |
`T` | The type of object stored in the array. |

#### Model of

Reversible Container.

#### Type requirements

None, except for those imposed by the requirements of Reversible Container.

#### Public base classes

None.

#### Members

Member | Description
--- | ---
`map_array ()` | Allocates a `map_array` that holds at most zero elements.
`map_array (size_type size)` | Allocates a `map_array` that holds at most `size` elements.
`map_array (const map_array &a)` | The copy constructor.
`~map_array ()` | Deallocates the `map_array` itself.
`void resize (size_type size)` | Reallocates a `map_array` to hold at most `size` elements. The content of the `map_array` is preserved.
`size_type size () const` | Returns the size of the `map_array`.
`data_reference operator [] (index_type i)` | Returns a reference of the element that is associated with a particular index. If the `map_array` does not already contain such an element, `operator[]` inserts the default`T ()`.
`map_array &operator = (const map_array &a)` | The assignment operator.
`map_array &assign_temporary (map_array &a)` | Assigns a temporary. May change the array `a`.
`void swap (map_array &a)` | Swaps the contents of the arrays.
`pointer insert (pointer it, const value_type &p)` | Inserts `p` into the array, using `it` as a hint to where it will be inserted.
`void erase (pointer it)` | Erases the value at `it`.
`void clear ()` | Clears the array.
`const_pointer find (index_type i) const` | Finds an element whose index is `i`.
`pointer find (index_type i)` | Finds an element whose index is `i`.
`const_pointer lower_bound (index_type i) const` | Finds the first element whose index is not less than `i` .
`pointer lower_bound (index_type i)` | Finds the first element whose index is not less than `i` .
`const_pointer upper_bound (index_type i) const` | Finds the first element whose index is greater than `i` .
`pointer upper_bound (index_type i)` | Finds the first element whose index is greater than `i` .
`const_iterator begin () const` | Returns a `const_iterator` pointing to the beginning of the `map_array`.
`const_iterator end () const` | Returns a `const_iterator` pointing to the end of the `map_array`.
`iterator begin ()` | Returns a `iterator` pointing to the beginning of the `map_array`.
`iterator end ()` | Returns a `iterator` pointing to the end of the `map_array`.
`const_reverse_iterator rbegin () const` | Returns a `const_reverse_iterator` pointing to the beginning of the reversed `map_array`.
`const_reverse_iterator rend () const` | Returns a `const_reverse_iterator` pointing to the end of the reversed `map_array`.
`reverse_iterator rbegin ()` | Returns a `reverse_iterator` pointing to the beginning of the reversed `map_array`.
`reverse_iterator rend ()` | Returns a `reverse_iterator` pointing to the end of the reversed `map_array`.

#### Interface

        // Map array
        template<class I, class T>
        class map_array {
        public:
            typedef std::size_t size_type;
            typedef std::ptrdiff_t difference_type;
            typedef I index_type;
            typedef T data_value_type;
            typedef const T &data_const_reference;
            typedef T &data_reference;
            typedef std::pair<I, T> value_type;
            typedef const std::pair<I, T> &const_reference;
            typedef std::pair<I, T> &reference;
            typedef const std::pair<I, T> *const_pointer;
            typedef std::pair<I, T> *pointer;

            // Construction and destruction
            map_array ();
            map_array (size_type size);
            map_array (const map_array &a);
            ~map_array ();

            // Resizing
            void resize (size_type size);

            size_type size () const;

            // Element access
            data_reference operator [] (index_type i);

            // Assignment
            map_array &operator = (const map_array &a);
            map_array &assign_temporary (map_array &a);

            // Swapping
            void swap (map_array &a);
            friend void swap (map_array &a1, map_array &a2);

            // Element insertion and deletion
            pointer insert (pointer it, const value_type &p);
            void insert (pointer it, pointer it1, pointer it2);
            void erase (pointer it);
            void erase (pointer it1, pointer it2);
            void clear ();

            // Element lookup
            const_pointer find (index_type i) const;
            pointer find (index_type i);
            const_pointer lower_bound (index_type i) const;
            pointer lower_bound (index_type i);
            const_pointer upper_bound (index_type i) const;
            pointer upper_bound (index_type i);

            // Iterators simply are pointers.

            typedef const_pointer const_iterator;

            const_iterator begin () const;
            const_iterator end () const;

            typedef pointer iterator;

            iterator begin ();
            iterator end ();

            // Reverse iterators

            typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

            const_reverse_iterator rbegin () const;
            const_reverse_iterator rend () const;

            typedef std::reverse_iterator<iterator> reverse_iterator;

            reverse_iterator rbegin ();
            reverse_iterator rend ();
        };

        template<class I, class T>
        map_array<I, T> &assign_temporary (map_array<I, T> &a1, map_array<I, T> &a2);

Copyright (©) 2000-2002 Joerg Walter, Mathias Koch
Permission to copy, use, modify, sell and distribute this document is granted provided this copyright notice appears in all copies. This document is provided ``as is'' without express or implied warranty, and with no claim as to its suitability for any purpose.

Last revised: 1/15/2003