First try at a std::vector from 1 to n

[Michael Hopkins]

Hi all

I want to create a std::vector that goes from 1 to n instead of 0 to n-1.
The only change this will have is in loops and when the vector returns
positions of elements etc. I am calling this uovec at the moment (for
Unit-Offset VECtor). I want the class to respond correctly to all usage of
STL containers and algorithms so that it is a transparent replacement for
std:vector.

The options seems to be:

1) deriving publicly from std::vector and then define operator(), but I
believe that std::vector is not meant to be used as a base class so no
virtual destructor (and possibly other gotchas) though in this case I
wouldn't need to store any members in the derived class so maybe this would
make no difference?

2) store a std::vector inside and use it as necessary - this appears to be
the preferred option.

3) other? Deriving privately from std::vector and an interface?

In any case I suspect housekeeping will be required to keep STL containers
and algorithms happy.

A couple of years ago I was asking these questions on the list and got
several helpful replies but got distracted by other tasks and dropped C++.
Am now back (and better prepared) and I was interested in a critique of this
first attempt. It uses (2) but I'm not sure if all the required STL
behaviour is covered so I have the getout clause of direct access to the
contained std::vector. I would prefer to avoid doing this.

template <class T>
/////////////////////////////////
// uovec - a std:vector<T> but with unit-offset via operator ()
// can add other stuff to make it exactly like std::vector
// can call v.foo() or use vref() if necessary but not very elegant
/////////////////////////////////
class uovec {
typedef std::vector<T> vT;

static const iter offset = 1;
vT v;

public:
// simple constructors
uovec ( const iter s ) : v( s ) {}
uovec ( const iter s, const T fill ) : v( s, fill ) {}

// copy constructors and assignments will be required but not given here

// access from 1 to n
inline T& operator() ( const iter i ) { return v[i-offset]; }
inline const T& operator() ( const iter i ) const { return v[i-offset]; }

inline vT& vref () { return v; } // return reference to v in
case complicated STL required... nasty
inline const vT& vref () const { return v; } // return const reference to
const v

// vector iterators
typename vT::iterator begin() { return v.begin(); }
typename vT::iterator end() { return v.end(); }
typename vT::const_iterator begin() const { return v.begin(); }
typename vT::const_iterator end() const { return v.end(); }

typename vT::reverse_iterator rbegin() { return v.rbegin(); }
typename vT::reverse_iterator rend() { return v.rend(); }
typename vT::const_reverse_iterator rbegin() const { return v.rbegin(); }
typename vT::const_reverse_iterator rend() const { return v.rend(); }

};


Michael

_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/

_/ _/ _/_/_/ Hopkins Research Ltd
_/ _/ _/ _/
_/_/_/_/ _/_/_/ http://www.hopkins-research.com/
_/ _/ _/ _/
_/ _/ _/ _/ 'touch the future'

_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/

 

[Neal Coombes]

3) other? Deriving privately from std::vector and an interface?

I haven't thought too much about it, but I think I would derive
privately and use the using directive to forward all those things that
are the same:

template <typename T, int offset = 1>
class uovec : std::vector<T>
{
public:
using std::vector<T>::begin;
using std::vector<T>::end;
using std::vector<T>::rbegin;
using std::vector<T>::rend;

T& operator[](int i) { return std::vector<T>:perator[](i - offset); }
T const& operator[](int i) const { return
std::vector<T>:perator[](i - offset); }
};

Notice I also made offset a template argument to make this even more
interesting, you can then have any offset you like. I also preferred
using the subscript operator over operator(), but that's just me.

Just be sure to open the standard and provide a complete interface.

HTH
Neal

 

[Andrew Koenig]

I want to create a std::vector that goes from 1 to n instead of 0 to n-1.
The only change this will have is in loops and when the vector returns
positions of elements etc. I am calling this uovec at the moment (for
Unit-Offset VECtor). I want the class to respond correctly to all usage
of
STL containers and algorithms so that it is a transparent replacement for
std:vector.

I don't see how that is possible. After all, if v is a std::vector, then
v[0] is well defined--but you're proposing to define a class in which v[0]
is not well defined. So it can't possibly be a transparent replacement.

 

[Carlos Moreno]

Hi all

I want to create a std::vector that goes from 1 to n instead of 0 to n-1.

You probably want to make that "from A to B", where A and B are
arbitrary (and specified at constructor-time).

The options seems to be:

1) deriving publicly from std::vector and then define operator(), but I
believe that std::vector is not meant to be used as a base class so no
virtual destructor (and possibly other gotchas) though in this case I
wouldn't need to store any members in the derived class so maybe this would
make no difference?

Still, it would be asking for trouble -- take for instance my suggestion
above; it's not far-fetched to think that maybe someone will add that
functionality after your initial version does only 1 to N. Then, you
may start getting in trouble, since future version might inadvertedly
break your initial assumptions.

But more specifically, you would still be incurring in undefined
behaviour, even if you test it and test it and it always behaves as
you expect and want.

2) store a std::vector inside and use it as necessary - this appears to be
the preferred option.

I would say so.

3) other? Deriving privately from std::vector and an interface?

Hmmm, I smell possibilities of trouble... Since there are many
elements of vector's interface that you have to provide as your
interface, and with the exact same name (you want a "transparent"
replacement for vector, right?), then whenever you provide one
of those, you may end up hiding other members from the now privately
accessible interface, and surprises may ensue... I'd stay out of
trouble by simply adding a vector as data member and mapping your
interface to that of your vector data member.

In any case I suspect housekeeping will be required to keep STL containers
and algorithms happy.

Provide all the iterators -- as typedefs:

template <typename T>
class Ovector
{
public:
typedef T value_type;
typedef vector<T>::iterator iterator;
typedef vector<T>::const_iterator const_iterator;
// ... same for others (reverse_iterator, etc.)

iterator begin() { return d_vector.begin(); }
const_iterator begin() const { return d_vector.begin(); }
iterator end() { return d_vector.end(); }
const_iterator end() const { return d_vector.end(); }
// ... etc.


The only thing I suspect is going to give you a headache is to
make the distinction between the constructors:

template <typename Iterator>
Ovector (Iterator begin, Iterator end)

And:

template <typename T>
Ovector (int size, T value)

When T is int (well, that would be size_t, but let's make it int
to simplify things). With vector, because it is part of the
language, the compiler is allowed to do some magic to disambiguate
the issue. But with a class that you're creating, I guess the only
solution would be to provided specialized class definitions for all
possible integral tyepes! (ouch :-( )

Sure, another solution would be not to provide those (after all, your
constructor would naturally expect an extra parameter if you do it
the way I suggested -- subscript being within an arbitrary range).
But would that be a transparent enough replacement for vector? I
guess only you can decide that.

HTH,

Carlos

 

[Allan W]

I want to create a std::vector that goes from 1 to n instead of 0 to n-1.

I was interested in a critique of this ... first attempt.
I'm not sure if all the required STL
behaviour is covered so I have the getout clause of direct access to the
contained std::vector. I would prefer to avoid doing this.

If you want to make sure that it covers ALL behavior of std::vector,
there's little alternative to referring to the documentation, either
the standard or something else definitive.

template <class T>
/////////////////////////////////
// uovec - a std:vector<T> but with unit-offset via operator ()
// can add other stuff to make it exactly like std::vector
// can call v.foo() or use vref() if necessary but not very elegant
/////////////////////////////////
class uovec {
typedef std::vector<T> vT;

I think you need a "typename" keyword here (and probably a few
other places). Also, I think you left off some typedefs here: at
the very least, iter. It doesn't seem to be the obvious

static const iter offset = 1;
vT v;

public:
// simple constructors
uovec ( const iter s ) : v( s ) {}
uovec ( const iter s, const T fill ) : v( s, fill ) {}

// copy constructors and assignments will be required but not given

here

That's one of the advantages of making v a member... the default
copy constructor and assignment should be fine.

// access from 1 to n
inline T& operator() ( const iter i ) { return v[i-offset]; }
inline const T& operator() ( const iter i ) const { return v[i-offset]; }

inline vT& vref () { return v; } // return reference to v in
case complicated STL required... nasty
inline const vT& vref () const { return v; } // return const reference to
const v

// vector iterators
typename vT::iterator begin() { return v.begin(); }
typename vT::iterator end() { return v.end(); }
typename vT::const_iterator begin() const { return v.begin(); }
typename vT::const_iterator end() const { return v.end(); }

typename vT::reverse_iterator rbegin() { return v.rbegin(); }
typename vT::reverse_iterator rend() { return v.rend(); }
typename vT::const_reverse_iterator rbegin() const { return v.rbegin(); }
typename vT::const_reverse_iterator rend() const { return v.rend(); }
};

Isn't there some problem with returning iterators to the embedded
container? I think there is but offhand I can't think of a reason why
this wouldn't work swimmingly. However, you ARE going to at least
typedef
iterator, const_iterator, and so on so that code like this works:

for(uovec<mytype>::iterator i=u.begin(); i!=u.end(); ++i)
/* whatever... */;

Currently code like this won't compile because you haven't defined
uovec<T>::iterator.

You're also going to want to define push_back, et. al.

 

[gottlobfrege]

Hi all

I want to create a std::vector that goes from 1 to n instead of 0 to

n-1.

OK, first of all, if this is just an experiment to get your feet wet,
then it is fine. However, I highly suggest against it for any other
reason. Even if you think that starting at 0 is the dumbest thing
you've ever seen (and maybe it is), just get over it, and learn to live
with it.

Sooner or later, even if you are a hermit coding in a cave today, some
day the most important thing about your code will be how you
*communicate to other programmers* through the code. No other C/C++
programmer will expect the vector/array/etc to start at 1 instead of 0.

There are many parts of the language that *could* be improved, but only
some of those *should* be. Pick other areas, this one is just tooooo
entrenched.

The options seems to be:

1) deriving publicly from std::vector and then define operator(), but I
believe that std::vector is not meant to be used as a base class so no
virtual destructor (and possibly other gotchas) though in this case I
wouldn't need to store any members in the derived class so maybe this would
make no difference?

I know that std::vector, etc. isn't supposed to be derived from, but in
this case, I would.
It is true that you want to avoid deriving from things without a
virtual destructor - so that someone doesn't see your uovec as a vector
and delete from there. But you know what? I don't think someone
*else* should be deleting your vector at all - the thing that created
it should probably delete it - and it will probably know what the
object really is (a uovec, not a vector). Or you should wrap it in
some kind of smart pointer, and then the pointer should know to do the
right thing.

Anyhow, by deriving, there is not much to override. And, conceptually,
it IS a vector. Or is it? Since it doesn't implement _exactly_ the
same interface as vector (ie a 0 to n-1 interface), it is not a vector.
But of course, as soon as it is casted to a vector, it does implement
the 0 to n-1 version:

// takes a vector:
int sum_of_even_entries(std::vector<int> const & vec)
{
int sum = 0;
for (size_t i = 0; i < vec.size(); i += 2)
{
sum += vec;
}
}

// takes any container:
template <typename container>
int sum_of_odd_entries(container const & vec)
{
int sum = 0;
for (size_t i = 1; i < vec.size(); i += 2)
{
sum += vec;
}
}

int foo()
{
uovec<int> vec;
read_ints_from_somewhere(vec);

assert(sum_of_even_entries(vec) == sum_of_odd_entries(vec));
// (actually, sum_of_odd subtly misses the last entry,
// but other than that, they add the same entries)
}


a bit of a contrived example, but allowing the conversion from uovec to
vector both makes sense and is scary (in my head).

You could probably protect the operator vector() call. So you could
still pass a uovec into any templatized functions, but not those that
explicitly took a vector.

And speaking of templatized calls! You are making a comtainer, and
trying to make it be compatible with STL algorithms (I hope/assume).
And it IS compatible for any algorithms that use just begin() and end()
(ie forward iterator based algorithms, etc), but uovec won't work
correctly with algorithms that use [] and assume [0] is the first
element (ie algorithms that take random access iterators). It will
COMPILE, but not work (which is much worse than not compiling...)

So again, it really isn't a good idea, other than to experiment. But
there are lots of other things to experiment with...

2) store a std::vector inside and use it as necessary - this appears to be
the preferred option.

3) other? Deriving privately from std::vector and an interface?


Michael

Tony

 

[dietmar_kuehl]

I want to create a std::vector that goes from 1 to n instead of 0 to

n-1.

This is not answering your question... However, I would guess that
your desire to create a vector indexing from 0 to n-1 is misguided
in the first place! There are actually several reasons why I think
this is the case:
- When applying STL concepts to programming correctly (and there
many strong reasons to do so), you don't care about "positions"
but only about iterators. In the cases where you actually care
about positions again, e.g. in algorithms taking random access
iterators, you will get back zero offset semantic in any case.
- You would need to cope with dual indexing rules, depending on
how you access your elements: when using iterators, you would
access 'v[1]' as either '*(v.begin())' or as '(v.begin())[0]'
or general values 'v[n]' as '(v.begin())[n-1]'.
- Although many text books use one as the index for the first
element in algorithms, it actually turns out that most
computations are easier and more consistent if the first index
were zero.
- Almost every reader of your code would expect 'v[1]' to access
the second element in the array and 'v.size() - 1' to be the
last accessible element. I remember vividly more than one
debugging session where I fixed other peoples code who created a
similar class (these were pre-STL times) and got themselves
confused by the different indexing rules (... and I had a hard
time, too).

Rather than helping you to create a good implementation of an
ill-advised class I propose that you drop the whole idea in the first
place! If you really think you need a different offset, do yourself
and everybody who later has to maintain your code the favor and at
least make the access to the class as different as reasonable from
the conventional array access! That is, you will be far better off
using neither operator[](), operator()(), nor at() to access the
elements!

I remember that I felt a similar desire for an arbitrary offset array
when I moved from Pascal to C and I used the techniques with the
non-portable negative offset to the first element of the array, i.e.
something like below (***NOTE***: this does ***NOT** work portably!):

int array_aux[10];
int* array = array_aux - 1; // undefined behavior here!

However, the culture in e.g. the Pascal community with respect to
arrays is much different than in C or C++: while in Pascal everybody
is used to check whether the array actually starts, everybody in C
or C++ simply assumes that it starts at zero. It didn't took long
and I started to shoot myself constantly into the foot due to this
offset such that I reworked the whole code to remove these offsets.
This process fixed quite a few bugs in the program.

 

[Hendrik Schober]

[...]
The only thing I suspect is going to give you a headache is to
make the distinction between the constructors:

template <typename Iterator>
Ovector (Iterator begin, Iterator end)

And:

template <typename T>
Ovector (int size, T value)

When T is int (well, that would be size_t, but let's make it int
to simplify things). With vector, because it is part of the
language, the compiler is allowed to do some magic to disambiguate
the issue. But with a class that you're creating, I guess the only
solution would be to provided specialized class definitions for all
possible integral tyepes! (ouch :-( )

How about this?

template <typename Iterator>
Ovector( Iterator begin, Iterator end
, typename std::iterator_traits<Iterator>::iterator_category

[...]
Carlos

Schobi

--
(e-mail address removed) is never read
I'm Schobi at suespammers dot org

"The presence of those seeking the truth is infinitely
to be prefered to those thinking they've found it."
Terry Pratchett

 

[kanze]

in message

I don't see how that is possible. After all, if v is a
std::vector, then v[0] is well defined--but you're proposing
to define a class in which v[0] is not well defined. So it
can't possibly be a transparent replacement.

More generally, isn't there supposed to be some sort of
relationship between [n] and begin()+n?

More generally, while there are certainly cases where having an
arbitrary lower bound is useful, doing so requires a number of
additional functions, like lowerBound() and upperBound(),
instead of just size(). And I'm not sure how relevant iterators
are in such cases; the only reasons I can think of for not using
0 as the lower bound involve indexes which depend on some
exteral (to the vector) values.

 

[Gary Labowitz]

I want to create a std::vector that goes from 1 to n instead of 0 to

n-1.

This is not answering your question... However, I would guess that
your desire to create a vector indexing from 0 to n-1 is misguided
in the first place! There are actually several reasons why I think
this is the case:
- When applying STL concepts to programming correctly (and there
many strong reasons to do so), you don't care about "positions"
but only about iterators. In the cases where you actually care
about positions again, e.g. in algorithms taking random access
iterators, you will get back zero offset semantic in any case.
- You would need to cope with dual indexing rules, depending on
how you access your elements: when using iterators, you would
access 'v[1]' as either '*(v.begin())' or as '(v.begin())[0]'
or general values 'v[n]' as '(v.begin())[n-1]'.
- Although many text books use one as the index for the first
element in algorithms, it actually turns out that most
computations are easier and more consistent if the first index
were zero.
- Almost every reader of your code would expect 'v[1]' to access
the second element in the array and 'v.size() - 1' to be the
last accessible element. I remember vividly more than one
debugging session where I fixed other peoples code who created a
similar class (these were pre-STL times) and got themselves
confused by the different indexing rules (... and I had a hard
time, too).

Rather than helping you to create a good implementation of an
ill-advised class I propose that you drop the whole idea in the first
place! If you really think you need a different offset, do yourself
and everybody who later has to maintain your code the favor and at
least make the access to the class as different as reasonable from
the conventional array access! That is, you will be far better off
using neither operator[](), operator()(), nor at() to access the
elements!

I remember that I felt a similar desire for an arbitrary offset array
when I moved from Pascal to C and I used the techniques with the
non-portable negative offset to the first element of the array, i.e.
something like below (***NOTE***: this does ***NOT** work portably!):

int array_aux[10];
int* array = array_aux - 1; // undefined behavior here!

I second this post. However, if the OP is dead-set on creating a class that
operates on indexes of A to B, he should write wrapper functions around a
standard vector and displace the index appropriately to the std::vector use.
This is no different than encryption/decryption of strings used in std::map.

 

[Carlos Moreno]

I want the class to respond correctly to all usage of
STL containers and algorithms so that it is a transparent replacement for
std:vector.

I don't see how that is possible. After all, if v is a std::vector, then
v[0] is well defined--but you're proposing to define a class in which v[0]
is not well defined. So it can't possibly be a transparent replacement.

AFAIK, STL algorithms never deal with v[0] -- they wouldn't even know
that such thing exists.

So, I think it is possible -- after all, from the original post, it
sounds to me like he meant a transparent replacement from the point
of view of STL algorithms (i.e., that you can still that Ovector as:
sort (v.begin(), v.end()), or find_if (v.rbegin(), v.rend()), etc.)

True that he did say "to all usage of STL containers and algorithms"...
But still, the way I understood it, he meant using that container the
with STL algorithms the same way you use STL containers with algorithms
(yeah, ok, so we would have to be careful with std::list, which has
his own versions of sort, replace...)

Carlos

 

[Jeff Flinn]

n-1.

This is not answering your question... However, I would guess that
your desire to create a vector indexing from 0 to n-1 is misguided

I think you meant 'not indexing from 0 to n-1'.

in the first place! There are actually several reasons why I think
this is the case:

[ snip thorough and valid reasoning ]

Is the OP merely wanting to avoid the proliferation of code mapping indices
from a non-zero based domain to the std container zero based domain? Then
perhaps it would be better to create a mapped index class and use that in
place of the raw index.

template< size_t Base >
struct based_index
{
size_t value;

explicit based_index( size_t avalue ):value(avalue-Base){}

operator size_t()const{ return value; }

based_index& operator++(){ ++value; return *this; }

...
};

void f()
{
std::vector<float> v(10);

typedef based_index<3> idx;

for( idx beg(3), end(13) ; beg != end ; ++beg )
{
v[beg] = 123.0f;
}

v[idx(7)] = 456.789f;
}

Jeff Flinn

 

[Jeff Flinn]

n-1.

This is not answering your question... However, I would guess that
your desire to create a vector indexing from 0 to n-1 is misguided

I think you meant 'not indexing from 0 to n-1'.

in the first place! There are actually several reasons why I think
this is the case:

[ snip thorough and valid reasoning ]

Is the OP merely wanting to avoid the proliferation of code mapping indices
from a non-zero based domain to the std container zero based domain? Then
perhaps it would be better to create a mapped index class and use that in
place of the raw index.

template< size_t Base >
struct based_index
{
size_t value;

explicit based_index( size_t avalue ):value(avalue-Base){}

operator size_t()const{ return value; }

based_index& operator++(){ ++value; return *this; }

...
};

void f()
{
std::vector<float> v(10);

typedef based_index<3> idx;

for( idx beg(3), end(13) ; beg != end ; ++beg )
{
v[beg] = 123.0f;
}

v[idx(7)] = 456.789f;
}

Jeff Flinn

 

[James Kanze]

(e-mail address removed) wrote:

[...]

Rather than helping you to create a good implementation of an
ill-advised class I propose that you drop the whole idea in
the first place! If you really think you need a different
offset, do yourself and everybody who later has to maintain
your code the favor and at least make the access to the class
as different as reasonable from the conventional array access!
That is, you will be far better off using neither
operator[](), operator()(), nor at() to access the elements!

I think you comment really hits on the key issue. There are
cases where having a non-zero first index is useful --
representing the diagonals of a two dimensional array, for
example. In such cases, however, as Dietmar correctly points
out, it is very important that it be clearly visible what is
going on. Although I've used such arrays in the past, and will
doubtlessly use them in the future, if the problem arises, I
would NOT give them an STL-like interface, and while I think I'd
still overload operator[] (after all, what's the difference
between my array and std::map< int, T >?), there would certainly
be something in the name of the class which cried out that it
was different.

However, the culture in e.g. the Pascal community with respect
to arrays is much different than in C or C++:

Now that is an extremely pertinant comment. You don't danse a
tango when the orchestre is playing a walse.

 

[Carlos Moreno]

[...]
The only thing I suspect is going to give you a headache is to
make the distinction between the constructors:

template <typename Iterator>
Ovector (Iterator begin, Iterator end)

And:

template <typename T>
Ovector (int size, T value)

When T is int (well, that would be size_t, but let's make it int
to simplify things). With vector, because it is part of the
language, the compiler is allowed to do some magic to disambiguate
the issue. But with a class that you're creating, I guess the only
solution would be to provided specialized class definitions for all
possible integral tyepes! (ouch :-( )

How about this?

template <typename Iterator>
Ovector( Iterator begin, Iterator end
, typename std::iterator_traits<Iterator>::iterator_category
= typename std::iterator_traits<Iterator>::iterator_category() )

I've got soooooo much to learn... I know: don't we all...
but I mean, my so-much is soooo much more than the average
so-much, apparently :-((

Carlos

 

[Old Wolf]

I think you need a "typename" keyword here (and probably a few
other places).

std::vector is already known to be a class (it was declared
in <vector>.

The OP code already has "typename" everywhere where it's
required (as far as I and GCC can tell).

 

[Carlos Moreno]

I think I'd
still overload operator[] (after all, what's the difference
between my array and std::map< int, T >?)

Do you really not know the difference?

Carlos

 

[James Kanze]

Allan W wrote:

std::vector is already known to be a class (it was declared in
<vector>.

More precisely, it's known not to be a class, but a template.
If it were a class, the < would be illegal.

If instead of std::vector, the user used a dependant name, he'd
have to write something like:
typedef T::template V< ... > ...

In order to correctly parse the input, the compiler has to know
not only what symbols are typenames, but also which name
templates. For dependant names, the only way it can know is if
you tell it.