Originally posted by: SystemAdmin
A very elegant solution to the multi-dimensional array problem is recursive templates.
Once you have defined such a template you can easily define multi-dimensional arrays
of any type. I sometimes use this one here:
template<unsigned int D,typename T> class Array;
// Partial specialization to terminate instantiation recursion.
template<typename T>
struct Array<1,T> {
typedef T nested_type;
typedef std::vector<T> container_type;
typedef typename container_type::iterator iterator;
typedef typename container_type::const_iterator const_iterator;
typedef typename container_type::reverse_iterator reverse_iterator;
typedef typename container_type::const_reverse_iterator const_reverse_iterator;
typedef typename container_type::size_type size_type;
typedef typename container_type::reference reference;
typedef typename container_type::const_reference const_reference;
typedef typename container_type::pointer pointer;
typedef typename container_type::const_pointer const_pointer;
typedef typename container_type::difference_type difference_type;
typedef typename container_type::value_type value_type;
typedef T base_type;
Array() : container() {}
template<typename I> Array(I const& i) : container(*i) {}
// Default copy constructor and assignment operator are ok
// but are expensive.
iterator begin() { return container.begin(); }
iterator end() { return container.end(); }
const_iterator begin() const { return container.begin(); }
const_iterator end() const { return container.end(); }
reverse_iterator rbegin() { return container.rbegin(); }
reverse_iterator rend() { return container.rend(); }
const_reverse_iterator rbegin() const { return container.rbegin(); }
const_reverse_iterator rend() const { return container.rend(); }
reference operator[](size_type idx) { return container[idx]; }
const_reference operator[](size_type idx) const { return container[idx]; }
reference at(size_type idx) { return container.at(idx); }
const_reference at(size_type idx) const { return container.at(idx); }
size_type size() const { return container.size(); }
void fill(T const& t) {
for (iterator it = begin(); it != end(); ++it)
*it = t;
}
private:
container_type container;
};
template<unsigned int D,typename T>
struct Array {
typedef Array<D-1,T> nested_type;
typedef typename std::vector<nested_type> container_type;
typedef typename container_type::iterator iterator;
typedef typename container_type::const_iterator const_iterator;
typedef typename container_type::reverse_iterator reverse_iterator;
typedef typename container_type::const_reverse_iterator const_reverse_iterator;
typedef typename container_type::size_type size_type;
typedef typename container_type::reference reference;
typedef typename container_type::const_reference const_reference;
typedef typename container_type::pointer pointer;
typedef typename container_type::const_pointer const_pointer;
typedef typename container_type::difference_type difference_type;
typedef typename container_type::value_type value_type;
typedef T base_type;
Array() : container() {}
template<typename I>
Array(I i) : container(*i, nested_type(i + 1)) {}
// Default copy constructor and assignment operator are ok
// but are expensive.
// template<typename C>
// Array(C const& c) : container(*c.begin(), c.begin() + 1) {}
iterator begin() { return container.begin(); }
iterator end() { return container.end(); }
const_iterator begin() const { return container.begin(); }
const_iterator end() const { return container.end(); }
reverse_iterator rbegin() { return container.rbegin(); }
reverse_iterator rend() { return container.rend(); }
const_reverse_iterator rbegin() const { return container.rbegin(); }
const_reverse_iterator rend() const { return container.rend(); }
reference operator[](size_type idx) { return container[idx]; }
const_reference operator[](size_type idx) const { return container[idx]; }
reference at(size_type idx) { return container.at(idx); }
const_reference at(size_type idx) const { return container.at(idx); }
size_type size() const { return container.size(); }
void fill(T const& t) {
for (iterator it = begin(); it != end(); ++it)
it->fill(t);
}
private:
container_type container;
};
Example use of this template is:
int
main(void)
{
unsigned int const dim[] = { 3, 4, 5 };
Array<3,int> array(dim);
array[0][0][0] = 1;
std::cout << array.size()
<< ", " << array[0].size()
<< ", " << array[0][0].size()
<< std::endl;
std::vector<unsigned int> dim2(dim, dim + sizeof(dim) / sizeof(dim[0]));
Array<3,int> array2(dim2.begin());
array2.fill(358);
std::cout << array2.size()
<< ", " << array2[0].size()
<< ", " << array2[0][0].size()
<< ", " << array2[0][1][2]
<< std::endl;
return 0;
}
The implementation above is dense, i.e. it will suffer from the memory issues
you mentioned. In order to have a sparse version I would base the template
definition on map rather than vector:
template<unsigned int D,typename T> class SparseArray;
// Partial specialization to terminate instantiation recursion.
template<typename T>
struct SparseArray<1,T> {
enum { dimension = 1 };
typedef std::map<int,T> container_type;
typedef typename container_type::iterator iterator;
typedef typename container_type::const_iterator const_iterator;
typedef typename container_type::reverse_iterator reverse_iterator;
typedef typename container_type::const_reverse_iterator const_reverse_iterator;
typedef typename container_type::size_type size_type;
typedef T &reference;
typedef T const &const_reference;
typedef T *pointer;
typedef T const *const_pointer;
typedef T base_type;
SparseArray() : container() {}
// Default copy constructor and assignment operator are ok
// but are expensive.
iterator begin() { return container.begin(); }
iterator end() { return container.end(); }
iterator find(int idx) { return container.find(idx); }
const_iterator begin() const { return container.begin(); }
const_iterator end() const { return container.end(); }
const_iterator find(int idx) const { return container.find(idx); }
reverse_iterator rbegin() { return container.rbegin(); }
reverse_iterator rend() { return container.rend(); }
const_reverse_iterator rbegin() const { return container.rbegin(); }
const_reverse_iterator rend() const { return container.rend(); }
reference operator[](size_type idx) { return container[idx]; }
const_reference operator[](size_type idx) const { return container[idx]; }
size_type size() const { return container.size(); }
private:
container_type container;
};
template<unsigned int D,typename T>
struct SparseArray {
enum { dimension = D };
typedef SparseArray<D-1,T> nested_type;
typedef typename std::map<int,nested_type> container_type;
typedef typename container_type::iterator iterator;
typedef typename container_type::const_iterator const_iterator;
typedef typename container_type::reverse_iterator reverse_iterator;
typedef typename container_type::const_reverse_iterator const_reverse_iterator;
typedef typename container_type::size_type size_type;
typedef nested_type &reference;
typedef nested_type const &const_reference;
typedef nested_type *pointer;
typedef nested_type const *const_pointer;
typedef T base_type;
// Default copy constructor and assignment operator are ok
// but are expensive.
iterator begin() { return container.begin(); }
iterator end() { return container.end(); }
iterator find(int idx) { return container.find(idx); }
const_iterator begin() const { return container.begin(); }
const_iterator end() const { return container.end(); }
const_iterator find(int idx) const { return container.end(); }
reverse_iterator rbegin() { return container.rbegin(); }
reverse_iterator rend() { return container.rend(); }
const_reverse_iterator rbegin() const { return container.rbegin(); }
const_reverse_iterator rend() const { return container.rend(); }
reference operator[](size_type idx) { return container[idx]; }
const_reference operator[](size_type idx) const { return container[idx]; }
size_type size() const { return container.size(); }
private:
container_type container;
};
Then you can do
int
main(void)
{
IloEnv env;
SparseArray<3,IloNumVar> array;
array[0][0][0] = IloNumVar(env, 0, 1, "x");
array[1][2][3] = IloNumVar(env, 0, 1, "y");
std::cout << array[1][2][3].getName() << std::endl
<< array[0][0][0].getName() << std::endl;
return 0;
}
Caveat:
-
Recursive templates require a decent compiler.
-
I know quite some stuff about templates but are by no means a guru. So the above examples may contain errors or stuff that can be done in a better way.
-
I designed the two templates a while ago for research purposes. I did not give them much testing in practice.
I'd be happy to hear if you find issues with my implementation or if it did help you.
You may also want to try to define your own recursive template. It is quite funny if you like coding :-)
#CPLEXOptimizers#DecisionOptimization