5
\$\begingroup\$

[EDIT]

The question has been edited. Please make sure to read the summary at the end of the post. If you'd like me to make a new post with a cleaner explanation and better examples, tell me to do so in the comments.

[/EDIT]

[ORIGINAL]

Recently, I've started learning and exploring more about template metaprogramming. I thought I had a new idea this morning when I thought of implementing a multidimensional vector declarator using templates, but turns out it has already been invented after just one google search :[

Here's a very simple implementation I've written:

// Multidimensional Vector Declarator

template <typename T, size_t D = 1>
struct matrix
    : std::vector <matrix <T, D - 1>> {

    static_assert(D > 0, "matrix dimensions must be positive");

    template <typename...Args>
    matrix (const size_t& size = 0, const Args&... args)
        : std::vector <matrix <T, D - 1>> (size, matrix <T, D - 1> (args...))
    { }
};

template <typename T>
struct matrix <T, 1>
    : public std::vector <T> {
    matrix (const size_t& size = 0, const T& value = 0)
        : std::vector <T> (size, value)
    { }
};

// Usage

// Declare a 1-D vector
matrix <int> m;             // equivalent to std::vector <int> m (0, 0)
matrix <int, 1> m;          // equivalent to std::vector <int> m (0, 0)
matrix <int, 1> m (10);     // equivalent to std::vector <int> m (10, 0)
matrix <int, 1> m (10, 42); // equivalent to std::vector <int> m (10, 42)

// Declare a 2-D vector
matrix <int, 2> m;             // equivalent to std::vector <std::vector <int>> m (0, std::vector <int> (0, 0))
matrix <int, 2> m (10);        // equivalent to std::vector <std::vector <int>> m (10, std::vector <int> (0, 0))
matrix <int, 2> m (10, 5);     // equivalent to std::vector <std::vector <int>> m (10, std::vector <int> (5, 0))
matrix <int, 2> m (10, 5, 42); // equivalent to std::vector <std::vector <int>> m (10, std::vector <int> (5, 42))

// ...so on

// alternate implementation
// i find that i'm more limited this way
// i could essentially add multiple constructors and make it more sophisticated
//   to be able to achieve what i want, but I'd like to do so in a simple
//   manner. suggestions on the same are welcome.
template <typename T, size_t D = 1>
struct matrix
    : std::vector <matrix <T, D - 1>> {

    static_assert(D > 0, "matrix dimensions must be positive");

    template <typename...Args>
    matrix (const Args&... args)
        : std::vector <matrix <T, D - 1>> (args...)
    { }
};

template <typename T>
struct matrix <T, 1>
    : public std::vector <T> {
    template <typename...Args>
    matrix (const Args&... args)
        : std::vector <T> (args...)
    { }
};

I would like to know if this achieves what I think it achieves (because it looks way too simple and I'm afraid of loss of freedom in how I'm able to use this sort of a multidimensional vector). I would also like to be able to use this as freely as I'm able to use the equivalent forms of std::vector. From some light testing, everything works well and good, and I'm happy, but as I'm no language expert, I can't be sure.

What are other ways I could achieve the same properties as I seek to achieve, perhaps ones without using deriving from classes, or without classes altogether? Is it possible to implement what I have purely through template <typename T> using ... = ...;?

[/ORIGINAL]

[EDIT]

After being asked by a fellow SE.CR-er, here's an example which you can compile and test.

// Forgive me for not writing all includes like I should
// PCH for fast compile time

#include "bits/stdc++.h"

// Just some debugging code
// Important stuff a couple of lines below this

namespace debugging::inline utility {

    template <typename T, typename = void>
    struct is_istream_streamble
        : std::false_type
    { };

    template <typename T>
    struct is_istream_streamble <T, std::void_t <decltype(std::cin >> std::declval <T&> ())>>
        : std::true_type
    { };

    template <typename T>
    constexpr bool is_istream_streamble_v = is_istream_streamble <T>::value;

    template <typename T, typename = void>
    struct is_ostream_streamble
        : std::false_type
    { };

    template <typename T>
    struct is_ostream_streamble <T, std::void_t <decltype(std::cerr << std::declval <T> ())>>
        : std::true_type
    { };

    template <typename T>
    constexpr bool is_ostream_streamble_v = is_ostream_streamble <T>::value;

    template <typename T, typename = void>
    struct has_begin_iterator
        : std::false_type
    { };

    template <typename T>
    struct has_begin_iterator <T, std::void_t <decltype(std::declval <T> ().begin())>>
        : std::true_type
    { };

    template <typename T>
    constexpr bool has_begin_iterator_v = has_begin_iterator <T>::value;

    template <typename T, typename = void>
    struct has_end_iterator
        : std::false_type
    { };

    template <typename T>
    struct has_end_iterator <T, std::void_t <decltype(std::declval <T> ().end())>>
        : std::true_type
    { };

    template <typename T>
    constexpr bool has_end_iterator_v = has_end_iterator <T>::value;

    template <typename T>
    constexpr bool has_begin_end_iterator_v = has_begin_iterator_v <T> && has_end_iterator_v <T>;
}

namespace debugging {

    class view {
      private:
        std::ostream& stream;
      public:
        view (std::ostream& stream = std::cerr) : stream (stream) { }

#ifdef LOST_IN_SPACE
        template <typename T>
        std::enable_if_t <is_ostream_streamble_v <T>, view&>
        operator () (const T& object)
        { return stream << object, *this; }

        template <typename T>
        std::enable_if_t <!is_ostream_streamble_v <T> && has_begin_end_iterator_v <T>, view&>
        operator () (const T& object) {
            (*this)("{");
            for (const auto& element : object)
                (*this)(element, ' ');
            return (*this)(object.begin() == object.end() ? "}" : "\b}");
        }

        template <typename A, typename B>
        view& operator () (const std::pair <A, B>& pair)
        { return (*this)("(", pair.first, ", ", pair.second, ")"); }

        template <size_t N, typename...T>
        std::enable_if_t <(sizeof...(T) <= N), view&>
        operator () (const std::tuple <T...>&)
        { return *this; }

        template <size_t N, typename...T>
        std::enable_if_t <(sizeof...(T) > N), view&>
        operator () (const std::tuple <T...>& tuple)
        { return (*this)(std::get <N> (tuple), ' '), operator () <N + 1, T...> (tuple); }

        template <typename...T>
        view& operator () (const std::tuple <T...>& tuple) {
            (*this)("<");
            operator () <0, T...> (tuple);
            return (*this)(sizeof...(T) > 0 ? "\b>" : ">");
        }

        view& operator () ()
        { return *this; }

        template <typename A, typename...B>
        view& operator () (const A& object, const B&...objects)
        { return (*this)(object)(objects...); }
#else
        template <typename...T>
        view& operator () (const T&...)
        { return *this; }
#endif
    };
}

using view = debugging::view;
view debug (std::cerr);
#define print(x) " [", #x, ": ", x, "]\n\n"

// Multidimensional Vector Declarator

template <typename T, size_t D = 1>
struct matrix
    : std::vector <matrix <T, D - 1>> {

    static_assert(D > 0, "matrix dimensions must be positive");

    template <typename...Args>
    matrix (const size_t& size = 0, const Args&... args)
        : std::vector <matrix <T, D - 1>> (size, matrix <T, D - 1> (args...))
    { }
};

template <typename T>
struct matrix <T, 1>
    : public std::vector <T> {
    matrix (const size_t& size = 0, const T& value = 0)
        : std::vector <T> (size, value)
    { }
};

int main () {
    // Usage

    // Declare a 1-D vector
    matrix <int> m1;             // equivalent to std::vector <int> m1 (0, 0)
    matrix <int, 1> m2;          // equivalent to std::vector <int> m2 (0, 0)
    matrix <int, 1> m3 (10);     // equivalent to std::vector <int> m3 (10, 0)
    matrix <int, 1> m4 (10, 42); // equivalent to std::vector <int> m4 (10, 42)

    // Declare a 2-D vector
    matrix <int, 2> m5;             // equivalent to std::vector <std::vector <int>> m5 (0, std::vector <int> (0, 0))
    matrix <int, 2> m6 (10);        // equivalent to std::vector <std::vector <int>> m6 (10, std::vector <int> (0, 0))
    matrix <int, 2> m7 (10, 5);     // equivalent to std::vector <std::vector <int>> m7 (10, std::vector <int> (5, 0))
    matrix <int, 2> m8 (10, 5, 42); // equivalent to std::vector <std::vector <int>> m8 (10, std::vector <int> (5, 42))

    debug(print(m1), print(m2), print(m3), print(m4), print(m5), print(m6), print(m7), print(m8));

    // Normally use like you'd use a vector <type>

    // Dimensions
    int a, b, c;
    std::cin >> a >> b >> c; // 2 3 2
    // Dynamic sized vector
    matrix <int, 3> m (a, b, c);

    // Reading input
    // 8 4 2 7 1 3 6 11 12 5 9 10
    for (int i = 0; i < a; ++i)
        for (int j = 0; j < b; ++j)
            for (auto& k : m [i].at(j))
                std::cin >> k;

    debug(print(m));

    // Sorting
    std::sort(begin(m), end(m));
    debug(print(m));
    std::sort(begin(m [1]), end(m.at(1)));
    debug(print(m));

    // Other std::algorithms
    std::transform(begin(m.at(1)[2]), end(m[1].at(2)), begin(m [1][2]), [] (auto i) -> int { return i + 1; });
    m [0][2][1] = 42;
    debug(print(m));

    // Clear
    m.clear();
    debug(print(m.size()));

    return 0;
}

Everything works like you'd expect it to. My matrix type is trying to abstract away the number of dimensions one would use to type std::vector <std::vector <.....>>. I have no problem regarding how efficient the code produced would be. I expect it to be equivalently efficient to the multiple dimension "normal" std::vector declaration. Please correct me if I'm wrong.

To respecify what I intend to do, here's a short bulletted summary:

  • Implement an interface which abstracts away the number of dimensions from using a multiple dimension std::vector. Doing things this way reduces the verbosity in declaring a 3D vector, let's say, and using it this way instead:
// long version
std::vector <std::vector <std::vector <int>>> v (a, std::vector <std::vector <int>> (b, std::vector <int> (c, d)));

// slighly shorter
template <typename T>
using vec = std::vector <T>;
vec <vec <vec <int>>> v (a, vec <vec <int>> (b, vec <int> (c, d)));

// better?
matrix <int, 3> v (a, b, c, d);
  • Implement as short as possible code (without the need to write multiple overloaded constructors, if possible) to construct the matrix type as freely as you'd be able construct equivalent std::vector implementation with initializer lists, etc...
// to use initialiser lists, what you can (need to) do is:
matrix <int, 1> m (std::initializer_list <int> {1, 2, 3});
// remember, with the above long example code, this is not possible.
// look at the code before the EDIT using variadic templates to use this

// presently, you can't do this:
matrix <int, 1> m {1, 2, 3};
// but this is what I'd like to achieve in as simple a way as possible.
//
// if not possible to do so in a simple straight-forward way without overloading
// many constructor versions, alright, end of discussion. i've figured as much too, as of now
//
// also, not just keeping the implementation limited to initializer lists, i would
// like it to be extensible too all constructor types and parameters of a std::vector
//
// in the near future, i also plan to make the implementation more generic.
// instead of limiting to std::vector, as in my current implementation, i would
// also accept other containers and only abstract the dimension part away.
// probable usage:
matrix <std::vector, int, 3> m; // 3 dimensional std::vector of int
matrix <std::array, int 2> m;   // 2 dimensional std::array of int
  • In my code above, I use class derivation. Is there an idea to do so without it? Is there a way to only use using ... = ... and be able to abstract away dimensions?

  • I do realise the fact that this question seems irrelevant to SE Code Review (because it is about best practices and writing efficient code), as also stated by fellow SE.CR-ers. It would be great, and I would be very thankful, if you could suggest me the right SE platform for this question. Stack Overflow?

[/EDIT]

\$\endgroup\$
8
  • \$\begingroup\$ Also, with the above code, I've noticed I can't freely use initializer lists without explicitly writing std::initializer_list, or using any similar implementation to it that adapts to c++ initializer lists, in the constructor. How could I get that sort of freedom back without bloating up my code size? I know it definitely doesn't work with the above version. However, on a similar version where I template specialize matrix <T, 1> with a variadic template constructor, I always need to use the std::initializer_list to get initializer lists to work. \$\endgroup\$ – Lost Arrow Nov 7 '20 at 17:36
  • \$\begingroup\$ Have you actually tested it and does it work as expected. \$\endgroup\$ – pacmaninbw Nov 10 '20 at 22:32
  • \$\begingroup\$ @pacmaninbw Yes, it does work as expected, except that it is limited in the way I can construct it. Writing all sorts of constructor overloads (which I did try) that in turn pass on the values to the constructors of std::vector makes everything work smoothly. Maybe not so smoothly as I'd expect though (I need to explicitly type std::initializer_list in front of a brace-enclosed initialiser to make it work, among other things which I may have left uncovered). All other things like accessing with [], resizing, sorting and clearing, work cleanly. \$\endgroup\$ – Lost Arrow Nov 10 '20 at 22:37
  • \$\begingroup\$ Please post the complete code it's missing the necessary headers. It would be best to post any unit test code you have as well. \$\endgroup\$ – pacmaninbw Nov 10 '20 at 22:43
  • \$\begingroup\$ @pacmaninbw Sure, doing so now. Unfortunately, I'll have to rewrite unit testing code as I have very messy debugging code lying around which will burn eyes. I'll get to it. \$\endgroup\$ – Lost Arrow Nov 10 '20 at 22:47
2
\$\begingroup\$

It has the same issues as almost all other recursion based solutions. It is inefficient AF.

Imagine you have a 4 dimensional matrix. Then to access an element you need to need to access memory 4 times in full random access. Currently, memory access is one of the main sources of slowdown of the system. On an average PC, access to RAM memory takes over a hundred cycles.

Memory is transferred in cachelines (64 bytes currently) so accessing data in the same cacheline is efficient. Also, if compiler is able to figure out beforehand which cacheline is needed to be loaded then it can sequence its load beforehand while doing other things.

But in your case neither optimization is even remotely possible to do in all 4 times as compiler has no clue what data is contained in those vertexes.

Standard practice it to flatten the matrix. Store a single std::vector of data and two arrays std::array<size_t,N> of dimensions and step sizes (normally step sizes are determined by dimensions but they are better be pre-calculated). And to figure out where exactly element corresponding to (x,y,z,w) simply compute x*step[0]+y*step[1]+z*step[2]+w*step[3] and access this element of the vector (normally either step[0] or step[3] is 1 depending on your choice of format).

In addition it reduces significantly the amount of calls to memory allocations and deallocations as those are slow AF and cause memory fragmentation issues if used too many times.

This way you need just a single memory load to access an element and if you use it contiguously with properly implemented iterators then the compiler will be able to optimize it to decent performance. To improve it further it'll require to utilize SIMD instructions and/or multithreading.

\$\endgroup\$
5
  • \$\begingroup\$ What does this answer have anything to do with my question? Please consider deleting it. \$\endgroup\$ – Lost Arrow Nov 10 '20 at 15:04
  • \$\begingroup\$ @LostArrow the problem is that the idea is impractical and there are far better solutions. \$\endgroup\$ – ALX23z Nov 10 '20 at 15:26
  • \$\begingroup\$ my question nowhere mentions that I'm looking for an efficient solution. The way I'd manually define std::vector <std::vector <...>>, I'd like to abstract the dimensions part off, and implement it with a generic interface which takes a type and dimension instead to do exactly what the nested vector declaration looks like and would do. As far as efficiency goes, if I wanted it, it'd have been mentioned in the question. Doing things the way I've given in the example will be equally as efficient as using the nested vectors. I'm not asking to efficient-ise that or the access with [][][][]... \$\endgroup\$ – Lost Arrow Nov 10 '20 at 15:44
  • \$\begingroup\$ @LostArrow I think you got to a wrong site. Code review is about reviewing written code - what's good or bad about it and some advices to improve it. If you want to learn how to write C++ code there are other sites for it like FreeCodeAcademy.com or something. Or just buy/download a C++ guide book. \$\endgroup\$ – ALX23z Nov 10 '20 at 15:55
  • \$\begingroup\$ @LostArrow One of main points of C++ is to implement efficient and safe code. If you abstract away dimension you ensure that it can be neither efficient nor type safe. At best you'll get runtime safety checks. You'll need to store dimensions in a dynamic array an accepts a range for input. Not suitable for basic classes. Also in general multidimensional matrices aren't practical as within a few dimensions you overload the whole memory RAM way too fast. \$\endgroup\$ – ALX23z Nov 10 '20 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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