Sign in to follow this  
ApochPiQ

Deriving from standard containers

Recommended Posts

Right, so we should all basically agree that deriving from standard containers (std::vector, std::map, et. al.) is a bad idea. The classes aren't designed for it; the lack of virtual functions and virtual destructors makes polymorphism a veritable minefield (if not outright impossible); and so on. Now here's my question - I need some ammunition for a debate over a few different options.
Option #1, the current way typedef std::map<foo, bar, std::less<foo>, special_allocator<std::pair<foo, bar>, memory_annotations> > FooBarMapT;
This works great, uses the custom allocator as required, and so on. The only real disadvantage is it is a bit verbose, and you have to specify the types twice (one for the container, one for the allocator).
Option #2, my preferred alternative #define SPECIALMAP(foo, bar, memory_annotations) std::map<foo, bar, std::less<foo>, special_allocator<std::pair<foo, bar>, memory_annotations> >
This cuts out the duplication, makes the declarations a bit shorter, and generally works as nicely as Option #1. The only problem is it introduces an unusual syntax (SPECIALMAP(foo, bar, quux) instead of std::map<foo, bar ...>
Option #3, which I am convinced is a veritable lie from the bowels of Satan himself template specialmap<class foo, class bar, quux memory_annotations> : public std::map<foo, bar, std::less<foo>, special_allocator<std::pair<foo, bar>, memory_annotations> > FooBarMapT;
This just feels evil to me. Yes, it preserves the original map<foo, bar ...> syntax, but... just... eew. Inheritance for no good reason. Deriving from an STL container class. Polymorphism is now verboten or we'll end up with a lot of really slimy bugs. Now, I'm not actually sure if I'm right about this. It seems, instinctively, that option #3 is just wrong. But I can't prove it. If I'm correct, I need some kind of thorough explanation as to why it's a bad idea, and if I'm wrong, then I need to know that, too [smile] So... break out your copy of the C++ standard and go to town. Enlighten us.

Share this post


Link to post
Share on other sites
Quote:

Option #1, the current way
typedef std::map<foo, bar, std::less<foo>, special_allocator<std::pair<foo, bar>, memory_annotations> > FooBarMapT;


This works great, uses the custom allocator as required, and so on. The only real disadvantage is it is a bit verbose, and you have to specify the types twice (one for the container, one for the allocator).

You don't have to specify them twice:

template <typename foo, typename bar, typename memory_annotations>
struct SpecialMap {
typedef std::map<foo, bar, std::less<foo>, special_allocator<std::pair<foo, bar>, memory_annotations> > type;
};

And then you can use it as SpecialMap<foo, bar, quux>::type;

Any problems with this approach?

Share this post


Link to post
Share on other sites
I wont go into it heavily, but i did option 3 without any problems. I didn't add any functionality, just mirrored the constructors and supplied an allocator.

I think this is an occasion i'm happy to do something strictly wrong, if i find it causes me lots of bugs i will happily fix it.

Share this post


Link to post
Share on other sites
Ok, in theory, option 3 invokes undefined behavior in a few different places depending on how you use it. In practice it'll work fine in most circumstances with most compilers. This is how D3DXVECTOR3 and similar classes are implemented in the DirectX SDK.

However, most circumstances is decidedly not the same as all circumstances. The inheritance introduces an additional type that can play havoc with template instantiations. Here's an example, somewhat simpler than the std::map in the original post:

#include <vector>
#include <iostream>

template <typename T>
class MyVector : public std::vector<T> {
};

template <typename Container>
void foo(Container &) {
std::cout << "original foo" << std::endl;
}

template <typename T>
void foo(std::vector<T> &) {
std::cout << "special foo" << std::endl;
}

int main(int, char **) {
MyVector<int> v1;
foo(v1);

std::vector<int> v2;
foo(v2);
}

Here v1 gets called with the first foo() and v2 gets called with the second foo(), so any special processing or more efficient algorithms for the case of std::vector versus a generic container will be lost. And like most template instantiation issues, these kinds of errors can be a real pain in the ass to track down.

As far as I can recall, template instantiations are really the only practical issue with option 3, and even then they only come up occasionally since most template functions used with containers are based on iterators. However, when they do come up they tend to more than eat up all the time you saved using the short name rather than the long name.

Share this post


Link to post
Share on other sites
Quote:
Original post by Spoonbender
You don't have to specify them twice:

template <typename foo, typename bar, typename memory_annotations>
struct SpecialMap {
typedef std::map<foo, bar, std::less<foo>, special_allocator<std::pair<foo, bar>, memory_annotations> > type;
};

And then you can use it as SpecialMap<foo, bar, quux>::type;

Any problems with this approach?


This is a nice trick, but we've all agreed we don't like the syntax [smile] Thanks anyways!


Quote:
Original post by Dave
I wont go into it heavily, but i did option 3 without any problems. I didn't add any functionality, just mirrored the constructors and supplied an allocator.

I think this is an occasion i'm happy to do something strictly wrong, if i find it causes me lots of bugs i will happily fix it.


That's what we're worried about - taking an easy, lazy shortcut now and introducing some very nasty bugs down the road.

Well, that's what I'm worried about. There is obviously some disagreement as to how much of a risk this really is.


Quote:
Original post by SiCrane
[snip for brevity]


Thanks! This is exactly the kind of stuff I need. The bottom line of my argument is that yeah, if we're ridiculously careful, we might get away with it, but the pitfalls are too numerous and subtle to take the chance.



Keep 'em coming... I'll need lots of fuel on this one [smile]

Share this post


Link to post
Share on other sites
Are you providing your own allocator for memory management reasons? If that is the case, you also have to take into account how lazy having to write a long declaration for every std::{container} will make some of your programmers, therefore introducing problems on the memory management side of things.

Share this post


Link to post
Share on other sites
Quote:
Original post by ApochPiQ
Thanks! This is exactly the kind of stuff I need. The bottom line of my argument is that yeah, if we're ridiculously careful, we might get away with it, but the pitfalls are too numerous and subtle to take the chance.


I can give you more examples of types of template instantiations that can lead to issues, but the problem is that when dealing with container classes, most of these aren't things that you'll have to deal with. For example:

template <typename T>
class MyVector : public std::vector<T> {
};

int main(int, char **) {
std::vector<std::vector<int> > my_vec;
std::vector<MyVector<int> > & ref = my_vec;
}

This example takes advantage of the fact that vector<T> is an unrelated type to vector<U> even if T and U have an inheritance relationship. However, in my experience containers aren't commonly a template parameter for other template classes, so this one rarely comes up in practice.

Of course, that particular example isn't subtle, though it can manifest in more subtle ways. A more subtle one is that more or less identical function bodies can be generated for two template types for each instantiation of the inheritance class. Not a huge deal on recent versions of MSVC, which has link time redundant COMDAT folding, but it can be a source of bloat with less sophisticated linkers.

Share this post


Link to post
Share on other sites
Actually we use nested containers fairly widely for certain data, so this is very likely to come along and bite us in the backside. It's especially problematic since we'd be talking about deriving from every container class, and we do have plenty of places where we use containers as template parameters.


So it looks like the derivation option #3 is out. Thanks all!



Quote:
Original post by Dave
Are you providing your own allocator for memory management reasons? If that is the case, you also have to take into account how lazy having to write a long declaration for every std::{container} will make some of your programmers, therefore introducing problems on the memory management side of things.


We already planned for that - because of how the global new/delete operators have been overloaded, we can trap unmarked allocations inside a "general" pool which is reserved for, well, general stuff. There's also a facility for dumping a call stack for every outstanding allocation in the game, so we can look at what's filling up the general pool and go correct the code to use the proper memory management typedefs.

Share this post


Link to post
Share on other sites
Quote:
This is a nice trick, but we've all agreed we don't like the syntax Thanks anyways!

Yet this is the recognized way to do template typedefs, which is what you want.l

Using inheritance is a way to achieve a strong typedefs, however constructors are not forwarded, so you have to rewrite them all. (Or use C++0x using).

Share this post


Link to post
Share on other sites
Quote:
Original post by ApochPiQ
Option #1, the current way
typedef std::map<foo, bar, std::less<foo>, special_allocator<std::pair<foo, bar>, memory_annotations> > FooBarMapT;


This works great, uses the custom allocator as required, and so on. The only real disadvantage is it is a bit verbose, and you have to specify the types twice (one for the container, one for the allocator).


Do you really have to specify the types twice? The std::map is just going to rebind anyways, and in this case it will rebind to special_allocator<std::pair<const foo, bar>, memory_annotations>

What about making a template class that derives privately from the container, then has using statements? Sure it would be a pain to write once, but then you get the normal syntax of the std::container.

Share this post


Link to post
Share on other sites
Quote:
Original post by loufoque
Yet this is the recognized way to do template typedefs, which is what you want.


Yes, I'm familiar with the method. The problem is, nobody else on the team is; and since we need our code to be legible and understandable by everyone, using such syntax is not really a good idea. I recognize that it is idiomatic C++, but a lot of the guys are still new to C++ and the less mess we force them to learn the better. We're out to get the job done, not to write perfect code [wink]


Quote:
Original post by mfawcett
Do you really have to specify the types twice? The std::map is just going to rebind anyways, and in this case it will rebind to special_allocator<std::pair<const foo, bar>, memory_annotations>

What about making a template class that derives privately from the container, then has using statements? Sure it would be a pain to write once, but then you get the normal syntax of the std::container.


If there's a way to avoid the duplicate type specifications in that typedef (without running afoul of the syntax issues mentioned earlier), I'd love to learn it [smile]

Share this post


Link to post
Share on other sites
// Note private, not public
// Also note that it does not matter what type you pass to special_allocator!
// std::map will just use special_allocator::rebind to get the right one.
template <class foo, class bar, quux memory_annotations>
struct specialmap : private std::map<foo, bar, std::less<foo>, special_allocator<int, memory_annotations> >
{
typedef std::map<foo, bar, std::less<foo>, special_allocator<std::pair<foo, bar>, memory_annotations> > map_type;

using map_type::insert;
using map_type::operator[];
// etc...
};

A serious pain...but you only have to go through it once. I think I did this once for grins and just copied the MSDN interface documentation, then recorded a quick macro that took every line and deleted the documentation but kept the method name and added the using keyword.

Honestly all that buys you is that when using the class, you don't have to write ::type like in Spoonbender's method (I prefer his method).

For further clarification (I'm sure you know this), what I meant about the allocator::rebind stuff - this compiles and works fine, because std::map will rebind to an allocator that allocates std::pair<const int, int>, not float:

std::map<int, int, std::less<int>, std::allocator<float> > testing;


Maybe you can use that to your advantage so you can get the right syntax but not specify the types twice?

Share this post


Link to post
Share on other sites
Question is, does that work for other containers besides map? We make heavy use of several different containers - vector, map/multimap, list, set/multiset, and deque are the heavy hitters. The other thing is the memory annotation parameter that needs to be passed to the allocator; do I just typedef int DummyT; and then just always use special_allocator<DummyT, annotations> or what? Is there a way to use default parameters to avoid the need for a dummy type?

Share this post


Link to post
Share on other sites
Quote:
Original post by ApochPiQ
Question is, does that work for other containers besides map? We make heavy use of several different containers - vector, map/multimap, list, set/multiset, and deque are the heavy hitters. The other thing is the memory annotation parameter that needs to be passed to the allocator; do I just typedef int DummyT; and then just always use special_allocator<DummyT, annotations> or what? Is there a way to use default parameters to avoid the need for a dummy type?


For your first question, VS2005 will rebind on every container I just tested it with:

std::vector<int, std::allocator<float> > testing;
std::deque<int, std::allocator<float> > testing;
std::map<int, int, std::less<int>, std::allocator<float> > testing;
std::list<int, std::allocator<float> > testing;

All of those compile, and I looked at the implementation and they all use rebind. I have a copy of the standard, but I haven't had a chance to look to see if an implementation is required to use rebind.

For your second question, (thinking out loud here) what if you provided a struct that contained enough information to create a real allocator from rebind only? e.g., something like this (I know it's not complete):

template <quux memory_annotations>
struct special_allocator_t
{
template <class T>
struct rebind
{
typedef special_allocator<T, memory_annotations> other;
};
};

Then people would just:
special_vector<int, special_allocator_t<memory_annotations> > my_vector;

Share this post


Link to post
Share on other sites
That looks like a pretty promising trick, thanks!

We'll be discussing the issue with all the programmers shortly, so we'll see what people end up thinking about the various syntax options. As long as there are no serious objections to the syntax (which there shouldn't be) we're likely to go with Spoonbender's original solution.


Thanks all for the input!

Share this post


Link to post
Share on other sites
I don't think that trick will work (or requires more investigation). I just tried it, and special_allocator_t would need to be convertible to special_allocator.

I would recommend going with Spoonbender's suggestion. It is the easiest and most idiomatic.

Share this post


Link to post
Share on other sites
Quote:
Original post by ApochPiQ
Quote:
Original post by loufoque
Yet this is the recognized way to do template typedefs, which is what you want.


Yes, I'm familiar with the method. The problem is, nobody else on the team is; and since we need our code to be legible and understandable by everyone, using such syntax is not really a good idea. I recognize that it is idiomatic C++, but a lot of the guys are still new to C++ and the less mess we force them to learn the better. We're out to get the job done, not to write perfect code [wink]

Fair point. :)

However, it seems that compared to so many other quirks in C++ that they'll have to get used to, this one should be pretty manageable. I mean, there's no magic involved. Once you accept the existence of typedefs, and that they can be nested inside a struct, it's straightforward, isn't it?

I understand your reasoning though. Picking an approach that everyone understands is probably a very good idea [grin]

Share this post


Link to post
Share on other sites
Quote:
Original post by ApochPiQ

Yes, I'm familiar with the method. The problem is, nobody else on the team is; and since we need our code to be legible and understandable by everyone, using such syntax is not really a good idea. I recognize that it is idiomatic C++, but a lot of the guys are still new to C++ and the less mess we force them to learn the better. We're out to get the job done, not to write perfect code [wink]


C9564: in line 3, post 7, Does Not Compute.

Rather than writing 5-ish template definitions, you are going to use macros, push the compiler to the limits and expose those *inexperienced* people to the infinite void that is undefined/obscure/invalid/edge behavior?

Share this post


Link to post
Share on other sites
Like I said, I'm personally all in favor of using the template typedef - the macro idea was a compromise to help shorten the declarations without affecting any of the underlying code - specifically, without invoking all the undefined behaviour of deriving from the containers in the first place.

I'll be making a case for not using macros, but ultimately the decision isn't really mine. If it were up to me I would have done the template typedef from the beginning and been done with it [smile]


Anyways, I fail to see how a preprocessor macro is any more strenuous on the compiler than a typedef. Can you explain that comment in more detail?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this