Design of pointer container template

Question

I would like to write a "versatile" class representing the general container storing pointers. Should I use public inheritance or containment?

template <class T>
class List : public std::vector <T *>
{
//...
}

Or

template <class T>
class List
{
private:
   std::vector <T *> items;
//...
}

May some problems occur with abstract classes (i.e. virtual destructor)?

If neither proposal is appropriate, what design should I follow (and could you include a short example)?

Its naught to call a vector a list. When you say list we expect certain intrinsic behavioral patterns. Vector does not supply those behaviors. For example inserting into the middle of a list I would expect to be constant time (this is not true for vector). — Martin York, Sep 21 '10 at 22:16
@Martin: He's not thinking of std::list; other languages/environments use "list" where C++ uses "vector". — , Sep 21 '10 at 22:22

score 3 · Answer 1 · edited May 23 '17 at 10:32

This is already done for you with Boost's pointer containers.

I do not like boost so I would like to use only C++ 0x00 standard :-).
— Ian (comment)

If you still want to re-invent these classes, look at the design decisions they made. In particular, they don't inherit from other containers as your first code does.

In fact, just copy the code right out from Boost. This is a header-only library and should be straight-forward (i.e. few implementation-specific workarounds). Boost's license is very liberal, not even requiring you to mention Boost when distributing compiled programs.

score 2 · Answer 2 · answered Sep 21 '10 at 22:04

2

How about:

typedef std::vector<boost::shared_ptr<T> > List;

That is, I think it's better to use a resource managing pointer within regular container classes than to reinvent each of the container classes to add resource management capability.

answered Sep 21 '10 at 22:04

Drew Hall

28,429
12
61
81

Why do you think it's better? – Sep 21 '10 at 22:10
But, in my opinion, such soluton will be slow. I need high-performance that can not be provided by shared_ptrs ... – Ian Sep 21 '10 at 22:11
@Roger: Because you get the resource management correct in one place (the pointer class), and you can use it in any arbitrary container from that point on. And, when you get an element from the container, you get it via a smart pointer that will play nice with the overall management of that resource. The use of raw pointers in C++ should be discouraged in most cases. – Drew Hall Sep 21 '10 at 22:14
1

@Ian: Opinions are one thing--what do your performance measurements tell you? – Drew Hall Sep 21 '10 at 22:14
1

Using std::unique_ptr from C++0x is the thinest you can get without doing everything manually – David Sep 21 '10 at 22:15
@Drew: 1) It's not all in one place, because you have to manage all the various details (such as null pointers and copying) throughout the entire code. 2) Boost's pointer containers are designed to own the pointed-to objects (just like shared_ptr does). 3) There are more than two choices; I am no more advocating raw pointers than you are. — [But don't take my word for it.](http://www.boost.org/doc/libs/1_44_0/libs/ptr_container/doc/ptr_container.html#motivation) – Sep 21 '10 at 22:20
@Drew Hall: I am going to work with data made up of millions of items (points from laser scanning). When we comparing time needed to create and fill such list (raw pointer vs shared_ptr), shared_ptr is about 10 times slower... – Ian Sep 21 '10 at 22:22
@Roger: Sorry--didn't mean to imply that you were advocating raw pointers. I agree that Boost's pointer containers are an equally viable solution, I just prefer the dumb container of smart pointers approach over the smart container of dumb pointers approach. To each his own :). – Drew Hall Sep 21 '10 at 22:29
@Ian: Fair enough. As long as you're speaking from measurement vs. speculation, I can't argue. But 10x does surprise me a bit. – Drew Hall Sep 21 '10 at 22:32
@Drew: That's the misconception I'm trying to dispel: pointer containers don't expose a dumb pointer (e.g. handling of null pointers and copying/"deepcopying" (the latter is a poor term)). It's dumb container of smart pointers vs. smart container of "normal" objects (which just happen to be allocated specially). ;) – Sep 21 '10 at 22:36
(Of course, when you *want* pointer semantics, such as sharing and null, then you need a container of pointers.) – Sep 21 '10 at 22:39
@Drew: I am sorry, I overrated the time difference. I have just proved an example: 10 000 000 2D points. Time to create, fill and manually destruct = 5sec for raw pointers. The same operation (with automatic destruction) = 18 sec for shared_ptr. MSVS 2010, release, Win7 32bit. But even so, they are significantly slower... – Ian Sep 21 '10 at 22:45
1

@Roger: I had never looked very closely at boost::ptr_container before--thanks for the motivation to do so. I always thought the only additional feature it provided was deleting the pointers in the destructor, but now I see there's a lot more to it. – Drew Hall Sep 21 '10 at 22:46
@Ian: Thanks for the numbers--no question there's a significant performance penalty there. I'm starting to like Roger's solution more (for your application, anyway... :)). – Drew Hall Sep 21 '10 at 22:49
@Drew: This has made me realize "pointer container" is a poor name for them, but nothing else immediately comes to mind (and Boost is stuck with the name, in any case). – Sep 21 '10 at 22:58
@Drew:Thanks for your posts and comments. But there is a "big" problem: I do not like boost so I would like to use only C++ 0x00 standard :-). In Europe, it's too late, I am going to sleep :-) – Ian Sep 21 '10 at 22:59
@Roger: How about "polymorphic container"? Agreed--pointer container is a terrible name! – Drew Hall Sep 21 '10 at 23:11
I'm not sure the name is that bad. I was literally working with containers of pointers up till the moment I noticed that name in the Boost library list -- if it hadn't been so obviously relevant to what I was doing, I might never have taken a second glance. – Porculus Sep 22 '10 at 00:03

score 0 · Answer 3 · answered Sep 21 '10 at 22:10

0

private inheritance is a common tactic for creating classes that are implemented in terms of another. Code that uses the class can't tell that the derived class is derived from a private base, so you won't end up in the sorts of situations that might ordinarily require a virtual destructor.

Use using to import members from the private base to the derived class. For example:

template<class T>
class List:
private std::vector<T>
{
public:
    using std::vector<T>::operator[];
    using std::vector<T>::size;
};

This is a bit crude, but it gives you some flexibility. You can start out by using private inheritance, and this saves you some typing compared to writing forwarding functions, but you can still write alternative implementations long-hand as required. And then, if/when this becomes inappropriate, you can change the implementation style -- perhaps have a vector as a member, for example, or maybe do everything by hand -- safe in the knowledge that client code won't need to change.

This is ideal for situations where you're pretty sure you'll eventually need a non-standard type of container, but have an existing container type that mostly fits the bill for now. And it's a better medium-term solution than a typedef, because there's no risk of client code accidentally (or on purpose...) using the two types interchangeably.

answered Sep 21 '10 at 22:10

Rationale for -1s appreciated ;) – Sep 21 '10 at 22:26
I can't see a reason to downvote either (and I'm out of votes for the day, so tomorrow). This is a good implementation strategy to know, even though this specific case has a [better answer](http://stackoverflow.com/questions/3764836/design-of-pointer-container-template/3764877#3764877). ;) – Sep 21 '10 at 22:30
@Steve: Private inheritance is encapsulation. – Sep 21 '10 at 22:31
Yes -- composition IS preferable, but private inheritance is a reasonable short-to-medium-term solution that shouldn't stuff you if it ends up long-term. Looks the same to client code, but it's less typing than composition, and much better than a typedef. That's a tradeoff I'm happy with, at any rate :) (As for boost, I've yet to use the compiler/platform/libraries combo that includes it out of the box, so I don't suggest it as an answer to questions that don't already refer to it explicitly.) – Sep 21 '10 at 22:45
@Steve. Why do you prefer it? – Ian Sep 21 '10 at 22:47
I'm not Steve, but -- inheritance, of any form, tends to imply is-a. That's not really true for private inheritance, but your readers stand a good chance of thinking it anyway. When you're writing something, you should spare a thought for the people who are reading it... – Sep 21 '10 at 22:50
@brone/@Ian/@Roger Pate - You're right, I'm removing my assertion – Steve Townsend Sep 21 '10 at 22:54

Design of pointer container template

3 Answers3

Linked