Deriving from standard containers

Started by
17 comments, last by ApochPiQ 15 years, 6 months ago
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.

Wielder of the Sacred Wands
[Work - ArenaNet] [Epoch Language] [Scribblings]

Advertisement
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?
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.
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.
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]

Wielder of the Sacred Wands
[Work - ArenaNet] [Epoch Language] [Scribblings]

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.
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.
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.

Wielder of the Sacred Wands
[Work - ArenaNet] [Epoch Language] [Scribblings]

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).
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.
--Michael Fawcett

This topic is closed to new replies.

Advertisement