std::cvector

[deodiaus]

I was looking at Plauger's <vector> template as implemented in MS DEV
6 owned by HP.
I modified it to implement <cvector>, a circular vector template. I
modified the obvious, e. g. replaced vector by cvector, and removed
some redundant defns.

A circular template class also has
cvector.end() the same as cvector.begin()
I am wondering if I should change operator++ so that when the iterator
points to end(), it will wrap around to begin(), but was wondering if
that might mess up other template functions.
I handle the wrap around by adding a check in my code (not in
<cvector>) so that if I reached the end(), I reset the iterator to
begin().
Has anyone done this all ready? Am I using the right template, maybe
I should be using <list>?

 

[Andrew Koenig]

I was looking at Plauger's <vector> template as implemented in MS DEV
6 owned by HP.
I modified it to implement <cvector>, a circular vector template. I
modified the obvious, e. g. replaced vector by cvector, and removed
some redundant defns.

A circular template class also has
cvector.end() the same as cvector.begin()

I don't see how you can do that and maintain the properties required of
iterators.

The simplest example I can think of is the following loop, which is intended
to visit every element of a container c:

iter = c.begin();
while (iter != c.end()) {
// do something to the element to which iter refers
}

All kinds of programs use loops similar to this one to deal with all the
elements in a container. If c.begin() and c.end() have the same value, then
the loop will terminate before it ever gets started.

 

[SaltPeter]

I was looking at Plauger's <vector> template as implemented in MS DEV
6 owned by HP.
I modified it to implement <cvector>, a circular vector template. I
modified the obvious, e. g. replaced vector by cvector, and removed
some redundant defns.

A circular template class also has
cvector.end() the same as cvector.begin()
I am wondering if I should change operator++ so that when the iterator
points to end(), it will wrap around to begin(), but was wondering if
that might mess up other template functions.
I handle the wrap around by adding a check in my code (not in
<cvector>) so that if I reached the end(), I reset the iterator to
begin().
Has anyone done this all ready? Am I using the right template, maybe
I should be using <list>?

Go to http://mindview.net/Books/TICPP/ThinkingInCPP2e.html
and look in the "Creating your own containers" section in the downloaded
book, you'll find a templated circular sequence container using a list
(ring.cpp). Note that this excludes using any algorithm with past-the-end
iterators but it gets the job done.

 

[E. Mark Ping]

Careful--that might be copyright infringement.

But anyway, why make a new container? Why not simply make a circular
iterator?

 

[Claudio Puviani]

I was looking at Plauger's <vector> template as implemented in MS DEV
6 owned by HP.
I modified it to implement <cvector>, a circular vector template. I
modified the obvious, e. g. replaced vector by cvector, and removed
some redundant defns.

A circular template class also has
cvector.end() the same as cvector.begin()
I am wondering if I should change operator++ so that when the iterator
points to end(), it will wrap around to begin(), but was wondering if
that might mess up other template functions.
I handle the wrap around by adding a check in my code (not in
<cvector>) so that if I reached the end(), I reset the iterator to
begin().
Has anyone done this all ready? Am I using the right template, maybe
I should be using <list>?

Two comments:

1) Your terminology conflicts with an existing data structure known as a
"circular buffer", which can lead to confusion. The semantics, however, are
quite different. A circular buffer still has a beginning and an end (which is
only adjacent to the beginning if the container is full).

2) Why write an entire new container when you can just increment an index modulo
the length of the vector? I.e.: i = (i + 1) % v.size() -- assuming v.size() > 0.

Claudio Puviani

 

[Howard Hinnant]

I was looking at Plauger's <vector> template as implemented in MS DEV
6 owned by HP.
I modified it to implement <cvector>, a circular vector template. I
modified the obvious, e. g. replaced vector by cvector, and removed
some redundant defns.

A circular template class also has
cvector.end() the same as cvector.begin()
I am wondering if I should change operator++ so that when the iterator
points to end(), it will wrap around to begin(), but was wondering if
that might mess up other template functions.
I handle the wrap around by adding a check in my code (not in
<cvector>) so that if I reached the end(), I reset the iterator to
begin().
Has anyone done this all ready? Am I using the right template, maybe
I should be using <list>?

Yeah, I've done it. I called it Metrowerks::cdeque. It is very useful,
and can't be created from vector. And no, you don't want to set begin()
== end() when size() == capacity().

If by any chance you own CodeWarrior (any version in the last several
years), then look in <cdeque>. Here's an article I wrote about it a few
years ago:

http://home.twcny.rr.com/hinnant/tip_archive/MSL C++ Tip #8

Unless you need iterator stability during push/pop_front/back, this
animal makes a better queue than deque or list (less memory thrashing).

I wrote it because it was just the thing to handle the "map" that must
exist inside of std::deque. Every implementation has one, just I
fleshed the Metrowerks version into a first class full blown container.

There has also been work done on circurlar buffers over at boost. That
design differs a bit from cdeque (I don't think it automatically
increases capacity). Not sure of the status, but you might want to
check it out.

-Howard
Metrowerks

 

[P.J. Plauger]

Unless you need iterator stability during push/pop_front/back, this
animal makes a better queue than deque or list (less memory thrashing).

I wrote it because it was just the thing to handle the "map" that must
exist inside of std::deque. Every implementation has one, just I
fleshed the Metrowerks version into a first class full blown container.

We implement deque as a circular queue of pointers to blocks, so our
deque makes a very good basis for a queue. But there is, of course,
no guarantee that another implementation will behave as nicely. You
need to make explicit use of a circular queue, as Howard describes,
if you want to guarantee good performance.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com

 

[SaltPeter]

Careful--that might be copyright infringement.

When i mentioned "it gets the job done" in no way was i implying that the
code was copied or otherwise reproduced.

But anyway, why make a new container? Why not simply make a circular
iterator?

Because you can't itirate through a given subset of your circular iterators
without a base reference point and also a bidirectional iterator has its
benefits. Also, why write something everytime you need it? A new templated
container can be used with virtually any object type. You'll find that
inserting a circular iterator is much more difficult to maintain should your
needs expand.

I did write a class named a Spindle which does employ a referenced list
object / resolved iterator somewhat similar to Bruce Eckel's design but that
does not qualify as a copyright infringement. Besides, his analysis of the
limitations and benefits of efficiently creating (and therefore maintaining)
a reusable library is quite interesting for the poster. After all, that was
his primary goal.

 

[E. Mark Ping]

When i mentioned "it gets the job done" in no way was i implying that the
code was copied or otherwise reproduced.

I didn't quote that becuause it wasn't what I was responding to. You
took someone elses work and started modifying it to make your new
class. After reading the copyright notice in <vector> it looks like
that is explicitly allowed as long as the original copyright notice is
included. At any rate, my comment was that it "might" be a problem.
I don't think it is now after further review.

Because you can't itirate through a given subset of your circular
iterators without a base reference point

And? How does this preclude a circular iterator?

and also a bidirectional iterator has its benefits.

Who said a circular iterator isn't bidirectional?

Also, why write something everytime you need it?

One good templated circular iterator should do the trick. Why would
you expect to write this more than once based on my comment?

A new templated container can be used with virtually any object type.

A templated circular iterator can be used with virtually any container
as well as object type.

You'll find that inserting a circular iterator is much more difficult
to maintain should your needs expand.

By 'insert' do you mean the insert function or just the idea of
managing a circular iterator in your body of code? Why would this be
more difficult to maintain than the existing iterators for, say,
vector?