8 Replies - 2223 Views - Last Post: 12 January 2012 - 01:15 PM Rate Topic: -----

#1 Ricky65  Icon User is offline

  • D.I.C Head

Reputation: 38
  • View blog
  • Posts: 115
  • Joined: 03-June 10

Multidimensional array using variadic templates (Advanced)

Posted 04 January 2012 - 01:38 PM

I have created a C++11 container using variadic templates and recursion which extends boost/std::array and supports fixed size multidimensional arrays with an arbitrary number of dimensions.

I have tested the library with the GCC 4.7 compiler and it seems to work fine. I do not have a great deal of experience with variadic templates and there's probably a superior way of achieving this but it is a start.

Here's a link to the container:
Link

Here's a simple test case:
Link

I have a few questions I hope some more advanced programmers familiar with variadic templates can help with.

How would I go about implementing a range checked at() member function? I can't see a way of making the recursion work.

Is there a way to return a pointer to the beginning of the array without using a cast?

Geeral feedback on the container is also welcomed. At the moment it is a work in progress but I feel it could eventually make a great C++11 alternative to built-in C multidimensional arrays.

Kind regards

Ricky

Is This A Good Question/Topic? 1
  • +

Replies To: Multidimensional array using variadic templates (Advanced)

#2 jimblumberg  Icon User is online

  • member icon


Reputation: 3993
  • View blog
  • Posts: 12,322
  • Joined: 25-December 09

Re: Multidimensional array using variadic templates (Advanced)

Posted 04 January 2012 - 02:04 PM

Since you are using items of the new standard that only the most cutting edge compilers will handle it may take awhile before you start getting any feedback. However in my opinion you should use a consistent indentation style and remove "dead" code before you ask for feedback.

Edit: Also you should post your code in the forum.

Jim

This post has been edited by jimblumberg: 04 January 2012 - 02:07 PM

Was This Post Helpful? 0
  • +
  • -

#3 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: Multidimensional array using variadic templates (Advanced)

Posted 04 January 2012 - 03:16 PM

the 'at' function is fairly simple. you would simply pass your variadic arguments to at and return the index of that at the first argument.

if(index >= PrimaryD) {
   throw std::out_of_bounds();
}
return at(...others)[index];



or something really close to that. if it throws at any layer of recursion it will simply unwind and not return the refrence.

This post has been edited by ishkabible: 04 January 2012 - 03:18 PM

Was This Post Helpful? 0
  • +
  • -

#4 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2089
  • View blog
  • Posts: 3,181
  • Joined: 21-June 11

Re: Multidimensional array using variadic templates (Advanced)

Posted 04 January 2012 - 05:28 PM

View PostRicky65, on 04 January 2012 - 09:38 PM, said:

Is there a way to return a pointer to the beginning of the array without using a cast?


In the multi-dimensional case you can return elems[0].data();, which already has type T* and thus doesn't need to be cast, and in the one-dimensional case there's no cast anyway.
Was This Post Helpful? 0
  • +
  • -

#5 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: Multidimensional array using variadic templates (Advanced)

Posted 04 January 2012 - 06:51 PM

this was kinda interesting so I thought I would follow though, turns out my original example is backwards.

here is a basic example of how to implement the 'at' method; I had to change how the typedef 'OneDimensionDownArrayT' was defined to do it however. your way defines 'OneDimensionDownArrayT' to be an array where as my way defines it as a variadic_array; that allows you to call the sub array's methods which allows for a multidimensional 'at' method. your way might work too I just couldn't think of a way to do it.

#include <iostream>
#include <stdexcept>

//start of container
template<class T, std::size_t ... RestD>
struct variadic_array;

template<class T, std::size_t PrimaryD >
struct variadic_array<T, PrimaryD> {
	typedef T type[PrimaryD];
	type data;
	T& at(std::size_t index) {
		if(index >= PrimaryD) {
			throw std::out_of_range("variadic_array");
		}
		return data[index];
	}
};

template<class T, std::size_t PrimaryD, std::size_t ... RestD >
struct variadic_array<T, PrimaryD, RestD...> {
	typedef variadic_array<T, RestD...> sub_dimension_array;
	typedef sub_dimension_array type[PrimaryD];
	type data;

	template<typename... RestI>
	T& at(std::size_t index, RestI... rest) {
		if(index >= PrimaryD) {
			throw std::out_of_range("variadic_array");
		}
		return data[index].at(rest...);
	}
};

int main() {
	variadic_array<int, 2, 2, 2> a;
	a.at(1, 0, 1) = 10;
	a.at(1, 1, 1) = 20;
	std::cout<<a.at(1, 0, 1)<<'\n';
	std::cout<<a.at(1, 1, 1)<<'\n';
	a.at(0, 1, 2); //throws error
}


edit:
also my original has the '...' operator backwards and the exception i was thinking of was "out_of_range" not "out_of_bounds"

This post has been edited by ishkabible: 04 January 2012 - 06:54 PM

Was This Post Helpful? 1
  • +
  • -

#6 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2089
  • View blog
  • Posts: 3,181
  • Joined: 21-June 11

Re: Multidimensional array using variadic templates (Advanced)

Posted 04 January 2012 - 07:14 PM

Nevermind.

This post has been edited by sepp2k: 04 January 2012 - 07:16 PM

Was This Post Helpful? 0
  • +
  • -

#7 Karel-Lodewijk  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 449
  • View blog
  • Posts: 849
  • Joined: 17-March 11

Re: Multidimensional array using variadic templates (Advanced)

Posted 04 January 2012 - 10:07 PM

Not really on-topic but related. I tried some different approaches to what you are trying to do and compared their memory lay-out.

Basically I compared

  • Native int[5][3]
  • Your approach
  • std::array<std::array<int, 3>, 5>
  • variadic wrapper for nested std::array


Interestingly they have the same size and memory lay-out as the native multidimensional array type, so there is no real reason to prefer one over the other. But If I had the choice, I'd go for the std::array<std::array> within a variadic wrapper, it has a lot of the functionality you need already.

It also raises interesting questions. How do you want a multi-dimensional array to behave ?

An iterator for a multi-dimensional array, should it go over elements or over the arrays that are 1 level down ?
What must a size function do ?

To me the default behavior of a nested std::array is more what I have in mind when I think of a stl multi-dimensional array. What you implemented are the member functions for a flat array grafted upon a multi-dimensional data structure.
Some convenience function for multi-dimensional arrays are nice (at(x,y,z)/flattened size/dimension query) and a flatten member function that gives me a flattened version of a multi-dimensional array.

Anyway, the test code (tested on g++ 4.6.1):
Spoiler


Also this was an interesting read: http://cpptruths.blo...ys-in-c11.html.

This post has been edited by Karel-Lodewijk: 04 January 2012 - 10:12 PM

Was This Post Helpful? 0
  • +
  • -

#8 Ricky65  Icon User is offline

  • D.I.C Head

Reputation: 38
  • View blog
  • Posts: 115
  • Joined: 03-June 10

Re: Multidimensional array using variadic templates (Advanced)

Posted 09 January 2012 - 08:12 AM

Sorry for the delay in replying; I've been a bit busy.

jimblumberg said:

...in my opinion you should use a consistent indentation style and remove "dead" code before you ask for feedback.
Edit: Also you should post your code in the forum.

Sorry, the indentation got messed up in my text editor although I think the dead code is negligible.
I thought about posting the source files on here but decided it was a bit large.

ishkabible said:

here is a basic example of how to implement the 'at' method; I had to change how the typedef 'OneDimensionDownArrayT' was defined to do it however. your way defines 'OneDimensionDownArrayT' to be an array where as my way defines it as a variadic_array; that allows you to call the sub array's methods which allows for a multidimensional 'at' method. your way might work too I just couldn't think of a way to do it.

Good idea. Why didn't I think of that?! After all, variadic_array is just a wrapper for a built-in array.
I too don't know the syntax for my way, hence that part of the OP. If you ever find out how, please share :).

Karel-Lodewijk said:

It also raises interesting questions. How do you want a multi-dimensional array to behave ?

As a multidimensional version of std::array, or in other words, an STL-like alternative to built-in multidimensional arrays. For example, it should know it's own size and the most significant dimension of the array shouldn't decay when passed to a function.

I'm aware that people may have different opinions as to what a fixed sized STL-like multidimensional array should be.

Karel-Lodewijk said:

An iterator for a multi-dimensional array, should it go over elements or over the arrays that are 1 level down ?

Like the STL, iterate over all the elements of the array. I have thought about including dimension iterators as I think they would be useful.

Karel-Lodewijk said:

What must a size function do ?

Like the size() member function of STL containers such as vector, it should return the total number of elements in the whole multidimensional array. I also provide a dim_size() member function to query the size of a specific dimension.

Karel-Lodewijk said:

To me the default behavior of a nested std::array is more what I have in mind when I think of a stl multi-dimensional array. What you implemented are the member functions for a flat array grafted upon a multi-dimensional data structure.

Nested std::array has several disadvantages. Firstly, the syntax can get very verbose and confusing. Do you get the syntax right for a 4D nested std::array first time? I don't!

Disadvantages of this method are that begin(), end() and size() all return meaningless values for two or more dimensions. We cannot enumerate over the elements using begin() and end() because they will return pointers to the next dimension down and size() will only return the number of elements in the most significant dimension of the array. My variadic_array solution is far superior imo.
Was This Post Helpful? 0
  • +
  • -

#9 Karel-Lodewijk  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 449
  • View blog
  • Posts: 849
  • Joined: 17-March 11

Re: Multidimensional array using variadic templates (Advanced)

Posted 12 January 2012 - 01:15 PM

View PostRicky65, on 09 January 2012 - 03:12 PM, said:

Sorry for the delay in replying; I've been a bit busy.


No problem, me too.

View PostRicky65, on 09 January 2012 - 03:12 PM, said:

Karel-Lodewijk said:

To me the default behavior of a nested std::array is more what I have in mind when I think of a stl multi-dimensional array. What you implemented are the member functions for a flat array grafted upon a multi-dimensional data structure.

Nested std::array has several disadvantages. Firstly, the syntax can get very verbose and confusing. Do you get the syntax right for a 4D nested std::array first time? I don't!


It doesn't have to be, in my previous snippet variadic_array1 was a way to create a nested std::array with the same syntax your class uses, variadic_array1<int, 5, 3>.

View PostRicky65, on 09 January 2012 - 03:12 PM, said:

Disadvantages of this method are that begin(), end() and size() all return meaningless values for two or more dimensions. We cannot enumerate over the elements using begin() and end() because they will return pointers to the next dimension down and size() will only return the number of elements in the most significant dimension of the array. My variadic_array solution is far superior imo.


That is why I suggested convenience functions like a number of dimensions query/a at(x,y,z) function and a flatten function that returns a flat representation of the same data.

I've written a POC for a multi-dimensional array based on a nested std::array. The most important addition is that it provides a flatten function that gives a flattened representation of the data so you can approach it as a 1D std::array. I also provided convenience functions that are useful to find out the number of dimensions, the flat size, and an at(x,y,z,...) function that takes any number of parameters <= dim and returns the appropriate element/subarray.

One thing I don't like about this is that by inheriting from std::array, it's no longer an aggregate type, which means I suddenly have to write a constructor for it to accept initializer lists and it's probably less efficient.

Note that I couldn't find a compiler with sufficient c++11 support to make it work to my liking. The code here does compile using clang++ >= 3.0 (clang++ -std=c++0x) but clang 3.0 doesn't support c++11 initializer lists, so it will not accept those yet. It does not compile with gcc <= 4.7 because gcc lacks templated typedefs and inheriting constructors. But it is valid C++11 as far as I can tell.

Not that it can't be fixed for gcc. Copying the constructors for std::array in multi_array and use the classic typedef within a templated struct for the templated typedef would do the trick.

code, see tests in main first:
Spoiler


version 2, it gets rid of the create_array, but essentially is the same structure. I'm not certain I like this better.
Spoiler


version 3, gcc 4.7 compatible version, supports initializer lists but not the at(x,y,z).
Spoiler


output:
Spoiler

This post has been edited by Karel-Lodewijk: 12 January 2012 - 10:43 PM

Was This Post Helpful? 2
  • +
  • -

Page 1 of 1