If this were Algol or Pascal, we might simply issue the following
declarations to implement ariels' example matrix:
type compass = array [-1..1, -1..1] of integer;
const conv = compass [7, 6, 5, 8, 0, 4, 1, 2, 3]; { HIGHLY compiler-dependent }
{ const conv: compass = ((7, 6, 5), (8, 0, 4), (1, 2, 3)); Delphi }
and simply use the
conv structured constant. But Pascal is not the favorite programming language of many people (more's the pity) and we must look to other languages to solve our problem.
ariels' method for his C example essentially works like this: Convert the array into a pointer, fiddle with the pointer, convert it back into an array. Now, I personally can't see how this would work any way other than the way he describes, but unfortunately, a C++ compiler isn't supposed to compile it.
You can convert an array to a pointer1 then add to it. But you can't convert a pointer back to an array, period. Converting a pointer into an array via static_cast is explicitly forbidden2 by the C++ Standard, and the section on reinterpret_cast3 does not mention it as one of the allowed conversions. Even if it were allowed, it would result in unspecified behavior.
If we only wanted a one-dimensional array, we wouldn't have to convert it back. We could do something like
const int *zero_based = { 7, 6, 5, 8, 0, 4, 1, 2, 3 };
const int *translated = zero_based+4;
and access
translated[-4] thru
translated[4] with no problems
4. Unfortunately, to get a multidimensional array, you need to
cast back to a multidimensional array type, which you can't do.
So, we're left with the problem of how to do negative array indexing in C++. The answer is "design a class to do it", as you might expect with anything complicated in C++. Examining the Pascal example above, we find there are four things to implement:
- Allocating and maintaining access to an array.
- Providing for negative array indexing.
- Restricting the allowed index values.
- Extending the array to multiple dimensions.
The most flexible type of array would also allow it to be rotated, such that sub-arrays
could be accessed from different dimensions, but that's extraneous to our purpose. But
examining and discarding this task helps us in our design: Examining the task further, we see
that issues 3 and 4 can also be put aside for now. Issue 3 can be solved using the
Constrained pattern to design a restricted index type for the array. Issue 4 can be solved
with recursive templates, or by designing proxy classes that allow different slices
into the array in much the same way as C++'s valarray template.
We're left with allocating and maintaining acces to the array, as well as providing for
negative array indexing. Believe it or not, C++ already contains a class that'll work for
us! We can simply use a std::map<long, value-type> for some value-type we want to collect. This technique is the best one if we have a fairly sparse array, or if we're going to access the array exclusively via the map's subscripting operator, operator[]() Unfortunately, map iterators don't work like array iterators. A secondary consideration is the greater amount of overhead for a map versus an array or a std::vector So if we want to use sandard algorithms on the elements of the array class, we'll have to roll our own.
But thinking about standard container classes introduces the notion that we could at least design an array class analogous to a standard one. We have the choice of emulating two Standard C++ Container classes: std::vector and std::valarray5. We can't use either directly, as both require an unsigned integral type as an index. We could simply wrap one of these classes and provide an offset:
#include <vector>
template<class T, class allocator=std::Allocator<T> >
class nvector
{
long offset;
std::vector<T, allocator> wrapped;
public:
typedef long index_type;
T &operator[] (long i) { return wrapped [i+offset]; }
T const &operator[] (long i) const { return wrapped [i+offset]; }
//
// Now, imagine all the other vector boiler plate, forwarded to the
// wrapped vector
//
};
However, since we've dropped the implied requirement for all indexes to start at zero, we've opened up the possibility of modifying the array at both ends (similar to a std::list). We will probably be better off making our own implemntation that takes care of both ends, using vector as our inspiration:
template<class T, class allocator=std::Allocator<T> >
class devector
{
private:
T *blkbeg;
T *arrbeg;
T *arrend;
T *blkend;
long begindex;
void ensure_index (long i); // implmentation left to your imagination
public:
T *begin() { return arrbeg; }
T const *begin() const { return arrbeg; }
T *end() { return arrbeg; }
T const *end() const { return arrend; }
size_t size() { return arrend-arrbeg; }
size_t capacity() { return blkend-blkbeg; }
typedef long index_type;
T &operator[] (long i)
{
ensure_index (i);
return *(arrbeg+begindex);
}
T const &operator[] (long i) const
{
if (i < begindex) return T();
if (begindex-i >= size() return T();
return *(arrbeg+begindex);
}
//
// Now, imagine all the other nice sequencey stuff, properly implemented
//
};
As suggested above, devector < devector <some-type> > would be a (somewhat inflexible) two-dimensional array that allowed negative indexing.
References to International Standard ISO-IEC 14882, Programming Languages -- C++, published by the American National Standards Institute, © 1998 Information Technology Industry Council:
1Section 4.2, Array-to-pointer conversion
2Section 5.2.9.6, static_cast
3Section 5.2.10, reinterpret_cast
4Section 5.2.1, Subscripting
5I hear you laughing, ariels. valarray is so complex as to be almost useless, but it is our best starting point for a rotatable, sliceable array that also allows negative indexing.