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_itera tor begin() const { return v.begin(); }
typename vT::const_itera tor end() const { return v.end(); }

typename vT::reverse_ite rator rbegin() { return v.rbegin(); }
typename vT::reverse_ite rator rend() { return v.rend(); }
typename vT::const_rever se_iterator rbegin() const { return v.rbegin(); }
typename vT::const_rever se_iterator rend() const { return v.rend(); }

};
Michael

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

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

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

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.m oderated. First time posters: Do this! ]

[Neal Coombes]

Michael Hopkins wrote:

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>: :operator[](i - offset); }
T const& operator[](int i) const { return
std::vector<T>: :operator[](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

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.m oderated. First time posters: Do this! ]

[Andrew Koenig]

"Michael Hopkins" <mi************ *@hopkins-research.com> wrote in message
news:BE9D1446.3 BD00%mi******** *****@hopkins-research.com...

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.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.m oderated. First time posters: Do this! ]

[Carlos Moreno]

Michael Hopkins wrote:

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 "transparen t"
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>::iter ator iterator;
typedef vector<T>::cons t_iterator const_iterator;
// ... same for others (reverse_iterat or, 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
--

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.m oderated. First time posters: Do this! ]

[Allan W]

Michael Hopkins wrote:

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
(std::vector<T> ::iterator)... more like some type of integer.
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_itera tor begin() const { return v.begin(); }
typename vT::const_itera tor end() const { return v.end(); }

typename vT::reverse_ite rator rbegin() { return v.rbegin(); } typename vT::reverse_ite rator rend() { return v.rend(); } typename vT::const_rever se_iterator rbegin() const { return v.rbegin(); } typename vT::const_rever se_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<mytyp e>::iterator i=u.begin(); i!=u.end(); ++i)
/* whatever... */;

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

You're also going to want to define push_back, et. al.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.m oderated. First time posters: Do this! ]

[gottlobfrege]

Michael Hopkins wrote:

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_ent ries(std::vecto r<int> const & vec)
{
int sum = 0;
for (size_t i = 0; i < vec.size(); i += 2)
{
sum += vec[i];
}
}

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

int foo()
{
uovec<int> vec;
read_ints_from_ somewhere(vec);

assert(sum_of_e ven_entries(vec ) == sum_of_odd_entr ies(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
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.m oderated. First time posters: Do this! ]

[dietmar_kuehl]

Michael Hopkins wrote:

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.
--
<mailto:di***** ******@yahoo.co m> <http://www.dietmar-kuehl.de/>
<http://www.eai-systems.com> - Efficient Artificial Intelligence
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.m oderated. First time posters: Do this! ]

[Hendrik Schober]

Carlos Moreno <mo************ ***********@xx. xxx> wrote:

[...]
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_t raits<Iterator> ::iterator_cate gory
= typename std::iterator_t raits<Iterator> ::iterator_cate gory() )
[...]
Carlos

Schobi

--
Sp******@gmx.de 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

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.m oderated. First time posters: Do this! ]

[kanze]

Andrew Koenig wrote:

"Michael Hopkins" <mi************ *@hopkins-research.com> wrote
in message
news:BE9D1446.3 BD00%mi******** *****@hopkins-research.com...

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.

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.

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, [phone]
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.m oderated. First time posters: Do this! ]

[Carlos Moreno]

Andrew Koenig wrote:

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

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.m oderated. First time posters: Do this! ]