Template Metaprogramming - Multidimensional Vector Declaration

Question

[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]

Answer 1

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.