Valentin Bonnard wrote:
....
> (1) set may just use std::allocator anyway

set<T,myallocator> is required to use myallocator, not std::allocator.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Matt Austern wrote:
>
> Valentin Bonnard writes:
>
> > > I'm looking for something similar to vector's reserve capability, but not
> > > quite as stringent, since the set guaranteed not to get any bigger than it
> > > has been in the past.
> >
> > You never know if a call to std::allocator::allocate, new, new[], or
> > malloc
> > will succed either in C or C++. Never.
>
> That's true, but you do know whether or not a call to
> my_namespace::my_allocator_with_a_custom_arena::allocate()
> will succeed.  You can allocate a big chunk at the beginning,
> and use that chunk for all future set<> allocations.

Yes, but:
(1) set may just use std::allocator anyway
(2) set might want to throw an exception (cf phase of the moon)
(3) even if set uses your allocator, it can request a _lot_ of
    memory, and your allocator will throw

We could solve (1) with the appropriate patch (applied to the
standard), or even (2) (by specifying when it can fail). We
cannot change (3) except by specifying how much memory set uses
in its implementation. But that's very very difficult.

[I think that (1) is worth fixing.]

> This is
> just the sort of thing that allocators were designed for.

Hum... some people consider that allocators are the wonderfull
tool that makes the STL so versatile. IMO, allocator are just
usable as a way to replace operator new/delete (with a fine grain).

This is useful: to have different memory pools, to log memory
allocation, to debug, to have faster or slower allocators...

But allocators aren't the magic (and impossible to understand)
template parameter that will make your STL code so versatile
that it's usable in every situation.

--

Valentin Bonnard
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

> Portability:
> In general, support for member templates is required for custom allocators
> in containers.  Your compiler may or may not yet support this standard C++
> language feature.  If it doesn't, there may be some compiler-specific work
> around to get your set to use a custom allocator.

The biggest portability problem with Howard's otherwise fine idea is that
the implementation is allowed to throw any implementation-defined
exceptions, for unspecified reasons. Not that I've ever seen an
implementation that does this, but why leave anything to chance when you
don't have to?

-Dave
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Howard Hinnant wrote in message ...
>> Is there a portable way to guarantee that inserting an element into a set
>> will succeed if a identically sized element has recently been removed?


>For set, I would think you could provide a custom allocator with this
>guarantee.  I don't have one in my back pocket, but I think it would work
>(with some caveats).


This should work with common implementations of set.  However I believe it
is possible to meet the set complexity requirements with data structures
that put all of the actual elements at leaf nodes (similar to B-Trees).
With such a structure an insert "far" from the most recent erase might
require an additional allocation (for new set internal structure) which
could fail.




[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Valentin Bonnard <Bonnard.V@wanadoo.fr> writes:

> > I'm looking for something similar to vector's reserve capability, but not
> > quite as stringent, since the set guaranteed not to get any bigger than it
> > has been in the past.
>
> You never know if a call to std::allocator::allocate, new, new[], or
> malloc
> will succed either in C or C++. Never.

That's true, but you do know whether or not a call to
my_namespace::my_allocator_with_a_custom_arena::allocate()
will succeed.  You can allocate a big chunk at the beginning,
and use that chunk for all future set<> allocations.  This is
just the sort of thing that allocators were designed for.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Dave Abrahams wrote in message ...
>
>The exception behaviors of the standard library were carefully designed to
>make this sort of atomicity easy to guarantee. It sounds like in your case,
>the best solution is something like this:
>
>void Modify( std::set<X*> s, set<X*>::iterator oldItem )
>{
>    std::auto_ptr<X> p = new X( *oldItem );
>    ModifyItem( *p );
>    s.insert( p.get() );
>    s.erase( oldItem );
>    p.release();
>}

The best solution I've come up with so far can be thought of as an
optimization on what you suggest.  *oldItem is expensive to copy.
Furthermore, I usually only want to make small changes to it, although those
changes do affect the ordering of s.  To avoid making a full copy of
*oldItem, I do the following (continuing with your naming conventions):

- I save a backup of the old values in *oldItem that are about to be
changed.
- I update *oldItem with my new values.  I cast away the constness of the
set's value type to do this.
- Since the previous step invalidated the ordering of my set, I set *oldItem
to point to the item preceding it in the set.  (My application never changes
the first element in the set).  This restores the set to a valid ordering.
Although it is not identical to the initial ordering, it is good enough to
guarantee that insert will work.
- I insert the updated item into the set.
- I remove the old item from the set.

The code looks something like this:

void Modify( std::set<X*> s, set<X*>::iterator oldItem )
{
    SX subsetOfX;
    try
    {
        subsetOfX = BackupChanges( *oldItem );
        ModifyItem( *oldItem );
        set<X*>::iterator prevItem = oldItem;
        --prevItem;
        *oldItem = *prevItem;
        s.insert( *oldItem );
        s.remove( oldItem );
    }
    catch (...)
    {
        // Restore backup.
    }
}

As far as I know, this is legitimate and will always work.  I'd be
interested in hearing what others think.

As a side note, does anyone know how to express the previous item in a set
without making a temporary iterator and decrementing it?
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Is there a portable way to guarantee that inserting an element into a set
will succeed if a identically sized element has recently been removed?

In my application, I have a set of pointers that is ordered by the value of
the pointed-to data.  If I need to change the pointed-to data, I first
remove the pointer from the set, change the data, and then reinsert the
pointer.

If reinserting the pointer throws an out-of-memory exception, I have a big
headache to gracefully fail without adding too much expense to successful
operations, due to atomicity constraints.

I'm looking for something similar to vector's reserve capability, but not
quite as stringent, since the set guaranteed not to get any bigger than it
has been in the past.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

>If reinserting the pointer throws an out-of-memory exception, I have a big
>headache to gracefully fail without adding too much expense to successful
>operations, due to atomicity constraints.
>
>I'm looking for something similar to vector's reserve capability, but not
>quite as stringent, since the set guaranteed not to get any bigger than it
>has been in the past.

I don't think that you can do that, the only safe way would seem to be
to do the insert of the new value *first* - then if it fails you can
fail gracefully, with your set remaining unchanged.

John Maddock
http://ourworld.compuserve.com/homepages/John_Maddock/
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Ed Brey wrote:

> Is there a portable way to guarantee that inserting an element into a set
> will succeed if a identically sized element has recently been removed?

No

> In my application, I have a set of pointers that is ordered by the value of
> the pointed-to data.  If I need to change the pointed-to data, I first
> remove the pointer from the set, change the data, and then reinsert the
> pointer.

Fine

> If reinserting the pointer throws an out-of-memory exception, I have a big
> headache to gracefully fail without adding too much expense to successful
> operations, due to atomicity constraints.

Consider that:

std::set<T*, Or> tmp = current;
tmp.erase (it);
tmp.insert (value);
swap (current, tmp);

This is safe but expensive.  :-(

> I'm looking for something similar to vector's reserve capability, but not
> quite as stringent, since the set guaranteed not to get any bigger than it
> has been in the past.

You never know if a call to std::allocator::allocate, new, new[], or
malloc
will succed either in C or C++. Never.

In general, you never know if a insert in a standard containner will
succed
or throw an exception because of insufficient memory. vector is an
exception
(no pun intended)

--

Valentin Bonnard
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <36FD4F53.5BC0@wanadoo.fr> , Valentin Bonnard
<Bonnard.V@wanadoo.fr>  wrote:

> In general, you never know if a insert in a standard containner will
> succed
> or throw an exception because of insufficient memory

Or for any other reason, I should point out. I've never seen an
implementation of a standard container that throws exceptions for other
reasons (aside from the at() member functions), but it is allowed by the
standard. Don't count on "bad_alloc or nothing", even if your contained type
doesn't throw any exceptions.

-Dave
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <7dea3f$jau4@interserv.etn.com> , "Ed Brey"
<brey@afd.mke.etn.com> wrote:

> If reinserting the pointer throws an out-of-memory exception, I have a big
> headache to gracefully fail without adding too much expense to successful
> operations, due to atomicity constraints.

The exception behaviors of the standard library were carefully designed to
make this sort of atomicity easy to guarantee. It sounds like in your case,
the best solution is something like this:

void Modify( std::set<X*> s, set<X*>::iterator oldItem )
{
    std::auto_ptr<X> p = new X( *oldItem );
    ModifyItem( *p );
    s.insert( p.get() );
    s.erase( oldItem );
    p.release();
}

Hope this helps,
Dave
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <7dea3f$jau4@interserv.etn.com>, "Ed Brey"
<brey@afd.mke.etn.com> wrote:

> Is there a portable way to guarantee that inserting an element into a set
> will succeed if a identically sized element has recently been removed?
>
> In my application, I have a set of pointers that is ordered by the value of
> the pointed-to data.  If I need to change the pointed-to data, I first
> remove the pointer from the set, change the data, and then reinsert the
> pointer.
>
> If reinserting the pointer throws an out-of-memory exception, I have a big
> headache to gracefully fail without adding too much expense to successful
> operations, due to atomicity constraints.
>
> I'm looking for something similar to vector's reserve capability, but not
> quite as stringent, since the set guaranteed not to get any bigger than it
> has been in the past.

For set, I would think you could provide a custom allocator with this
guarantee.  I don't have one in my back pocket, but I think it would work
(with some caveats).

All objects in a set are the same size.  This can be taken advantage of
with a fixed-size pool allocator.  Your allocator could preallocate a
number of chunks of memory (set nodes) for the set to consume.  When set
requests a node, the allocator passes one in.  When set erases a node, the
allocator keeps it around for later use.

In your scenario, the allocator is guaranteed to have a node available for
use, because the set just freed one.

Caveats:

If the constructor of the object contained in set also allocates memory,
then all bets are off (unless you recursively play this game with that
object).  Of course, with a set<pointer_type> this shouldn't be a concern.

Your allocator could be one of two designs:

1.  It could share it's pools among all sets<T>, or even among all
containers requesting an allocator<T>.  But in this case you would have to
be careful that someone else didn't reqeust memory during your vulnerable
window.  i.e.  Lock the pool if you are multi-threading, or don't allow
other containers to use the pool while you're modifying your pointer.

2.  It could not share it's pools with anybody else.  This makes it 100%
safe, but at the expensive of possibly hogging more than its share of
memory.

Portability:
In general, support for member templates is required for custom allocators
in containers.  Your compiler may or may not yet support this standard C++
language feature.  If it doesn't, there may be some compiler-specific work
around to get your set to use a custom allocator.

Disclaimers:
Just an idea.  Don't have a proof of concept to show you.  But I have
played with custom allocators, and they aren't that much work.

-Howard
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]