I am interested in having a container which has properties of both the
STL's list and vector. (I want my cake and to eat it too).

In my application, I will need to add/remove items from arbitrary
points in the container.

I will also need to be able to perform random access to elements of
the container -- accessed by index, not associatively.

Fortunately, in my application, I don't need to do both of these
things at the same time. I.e. I will do a bunch of adding/removing,
followed by a bunch of random access. Then I may go back to a bunch
of adding/removing, and then a whole bunch of random access.

So, my idea right now is to implement a container which is backed by a
list, but when you need to do random access, the list is 'frozen'. At
that point, a vector (or a boost array) is created to satisfy the
random access needs. Then, when you want to go back to inserting/
removing, the list is 'thawed' and the vector is destroyed.

I am still debating whether to make this freeze/thaw explicit or
automatic. Automatic is nice, but explicit would make sure the user
(me) doesn't screw up. Opinions appreciated.

Does this sort of thing exist already? Perhaps there is a keyword I'm
not searching for. Any pointers are appreciated.

I would rather not have to implement a complete STL container from
scratch, but from what I've read, they really aren't set up for
inheritance. What is the best way to go about implementing this idea?

Thanks in advance for any tips,

Rob

* Rob McDonald:
> I am interested in having a container which has properties of both the
> STL's list and vector. (I want my cake and to eat it too).
>
> In my application, I will need to add/remove items from arbitrary
> points in the container.
>
> I will also need to be able to perform random access to elements of
> the container -- accessed by index, not associatively.
>
> Fortunately, in my application, I don't need to do both of these
> things at the same time. I.e. I will do a bunch of adding/removing,
> followed by a bunch of random access. Then I may go back to a bunch
> of adding/removing, and then a whole bunch of random access.
>
> So, my idea right now is to implement a container which is backed by a
> list, but when you need to do random access, the list is 'frozen'. At
> that point, a vector (or a boost array) is created to satisfy the
> random access needs. Then, when you want to go back to inserting/
> removing, the list is 'thawed' and the vector is destroyed.
>
> I am still debating whether to make this freeze/thaw explicit or
> automatic. Automatic is nice, but explicit would make sure the user
> (me) doesn't screw up. Opinions appreciated.
>
> Does this sort of thing exist already? Perhaps there is a keyword I'm
> not searching for. Any pointers are appreciated.
>
> I would rather not have to implement a complete STL container from
> scratch, but from what I've read, they really aren't set up for
> inheritance. What is the best way to go about implementing this idea?

"Best" is meaningless without some criteria.

In addition to clear criteria for that, the specification needs to be fleshed
out. E.g., are the elements small ones (like char) or large ones? During adding,
do you need to insert elements at random positions, or are elements just added
at ends or perhaps one end, or, for example, is the insert position only moved
one element position at a time?

Depending on this there may already be a suitable C++ standard library
container, or in some other library, or you may have to create your own one. In
the latter case the question doesn't really have much to do with C++. So you'd
be better off asking in e.g. [comp.programming].


Cheers, & hth.,

- Alf

[cross-posted to comp.programming, follow-ups set to comp.programming]

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

On Jul 16, 9:32pm, "Alf P. Steinbach" <al...@start.no> wrote:
> * Rob McDonald:
> > I am interested in having a container which has properties of both the
> > STL's list and vector. (I want my cake and to eat it too).
>
> > In my application, I will need to add/remove items from arbitrary
> > points in the container.
>
> > I will also need to be able to perform random access to elements of
> > the container -- accessed by index, not associatively.
>
> > Fortunately, in my application, I don't need to do both of these
> > things at the same time. I.e. I will do a bunch of adding/removing,
> > followed by a bunch of random access. Then I may go back to a bunch
> > of adding/removing, and then a whole bunch of random access.
>
> > So, my idea right now is to implement a container which is backed by a
> > list, but when you need to do random access, the list is 'frozen'. At
> > that point, a vector (or a boost array) is created to satisfy the
> > random access needs. Then, when you want to go back to inserting/
> > removing, the list is 'thawed' and the vector is destroyed.
>
> > I am still debating whether to make this freeze/thaw explicit or
> > automatic. Automatic is nice, but explicit would make sure the user
> > (me) doesn't screw up. Opinions appreciated.
>
> > Does this sort of thing exist already? Perhaps there is a keyword I'm
> > not searching for. Any pointers are appreciated.
>
> > I would rather not have to implement a complete STL container from
> > scratch, but from what I've read, they really aren't set up for
> > inheritance. What is the best way to go about implementing this idea?
>
> "Best" is meaningless without some criteria.
>
> In addition to clear criteria for that, the specification needs to be fleshed
> out. E.g., are the elements small ones (like char) or large ones? During adding,
> do you need to insert elements at random positions, or are elements just added
> at ends or perhaps one end, or, for example, is the insert position only moved
> one element position at a time?

My intent would be to end up with a template container which would be
well behaved no matter the size of what I'm holding. In my immediate
application, it would probably hold a pointer to something more
complex.

Typically, when I will add to the list, I won't really care where they
go, so at the end is fine.

On the other hand, removals need to happen from arbitrary locations.

> Depending on this there may already be a suitable C++ standard library
> container, or in some other library, or you may have to create your own one. In
> the latter case the question doesn't really have much to do with C++. So you'd
> be better off asking in e.g. [comp.programming].

That is exactly the kind of guidance I was hoping for. Hopefully my
clarifications to your questions will answer these questions.

> [cross-posted to comp.programming, follow-ups set to comp.programming]

I appreciate the redirection, but I really think this question is more
appropriate to a C++/STL group than a general programming group. I am
developing in C++, using STL containers, with some Boost libraries,
and the any_iterator library to make things a bit more flexible. I
see my question as an implementation question rather than an algorithm/
design question.

[switched back to comp.lang.c++, not cross-posted]

In article <baa0f55b-25e2-43df-ab25-ed6ad23382f4@
26g2000hsk.googlegroups.com>, rob.a.mcdonald@gmail.com says...

[ ... ]

> Typically, when I will add to the list, I won't really care where they
> go, so at the end is fine.
>
> On the other hand, removals need to happen from arbitrary locations.

Does the fact that you don't care where additions go imply that overall
order doesn't matter?

If you can reorder elements with inpunity, deleting from the middle of a
vector is trivial: swap the element(s) to be removed to the end of the
sequence, then delete them. All the vector has to do to delete from the
end is change the count of elements currently in use, so it's generally
_quite_ fast.

--
Later,
Jerry.

The universe is a figment of its own imagination.

> > Typically, when I will add to the list, I won't really care where they
> > go, so at the end is fine.
>
> > On the other hand, removals need to happen from arbitrary locations.
>
> Does the fact that you don't care where additions go imply that overall
> order doesn't matter?
>
> If you can reorder elements with inpunity, deleting from the middle of a
> vector is trivial: swap the element(s) to be removed to the end of the
> sequence, then delete them. All the vector has to do to delete from the
> end is change the count of elements currently in use, so it's generally
> _quite_ fast.
>
> --
> Jerry.

That will probably work. Good idea.

So, for the implementation, what I'd like is an STL vector with
remove(i), remove_if, remove(<T> t) etc. implemented as swap & remove.

Is there an elegant way to implement this without either 1) re-
implementing everything in a vector. or 2) implementing wrappers which
redirect to a held vector?

In the name of code re-use, I'd really prefer to use all the hard work
which has gone into vector implementations.

Rob

On Jul 17, 12:18am, Rob McDonald <rob.a.mcdon...@gmail.com> wrote:
> I am interested in having a container which has properties of both the
> STL's list and vector. (I want my cake and to eat it too).
>
> In my application, I will need to add/remove items from arbitrary
> points in the container.
>
> I will also need to be able to perform random access to elements of
> the container -- accessed by index, not associatively.
>
> Fortunately, in my application, I don't need to do both of these
> things at the same time. I.e. I will do a bunch of adding/removing,
> followed by a bunch of random access. Then I may go back to a bunch
> of adding/removing, and then a whole bunch of random access.
>
> So, my idea right now is to implement a container which is backed by a
> list, but when you need to do random access, the list is 'frozen'. At
> that point, a vector (or a boost array) is created to satisfy the
> random access needs. Then, when you want to go back to inserting/
> removing, the list is 'thawed' and the vector is destroyed.
>
> I am still debating whether to make this freeze/thaw explicit or
> automatic. Automatic is nice, but explicit would make sure the user
> (me) doesn't screw up. Opinions appreciated.
>
> Does this sort of thing exist already? Perhaps there is a keyword I'm
> not searching for. Any pointers are appreciated.
>
> I would rather not have to implement a complete STL container from
> scratch, but from what I've read, they really aren't set up for
> inheritance. What is the best way to go about implementing this idea?
>
> Thanks in advance for any tips,
>
> Rob

As a first cut I would use a std::deque. It allows random access to
it's
elements (like a std::vector) but does not have the requirement that
it's
memory is contiguous (in that sense it's like a std::list).

HTH

In article <b14f7eb4-0434-43a5-b174-
7dad2b0d57cb@z72g2000hsb.googlegroups.com>, rob.a.mcdonald@gmail.com
says...

[ ... ]

> So, for the implementation, what I'd like is an STL vector with
> remove(i), remove_if, remove(<T> t) etc. implemented as swap & remove.

Actually, if you look carefully, you'll find that all remove, remove_if,
etc., do is swap things to the end of the container. You have to use the
container's erase() to actually delete the items. Nicely enough, remove
and company return an iterator to the beginning of where the put the
items you asked to have removed, so you do something like:

myVector.erase(remove(whatever), myVector.end());

--
Later,
Jerry.

The universe is a figment of its own imagination.