operator= in allocators

Discussion in 'C++' started by Mark A. Gibbs, Apr 4, 2004.

  1. I'm having yet another headache with making a standard allocator. What
    behaviour should be expected from the assigment operator? When would it
    be called? Why is it there at all, when you can't change allocators in
    containers?

    To give a little more depth, I have a class like this:

    class HeapAllocator
    {
    // All requirements of the allocator interface are met along with:
    // - A constructor to pass in a heap reference
    // - A GetHeap function that returns a reference to the internal heap
    // (which can never be 0)

    private:
    mutable Heap* heap_;
    };

    Now, I would have liked to define heap_ as a Heap&, but I can't because of:

    template <class U>
    HeapAllocator& operator=(HeapAllocator<U> const& ha) /*throw()*/
    {
    heap_ = ha.heap_;
    }

    Which is an annoyance but otherwise not that big of an issue. The
    problem for me is one of elegance and robustness. Under what
    circumstances could I expect operator= to be called (aside from in
    operator= in a container)? Memory allocated in one heap cannot be
    deallocated in another (operator== tests for heap equality). Am I
    guaranteed that all allocations would be deallocated by the correct
    allocator (or to put it more specifically allocations by an allocator A
    will only be deallocated by A or by another allocator B for which B ==
    A) - ie, is this a requirement?

    I'm a little disturbed by the statement in 20.1.5.4:

    "Implementations of containers described in this International Standard
    are permitted to assume that their Allocator template parameter meets
    the following two additional requirements....

    - All instances of a given allocator type are required to be
    interchangeable and always compare equal to each other."

    Does this mean that I am essentially wasting my time?

    mark
     
    Mark A. Gibbs, Apr 4, 2004
    #1
    1. Advertising

  2. "Mark A. Gibbs" <_x> wrote
    > I'm having yet another headache with making a
    > standard allocator. What behaviour should be
    > expected from the assigment operator? When
    > would it be called? Why is it there at all, when
    > you can't change allocators in containers?
    >
    > [rest snipped]


    What does copying an allocator mean to you? If your answer is, "it's
    meaningless" -- as I hope it is -- then you shouldn't provide coping
    operations. Just declare the copy constructor and operator= as private and
    don't implement them. Not all objects should have value semantics, and
    allocators are a prime example.

    Claudio Puviani
     
    Claudio Puviani, Apr 4, 2004
    #2
    1. Advertising

  3. Claudio Puviani wrote:

    > What does copying an allocator mean to you? If your answer is, "it's
    > meaningless" -- as I hope it is -- then you shouldn't provide coping
    > operations. Just declare the copy constructor and operator= as private and
    > don't implement them. Not all objects should have value semantics, and
    > allocators are a prime example.


    I agree, that's actually the basis for my question. Aren't operator= and
    the copy constructor required for the allocator interface?

    mark
     
    Mark A. Gibbs, Apr 4, 2004
    #3
  4. "Mark A. Gibbs" <_x> wrote
    > Claudio Puviani wrote:
    >
    > > What does copying an allocator mean to you? If your answer is, "it's
    > > meaningless" -- as I hope it is -- then you shouldn't provide coping
    > > operations. Just declare the copy constructor and operator= as private

    and
    > > don't implement them. Not all objects should have value semantics, and
    > > allocators are a prime example.

    >
    > I agree, that's actually the basis for my question. Aren't operator= and
    > the copy constructor required for the allocator interface?


    20.1.5 ("Allocator requirements") doesn't state copyability as a
    requirement. Comparison, yes, but definitely not copying.

    Claudio Puviani
     
    Claudio Puviani, Apr 4, 2004
    #4
  5. Claudio Puviani wrote:

    > 20.1.5 ("Allocator requirements") doesn't state copyability as a
    > requirement. Comparison, yes, but definitely not copying.


    But that makes no logical sense if containers own their allocator.

    vector<int, SomeAllocator> foo()
    {
    SomeAllocator a;
    vector<int, SomeAllocator> v(a);
    return v;
    }

    void bar()
    {
    vector<int, SomeAllocator> v = foo();
    // Undefined behaviour
    }

    And how can the containers not own their own allocator?

    mark
     
    Mark A. Gibbs, Apr 4, 2004
    #5
  6. In article
    <DeIbc.17976$>,
    "Mark A. Gibbs" <_x> wrote:

    > I'm having yet another headache with making a standard allocator. What
    > behaviour should be expected from the assigment operator? When would it
    > be called? Why is it there at all, when you can't change allocators in
    > containers?
    >
    > To give a little more depth, I have a class like this:
    >
    > class HeapAllocator
    > {
    > // All requirements of the allocator interface are met along with:
    > // - A constructor to pass in a heap reference
    > // - A GetHeap function that returns a reference to the internal heap
    > // (which can never be 0)
    >
    > private:
    > mutable Heap* heap_;
    > };
    >
    > Now, I would have liked to define heap_ as a Heap&, but I can't because of:
    >
    > template <class U>
    > HeapAllocator& operator=(HeapAllocator<U> const& ha) /*throw()*/
    > {
    > heap_ = ha.heap_;
    > }
    >
    > Which is an annoyance but otherwise not that big of an issue. The
    > problem for me is one of elegance and robustness. Under what
    > circumstances could I expect operator= to be called (aside from in
    > operator= in a container)? Memory allocated in one heap cannot be
    > deallocated in another (operator== tests for heap equality). Am I
    > guaranteed that all allocations would be deallocated by the correct
    > allocator (or to put it more specifically allocations by an allocator A
    > will only be deallocated by A or by another allocator B for which B ==
    > A) - ie, is this a requirement?
    >
    > I'm a little disturbed by the statement in 20.1.5.4:
    >
    > "Implementations of containers described in this International Standard
    > are permitted to assume that their Allocator template parameter meets
    > the following two additional requirements....
    >
    > - All instances of a given allocator type are required to be
    > interchangeable and always compare equal to each other."
    >
    > Does this mean that I am essentially wasting my time?


    Not at all. But it does mean you have stumbled into implementation
    defined territory. Your experience could contribute to the next C++
    standard.

    Allocators are not required to be assignable, so you could just omit the
    operator=. However, allocators are required to be equal. But however
    again, implementors are encouraged to deal with non-equal allocators
    (and several do).

    Non-equal allocators mainly come into play during resource transferring
    operations such as swap or splice, but not during container assignment.
    There is an open lwg issue concerning swap here:

    http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-active.html#431

    Here is a response I have written to that issue:

    http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/papers/2004/n1599.html

    Neither the issue, nor the response have yet been discussed in
    committee. I point them out just fyi, and also so that you have the
    opportunity to join in the discussion.

    -Howard
     
    Howard Hinnant, Apr 4, 2004
    #6
  7. Howard Hinnant wrote:
    > Allocators are not required to be assignable, so you could just omit the
    > operator=. However, allocators are required to be equal. But however
    > again, implementors are encouraged to deal with non-equal allocators
    > (and several do).


    DOH! You're right, I just re-read that section. What I thought was a
    requirement for a1 = a2 is actually a requirement for a1 == a2.
    Assignment is not necessary. So that problem is all but solved.

    But when you say that allocators are required to be equal, do you mean
    that a1 == a2 MUST return true? Or that a1 and a2 should be
    interchangeable for all purposes even if a1 != a2?

    I have already implemented the latter anyway throughout the course of my
    experimentation. The deallocate function in my HeapAllocator class is
    roughly:

    void HeapAllocator::deallocate(pointer p, size_type n)
    {
    Heap* the_heap = heap_;
    if (!the_heap->Owns(p))
    the_heap = Heap::GetOwner(p);
    the_heap->Deallocate(p);
    }

    In other words, as currently written, any instance of HeapAllocator can
    free memory allocated by any other instance of HeapAllocator, even if
    they are not "equal" (ie, the heap_ member is different). This is a
    simplification, along with all the assertions, a trace statement records
    cases when heap_->Owns(p) is false.

    But to me, this is a nasty hack that I would like to avoid if possible.

    > Non-equal allocators mainly come into play during resource transferring
    > operations such as swap or splice, but not during container assignment.
    > There is an open lwg issue concerning swap here:
    >
    > http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-active.html#431
    >
    > Here is a response I have written to that issue:
    >
    > http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/papers/2004/n1599.html
    >
    > Neither the issue, nor the response have yet been discussed in
    > committee. I point them out just fyi, and also so that you have the
    > opportunity to join in the discussion.


    No, thank you. I appreciate the offer, but I'm just a hobbyist
    programmer who has never taken a "real" programming course - let alone
    an entire cs or sotware engineering degree.

    But if I may point out some things that came to mind reading your
    comments....

    Your second concern in option 2 could be allayed via the use of a
    smarter iterator class for the container. The enhanced iterator class
    would not be necessary for containers using std::allocator - or for any
    containers using an always-equal allocator - so existing code and
    binaries remain unchanged, and continue to use naked pointers if that's
    what they do. I suppose a *really* smart compiler and library could
    theoretically even optimize the smart iterators down to dumb iterators
    at compile time if it detects that operator== is always true, but that's
    probably not practical. I guess you could create a static boolean
    constant in the allocator interface that is true if the allocators are
    always equal, but that's a whole new can of worms.

    But your first concern in option 2 is also a little odd to me, unless
    I'm just misunderstanding what you mean by slow swap. swap() is only
    guaranteed nothrow if both the copy constructor is nothrow and either no
    allocation is required or the allocation is nothrow. Unless your
    definition of slow swap is not the same as mine, I don't see how an
    element-by-element swap violates that principle just because now a1 may
    or may not be == a2.

    The net result of all this is that I don't see the problematic semantic
    changes you allude to, though I do see performance concerns.

    That's all I have. Though I really appreciate the knock on the skull
    regarding the non-necessity of an assignment operator.

    mark
     
    Mark A. Gibbs, Apr 4, 2004
    #7
  8. Mark A. Gibbs

    Rolf Magnus Guest

    Mark A. Gibbs wrote:

    > Claudio Puviani wrote:
    >
    >> 20.1.5 ("Allocator requirements") doesn't state copyability as a
    >> requirement. Comparison, yes, but definitely not copying.


    It does state that a conversion constructor must be there to convert an
    allocator for one type into an allocator for another type. But "one"
    and "another" can also be the same type, making that constructor also a
    copy constructor.

    > But that makes no logical sense if containers own their allocator.
    >
    > vector<int, SomeAllocator> foo()
    > {
    > SomeAllocator a;
    > vector<int, SomeAllocator> v(a);


    Even the above line would need the allocator to be copied.

    > return v;
    > }
    >
    > void bar()
    > {
    > vector<int, SomeAllocator> v = foo();
    > // Undefined behaviour
    > }
    >
    > And how can the containers not own their own allocator?
     
    Rolf Magnus, Apr 4, 2004
    #8
  9. Mark A. Gibbs

    Rolf Magnus Guest

    Mark A. Gibbs wrote:

    > But when you say that allocators are required to be equal, do you mean
    > that a1 == a2 MUST return true? Or that a1 and a2 should be
    > interchangeable for all purposes even if a1 != a2?


    20.1p4 says it quite explicitly:

    Implementations of containers described in this International Standard
    are permitted to assume that their Allocator template parameter meets
    the following two additional requirements beyond those in Table 32.

    - All instances of a given allocator type are required to be
    interchangable and always compare equal to each other.

    ....
     
    Rolf Magnus, Apr 4, 2004
    #9
  10. Rolf Magnus wrote:

    > Mark A. Gibbs wrote:
    >
    >
    >>But when you say that allocators are required to be equal, do you mean
    >>that a1 == a2 MUST return true? Or that a1 and a2 should be
    >>interchangeable for all purposes even if a1 != a2?

    >
    >
    > 20.1p4 says it quite explicitly:
    >
    > Implementations of containers described in this International Standard
    > are permitted to assume that their Allocator template parameter meets
    > the following two additional requirements beyond those in Table 32.
    >
    > - All instances of a given allocator type are required to be
    > interchangable and always compare equal to each other.


    The way I read this is that containers don't need to bother testing a1
    == a2 - they can just assume that it will always be true. "Containers
    may assume that allocators always return true" is not the same as
    "Allocators must always return true" to me.

    My interpretation is that I am free to provide allocators that are
    non-interchangeable, and not always equal, but that in doing so I am
    relying on undefined behaviour (p5). My question is that if I were to
    provide allocators that *are* interchangeable - even though they may not
    return true (the result would be a trace in an error log and a
    performance penalty) - would I still be ok according to the strict
    definition (p4, as quoted)?

    I mean, is there any known implementation that tests for allocator
    equality and chokes if they are not equal (via an exception, I assume).
    This kind of thing introduces a subtle and unnecessary run time error,
    unless I write a separate test unit to include with the library to test
    for that explicit scenario.

    In my case the equality test does not constitute a test for correctness,
    but a test for performance costs. If a container detects that two
    allocators are equal then it can skip a lot of work in swap and splice
    operations. But if the container just assumes the allocators are equal,
    and later one allocator tries to deallocate memory allocated in another
    allocator, the only penalty is a performance hit (Heap::GetOwner(void*)
    is expensive, far more so than a slow copy).

    In the more general case my question is: If I were to write an allocator
    that does not always return true but allows cross-allocator
    deallocations regardless, would that allocator satisfy both the current
    standard and future changes? Would this method present a problem on any
    known implementations?

    mark
     
    Mark A. Gibbs, Apr 4, 2004
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ross Ridge
    Replies:
    2
    Views:
    881
    Dhruv
    Jul 7, 2003
  2. Richard Smith
    Replies:
    20
    Views:
    993
    Andy Sawyer
    Jul 21, 2003
  3. mar00ned

    Help with STL allocators

    mar00ned, Sep 24, 2004, in forum: C++
    Replies:
    6
    Views:
    451
    John Harrison
    Sep 24, 2004
  4. Ares Lagae

    Containers & Allocators

    Ares Lagae, Feb 15, 2005, in forum: C++
    Replies:
    6
    Views:
    401
    Ares Lagae
    Feb 21, 2005
  5. Andy Venikov

    std containers and allocators.

    Andy Venikov, Jul 11, 2005, in forum: C++
    Replies:
    4
    Views:
    1,352
    Andy Venikov
    Jul 13, 2005
Loading...

Share This Page