 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Kaba
Guest
|
 Posted: Sat Jul 14, 2012 12:23 am Post subject: Layered data structures |
 |
|
Hi,
In the following is a generic problem concerning the design of data
structures in C++11. I have found 4 ways to solve the problem (listed
below), but I'm not completely happy with any of them. Can you find a
better solution?
### Problem
Consider data structures A and B, where B refers to parts of A.
Then the modification, or destruction, of A, invalidates the state
of B. How can we guarantee that A is not modified or destructed
while B is referring to A?
Concrete example. We create a grammar-object to represent a context-free
grammar, and then want to generate different kinds of parsers for the
grammar, such as LR, LALR, and NLALR parsers:
Grammar grammar;
// ...
LrZeroAutomaton lrZero(cGrammar);
LalrAutomaton lalr(cGrammar);
The automata will refer back to the productions of the grammar.
### Option 1: Documenting
In this option we simply state in documentation that A must not be
modified or destructed when it is referred to in B, and leave it to
the user to enforce this. This approach simply begs for bugs.
### Option 2: Versioning
In this option the A has a version number associated with it.
This version number is incremented every time a mutating operation
is called on A. Before accessing A, the B always checks for the
current version number of A against the version number of A when
creating B. If the version numbers do not match, an error is
generated. A problem with this approach is that not all mutating
operations may go through A. This is the case when A offers direct
access to some of its parts. Otherwise this can be seen as a rule
which the user is required to follow, with the library checking for
the rule at run-time. We would rather want to check the condition
at compile-time.
### Option 3: Transferred ownership
In this option A is moved into B. This guarantees that B can not
be modified or destructed, as long as A exists and refers to B.
The A can release the ownership of B to outside, given that it
also clears its state. The problem with this approach is that there
can be only one data structure B which can refer to A.
### Option 4: Read-only objects
In this option A is moved into a read-only-object. This is an object
which contains a shared_ptr to an A to which A is move-constructed.
Copying a read-only object copies the shared_ptr, not the A, thus
making it possible to have multiple references to A. The
read-only-object can only be used to access a const-reference of A. The
read-only-object can release its object to outside given that it only
has one single reference. The B object accepts a read-only-object of A,
instead of A. This approach fixes the problem with option 3. The problem
with this approach is that it is a bit awkward to use:
Grammar grammar;
// ...
ReadOnly<Grammar> cGrammar = std::move(grammar);
{
LrZeroAutomaton lrZero(cGrammar);
LalrAutomaton lalr(cGrammar);
// Do some stuff..
}
grammar = cGrammar.release();
--
http://kaba.hilvi.org
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
 |
Kaba
Guest
|
| Posted: Sat Jul 14, 2012 1:41 pm Post subject: Re: Layered data structures |
|
|
14.7.2012 3:23, Kaba wrote:
| Quote: | ### Option 3: Transferred ownership
In this option A is moved into B. This guarantees that B can not be
modified or destructed, as long as A exists and refers to B. The A
can release the ownership of B to outside, given that it also clears
its state. The problem with this approach is that there can be only
one data structure B which can refer to A.
|
Clearly there is an error here, since I had the roles of A and B
reversed. It should have been:
### Option 3: Transferred ownership
In this option A is moved into B. This guarantees that A can not be
modified or destructed, as long as B exists and refers to A. The B
can release the ownership of A to outside, given that it also clears
its state. The problem with this approach is that there can be only
one data structure B which can refer to A.
I will also add:
### Option 5: Locking
In this option B notifies A that it is being referred to. In each
mutating operation of A, or when destructing A, A checks whether it is
being referred to. If this is the case, an error is generated at
run-time.
--
http://kaba.hilvi.org
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Wil Evers
Guest
|
| Posted: Sat Jul 14, 2012 5:42 pm Post subject: Re: Layered data structures |
|
|
Kaba wrote:
| Quote: | ### Problem
Consider data structures A and B, where B refers to parts of A.
Then the modification, or destruction, of A, invalidates the state
of B. How can we guarantee that A is not modified or destructed
while B is referring to A?
Concrete example. We create a grammar-object to represent a
context-free grammar, and then want to generate different kinds of
parsers for the grammar, such as LR, LALR, and NLALR parsers:
Grammar grammar;
// ...
LrZeroAutomaton lrZero(cGrammar);
LalrAutomaton lalr(cGrammar);
The automata will refer back to the productions of the grammar.
|
[snip]
| Quote: | ### Option 4: Read-only objects
In this option A is moved into a read-only-object. This is an object
which contains a shared_ptr to an A to which A is move-constructed.
Copying a read-only object copies the shared_ptr, not the A, thus
making it possible to have multiple references to A. The
read-only-object can only be used to access a const-reference of
A. The read-only-object can release its object to outside given that
it only has one single reference. The B object accepts a
read-only-object of A, instead of A. This approach fixes the problem
with option 3. The problem with this approach is that it is a bit
awkward to use:
Grammar grammar;
// ...
ReadOnly<Grammar> cGrammar = std::move(grammar);
{
LrZeroAutomaton lrZero(cGrammar);
LalrAutomaton lalr(cGrammar);
// Do some stuff..
}
grammar = cGrammar.release();
|
That is actually a pretty nifty idea; I don't think I've seen this
before.
If I understand you correctly, the idea is to first build the grammar
object, which is then moved to an immutable instance of itself living
on the heap. Because it is now immutable, it can safely be
reference-counted without risking either unexpected modifications or
premature destruction; the key is to first 'constipate' the object
before it becomes shared. I think it was Andrew Koenig who first said
that for immutable objects, there is little difference between
pass-by-value and pass-by-reference.
One thing that puzzles me though is the last line of your example. Is
it meant to reopen the grammar for further modifications after all
parsers are done with it?
shared_ptr has a reset(), but it doesn't have a release(). The
transfer of ownership to a shared_ptr is irreversible, because it is
impossible to provide a general compile-time guarantee that the number
of references to the shared object is exactly one.
IMHO, this restriction prevents an important source of run-time errors.
Without it, it seems to me your solution fails to provide the object
lifetime guarantees you're asking for.
Regards,
- Wil
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Kaba
Guest
|
| Posted: Sat Jul 14, 2012 9:55 pm Post subject: Re: Layered data structures |
|
|
14.7.2012 20:42, Wil Evers wrote:
| Quote: | If I understand you correctly, the idea is to first build the
grammar object, which is then moved to an immutable instance of
itself living on the heap.
|
A an object of type Grammar is move-constructed to an object of type
Grammar. The latter object lives in the heap, managed by
shared_ptr<Grammar> (which is contained in ReadOnly<Grammar>).
| Quote: | Because it is now immutable, it can safely be reference-counted
without risking either unexpected modifications or premature
destruction; the key is to first 'constipate' the object before it
becomes shared.
|
The object in the heap can not be modified because ReadOnly only
provides a const reference to the contained Grammar. There can be no
existing mutable references to the Grammar object in the heap, because
it was just created.
| Quote: | I think it was Andrew Koenig who first said that for immutable
objects, there is little difference between pass-by-value and
pass-by-reference.
One thing that puzzles me though is the last line of your example.
Is it meant to reopen the grammar for further modifications after
all parsers are done with it?
|
Yes. When there are no objects referring to the grammar object, it can
again be modified at will.
| Quote: | shared_ptr has a reset(), but it doesn't have a release(). The
transfer of ownership to a shared_ptr is irreversible, because it is
impossible to provide a general compile-time guarantee that the
number of references to the shared object is exactly one.
|
A release() for the shared_ptr is not needed. The object living in the
heap is moved (std::move sense) back to the object living in the stack
('grammar'). This operation is only allowed if the reference count is
one.
| Quote: | IMHO, this restriction prevents an important source of run-time
errors. Without it, it seems to me your solution fails to provide
the object lifetime guarantees you're asking for.
|
Not sure what this is referring to.
--
http://kaba.hilvi.org
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Francis Glassborow
Guest
|
| Posted: Sun Jul 15, 2012 6:44 pm Post subject: Re: Layered data structures |
|
|
On 14/07/2012 22:55, Kaba wrote:
| Quote: | 14.7.2012 20:42, Wil Evers wrote:
If I understand you correctly, the idea is to first build the
grammar object, which is then moved to an immutable instance of
itself living on the heap.
A an object of type Grammar is move-constructed to an object of type
Grammar. The latter object lives in the heap, managed by
shared_ptr<Grammar> (which is contained in ReadOnly<Grammar>).
Because it is now immutable, it can safely be reference-counted
without risking either unexpected modifications or premature
destruction; the key is to first 'constipate' the object before it
becomes shared.
The object in the heap can not be modified because ReadOnly only
provides a const reference to the contained Grammar. There can be no
existing mutable references to the Grammar object in the heap,
because it was just created.
I think it was Andrew Koenig who first said that for immutable
objects, there is little difference between pass-by-value and
pass-by-reference.
One thing that puzzles me though is the last line of your example.
Is it meant to reopen the grammar for further modifications after
all parsers are done with it?
Yes. When there are no objects referring to the grammar object, it
can again be modified at will.
|
I am having a big problem trying to understand what the problem is
that you are trying to solve. Given that you want the object of type A
to be immutable as long as any object of type B is 'referring' to it
is it also a requirement that all objects of type B reference an
identical version of the object of type A?
If the answer to that is 'yes', why does it matter whether the objects
of type B are simultaneously using the same A object rather than
sequentially doing so? If sequentially the A object may well be
changed during the sequence if there is ever a moment when no B object
currently holds a reference to that A object.
So:
1) If all B objects MUST reference an identical A object then the A
object needs to be (deeply) immutable and the A object Must have a
reference counter to inhibit its destruction whilst any B object is
referring to it.
2) If B objects need not reference an identical A object then each B
object should hold its own copy of the A object and destroy that copy
when it has finished with it.
I guess 2) might raise issues of executable size but that is an
optimisation issue not a design issue.
Both 1) and 2) need care when working in an environment where
concurrency is active.
Francis
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Wil Evers
Guest
|
| Posted: Sun Jul 15, 2012 11:05 pm Post subject: Re: Layered data structures |
|
|
Francis Glassborow wrote:
| Quote: | 2) If B objects need not reference an identical A object then each B
object should hold its own copy of the A object and destroy that
copy when it has finished with it.
I guess 2) might raise issues of executable size but that is an
optimisation issue not a design issue.
|
Agreed, but how do we solve that optimization issue? Instead of
giving each B its own A instance, we may want some instances of B to
*share* an immutable instance of A. The question is how to express
that in B's class definition. Since the immutability requirement is
in B, A's definition should not have to change because of it.
It might seem having B's constructor take and store a
shared_ptr<const A> would do the job, but that is not good enough.
A shared_ptr<const A> does not guarantee the A pointed to is
immutable: a single A instance may be owned by several instances
of both shared_ptr<const A> and shared_ptr<A>.
I think the key is to make sure the A instance is closed for
modification before it is shared. The following class template is my
take at expressing that:
template <typename T>
class shared_immutable_ptr {
public :
template <typename U>
shared_immutable_ptr(std::unique_ptr<U> consumed)
: instance(std::move(consumed))
{ }
const T *operator->() const
{ return instance.operator->(); }
const T& operator*() const
{ return *instance; }
// etc...
private :
std::shared_ptr<const T> instance;
};
B can now state its requirements by having a constructor that takes
and stores a shared_immutable_ptr<A>. User code would look something
like this:
std::unique_ptr<A> build_a()
{
std::unique_ptr<A> result(new A);
result->modify();
return result;
}
void f()
{
shared_immutable_ptr<A> shared_a(build_a());
B b1(shared_a);
B b2(shared_a);
// ...
}
Regards,
- Wil
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Kaba
Guest
|
| Posted: Mon Jul 16, 2012 4:28 am Post subject: Re: Layered data structures |
|
|
15.7.2012 21:44, Francis Glassborow wrote:
| Quote: | I am having a big problem trying to understand what the problem is
that you are trying to solve. Given that you want the object of type
A to be immutable as long as any object of type B is 'referring' to
it is it also a requirement that all objects of type B reference an
identical version of the object of type A?
|
An object of type A may be referred to zero, one, or multiple times by
objects of type B.
In general, the objects of type B compute something out of objects of
type A. This computation recovers some structure that is contained
implicitly in A. The B makes this structure explicit, and does this by
referring to things in A in a new way. Referring to things most often
means having iterators to A, since iterators encapsulate pointing to a
part of A.
If an object of type A is changed, or even destructed, then its parts
(iterators) may be invalidated. This makes the state of a referring
object of type B invalid. This is the problem I would like to guard
against; it should not be possible for a user to place an object in an
invalid state.
| Quote: | If the answer to that is 'yes', why does it matter whether the
objects of type B are simultaneously using the same A object rather
than sequentially doing so?
|
I'm not sure I understand what you mean by simultaneous or sequential
here.
| Quote: | If sequentially the A object may well be changed during the sequence
if there is ever a moment when no B object currently holds a
reference to that A object.
So:
1) If all B objects MUST reference an identical A object then the A
object needs to be (deeply) immutable and the A object Must have a
reference counter to inhibit its destruction whilst any B object is
referring to it.
|
True, if 'all B objects' is understood as being those B objects which
refer to a given A object.
| Quote: | 2) If B objects need not reference an identical A object then each B
object should hold its own copy of the A object and destroy that
copy when it has finished with it.
|
This is problematic in two ways. First, as already stated, the
identity of the parts is often important (in my problem it
is). Second, duplicating identical objects wastes resources.
--
http://kaba.hilvi.org
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Seungbeom Kim
Guest
|
| Posted: Mon Jul 16, 2012 1:26 pm Post subject: Re: Layered data structures |
|
|
On 2012-07-15 16:05, Wil Evers wrote:
| Quote: |
I think the key is to make sure the A instance is closed for
modification before it is shared. The following class template is my
take at expressing that:
template <typename T
class shared_immutable_ptr {
public :
template <typename U
shared_immutable_ptr(std::unique_ptr<U> consumed)
: instance(std::move(consumed))
{ }
|
Since you cannot copy std::unique_ptr<U>, you need a reference parameter.
| Quote: |
const T *operator->() const
{ return instance.operator->(); }
const T& operator*() const
{ return *instance; }
// etc...
private :
std::shared_ptr<const T> instance;
};
|
How is shared_immutable_ptr<T> different from std::shared_ptr<const T>?
--
Seungbeom Kim
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
evansl
Guest
|
| Posted: Mon Jul 16, 2012 1:28 pm Post subject: Re: Layered data structures |
|
|
On Saturday, July 14, 2012 8:41:22 AM UTC-5, Kaba wrote:
[snip]
| Quote: | I will also add:
### Option 5: Locking
In this option B notifies A that it is being referred to. In each
mutating operation of A, or when destructing A, A checks whether it
is being referred to. If this is the case, an error is generated at
run-time.
|
This Option 5 sounds a bit like MVC:
http://net.tutsplus.com/tutorials/other/mvc-for-noobs/
Where the Model would be the A, the Views would be the B's;
however, I'm not sure what the Controller would be.
The "an error is generated at run-time" I suppose would
happen when the Model sent a message to the controller
saying "I've been changed" and the Controller would
send a message to all the Views (B's) saying "your A
has changed in some way".
Would that be another way of viewing the problem?
-regards,
Larry
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Kaba
Guest
|
| Posted: Mon Jul 16, 2012 6:27 pm Post subject: Re: Layered data structures |
|
|
16.7.2012 16:28, evansl wrote:
| Quote: | On Saturday, July 14, 2012 8:41:22 AM UTC-5, Kaba wrote:
[snip]
### Option 5: Locking
In this option B notifies A that it is being referred to. In each
mutating operation of A, or when destructing A, A checks whether it
is being referred to. If this is the case, an error is generated at
run-time.
This Option 5 sounds a bit like MVC:
|
-- 8x --
| Quote: | Would that be another way of viewing the problem?
|
Rather than the MVC, I would perhaps more specifically subscribe to
the observer pattern. A generalization of option 5 is then:
### Option 6: Observers
In this option B registers itself to A as an observer. As A faces
changes, it notifies of them to all observers B's. If B gets a
notification of its underlying A changing, it will raise a run-time
error.
However, this generality is not needed; any change to A during being
referred to by a B should raise an error. Therefore that logic can be
placed into A, as in option 5.
--
http://kaba.hilvi.org
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Pete Becker
Guest
|
| Posted: Mon Jul 16, 2012 6:29 pm Post subject: Re: Layered data structures |
|
|
On 2012-07-16 13:28:34 +0000, evansl said:
| Quote: | On Saturday, July 14, 2012 8:41:22 AM UTC-5, Kaba wrote:
[snip]
I will also add:
### Option 5: Locking
In this option B notifies A that it is being referred to. In each
mutating operation of A, or when destructing A, A checks whether it
is being referred to. If this is the case, an error is generated at
run-time.
This Option 5 sounds a bit like MVC:
http://net.tutsplus.com/tutorials/other/mvc-for-noobs/
Where the Model would be the A, the Views would be the B's; however,
I'm not sure what the Controller would be. The "an error is
generated at run-time" I suppose would happen when the Model sent a
message to the controller saying "I've been changed" and the
Controller would send a message to all the Views (B's) saying "your
A has changed in some way".
Would that be another way of viewing the problem?
|
Seems like a stretch. Under MVC, changing the data is not an error.
--
Pete
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Kaba
Guest
|
| Posted: Mon Jul 16, 2012 6:44 pm Post subject: Re: Layered data structures |
|
|
16.7.2012 2:05, Wil Evers kirjoitti:
| Quote: | I think the key is to make sure the A instance is closed for
modification before it is shared.
|
Here's a complete example program demonstrating both the problem and
its solution by Option 4 (read-only objects).
#include <cassert>
#include <iostream>
#include <memory>
#include <set>
typedef std::set<int> NumberSet;
typedef NumberSet::const_iterator Number_ConstIterator;
template <typename Type>
class ReadOnly
{
public:
ReadOnly(Type&& data)
: data_(new Type(std::move(data)))
{
}
const Type& operator()() const
{
return *data_;
}
Type release()
{
assert(data_.use_count() == 1);
return std::move(*data_);
}
private:
std::shared_ptr<Type> data_;
};
class NumberAnalysis
{
public:
NumberAnalysis(
ReadOnly<NumberSet> numberSet)
: numberSet_(numberSet)
, minEven_()
{
analyze();
}
Number_ConstIterator minEven() const
{
return minEven_;
}
private:
void analyze()
{
for (auto iter = numberSet_().cbegin();
iter != numberSet_().cend();
++iter)
{
if ((*iter & 1) == 0)
{
minEven_ = iter;
break;
}
};
}
ReadOnly<NumberSet> numberSet_;
Number_ConstIterator minEven_;
};
int main()
{
int numbers[] = {1, 5, 4, 2};
NumberSet numberSet;
numberSet.insert(std::begin(numbers), std::end(numbers));
// Close for modification.
ReadOnly<NumberSet> cNumberSet =
std::move(numberSet);
{
// Analyze the read-only number-set.
NumberAnalysis analysis(cNumberSet);
if (analysis.minEven() != cNumberSet().cend())
{
std::cout << "The minimum even number in the set is "
<< *analysis.minEven() << "." << std::endl;
}
else
{
std::cout << "There are no even numbers in the set."
<< std::endl;
}
}
// Recover the number-set for modification.
numberSet = std::move(cNumberSet.release());
numberSet.insert(10);
return 0;
}
This demonstrates Option 4. Somehow I dislike this solution. Also,
when writing this program I first wrote "!= numberSet.cend()", which
caused the program to crash. It seems easy to get confused between the
read-only object 'cNumberSet' and the original object 'numberSet'.
--
http://kaba.hilvi.org
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Wil Evers
Guest
|
| Posted: Mon Jul 16, 2012 10:53 pm Post subject: Re: Layered data structures |
|
|
Seungbeom Kim wrote:
| Quote: | On 2012-07-15 16:05, Wil Evers wrote:
I think the key is to make sure the A instance is closed for
modification before it is shared. The following class template is
my take at expressing that:
template <typename T
class shared_immutable_ptr {
public :
template <typename U
shared_immutable_ptr(std::unique_ptr<U> consumed)
: instance(std::move(consumed))
{ }
Since you cannot copy std::unique_ptr<U>, you need a reference
parameter.
|
Well, I'll admit I'm still getting used to move semantics. However,
my understanding is that, because std::unique_ptr<U> has a move
constructor while its copy constructor is deleted, the constructor
argument above will bind to rvalues of std::unique_ptr<any type>,
while not binding to lvalues. g++-4.7.1 appears to agree with me.
The intent is that shared_immutable_ptr<T> acts as a sink, taking
ownership away from the unique_ptr passed to its constructor. Perhaps
I should have written
template <typename U>
shared_immutable_ptr(std::unique_ptr<U>&& consumed)
: instance(std::move(consumed))
{ }
In practice, I think both forms are mostly equivalent here.
| Quote: | const T *operator->() const
{ return instance.operator->(); }
const T& operator*() const
{ return *instance; }
// etc...
private :
std::shared_ptr<const T> instance;
};
How is shared_immutable_ptr<T> different from
std::shared_ptr<const T>?
|
The difference is that there is a conversion from shared_ptr<T> to
shared_ptr<const T>, while there is no conversion from shared_ptr<T>
to shared_immutable_ptr<T>. The effect is that the T instance passed
to it is marked as const before it becomes shared.
In other words, when compared to shared_ptr<const T>,
shared_immutable_ptr<T> provides the additional guarantee that there
are no other smart pointers around that could act as a backdoor for
modifying the object pointed to.
Regards,
- Wil
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Kaba
Guest
|
| Posted: Tue Jul 17, 2012 1:06 am Post subject: Re: Layered data structures |
|
|
14.7.2012 3:23, Kaba wrote:
| Quote: | Consider data structures A and B, where B refers to parts of A.
Then the modification, or destruction, of A, invalidates the state
of B. How can we guarantee that A is not modified or destructed
while B is referring to A?
|
First, let us rephrase the problem slightly better.
Consider data structures A and B, where B refers to parts of A. Then the
modification, or destruction, of A, invalidates the state of B. How
can we guarantee that the state of B is always valid?
### Option 7: Read pointers
In this option A is derived from ReadProtected<A>, which injects a
reference count into A. Whoever wants to place A into an immutable
state, obtains a ReadPtr<A> from the ReadProtected<A> object. To this
extent, ReadProtected<A> is implicitly convertible to a ReadPtr<A>, and
this is the only way to obtain an original ReadPtr<A>. Other
ReadPtr<A>'s are copies of each other. The reference count in
ReadProtected<A> is the number of ReadPtr<A>'s that reference the
derived class A. ReadProtected<A> contains a member function
readProtect(), which is used to check that there are no active ReadPtr<A>'s.
#include <cassert>
#include <utility>
#include <memory>
typedef int integer;
template <typename Type>
class ReadProtected;
template <typename Type>
class ReadPtr
{
public:
const Type& operator*() const
{
return data_;
}
const Type* operator->() const
{
return data_;
}
ReadPtr()
: data_(0)
, count_(0)
{
}
ReadPtr(ReadPtr<Type>&& that)
: data_(0)
, count_(0)
{
swap(that);
}
ReadPtr(const ReadPtr<Type>& that)
: data_(that.data_)
, count_(that.count_)
{
increaseCount();
}
ReadPtr& operator=(ReadPtr that)
{
swap(that);
return *this;
}
~ReadPtr()
{
clear();
}
void swap(ReadPtr& that)
{
using std::swap;
swap(data_, that.data_);
swap(count_, that.count_);
}
void clear()
{
decreaseCount();
data_ = 0;
count_ = 0;
}
integer count() const
{
assert(count_);
return *count_;
}
private:
friend class ReadProtected<Type>;
explicit ReadPtr(const Type* data, integer* count)
: data_(data)
, count_(count)
{
increaseCount();
}
void increaseCount()
{
if (count_)
{
++(*count_);
}
}
void decreaseCount()
{
if (count_)
{
--(*count_);
}
}
const Type* data_;
integer* count_;
};
template <typename Type>
class ReadProtected
{
public:
ReadProtected()
: readCount_(new integer(0))
{
}
~ReadProtected()
{
readProtect();
}
void swap(ReadProtected& that)
{
readCount_.swap(that.readCount_);
}
operator ReadPtr<Type>() const
{
return ReadPtr<Type>((const Type*)this, readCount_.get());
}
protected:
void readProtect()
{
bool ObjectIsMutable =
(*readCount_ == 0);
assert(ObjectIsMutable);
}
std::unique_ptr<integer> readCount_;
};
class Grammar
: public ReadProtected<Grammar>
{
public:
Grammar()
{
}
void mutate()
{
readProtect();
}
integer query() const
{
return 0;
}
};
class GrammarAnalysis
{
public:
explicit GrammarAnalysis(
const ReadPtr<Grammar>& grammar)
: grammar_(grammar)
{
grammar_->query();
}
private:
ReadPtr<Grammar> grammar_;
};
int main()
{
Grammar grammar;
// Ok
grammar.mutate();
{
GrammarAnalysis analysis(grammar);
// Ok
grammar.query();
// Error
grammar.mutate();
}
// Ok
grammar.mutate();
return 0;
}
This is starting to look like an acceptable solution to me. The only
downside is that one must derive from ReadProtected. This ok, but then
for example when swapping Grammars, one needs to remember to swap the
ReadProtected too. Note that it is necessary that A be reference-counted
and that its mutable functions be marked explicitly, so these are not
extraneous.
--
http://kaba.hilvi.org
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Seungbeom Kim
Guest
|
| Posted: Tue Jul 17, 2012 10:14 pm Post subject: Re: Layered data structures |
|
|
On 2012-07-16 15:53, Wil Evers wrote:
| Quote: | Seungbeom Kim wrote:
On 2012-07-15 16:05, Wil Evers wrote:
template <typename U
shared_immutable_ptr(std::unique_ptr<U> consumed)
: instance(std::move(consumed))
{ }
Since you cannot copy std::unique_ptr<U>, you need a reference
parameter.
Well, I'll admit I'm still getting used to move semantics. However,
my understanding is that, because std::unique_ptr<U> has a move
constructor while its copy constructor is deleted, the constructor
argument above will bind to rvalues of std::unique_ptr<any type>,
while not binding to lvalues. g++-4.7.1 appears to agree with me.
The intent is that shared_immutable_ptr<T> acts as a sink, taking
ownership away from the unique_ptr passed to its constructor.
Perhaps I should have written
template <typename U
shared_immutable_ptr(std::unique_ptr<U>&& consumed)
: instance(std::move(consumed))
{ }
In practice, I think both forms are mostly equivalent here.
|
I think you're right that the constructor argument will bind to
rvalues of type std::unique_ptr, and your example will work. I was
thinking of more general cases where lvalues can be given to the
constructor.
| Quote: | How is shared_immutable_ptr<T> different from
std::shared_ptr<const T>?
The difference is that there is a conversion from shared_ptr<T> to
shared_ptr<const T>, while there is no conversion from shared_ptr<T
to shared_immutable_ptr<T>. The effect is that the T instance
passed to it is marked as const before it becomes shared.
In other words, when compared to shared_ptr<const T>,
shared_immutable_ptr<T> provides the additional guarantee that there
are no other smart pointers around that could act as a backdoor for
modifying the object pointed to.
|
Sorry, I still don't understand. If you use std::shared_ptr<const T>
instead of shared_immutable_ptr<T> in your example:
std::unique_ptr<A> build_a()
{
std::unique_ptr<A> result(new A);
result->modify();
return result;
}
void f()
{
std::shared_ptr<const A> shared_a(build_a());
B b1(shared_a);
B b2(shared_a);
// ...
}
there should still be no backdoor for modification. If you're
considering what could happen to the result of build_a() before it
binds to shared_a, the situation is no different for
shared_immutable_ptr. Once an object of std::shared_ptr<const A>
becomes the sole owner, there is no conversion from it to
std::shared_ptr<A>, so there can be no further modification. Is this
correct?
--
Seungbeom Kim
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Powered by phpBB © 2001, 2006 phpBB Group
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
