Hybrid container

R

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
 
R

Rob McDonald

* Rob McDonald:








"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 help 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]
 
J

Jerry Coffin

[ ... ]
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.
 
R

Rob McDonald

Typically, when I will add to the list, I won't really care where they
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.

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
 
A

AnonMail2005

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
 
J

Jerry Coffin

(e-mail address removed)>, (e-mail address removed)
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());
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top