Large matrix with lots of repetitive fields (C++) I wrote a timetabling program and I have been using a matrix to check for clashes between courses. Index (i, j) in the matrix tells us how many people are in both courses i and j.



My previous Matrix was just using nested vectors:

std::vector&lt;std::vector&lt;int&gt;&gt; clashes;


This would throw std::bad_alloc because the matrix is of dimension 18000 x 18000.



Since many of the entries would be 0, I made my own matrix class using unordered maps. This preserves a lot of data as it uses a default value for all of entries that have not been given a value.

template &lt;typename T&gt;
class UMapMatrix
{
public:

UMapMatrix(T default_val) : default_val(default_val) {
}

T get(const int&amp; a, const int&amp; b) const {
    int x, y;
    if (a &lt; b) {
        x = a;
        y = b;
    }
    else {
        x = b;
        y = a;
    }

    auto search = data.find(x);
    if (search != data.end()) {
        auto search2 = search-&gt;second.find(y);
        if (search2 != search-&gt;second.end()) {
            return search2-&gt;second;
        }
    }
    return default_val;
}

void set(const int&amp; a, const int&amp; b, T val) {
    if (a &lt; b) data[a][b] = val;
    else data[b][a] = val;
}

private:
T default_val;
std::unordered_map&lt;int, std::unordered_map&lt;int, T&gt;&gt; data;
};


Are there any significant improvements that could be made to the memory usage and/or speed? 
Are there any other data structures that could be used here?
Why have nested unordered_maps. Just use a single unordreed map using a key that is the x and y coordinates?

One enhancement I would add is using the operator[][] to access the elements.

#include &lt;unordered_map&gt;
#include &lt;utility&gt;
#include &lt;iostream&gt;
#include &lt;functional&gt;


template &lt;typename T&gt;
class UMapMatrix
{
    public:

        UMapMatrix(T const&amp; default_val = T())
            : default_val(default_val)
        {   
        }   

        T const&amp; get(int a, int b) const
        {   
            auto key    = getKey(a, b); 
            auto search = data.find(key);
            return (search != data.end())
                       ? search-&gt;second;
                       : default_val;
        }   

        void set(int a, int b, T const&amp; val)
        {   
            data.insert(std::make_pair(getKey(a,b), val));
        }   
        void set(int a, int b, T&amp;&amp; val)
        {   
            data.insert(std::make_pair(getKey(a,b), std::move(val)));
        }

        class Row 
        {   
            UMapMatrix const* parent;
            int a;

            public:
            Row(UMapMatrix const* parent, int a)
                : parent(parent)
                , a(a)
            {}  
            T const&amp; operator[](int b) const
            {   
                return parent-&gt;get(a, b); 
            }   
        };  
        Row operator[](int a) const {
            return Row{this, a}; 
        }   


    private:
        T default_val;
        using Key = std::pair&lt;int, int&gt;;
        struct PairHash
        {   
            std::size_t operator()(Key const&amp; key) const
            {   
                return std::hash&lt;int&gt;()(key.first) ^ std::hash&lt;int&gt;()(key.second);
            }   
        };  


        Key getKey(int a, int b) const {

            int x = std::min(a, b); 
            int y = std::max(a, b); 
            return std::make_pair(x, y); 
        }   

        std::unordered_map&lt;Key, T, PairHash&gt;  data;
};

int main()
{
    UMapMatrix&lt;int&gt;     data;

    std::cout &lt;&lt; data.get(1500, 3000) &lt;&lt; "\n";
    data.set(1500, 3000, 234);

    std::cout &lt;&lt; data[1500][3000] &lt;&lt; "\n";
}