 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Gareth Stockwell
Guest
|
 Posted: Fri Jan 16, 2004 6:07 pm Post subject: STL container wrapper |
 |
|
I have been working on some templates which I think may be of use to
others, and I was wondering if anyone has any comments - including
whether you think this is duplicating any existing projects.
I have been working on a set of wrappers for STL container classes, of
the form
template<typename Data, template
class ContainerWrapper;
so that you can write e.g.
ContainerWrapper<int, std::vector> W;
and get an object which exposes all the member functions of a
std::vector<int>, plus a set of functions which are exposed whatever
the type of the second parameter. For example, I want to be able to
write
typedef ContainerWrapper<int, stl_container_type> wrapper;
wrapper W;
// Assume for now that each element in W is unique
W::iterator i = W.insert(10);
W::iterator j = W.find(10);
W.erase(10);
int x = W[5];
whatever the type of stl_container_type (e.g. std::vector, std::list,
std::set).
Note that I disallow pair associative containers; in fact that
template<typename> parameter does that for me automatically.
The reason for writing ContainerWrapper is that I want to be able to
provide, as a template parameter, the containers used *inside*
higher-order data structures. This is a technique used in the boost
graph library, where clients specify which containers a graph is to
use for storing its vertex and edge objects. In a similar vein
example, one of my tree classes looks (roughly) like:
template<class NodeType, template
class NaryTree;
By doing this, the client can choose the child container which
provides the best speed/efficiency characteristics for the application
being developed.
The way this is implemented is by having ContainerWrapper inherit from
a set of template classes which, by using traits and compile-time
dispatch, decide how to implement each of the functions which the
wrapper eventually exposes. For example, the random-access operator
is implemented for std::vector by simple forwarding to the vector
object which is inside the wrapper:
inline X&
ContainerWrapper<X, Container>::operator[](const size_t& n)
{ return container_[n]; }
But when the Container parameter is not a random-access container
(e.g. std::list), we implement it like this:
inline X&
ContainerWrapper<X, Container>::operator[](const size_t& n) {
int m = n;
iterator i = container_.begin();
while(m-- > 0) ++i;
return *i;
}
Now, I go a step further, and add a third template parameter to my
ContainerWrapper template, which specifies the 'containment policy',
which may be e.g.
i) the container stores objects by value (as do vanilla STL
containers)
ii) the container stores pointers to dynamically-allocated objects,
and assumes 'ownership' of those objects (think of it as a
smart_container)
iii) the container stores pointers to objects, but does not assume
ownership
iv) stores reference-counted pointers
etc etc
Whatever the containment policy, I want my operator[],
iterator::operator* etc to return an X& reference, so again,
compile-time dispatch is used to determine how to implement such
functions.
So, what do you think about this approach? To me, it seems a useful
way of making the implementation of a class like NaryTree independent
of the type of container used inside it. Since the function dispatch
is done at compile-time, those member functions which simply forward
to the STL container should be as fast as using the STL container
directly.
I look forward to your comments!
Gareth
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
 |
Jonathan Turkanis
Guest
|
| Posted: Sat Jan 17, 2004 10:56 am Post subject: Re: STL container wrapper |
|
|
Gareth Stockwell" <gareth (AT) ebi (DOT) ac.uk> wrote
| Quote: | I have been working on some templates which I think may be of use to
others, and I was wondering if anyone has any comments - including
whether you think this is duplicating any existing projects.
I have been working on a set of wrappers for STL container classes,
of
the form
template<typename Data, template
class ContainerWrapper;
so that you can write e.g.
ContainerWrapper<int, std::vector> W;
|
Let me just comment on one aspect of your design.
The above code is not portable, because std::vector is specified to
have at least two template parameters -- the second is an allocator
type -- and may have more depending on the implementation. So
std::vector should not match a template template parameter declared as
'template<typename> class Container', although some compilers, notably
gcc (at least through 3.3.1), allow it. (See
http://lists.boost.org/MailArchives/boost-users/msg04509.php.)
It is possible to let users supply a specialization of a container as
a type template parameter and internally extract all the needed
information (e.g., whether it is a vector and what its template
arguments are).
Jonathan
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Dan McLeran
Guest
|
| Posted: Sat Jan 17, 2004 11:03 am Post subject: Re: STL container wrapper |
|
|
I assume that you would derive publicly from the container you've
chosen? Seems like alot of work. A better way to get what you want
might be to typedef the container chosen and use it directly. This
way, ContainerWrapper is merely a struct that fully typedefs the
container for you. I have provided an example that compiles on both
MinGW g++ 3.1 and MSVC7.12003.
#include <iostream>
#include <vector>
template<class T,template
AllocatorType,template<class,class> class ContainerType>
struct ContainerWrapper
{
typedef ContainerType<T,AllocatorType type;
};
int main()
{
using namespace std;
typedef ContainerWrapper<int,std::allocator,std::vector>::type
ContainerType;
typedef ContainerType::iterator IteratorType;
ContainerType c;
for(int i = 1;i < 11;++i)
{
c.push_back(i);
}
for(IteratorType it = c.begin();it != c.end();++it)
{
cout<<*it<
}
return 0;
}
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Allan Odgaard
Guest
|
| Posted: Sat Jan 17, 2004 11:07 am Post subject: Re: STL container wrapper |
|
|
[email]gareth (AT) ebi (DOT) ac.uk[/email] (Gareth Stockwell) wrote in message news:<d1b18d21.0401160256.77aad6a1 (AT) posting (DOT) google.com>...
| Quote: | The way this is implemented is by having ContainerWrapper inherit from
a set of template classes which, by using traits and compile-time
dispatch, decide how to implement each of the functions which the
wrapper eventually exposes. For example, the random-access operator
is implemented for std::vector by simple forwarding to the vector
[...] But when the Container parameter is not a random-access container
(e.g. std::list), we implement it like this: [...]
|
You should be able to use the compile-time dispatch with the iterators
instead of the containers, which might eliminiate the need for your
wrapper classes.
E.g. for your "nth element" you can use:
iterator it = container.begin();
std::advance(it, n);
return *it;
And it will give you O(1) access for std::vector, and O(n) for
std::list.
If you want the bracket shorthand notation, you can always make a
private member class in your data structure which wrap the container
and overload this operator (which will then be a generic
implementation which work for all containers passed in, and not be the
chore of the user to wrap the containers.
Though you may still need some sort of traits-system to allow
insertion into the sequence. Perhaps also use the traits system to
obtain the first/last element of the sequence, so that it could e.g.
be used with primitive arrays (although it might be a challenge  ).
| Quote: | Now, I go a step further, and add a third template parameter to my
ContainerWrapper template, which specifies the 'containment policy',
which may be e.g.
i) the container stores objects by value [...]
ii) the container stores pointers to dynamically-allocated objects [...]
iii) the container stores pointers to objects [...]
iv) stores reference-counted pointers [...]
|
I would think that smart pointers are better suited for this.
This removes the logic from the data structure and also allows for
better re-use. E.g. the data structure may temporarily need to store
some objects in a std::vector (where the storage policy should also
apply, i.e. reference-counting or similar).
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Ivan Vecerina
Guest
|
| Posted: Sat Jan 17, 2004 11:28 pm Post subject: Re: STL container wrapper |
|
|
"Gareth Stockwell" <gareth (AT) ebi (DOT) ac.uk> wrote
| Quote: | I have been working on some templates which I think may be of use to
others, and I was wondering if anyone has any comments - including
whether you think this is duplicating any existing projects.
I have been working on a set of wrappers for STL container classes, of
the form
template<typename Data, template
class ContainerWrapper;
....
and get an object which exposes all the member functions of a
std::vector<int>, plus a set of functions which are exposed whatever
the type of the second parameter. For example, I want to be able to
write
[ok, providing a superset of vector's interface |
for all sequence containers]
So far, I would prefer to provide such support with non-member
functions, defined in a dedicated namespace:
namespace gnrlcont {
template<class T>
T& at(vector<T>& cont, size_t ind) { return cont[ind]; }
template<class T>
T& at(list<T>& cont, size_t ind) { /*some implementation*/ }
//etc...
};
As long as all you need is to extend the interface of a container,
I think that non-member functions approach is to be preferred:
- it is more maintainable and easier to extend
- it can be applied to any container instance (e.g. external
code calling you with a reference to a standard container).
| Quote: | Now, I go a step further, and add a third template parameter to my
ContainerWrapper template, which specifies the 'containment policy',
which may be e.g.
i) the container stores objects by value (as do vanilla STL
containers)
ii) the container stores pointers to dynamically-allocated objects,
and assumes 'ownership' of those objects (think of it as a
smart_container)
iii) the container stores pointers to objects, but does not assume
ownership
iv) stores reference-counted pointers
etc etc
Whatever the containment policy, I want my operator[],
iterator::operator* etc to return an X& reference, so again,
compile-time dispatch is used to determine how to implement such
functions.
|
The only thing here that seems to require a new type is
the containment policy. However, it seems difficult to support
a common interface for all the policies you describe here.
| Quote: | So, what do you think about this approach? To me, it seems a useful
way of making the implementation of a class like NaryTree independent
of the type of container used inside it. Since the function dispatch
is done at compile-time, those member functions which simply forward
to the STL container should be as fast as using the STL container
directly.
I think it makes sense. But I would prefer the more "lightweight" |
approach of the non-member functions to the creation of new container
types.
Just my two cents...
Kind regards,
Ivan
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- e-mail contact form
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Gareth Stockwell
Guest
|
| Posted: Sun Jan 18, 2004 12:00 am Post subject: Re: STL container wrapper |
|
|
[email]dan.r.mcleran (AT) seagate (DOT) com[/email] (Dan McLeran) wrote in message news:<19b0e504.0401161557.757e2ce8 (AT) posting (DOT) google.com>...
| Quote: | I assume that you would derive publicly from the container you've
chosen?
|
No - the wrapper contains the STL container by value. Inheriting from
STL containers is not a good idea because they aren't guaranteed to
have virtual destructors.
| Quote: | Seems like alot of work. A better way to get what you want
might be to typedef the container chosen and use it directly.
|
But this would not achieve my aim of providing a set of member
functions which are valid whatever the type of STL container used. If
I take your version of ContainerWrapper, and then write
template<class T,template
AllocatorType,template<class,class> class ContainerType>
class SomeClass {
public:
void blah(const T& x) { wrapper.push_back(x); }
private:
ContainerWrapper<T,AllocatorType,ContainerType> wrapper;
};
Then an attempt to instantiate SomeClass with ContainerType=std::set
fails. I want a generic 'insert_value' function in ContainerWrapper
which works no matter what the type of the STL container.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Gareth Stockwell
Guest
|
| Posted: Sun Jan 18, 2004 12:02 am Post subject: Re: STL container wrapper |
|
|
[email]Duff (AT) DIKU (DOT) DK[/email] (Allan Odgaard) wrote in message news:<689e217.0401162006.35ae5c4a (AT) posting (DOT) google.com>...
| Quote: | gareth (AT) ebi (DOT) ac.uk (Gareth Stockwell) wrote in message news:<d1b18d21.0401160256.77aad6a1 (AT) posting (DOT) google.com>...
E.g. for your "nth element" you can use:
iterator it = container.begin();
std::advance(it, n);
return *it;
And it will give you O(1) access for std::vector, and O(n) for
std::list.
|
Nice idea! This way the STL does the dispatch, rather than me
reinventing the wheel...
| Quote: | Though you may still need some sort of traits-system to allow
insertion into the sequence. Perhaps also use the traits system to
obtain the first/last element of the sequence, so that it could e.g.
be used with primitive arrays (although it might be a challenge ).
|
I could ... but actually I have already written a wrapper for
primitive arrays
template<typename T, size_t N> class FixedArray;
.... which provides iterators, so I can wrap that in ContainerWrapper
just as I would with a std::vector. Of course I need to provide a
is_fixed_size container trait, so that attempts to call insert(...) or
erase(...) on a FixedArray wrapper always fail.
| Quote: | I would think that smart pointers are better suited for this.
|
Maybe I have my terminology mixed up. My (non-intrusive) ref-counted
pointer template contains the raw pointer, and a pointer to a count
which is incremented whenever the RCP is copied. Is this what you
mean by a smart pointer aswell?
| Quote: |
This removes the logic from the data structure and also allows for
better re-use. E.g. the data structure may temporarily need to store
some objects in a std::vector (where the storage policy should also
apply, i.e. reference-counting or similar).
|
Sorry, I don't see what you mean by this - could you expand a bit?
Thanks for your comments,
Gareth
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Jonathan Turkanis
Guest
|
| Posted: Sun Jan 18, 2004 1:18 am Post subject: Re: STL container wrapper |
|
|
"Jonathan Turkanis" <technews (AT) kangaroologic (DOT) com> wrote
| Quote: | Gareth Stockwell" <gareth (AT) ebi (DOT) ac.uk> wrote in message
news:d1b18d21.0401160256.77aad6a1 (AT) posting (DOT) google.com...
I have been working on some templates which I think may be of use
to
others, and I was wondering if anyone has any comments -
including
whether you think this is duplicating any existing projects.
I have been working on a set of wrappers for STL container
classes,
of
the form
template<typename Data, template
class ContainerWrapper;
so that you can write e.g.
ContainerWrapper<int, std::vector> W;
Let me just comment on one aspect of your design.
The above code is not portable, because std::vector is specified to
have at least two template parameters -- the second is an allocator
type -- and may have more depending on the implementation. So
|
It looks like library implementers are not allowed to add extra
template parameters with default values:
http://std.dkuug.dk/jtc1/sc22/wg21/docs/lwg-closed.html#94
(Would some please let me know if this is the last word on the
matter?) At any rate, the main point still holds, you have to allow
for all the documented parameters, including allocators.
Jonathan
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Gareth Stockwell
Guest
|
| Posted: Sun Jan 18, 2004 1:24 am Post subject: Re: STL container wrapper |
|
|
"Jonathan Turkanis" <technews (AT) kangaroologic (DOT) com> wrote
| Quote: | The above code is not portable, because std::vector is specified to
have at least two template parameters -- the second is an allocator
type -- and may have more depending on the implementation.
|
Oops, overlooked that.
| Quote: | It is possible to let users supply a specialization of a container as
a type template parameter and internally extract all the needed
information (e.g., whether it is a vector and what its template
arguments are).
|
OK, so I can modify ContainerWrapper's signature to
template<class ContainerSpecialization, class ContainmentPolicy>
class ContainerWrapper;
and then do
ContainerWrapper<std::vector w;
Thanks,
Gareth
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Allan Odgaard
Guest
|
| Posted: Sun Jan 18, 2004 11:25 am Post subject: Re: STL container wrapper |
|
|
[email]gareth (AT) ebi (DOT) ac.uk[/email] (Gareth Stockwell) wrote in message news:<d1b18d21.0401170810.4dc8d57e (AT) posting (DOT) google.com>...
| Quote: | [...] also use the traits system to obtain the first/last element [...]
I could ... but actually I have already written a wrapper for
primitive arrays [...]
|
Okay, although I didn't explicitly say so, I wanted to get rid of the
wrappers entirely.
By using wrapper classes, you basically declare an interface that no
existing types will conform to, even though many already have the
desired functionality.
| Quote: | I would think that smart pointers are better suited for this.
Maybe I have my terminology mixed up. My (non-intrusive) ref-counted
pointer template contains the raw pointer, and a pointer to a count
which is incremented whenever the RCP is copied. Is this what you
mean by a smart pointer aswell?
|
I do not follow this, but a smart pointer is an entity which works
exactly as if it was the object being pointed to, but may do some
extra work e.g. when copied, assigned to, going out of scope
(destroyed) etc.
It would look something like this:
template <typename T>
struct ref_count
{
typedef ref_count<T> self;
T* obj;
void reset (T* newObj)
{
if(obj != NULL) release(obj);
if(obj = newObj) retain(newObj);
}
ref_count () : obj(NULL) { }
ref_count (T* o) : obj(NULL) { reset(o); }
ref_count (self const& rhs) : obj(NULL) { reset(rhs); }
self& operator= (self const& rhs) { reset(rhs); return *this; }
self& operator= (T* o) { reset(o); return *this; }
operator T* () const { return obj; }
T& operator* () { return *obj; }
T* operator-> () { return obj; }
...
};
So assuming you have a class like this:
struct foo
{
int retainCount;
foo () : retainCount(0) { }
...
};
And functions like:
void retain (foo* o) { ++(o->retainCount); }
void release (foo* o) { if(--(o->retainCount) == 0) delete o; }
You can declare e.g.:
std::vector< ref_count v;
And do:
fill_n(back_inserter(v), 10, new foo);
for(int i = 0; i < 10; i++)
v.push_back(new foo);
foreach(it, v.begin(), v.end())
printf("Retain count: %d", (*it)->retainCount);
v.erase(v.begin(), v.end());
Here std::vector should probably retain the elements and release them
again when they are removed (and they'll be deleted, when the retain
count hits zero), but std::vector is ignorant of the retain/release
system, and the user of the std::vector can just treat the values as
normal foo*, both when inserting values and reading the contained
ones.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
