Intrinsic Array as a Container

[Frederick Gotham]

Inspired by page 219 of Nicolai M. Josuttis's book, I set out to write a
class for an intrinsic array which would behave, to as far an extent as
possible, like a container. Also though, I wanted no overhead whatsoever.

The code I'm about to show below is not finished, it may contain the odd
oversight, bug or error (but at a quick glance it seems OK).

First of all though, I want to show you some macros I've written. The
purpose of the macros is to:

(1) Reduce repetitive typing.
(2) Reduce the possibility for error.

Before you use these macros though, you must a typedef to your class, e.g.:

class SmartPointerOrW hatever {
typedef SmartPointerOrW hatever ThisClass;
};

The first macro, "POST_IN_TERMS_ OF", expands to a definition of a post-
operator which invokes the corresponding pre-operator. Here it is:

#define POST_IN_TERMS_O F(op) \
ThisClass operator op(int) \
{ \
ThisClass const temp(*this); \
op *this; \
return temp; \
}

The second macro, "OP_IN_TERMS_OF ", expands to a definition of an operator
such as +, which works off +=. Here it is:

#define OP_IN_TERMS_OF( op,param_dec,ob j) \
ThisClass operator op(param_dec) const \
{ \
ThisClass temp(*this); \
temp op##= obj; \
return temp; \
}

(I realise that this won't work if "param_dec" were to contain a comma.)

The third macro, "NON_CONST_IN_T ERMS_OF", expands to a definition of a non-
const member function (or member function operator) which calls the const
version. Here it is:

#define NON_CONST_IN_TE RMS_OF(ret,func _dec,call) \
ret func_dec \
{ \
return \
const_cast<ret> ( \
const_cast<This Class const*>(this)-call \
); \
}

(I realise that this won't work if "func_dec" were to contain a comma.)

First of all I'd like to ask, what do you think of these macros? Has anyone
ever done something similar? You can see them in action now below as I
implement "IntrinsicArray ". Before that though, I'm going to implement a
reverse pointer for use as a reverse iterator:

#include <cstddef>

template<class T>
struct ReversePtr {

typedef ReversePtr ThisClass;
typedef std::size_t size_t;

T *p;

ReversePtr(T *const arg) : p(arg) {}

operator T*() { return p; }
operator T const *() const { return p; }

ReversePtr &operator++( ) { --p; return *this; }
ReversePtr &operator--() { ++p; return *this; }

POST_IN_TERMS_O F(++)
POST_IN_TERMS_O F(--)

ReversePtr &operator+=(siz e_t const i) { p -= i; return *this; }
ReversePtr &operator-=(size_t const i) { p += i; return *this; }

OP_IN_TERMS_OF( +,size_t const i,i)
OP_IN_TERMS_OF(-,size_t const i,i)

T const &operator[](size_t const i) const { return *(p-i); }
NON_CONST_IN_TE RMS_OF(T&,opera tor[](size_t const i),operator[](i))
};

What do you think of ReversePtr? I appreciate any suggestions.

Now here's IntrinsicArray:

#include <cstddef>
#include <stdexcept>

template<class T,std::size_t len>
struct IntrinsicArray {

typedef IntrinsicArray ThisClass;

T arr[len];

typedef T value_type;
typedef T *iterator;
typedef T const *const_iterator ;
typedef T &reference;
typedef T const &const_referenc e;
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type ;

T const *begin() const { return arr; }
NON_CONST_IN_TE RMS_OF(T*,begin (),begin())

T const *end() const { return arr+len; }
NON_CONST_IN_TE RMS_OF(T*,end() ,end())

ReversePtr<T constrbegin() const { return arr+(len-1); }
NON_CONST_IN_TE RMS_OF(ReverseP tr<T>,rbegin(), rbegin())

ReversePtr<T constrend() const { return arr-1; }
NON_CONST_IN_TE RMS_OF(ReverseP tr<T>,rend(),re nd())

T const &operator[](size_type const i) const {return arr[i];}
NON_CONST_IN_TE RMS_OF(T&,opera tor[](size_type const i),operator[](i))

T const &at(size_typ e const i) const
{
if (i >= len) throw std::range_erro r();
return arr[i];
}
NON_CONST_IN_TE RMS_OF(T&,at(si ze_type const i),at(i))

T const &front() const { return *arr; }
NON_CONST_IN_TE RMS_OF(T&,front (),front())

T const &back() const { return arr[len-1]; }
NON_CONST_IN_TE RMS_OF(T&,back( ),back())

size_type size() const { return len; }
bool empty() const { return false; }
size_type capacity() const { return len; }
size_type max_size() const { return len; }
};

Of course, the code isn't finished yet, but I welcome any comments,
questions, or suggestions.

--

Frederick Gotham

[Kai-Uwe Bux]

Roland Pibinger wrote:

On Fri, 24 Nov 2006 05:57:07 -0500, Kai-Uwe Bux wrote:

>>You seem to think that there is a difference between:

typedef T* iterator;
T* begin() { ... }

and:

typedef T* iterator;
iterator begin() { ... }

But there is none.

Of course there is a difference! When a function returns T* one uses a
T* variable to capture the return value, when a function returns an
iterator an iterator variable is used.

Typedefs introduce aliases. Thus, a variable of type T* and a variable of
type IntrinsicArray< T>::iterator have the same type. The only difference is
in your head, not in the code. You are mistaking the implementation for the
documentation. The docs could (maybe should) state that the return type of
begin() is iterator. The implementation, however, is free to make up to
that promise in any way it pleases.

>>STL-style written client code will always use the
IntrinsicArra y<T>::iterator typedef.

Nope. C/C++ clients can rely on the type of the return value because
that type is part of the function contract.

a) C++ does not support contracts in code. The contract is defined in the
documentation. We have not seen that. I already said that I would specify
iterator in the docs. However, one could, of course, make the guarantee
that iterator = T* part of the specification.

b) If you use the IntrinsicArray< Tas defined, then your code will not
break even if you use T*. Using iterator is still wise and makes your code
easier to change when you want to switch containers. But that's all.
Best

Kai-Uwe Bux

[Gavin Deane]

Kai-Uwe Bux wrote:

Roland Pibinger wrote:

On Fri, 24 Nov 2006 05:57:07 -0500, Kai-Uwe Bux wrote:

>You seem to think that there is a difference between:

typedef T* iterator;
T* begin() { ... }

and:

typedef T* iterator;
iterator begin() { ... }

But there is none.

Of course there is a difference! When a function returns T* one uses a
T* variable to capture the return value, when a function returns an
iterator an iterator variable is used.

Typedefs introduce aliases. Thus, a variable of type T* and a variable of
type IntrinsicArray< T>::iterator have the same type. The only difference is
in your head, not in the code.

Of course the difference is only in a human reader's head, but then
that's the only place that matters. There are always countless
different ways to express identical intent to the compiler and the
compiler will cope with all of them equally. Your job as a programmer
is to select, from all those possiblities, the one that most clearly
expresses your intent to a human being.

It is not clear from the first example whether begin() is intended to
return a T* because that is what iterator is typedef'd to be, or
whether begin() is intended to return a T* regardless of what type
iterator is.

In the second example, it is clear that begin() is meant to return an
iterator, whatever type that is.

You are mistaking the implementation for the
documentation. The docs could (maybe should) state that the return type of
begin() is iterator. The implementation, however, is free to make up to
that promise in any way it pleases.

I would argue that, at best, the at-first-glance mistmatch between the
documentation and your first code example needlessly introduces the
risk of confusing the reader for zero gain.

There is the other point that, as the maintainer of the class, if I
need to refactor the class to use a different type for iterator, or
maybe just a different type for a debug build, your first example makes
it harder for me to do that. Not very much harder necessarily,
depending how many function signatures use T* when they mean iterator,
but still needless extra complication for zero gain.

Gavin Deane

[Frederick Gotham]

Roland Pibinger:

Of course there is a difference! When a function returns T* one uses a
T* variable to capture the return value, when a function returns an
iterator an iterator variable is used.

int Func1() { return 7; }

typedef int MyInt;

MyInt Func2() { return 7; }

int main()
{
int a = Func1();
MyInt b = Func1();

int c = Func2();
MyInt d = Func2();

a = b = c = d;
}

If that doesn't compile, burn your compiler.

--

Frederick Gotham

[Frederick Gotham]

Gavin Deane:

Of course the difference is only in a human reader's head, but then
that's the only place that matters. There are always countless
different ways to express identical intent to the compiler and the
compiler will cope with all of them equally. Your job as a programmer
is to select, from all those possiblities, the one that most clearly
expresses your intent to a human being.

We will have to simply disagree on this.

I could have written "const_iterator " instead of "T const*", but I prefer the
latter as it's more tangible in my own mind. If you would prefer to write the
former, then fair enough that's your choice.

If I were to write documentation for "IntrinsicArray ", I might choose to list
the function signatures as returning "const_iterator " instead of "T const*".

--

Frederick Gotham

[Kai-Uwe Bux]

Gavin Deane wrote:

>
Kai-Uwe Bux wrote:

>Roland Pibinger wrote:

On Fri, 24 Nov 2006 05:57:07 -0500, Kai-Uwe Bux wrote:
You seem to think that there is a difference between:

typedef T* iterator;
T* begin() { ... }

and:

typedef T* iterator;
iterator begin() { ... }

But there is none.

Of course there is a difference! When a function returns T* one uses a
T* variable to capture the return value, when a function returns an
iterator an iterator variable is used.

Typedefs introduce aliases. Thus, a variable of type T* and a variable of
type IntrinsicArray< T>::iterator have the same type. The only difference
is in your head, not in the code.

Of course the difference is only in a human reader's head, but then
that's the only place that matters. There are always countless
different ways to express identical intent to the compiler and the
compiler will cope with all of them equally. Your job as a programmer
is to select, from all those possiblities, the one that most clearly
expresses your intent to a human being.

The point is which human being we are talking about. Mr Pibinger, I took it,
was talking about a programmer of client code. Such programmer, in my
opinion, should not have any need to read the code for IntrinsicArray< >;
and there is no promise/contract/intent in the code conveyed to the client
programmer.

I grant you that the two variations of the code are not equivalent in
quality: the difference lies in ease of maintainance. There, you have a
point about conveying intent.

It is not clear from the first example whether begin() is intended to
return a T* because that is what iterator is typedef'd to be, or
whether begin() is intended to return a T* regardless of what type
iterator is.

In the second example, it is clear that begin() is meant to return an
iterator, whatever type that is.

The point where to make clear what begin() is supposed to return, is the
specs/docs for this class, not the code. If I open the header files for my
STL implementation of <vector>, I might find that begin() returns something
of type

whatever_fancy_ iterator_facade < value_type * >

where the standard says that begin() returns iterator. Should I believe the
standard or the header file?

>You are mistaking the implementation for the
documentatio n. The docs could (maybe should) state that the return type
of begin() is iterator. The implementation, however, is free to make up
to that promise in any way it pleases.

I would argue that, at best, the at-first-glance mistmatch between the
documentation and your first code example needlessly introduces the
risk of confusing the reader for zero gain.

True.

There is the other point that, as the maintainer of the class, if I
need to refactor the class to use a different type for iterator, or
maybe just a different type for a debug build, your first example makes
it harder for me to do that. Not very much harder necessarily,
depending how many function signatures use T* when they mean iterator,
but still needless extra complication for zero gain.

Here, you are correct, too. I was not arguing that the two examples are
equal in code quality. I was arguing that they are equivalent in observable
behavior and make the same promisses to any client (namely none since, in
this case, promisses to clients have to be part of the docs/specs).

Best

Kai-Uwe Bux

[Gavin Deane]

Frederick Gotham wrote:

Gavin Deane:

Of course the difference is only in a human reader's head, but then
that's the only place that matters. There are always countless
different ways to express identical intent to the compiler and the
compiler will cope with all of them equally. Your job as a programmer
is to select, from all those possiblities, the one that most clearly
expresses your intent to a human being.

We will have to simply disagree on this.

As long as I never have to maintain code you wrote, that approach is
fine by me.

I could have written "const_iterator " instead of "T const*", but I prefer the
latter as it's more tangible in my own mind. If you would prefer to write the
former, then fair enough that's your choice.

The difference to me is that, if, conceptually, the function returns an
object that can be used to iterate through the sequence and can be
used, by dereferencing, to obtain an immutable object in that sequence,
then C++ has a name for such a concept and that name is const_iterator.
The fact that, at the particular point in time you wrote the code, the
underlying type you chose to model the const_iterator concept was a T
const* is incidental. It is an implementation detail. To confuse the
abstract concept with the implementation detail is indicative of a lack
of clarity of thinking.

If I were to write documentation for "IntrinsicArray ", I might choose to list
the function signatures as returning "const_iterator " instead of "T const*".

Then you still introduce the maintenance problem I described.

Gavin Deane

[Gavin Deane]

Kai-Uwe Bux wrote:

Gavin Deane wrote:

Kai-Uwe Bux wrote:

Roland Pibinger wrote:
On Fri, 24 Nov 2006 05:57:07 -0500, Kai-Uwe Bux wrote:
You seem to think that there is a difference between:

typedef T* iterator;
T* begin() { ... }

and:

typedef T* iterator;
iterator begin() { ... }

But there is none.

<snip>

Of course the difference is only in a human reader's head, but then
that's the only place that matters. There are always countless
different ways to express identical intent to the compiler and the
compiler will cope with all of them equally. Your job as a programmer
is to select, from all those possiblities, the one that most clearly
expresses your intent to a human being.

The point is which human being we are talking about. Mr Pibinger, I took it,
was talking about a programmer of client code. Such programmer, in my
opinion, should not have any need to read the code for IntrinsicArray< >;
and there is no promise/contract/intent in the code conveyed to the client
programmer.

I was indeed talking about the human being who has to read the code. As
a client of std::vector, I have no more need to be able to comprehend
the code in my <vectorheader than my Grandmother does. I look in my
copy of the standard or my copy of Josuttis to find out what interface
std::vector provides. I don't look in the <vectorheader for that
information because I expect my standard library supplier to implement
the standard correctly or to documnet the instances where they don't
and as long as they do that, I don't care how they do it.

So let me rephrase:
Your job as a programmer is to select, from all those possiblities, the
one that most clearly expresses your intent to the human beings who
need to read your code.

I grant you that the two variations of the code are not equivalent in
quality: the difference lies in ease of maintainance. There, you have a
point about conveying intent.

It is not clear from the first example whether begin() is intended to
return a T* because that is what iterator is typedef'd to be, or
whether begin() is intended to return a T* regardless of what type
iterator is.

In the second example, it is clear that begin() is meant to return an
iterator, whatever type that is.

The point where to make clear what begin() is supposed to return, is the
specs/docs for this class, not the code. If I open the header files for my
STL implementation of <vector>, I might find that begin() returns something
of type

whatever_fancy_ iterator_facade < value_type * >

where the standard says that begin() returns iterator. Should I believe the
standard or the header file?

If you provide me with a class to use, I absolutely agree with you
that, to understand how to use that class I should look in the
documentation you provide, not in the code. If the code does not behave
as documented, the solution is to ask for a refund.

However, I was coming from the perspective of your successor on the
project. If you move on to bigger and brighter things and I pick up
your code and documentation to maintain, it is very important to me
(and therefore to my employer if we assume a professional context) that
your code and documentation are easy to comprehend.

<snip>

Gavin Deane