8
\$\begingroup\$

Today, I tried to create a really simple sparse_array container adapter. I did not provide all the STL-like functions, only the elementary ones as a proof of concept. I also trimmed the class from its copy constructor and all the unecessary things for this review actually. Here is the code:

#include <cstddef>
#include <map>

template<typename T, template <typename...> class Container=std::map>
struct sparse_array
{
    class proxy
    {
        sparse_array& sp;
        std::size_t index;

        proxy(sparse_array& sp, std::size_t index):
            sp(sp),
            index(index)
        {}

        public:
        proxy(const proxy& other) = default;
        auto operator=(const proxy& other)
            -> proxy&
        {
            sp.data[index] = T(other);
            return *this;
        }

        auto operator=(const T& val)
            -> proxy&
        {
            if (val != sp.default_value)
            {
                sp.data[index] = val;
            }
            else
            {
                sp.data.erase(index);
            }
            return *this;
        }  

        operator T() const
        {
            auto res = sp.data.find(index);
            if (res != sp.data.end())
            {
                return res->second;
            }
            return sp.default_value;
        }

        friend class sparse_array;
    };

    auto operator[](std::size_t index)
        -> proxy
    {
        return { *this, index };
    }

    auto operator[](std::size_t index) const
        -> const proxy
    {
        return { *this, index };
    }

    auto size() const
        -> std::size_t
    {
        return data.size();
    }

    private:
    T default_value = {};
    Container<std::size_t, T> data;
};

What I tried to do is to have a sparse array whose number of elements is strictly equal to the number of elements that are different from default_value, hence the elements that are deleted when default_value is assigned to them. Here comes a small example:

#include <iostream>

int main()
{
    sparse_array<int> sp;

    std::cout << sp[15] << " / " << sp.size() << std::endl;
    sp[8] = sp[13] = 9;
    std::cout << sp[8] << " " << sp[13] << " / " << sp.size() << std::endl;
    sp[11] = 0;
    std::cout << sp[11] << " / " << sp.size() << std::endl;
    sp[8] = 0;
    std::cout << sp[8] << " / " << sp.size() << std::endl;
}

Do you think there are obvious design flaws in this code? I bet there are some in the proxy mechanism, and it would be great if you could hilight some of them.

\$\endgroup\$
1
  • \$\begingroup\$ A possible API is to see your data structure more as a map, i.e. iteration returns key,value pairs, where key is the index and value is a non default value \$\endgroup\$
    – Yann TM
    Commented Dec 11, 2019 at 19:42

1 Answer 1

5
\$\begingroup\$

The primary question I have is one of usage. By the name sparse_array, it sounds like you want to expose an interface that is similar to an array. Perhaps it needs dynamic sizing, or perhaps not, but in particular I expect to be able to iterate over its elements with code like this:

sparse_array<int> sp;
// ::: fill array here :::

for (int elt: sp)
    std::cout << elt << ", ";

// or better
std::ostream_iterator<int> out_it(std::cout, ", ");
std::copy(std::begin(sp), std::end(sp), out_it);

It needs to be clear what the output from that would be. Would it include the default values in most indices? Or is this usage prohibited (perhaps due to that unclarity), as currently there are no iterator related methods? Maybe this is just part of what you intentionally excluded from the review, but it leaves so much unanswered, including things that probably come back to your proxy class, such as how *std::begin(sp) = 3 will work.

The one definite gap I see has to do with operator&. Will you support code that looks like normal array-style addressing? Right now the following code will certainly not work correctly; should it fail to compile, or should it modify sp[5]?

auto spot = &sp[4];
*(spot + 1) = 5;

Other comments:

  • I think your proxy approach here is justified for the usage you want to offer.
  • It's unclear what values are permissible as alternatives to std::map for your Container. Perhaps this is because there are no comments anywhere.
  • You aren't completely consistent about use of parentheses vs. braces for initialization. For example, proxy's constructor uses parentheses where I believe it should use braces: proxy(sparse_array& sp, std::size_t index) : sp{sp}, index{index}
  • It's plausible that default_value should be exposed in the template as well, rather than relying on its type's default.
  • I'm not yet sold on auto method_name(params) -> result_type when result_type is a simple known type. It's too different from the result_type method_name(params) that I've been using for so many years.
\$\endgroup\$
2
  • \$\begingroup\$ Haha, you're already the third to say you don't like the new return type syntax. As I said somewhere else, I find it clearer (but have to admit that it took me a while to adopt it) and allows me to always use the same function syntax. Also, it reminds me of types theory. Well, that's only stylistic whatsoever. \$\endgroup\$
    – Morwenn
    Commented Mar 9, 2014 at 18:10
  • \$\begingroup\$ Concerning the Container, I should have called it AssociativeContainer, that's true. Concerning the iteration, the operator& the truth is that I still have choices to make and the exposition of default_value, which is why I did not include them. Actually, I was seeking review for the proxy mechanism. But your comments are insightful and underline the real problems :) \$\endgroup\$
    – Morwenn
    Commented Mar 9, 2014 at 18:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.