Hybrid container

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

Thanks in advance for any tips,

Rob

[Rob McDonald]

Re: Hybrid container

On Jul 16, 9:32 pm, "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.programmin g].

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

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

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]

[AnonMail2005@gmail.com]

Re: Hybrid container

On Jul 17, 12:18 am, Rob McDonald <rob.a.mcdon... @gmail.comwrote :

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

[Jerry Coffin]

Re: Hybrid container

In article <b14f7eb4-0434-43a5-b174-
7dad2b0d57cb@z7 2g2000hsb.googl egroups.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(<Tt) 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.