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

[Pete Becker]

Frederick Gotham wrote:

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.

Sounds suspiciously like std::tr1::array .

--

-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)

[Roland Pibinger]

On Wed, 22 Nov 2006 14:44:47 GMT, Frederick Gotham wrote:

>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.

You mean this?
http://www.josuttis.com/libbook/cont/carray.hpp.html

>First of all though, I want to show you some macros I've written.

[...]

>First of all I'd like to ask, what do you think of these macros?

C++ is powerful enough to avoid that kind of macros.

>Before that though, I'm going to implement a
reverse pointer for use as a reverse iterator:

#include <cstddef>

template<cla ss T>
struct ReversePtr {

What about std::reverse_it erator?

>Now here's IntrinsicArray:

#include <cstddef>
#include <stdexcept>

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

typedef IntrinsicArray ThisClass;

T arr[len];

public?

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; }

begin(), end() return (const_)iterato rs

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

Hmm, well ...

Best wishes,
Roland Pibinger

[Kai-Uwe Bux]

Frederick Gotham wrote:

>
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.

Use std::reverse_it erator<T*instea d. It has the advantage of not requiring
UB in implementing rend(). (See below)

>
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; }

UB: there is no "before-begin" pointer. (I know, it's a shame.)

You could just use std::reverse_it erator<T*>.

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.

Reminds me of std::tr1::array . It also reminds me of my own try (posted just
for inspiration):

template < typename T, std::size_t the_size >
class array {
private:

typedef T T_array [the_size];
typedef T_array & T_array_ref;
typedef T_array const & T_array_const_r ef;

T_array a_ptr;

public:

// Typedefs
// ========

typedef T value_type;
typedef value_type * pointer;
typedef value_type const * const_pointer;
typedef value_type & reference;
typedef value_type const &
const_reference ;
typedef pointer_iterato r< value_type,
pointer,
reference iterator;
typedef pointer_iterato r< const value_type,
const_pointer,
const_reference const_iterator;
typedef typename std::reverse_it erator< iterator >
reverse_iterato r;
typedef typename std::reverse_it erator< const_iterator >
const_reverse_i terator;
typedef std::size_t size_type;
typedef std::ptrdiff_t
difference_type ;
// Construction / Destruction
// =============== ===========

array ( void ) {}

array ( const_reference t ) {
for ( std::size_t i = 0; i < the_size; ++ i ) {
a_ptr[i] = t;
}
}

array ( T_array_const_r ef c_ref )
: a_ptr ( c_ref )
{}

array ( array const & other ) {
for ( size_type index = 0; index < the_size; ++index ) {
a_ptr[index] = other.a_ptr[index];
}
}

template < typename ConstIterType >
array ( ConstIterType from, ConstIterType to ) {
std::size_t i = 0;
for ( ConstIterType iter = from; iter != to; ++ iter ) {
if ( i < the_size ) {
a_ptr[i] = *iter;
++ i;
} else {
// flag_range_erro r( __FILE__, __LINE__, "argument list too long" );
return;
}
}
while ( i < the_size ) {
// flag_range_erro r( __FILE__, __LINE__, "argument list too short" );
// return;
a_ptr[i] = value_type();
++i;
}
}

// Conversion
// ==========

operator T_array_ref () {
return( a_ptr );
}
// Assignment
// ==========

array const & operator= ( array const & other ) {
for ( size_type index = 0; index < the_size; ++index ) {
a_ptr[index] = other.a_ptr[index];
}
return( *this );
}

void swap ( array & other ) {
std::swap_range s( this->begin(), this->end(), other.begin() );
}
// Access
// ======

reference at ( std::size_t pos ) {
if ( the_size <= pos ) {
flag_range_erro r( __FILE__, __LINE__, "index out of range" );
}
return( a_ptr[pos] );
}
const_reference at ( std::size_t pos ) const {
if ( the_size <= pos ) {
flag_range_erro r( __FILE__, __LINE__, "index out of range" );
}
return( a_ptr[pos] );
}

reference operator[] ( std::size_t pos ) {
return( a_ptr[pos] );
}

const_reference operator[] ( std::size_t pos ) const {
return( a_ptr[pos] );
}

reference front ( void ) {
return( a_ptr[0] );
}
const_reference front ( void ) const {
raturn( a_ptr[0] );
}
reference back ( void ) {
return( a_ptr[the_size-1] );
}
const_reference back ( void ) const {
return( a_ptr[the_size-1] );
}

// About
// =====

size_type size ( void ) const {
return( the_size );
}
bool empty ( void ) const {
return( the_size == 0 );
}
// Iterators
// =========

iterator begin ( void ) {
return( a_ptr );
}
const_iterator begin ( void ) const {
return( a_ptr );
}
iterator end ( void ) {
return( a_ptr + the_size );
}
const_iterator end ( void ) const {
return( a_ptr + the_size );
}

reverse_iterato r rbegin ( void ) {
return( reverse_iterato r( this->end() ) );
}

const_reverse_i terator rbegin ( void ) const {
return( reverse_iterato r( this->end() ) );
}

reverse_iterato r rend ( void ) {
return( reverse_iterato r( this->begin() ) );
}

const_reverse_i terator rend ( void ) const {
return( reverse_iterato r( this->begin() ) );
}

}; // array< T, the_size >

template < typename T, std::size_t N >
void swap ( array< T, N & a, array< T, N & b ) {
a.swap(b);
}


Best

Kai-Uwe Bux

[Frederick Gotham]

Roland Pibinger:

C++ is powerful enough to avoid that kind of macros.

Can you please show me how?

> T const *begin() const { return arr; }

begin(), end() return (const_)iterato rs

Yes, which is why I have the functions return "T const*".

--

Frederick Gotham

[Roland Pibinger]

On Thu, 23 Nov 2006 19:21:43 GMT, Frederick Gotham wrote:

>Roland Pibinger:

> begin(), end() return (const_)iterato rs

Yes, which is why I have the functions return "T const*".

But you should return iterator and const_iterator.

[Kai-Uwe Bux]

Roland Pibinger wrote:

On Thu, 23 Nov 2006 19:21:43 GMT, Frederick Gotham wrote:

>>Roland Pibinger:

>> begin(), end() return (const_)iterato rs

Yes, which is why I have the functions return "T const*".

But you should return iterator and const_iterator.

They do. From the original post:

typedef T *iterator;
typedef T const *const_iterator ;

...

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())

Best

Kai-Uwe Bux

[Roland Pibinger]

On Thu, 23 Nov 2006 17:52:41 -0500, Kai-Uwe Bux wrote:

>Roland Pibinger wrote:

>On Thu, 23 Nov 2006 19:21:43 GMT, Frederick Gotham wrote:

>>>Roland Pibinger:
begin(), end() return (const_)iterato rs
Yes, which is why I have the functions return "T const*".

But you should return iterator and const_iterator.

They do. From the original post:

typedef T *iterator;
typedef T const *const_iterator ;

But where are those typedefs used?

IMO, there are two possibilities:
1. Apply STL compliant style and use iterators which may be pointers
but may also be templates, e.g. in a (debug-)checked implementation.
2. Write an 'array template' that mimics a C++ array. In that case
avoid the STL related (typedef) stuff and use only pointers.

BTW, the implementation would be more useful if it were a 'maximum
size' instead of an 'always full' container.

Best wishes,
Roland Pibinger

[Kai-Uwe Bux]

Roland Pibinger wrote:

On Thu, 23 Nov 2006 17:52:41 -0500, Kai-Uwe Bux wrote:

>>Roland Pibinger wrote:

>>On Thu, 23 Nov 2006 19:21:43 GMT, Frederick Gotham wrote:
Roland Pibinger:
begin(), end() return (const_)iterato rs
Yes, which is why I have the functions return "T const*".
But you should return iterator and const_iterator.

They do. From the original post:

typedef T *iterator;
typedef T const *const_iterator ;

But where are those typedefs used?

In client code, of course. As with the STL containers, the point of the
typedefs is just that clients do not need to know how iterators are
implemented. However, in implementing the array class, the programmer has
no reason to pretend that he did not know how he decided to implement
iterators.

IMO, there are two possibilities:
1. Apply STL compliant style and use iterators which may be pointers
but may also be templates, e.g. in a (debug-)checked implementation.

That is exactly what the code is doing. A different implementation is
perfectly free to say

class iterator { ... };
iterator begin() { ... };

instead; and client code written generically will not see the difference.

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.

STL-style written client code will always use the
IntrinsicArray< T>::iterator typedef. Relying on iterator = T* is a bug in
client code [the classical one of relying on an implementation detail] but
not a bug in the implementation. Of course, I am assuming here that the
documentation of IntrinsicArray, which has not been posted, does not
guarantee that iterator = T*.

2. Write an 'array template' that mimics a C++ array. In that case
avoid the STL related (typedef) stuff and use only pointers.

The OP decided for the other option.

BTW, the implementation would be more useful if it were a 'maximum
size' instead of an 'always full' container.

Maybe, but that would introduce the need for a size variable which, in the
eyes of the OP, is likely to qualify as overhead.

Best

Kai-Uwe Bux

[Roland Pibinger]

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.

>STL-style written client code will always use the
IntrinsicArray <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.

Best wishes,
Roland Pibinger