Pointers in const containers
Adam Badura
class tree_node {
public:
typedef std::vector< tree_node* > children_vector;
const children_vector& get_children() const { return children_; }
children_vector& get_children() { return children_; }
const tree_node* get_parent() const { return parent_; }
tree_node* get_parent() { return parent_; }
private:
children_vector children_;
tree_node* parent_;
};
(Code was not compiled and important parts - like constructors and
destructor - are not present since they are not important for the
problem inhere.)
There is an obvious problem of constness. Lets say we have a variable
"p_node" of type "const tree_node*". The pointer is to a const object
so we would except the object not being modified using this pointer
(compiler ought to check that). But as it is not possible to write:
p_node->get_children().clear()
since get_children returns const reference it is possible to do
following:
p_node->get_children().front()->do_something_non_const();
p_node->get_children().back() = new tree_node();
p_node->get_children().front()->get_parent()-
>do_something_non_const();
(assuming the vector is not empty). Note that the last instruction
calls "do_something_non_const" on object pointed by "p_node"...
This should not be possible for a const tree_node (or at least in my
opinion) and is possible only because of use of container (for
simplicity) and pointers (since tree_node cannot be used to
instantiate std::vector before it is a complete type and it is not a
complete type while defining
children_type).
How to solve this problem?
I already came to two solutions:
1) Do not return the container, but add functions like
"children_begin" and "children_end" and define iterators so that the
will be const or non-const as appropriate. This requires somewhat more
coding but on the other hand makes tree_node's interface independent
on the actual implementation of children_. But this solution does not
go well with code which requires container and not pair of iterators,
like inserter iterators, BOOST_FOREACH, legacy code and so on...
2) Make tree_node behave like it was a container of "tree_node*". This
implies a lot of writing, since we would have to cover the all
requirements placed on a container. But using the same trick with
defining const and non-const iterators we can solve problem of
modifying const object. And the object of "tree_node" behaves like a
vector so we can use insert iterators, BOOST_FOREACH and all those
things mentioned in 1. But this solution is not good when tree_node
has children of two types, for example if we want to distinguish
children being leafs and children not being leafs. Since then
tree_node is a container of both other tree_nodes and appropriate
children.
So is there another solution?
Adam Badura
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Pavel Minaev
The first obvious question is, why do you have a container of
pointers, and not plain objects? Since it's a tree, you shouldn't need
to have several parent nodes point to the same child node.
If you really need the pointers, though, then you might want to look
at Boost pointer container library, and in particular,
boost::ptr_vector. It implements full ownership semantics for the
pointer elements it contains, and therefore, propagates constness in
all member-access operations.
Martin T
> Lets consider following (typical as I think) code:
>
> class tree_node {
> public:
> typedef std::vector< tree_node* > children_vector;
>
> const children_vector& get_children() const { return children_; }
> children_vector& get_children() { return children_; }
>
> const tree_node* get_parent() const { return parent_; }
> tree_node* get_parent() { return parent_; }
>
> private:
> children_vector children_;
> tree_node* parent_;
>
> };
>
> (Code was not compiled and important parts - like constructors and
> destructor - are not present since they are not important for the
> problem inhere.)
>
> There is an obvious problem of constness. Lets say we have a variable
> "p_node" of type "const tree_node*". The pointer is to a const object
> so we would except the object not being modified using this pointer
I used to think that too, until I realized that these semantics simply
do not work this way in C++.
Given a type T there are two pointer-types. A pointer_to_T (T*) and a
pointer_to_const_T (T const* or const T* which are the same).
These two can be const-qualified and will then be a const_pointer_to_t
or a const_pointer_to_const_T.
There simply no way to make something that references a T* to reference
a T const* through const qualifying that something.
Consider:
struct B {};
struct A {
B* b_;
};
You will _always_ be able to modify the B pointed to by b_ through any
conceivable reference/pointer to A.
> ...
> How to solve this problem?
>
> I already came to two solutions:
> 1) Do not return the container, but add functions like
> "children_begin" and "children_end" and define iterators so that the
> will be const or non-const as appropriate. This requires somewhat more
> coding but on the other hand makes tree_node's interface independent
> on the actual implementation of children_. But this solution does not
> go well with code which requires container and not pair of iterators,
> like inserter iterators, BOOST_FOREACH, legacy code and so on...
> 2) Make tree_node behave like it was a container of "tree_node*". This
> implies a lot of writing, since we would have to cover the all
> requirements placed on a container. But using the same trick with
> defining const and non-const iterators we can solve problem of
> modifying const object. And the object of "tree_node" behaves like a
> vector so we can use insert iterators, BOOST_FOREACH and all those
> things mentioned in 1. But this solution is not good when tree_node
> has children of two types, for example if we want to distinguish
> children being leafs and children not being leafs. Since then
> tree_node is a container of both other tree_nodes and appropriate
> children.
>
> So is there another solution?
>
One way is to make tree_node a template that defines the type of the
children (so either tree_node* or tree_node const*). And then use the
version with tree_node const* where you need const-semantics. This
solution is also a bit complicated, but I think it has different
drawbacks than the other two so it may be an alternative.
br,
Martin
Mathias Gaunard
> The first obvious question is, why do you have a container of
> pointers, and not plain objects?
Pointers can do more than objects.
However containers of pointers are almost always a bad thing to do,
since they lead to exception safety issues.
Using unique_ptr is a very simple and well working solution. (requires
C++0x)
For C++03, well, you'll never get that kind of efficiency without
using reference counting under the hood, which is still way less
efficient than unique_ptr.
Pointer containers are therefore the recommended solution if you care
about efficiency in C++03.
Greg Herlihy
> Lets consider following (typical as I think) code:
>
> class tree_node {
> public:
> typedef std::vector< tree_node* > children_vector;
>
> const children_vector& get_children() const { return children_; }
> children_vector& get_children() { return children_; }
>
> const tree_node* get_parent() const { return parent_; }
> tree_node* get_parent() { return parent_; }
>
> private:
> children_vector children_;
> tree_node* parent_;
> };
>
> "p_node" of type "const tree_node*". The pointer is to a const object
> so we would except the object not being modified using this pointer
> (compiler ought to check that). But as it is not possible to write:
>
> p_node->get_children().clear()
>
> since get_children returns const reference it is possible to do
> following:
> p_node->get_children().front()->do_something_non_const();
> p_node->get_children().back() = new tree_node();
> p_node->get_children().front()->get_parent()->do_something_non_const();
The const-ness of a container is orthogonal to the const-ness of the
objects referenced by its contents. In this case, the fact that
tree_node::get_children() returns a const std::vector of tree_node
pointers does not mean that those pointers point to const tree_node
objects. On the contrary, if the pointers in the vector point to const
tree_node objects, then tree_node::get_children() has to return a:
const std::vector<const tree_node*>&
instead of the vector of pointers to non-const tree_node object that
it currently returns.
> This should not be possible for a const tree_node.
The program in this example does not modify the tree_node object
through the "pnode" pointer - but through (non-const) tree_node
pointer to the same object. In other words, although the program may
not use pnode to modify a particular tree_node object - there is
nothing that prohibits the program from modifying that same object
through a pointer to a non-const tree node object - should one happen
to exist..
Therefore, in order to prevent a tree_node object from being modified,
the program has to ensure that the tree_node object is not referenced
by a pointer to a non-const tree object - including those tree_node
pointers found in the std::vector that tree_node::get_children()
returns to its caller.
> How to solve this problem?
>
> I already came to two solutions:
> 1) Do not return the container, but add functions like
> "children_begin" and "children_end" and define iterators so that the
> will be const or non-const as appropriate. ...
> 2) Make tree_node behave like it was a container of "tree_node*"...
3) Have tree_node::get_children() return a reference to a const
std::vector<const tree_node*> (as described above) when called with a
const tree_node object.
Greg
Adam Badura
This is another solution to the problem. However it does not go
well with conversions. Since pointer to tree_node<tree_node*> cannot
be converted to tree_node<const tree_node*> which makes the solution
(if this is what you ment) useful in a very narrow range fo problems.
Adam Badura
Adam Badura
> std::vector<const tree_node*> (as described above) when called with a
> const tree_node object.
Yes. This is another solution to the problem. However it requires
creation of a copy of children vector since the original value is of
type (const) std::vector<tree_node*> (const depends on constness of
member function) and there is no conversion from
std::vector<tree_node*> to std::vector<const tree_node*> (pity since
in this particular case it would be handy and seems just OK).
Adam Badura
Adam Badura
> pointers, and not plain objects? Since it's a tree, you shouldn't need
> to have several parent nodes point to the same child node.
Pointers are required due to language constraints. It is not
possible to write:
struct tree_node {
/* ... */
private:
std::vector<tree_node> children_;
};
(although some compilers allow it) because at the place of declaration
of children_ tree_node is incomplete type and incomplete types cannot
be used with STL containers.
And obviously parent has to be stored as a pointer (reference will
not do because of root node and possibility of moving nodes).
> If you really need the pointers, though, then you might want to look
> at Boost pointer container library, and in particular,
> boost::ptr_vector. It implements full ownership semantics for the
> pointer elements it contains, and therefore, propagates constness in
> all member-access operations.
Looks promising. Thanks!
Adam Badura
Mathias Gaunard
> > If you really need the pointers, though, then you might want to look
> > at Boost pointer container library, and in particular,
> > boost::ptr_vector. It implements full ownership semantics for the
> > pointer elements it contains, and therefore, propagates constness in
> > all member-access operations.
>
> Looks promising. Thanks!
For a tree, a variant can also probably a good solution.
See boost variant and its tree examples.