Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > First try at a std::vector from 1 to n

Reply
Thread Tools

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

 
 
Michael Hopkins
Guest
Posts: n/a
 
      05-03-2005


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'

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



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

 
Reply With Quote
 
 
 
 
Neal Coombes
Guest
Posts: n/a
 
      05-04-2005
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>: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

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

 
Reply With Quote
 
 
 
 
Andrew Koenig
Guest
Posts: n/a
 
      05-04-2005
"Michael Hopkins" <(E-Mail Removed)> wrote in message
news:BE9D1446.3BD00%(E-Mail Removed)...

> 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++.moderated. First time posters: Do this! ]

 
Reply With Quote
 
Carlos Moreno
Guest
Posts: n/a
 
      05-04-2005
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 "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
--

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

 
Reply With Quote
 
Allan W
Guest
Posts: n/a
 
      05-04-2005
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_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.


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

 
Reply With Quote
 
gottlobfrege@gmail.com
Guest
Posts: n/a
 
      05-04-2005
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_entries(std::vector<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_entries(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_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


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

 
Reply With Quote
 
dietmar_kuehl@yahoo.com
Guest
Posts: n/a
 
      05-04-2005
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.
--
<(E-Mail Removed)> <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++.moderated. First time posters: Do this! ]

 
Reply With Quote
 
Hendrik Schober
Guest
Posts: n/a
 
      05-04-2005
Carlos Moreno <(E-Mail Removed)> 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_traits<Iterator>::iterator_category
= typename std::iterator_traits<Iterator>::iterator_category( ) )

> [...]
> Carlos


Schobi

--
http://www.velocityreviews.com/forums/(E-Mail 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



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

 
Reply With Quote
 
kanze@gabi-soft.fr
Guest
Posts: n/a
 
      05-04-2005
Andrew Koenig wrote:
> "Michael Hopkins" <(E-Mail Removed)> wrote
> in message
> news:BE9D1446.3BD00%(E-Mail Removed)...


> > 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 objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34


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

 
Reply With Quote
 
Gary Labowitz
Guest
Posts: n/a
 
      05-04-2005
"(E-Mail Removed)" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) oups.com...
> 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!


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



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

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
who is simpler? try/except/else or try/except Fabio Z Tessitore Python 5 08-13-2007 12:52 AM
converting a nested try/except statement into try/except/else John Salerno Python 20 08-11-2006 02:48 PM
Can I have a second TRY inside the first TRY/CATCH in ASP.NET ??? bienwell ASP .Net 4 05-27-2005 05:05 PM
Compiler error occurred when try to use a flexible template expression in preprocessor definesCompiler error occurred when try to use a flexible template expression in preprocessor defines snnn C++ 6 03-14-2005 04:09 PM
Try, Try, Try, again... Rick12N4@netscape.net Computer Support 3 01-29-2005 04:02 PM



Advertisments