A non-const std::set iterator

[Michael Klatt]

I am trying to write an iterator for a std::set that allows the
iterator target to be modified. Here is some relvant code:

template <class Set> // Set is an instance of std::set<>
class Iterator
{
public :
typedef typename Set::value_type T;
typedef typename Set::iterator SetIterator;
Iterator(Set& container, const SetIterator& it);
Iterator& operator=(const Iterator& rhs);
T& operator*() { return m_proxy; }
T* operator->() { return &m_proxy; }
Iterator& operator++();
~Iterator() { sync(); }

private :
void sync();
Set& m_container;
SetIterator m_iterator;
T m_proxy;
};

template <class Set>
Iterator<Set>:: Iterator(Set& container, const SetIterator& it) :
m_container(con tainer),
m_iterator(it)
m_proxy(*it) {}

template <class Set>
Iterator<Set>& Iterator<Set>:: operator++()
{
sync();
++m_iterator;
return *this;
}

template <class Set>
Iterator<Set>& Iterator<Set>:: operator=(const Iterator& rhs)
{
sync();
m_container = rhs.m_contaner;
m_iterator = rhs.m_iterator;
m_proxy = rhs.m_proxy;
return *this;
}


template <class Set>
void Iterator<Set>:: sync()
{
typedef Set::key_compar e Compare;
if (Compare(*m_ite rator, m_proxy) || Compare(m_proxy , *m_iterator))
{
// sort order will be changed
container.erase (m_iterator);
m_iterator = container.inser t(m_proxy);
}
else
{
// modify set element directly (should be faster than having to do
// an insert)
const_cast<T&>( *m_iterator) = m_proxy;
}
return;
}

Am I on the right track with this, or is this a really bad idea? One
concern I have is concurrency. If more than one iterator points to
the same element it is possible for that element to get out of sync.

[Nick Hounsome]

Re: A non-const std::set iterator


"Michael Klatt" <mdklatt@ou.edu > wrote in message
news:2cb75565.0 404050652.53964 18c@posting.goo gle.com...[color=blue]
> I am trying to write an iterator for a std::set that allows the
> iterator target to be modified. Here is some relvant code:[/color]
.....[color=blue]
> Am I on the right track with this, or is this a really bad idea? One[/color]

It's a really bad idea.
Sets are ordered collections.
Changing a member potentially changes its position in the set and therefore
must be banned.
If you wish to argue that your operartor< only compares some fields and you
were only going to change some others then I say:
1. How is the compiler supposed to know and enforce that.
2. Your comparison operator is flawed.
3. What you really want is a map
[color=blue]
> concern I have is concurrency. If more than one iterator points to
> the same element it is possible for that element to get out of sync.[/color]

[Nick Hounsome]

Re: A non-const std::set iterator


"Michael Klatt" <mdklatt@ou.edu > wrote in message
news:2cb75565.0 404050652.53964 18c@posting.goo gle.com...[color=blue]
> I am trying to write an iterator for a std::set that allows the
> iterator target to be modified. Here is some relvant code:[/color]
.....[color=blue]
> Am I on the right track with this, or is this a really bad idea? One[/color]

It's a really bad idea.
Sets are ordered collections.
Changing a member potentially changes its position in the set and therefore
must be banned.
If you wish to argue that your operartor< only compares some fields and you
were only going to change some others then I say:
1. How is the compiler supposed to know and enforce that.
2. Your comparison operator is flawed.
3. What you really want is a map
[color=blue]
> concern I have is concurrency. If more than one iterator points to
> the same element it is possible for that element to get out of sync.[/color]

[Leor Zolman]

Re: A non-const std::set iterator

On Mon, 5 Apr 2004 17:18:40 +0100, "Nick Hounsome" <nh002@blueyond er.co.uk>
wrote:
[color=blue]
>
>"Michael Klatt" <mdklatt@ou.edu > wrote in message
>news:2cb75565. 0404050652.5396 418c@posting.go ogle.com...[color=green]
>> I am trying to write an iterator for a std::set that allows the
>> iterator target to be modified. Here is some relvant code:[/color]
>....[color=green]
>> Am I on the right track with this, or is this a really bad idea? One[/color]
>
>It's a really bad idea.
>Sets are ordered collections.
>Changing a member potentially changes its position in the set and therefore
>must be banned.
>If you wish to argue that your operartor< only compares some fields and you
>were only going to change some others then I say:
>1. How is the compiler supposed to know and enforce that.
>2. Your comparison operator is flawed.
>3. What you really want is a map
>[/color]

I'm not sure it is /that/ bad an idea, although I'm not yet sure it is a
/good/ one. Upon first reading the OP's idea I immediately thought about
the ordering problem, but then I took a look at his code. It looks like his
special Iterator tests to see whether assignment through the iterator
would cause a change in the ordering, and special-cases the two
possibilities. If it does change the ordering, it just erases and inserts
(and for this purpose it stores a ref to the entire container). If not,
then it performs an in-place copy into the element (casting away constness
to make it compile). I tried this to test it, but got a slew of errors from
the template code:

int main()
{
set<int> s;
// fill up s... including the value 6
// (I used InitUtil, so I'll omit all of that)

set<int>::itera tor it;
if ((it = find(s.begin(), s.end(), 6)) != s.end())
cout << "Found it!" << endl;
else
{
cout << "Didn't find 6..." << endl;
exit(1);
}

Iterator<set<in t> > ncit(s, it);
*ncit = 75;

cout << "after replacing 6 with 75: " << endl;

// dump out the values

return 0;
}

He didn't say it was supposed to work yet ;-)
I think when it does, we may have something at least a little bit
interesting to talk about.
-leor


--
Leor Zolman --- BD Software --- www.bdsoft.com
On-Site Training in C/C++, Java, Perl and Unix
C++ users: Download BD Software's free STL Error Message Decryptor at:

https://www.bdsoft.com/tools/stlfilt.html

[Leor Zolman]

Re: A non-const std::set iterator

On Mon, 5 Apr 2004 17:18:40 +0100, "Nick Hounsome" <nh002@blueyond er.co.uk>
wrote:
[color=blue]
>
>"Michael Klatt" <mdklatt@ou.edu > wrote in message
>news:2cb75565. 0404050652.5396 418c@posting.go ogle.com...[color=green]
>> I am trying to write an iterator for a std::set that allows the
>> iterator target to be modified. Here is some relvant code:[/color]
>....[color=green]
>> Am I on the right track with this, or is this a really bad idea? One[/color]
>
>It's a really bad idea.
>Sets are ordered collections.
>Changing a member potentially changes its position in the set and therefore
>must be banned.
>If you wish to argue that your operartor< only compares some fields and you
>were only going to change some others then I say:
>1. How is the compiler supposed to know and enforce that.
>2. Your comparison operator is flawed.
>3. What you really want is a map
>[/color]

I'm not sure it is /that/ bad an idea, although I'm not yet sure it is a
/good/ one. Upon first reading the OP's idea I immediately thought about
the ordering problem, but then I took a look at his code. It looks like his
special Iterator tests to see whether assignment through the iterator
would cause a change in the ordering, and special-cases the two
possibilities. If it does change the ordering, it just erases and inserts
(and for this purpose it stores a ref to the entire container). If not,
then it performs an in-place copy into the element (casting away constness
to make it compile). I tried this to test it, but got a slew of errors from
the template code:

int main()
{
set<int> s;
// fill up s... including the value 6
// (I used InitUtil, so I'll omit all of that)

set<int>::itera tor it;
if ((it = find(s.begin(), s.end(), 6)) != s.end())
cout << "Found it!" << endl;
else
{
cout << "Didn't find 6..." << endl;
exit(1);
}

Iterator<set<in t> > ncit(s, it);
*ncit = 75;

cout << "after replacing 6 with 75: " << endl;

// dump out the values

return 0;
}

He didn't say it was supposed to work yet ;-)
I think when it does, we may have something at least a little bit
interesting to talk about.
-leor


--
Leor Zolman --- BD Software --- www.bdsoft.com
On-Site Training in C/C++, Java, Perl and Unix
C++ users: Download BD Software's free STL Error Message Decryptor at:

https://www.bdsoft.com/tools/stlfilt.html

[richard.forrest1]

Re: A non-const std::set iterator


"Leor Zolman" <leor@bdsoft.co m> wrote in message
news:qt6370teul gf5180u93kav70i obeedo7ge@4ax.c om...[color=blue]
> On Mon, 5 Apr 2004 17:18:40 +0100, "Nick Hounsome"[/color]
<nh002@blueyond er.co.uk>[color=blue]
> wrote:[/color]
[color=blue]
>
> I'm not sure it is /that/ bad an idea, although I'm not yet sure it is a
> /good/ one. Upon first reading the OP's idea I immediately thought about
> the ordering problem, but then I took a look at his code. It looks like[/color]
his[color=blue]
> special Iterator tests to see whether assignment through the iterator
> would cause a change in the ordering, and special-cases the two
> possibilities. If it does change the ordering, it just erases and inserts
> (and for this purpose it stores a ref to the entire container). If not,
> then it performs an in-place copy into the element (casting away constness
> to make it compile). I tried this to test it, but got a slew of errors[/color]
from[color=blue]
> the template code:[/color]

It is an interesting idea but I think it has a serious difficulty.

A range represented by a pair of these iterators will act in an unexpected
(i.e. bad) way if their are used to modify elements.
Whilst every element in the range will be encountered at least once, some
elements may be encountered more than once. This occurs when modifying a
element repositions it beyond the current iterator rather than before it.

The problem is not so much in the software but in the concept of what it
means to iterate through a range in a set whilst modifying it. As soon as it
is modified it is no longer the same range as it may contain a different
number of different elements in a different order.

Richard

[richard.forrest1]

Re: A non-const std::set iterator


"Leor Zolman" <leor@bdsoft.co m> wrote in message
news:qt6370teul gf5180u93kav70i obeedo7ge@4ax.c om...[color=blue]
> On Mon, 5 Apr 2004 17:18:40 +0100, "Nick Hounsome"[/color]
<nh002@blueyond er.co.uk>[color=blue]
> wrote:[/color]
[color=blue]
>
> I'm not sure it is /that/ bad an idea, although I'm not yet sure it is a
> /good/ one. Upon first reading the OP's idea I immediately thought about
> the ordering problem, but then I took a look at his code. It looks like[/color]
his[color=blue]
> special Iterator tests to see whether assignment through the iterator
> would cause a change in the ordering, and special-cases the two
> possibilities. If it does change the ordering, it just erases and inserts
> (and for this purpose it stores a ref to the entire container). If not,
> then it performs an in-place copy into the element (casting away constness
> to make it compile). I tried this to test it, but got a slew of errors[/color]
from[color=blue]
> the template code:[/color]

It is an interesting idea but I think it has a serious difficulty.

A range represented by a pair of these iterators will act in an unexpected
(i.e. bad) way if their are used to modify elements.
Whilst every element in the range will be encountered at least once, some
elements may be encountered more than once. This occurs when modifying a
element repositions it beyond the current iterator rather than before it.

The problem is not so much in the software but in the concept of what it
means to iterate through a range in a set whilst modifying it. As soon as it
is modified it is no longer the same range as it may contain a different
number of different elements in a different order.

Richard

[Leor Zolman]

Re: A non-const std::set iterator

On Mon, 5 Apr 2004 18:34:07 +0100, "richard.forres t1"
<richard.forres t1@ntlworld.com > wrote:
[color=blue]
>A range represented by a pair of these iterators will act in an unexpected
>(i.e. bad) way if their are used to modify elements.
>Whilst every element in the range will be encountered at least once, some
>elements may be encountered more than once. This occurs when modifying a
>element repositions it beyond the current iterator rather than before it.
>
>The problem is not so much in the software but in the concept of what it
>means to iterate through a range in a set whilst modifying it. As soon as it
>is modified it is no longer the same range as it may contain a different
>number of different elements in a different order.
>
>Richard[/color]

Yup. So there's at least one way of using it down the drain.

I doubt anyone (including the OP) was planning to go proposing one of these
as an addition to the Standard ;-) but perhaps the technique, possibly
generalized to all associative containers, might find a niche as a simple
shorthand for the otherwise-required rigmarole to "change" the value of an
element of one of those containers. It (or something along those lines)
sounds like it mght still be useful.
-leor

--
Leor Zolman --- BD Software --- www.bdsoft.com
On-Site Training in C/C++, Java, Perl and Unix
C++ users: Download BD Software's free STL Error Message Decryptor at:

https://www.bdsoft.com/tools/stlfilt.html

[Leor Zolman]

Re: A non-const std::set iterator

On Mon, 5 Apr 2004 18:34:07 +0100, "richard.forres t1"
<richard.forres t1@ntlworld.com > wrote:
[color=blue]
>A range represented by a pair of these iterators will act in an unexpected
>(i.e. bad) way if their are used to modify elements.
>Whilst every element in the range will be encountered at least once, some
>elements may be encountered more than once. This occurs when modifying a
>element repositions it beyond the current iterator rather than before it.
>
>The problem is not so much in the software but in the concept of what it
>means to iterate through a range in a set whilst modifying it. As soon as it
>is modified it is no longer the same range as it may contain a different
>number of different elements in a different order.
>
>Richard[/color]

Yup. So there's at least one way of using it down the drain.

I doubt anyone (including the OP) was planning to go proposing one of these
as an addition to the Standard ;-) but perhaps the technique, possibly
generalized to all associative containers, might find a niche as a simple
shorthand for the otherwise-required rigmarole to "change" the value of an
element of one of those containers. It (or something along those lines)
sounds like it mght still be useful.
-leor

--
Leor Zolman --- BD Software --- www.bdsoft.com
On-Site Training in C/C++, Java, Perl and Unix
C++ users: Download BD Software's free STL Error Message Decryptor at:

https://www.bdsoft.com/tools/stlfilt.html

[Michael Klatt]

Re: A non-const std::set iterator

Leor Zolman <leor@bdsoft.co m> wrote in message news:<qt6370teu lgf5180u93kav70 iobeedo7ge@4ax. com>...[color=blue]
>
> He didn't say it was supposed to work yet ;-)
> I think when it does, we may have something at least a little bit
> interesting to talk about.
> -leor[/color]

No, the sample I posted is definitely not ready for prime time. There
are a few syntax errors, and at least one logic error. There are also
some member functions that need to be added. Fixing these is left as
an exercise for the reader. :)

Actually, I've got a version that compiles, and more or less (more on
that later) works, but there's a problem in constructor Iterator(Set*
container, const SetIterator& it). There was a problem with
deferencing container->end(), but even accounting for this I still get
a segmentation fault. I'm also not sure about the semantics of the
boolean operators. Are two Iterators eqivalent merely if they
reference the same set element, or does the local proxy object have to
be the same as well? Also, there is still the problem of concurrency
if there are multiple iterators pointing to the same element.

For now, I think I'm going to be less ambitious and develop a simple
replace() function that operates directly on a container rather than
via an iterator.

[Michael Klatt]

Re: A non-const std::set iterator

Leor Zolman <leor@bdsoft.co m> wrote in message news:<qt6370teu lgf5180u93kav70 iobeedo7ge@4ax. com>...[color=blue]
>
> He didn't say it was supposed to work yet ;-)
> I think when it does, we may have something at least a little bit
> interesting to talk about.
> -leor[/color]

No, the sample I posted is definitely not ready for prime time. There
are a few syntax errors, and at least one logic error. There are also
some member functions that need to be added. Fixing these is left as
an exercise for the reader. :)

Actually, I've got a version that compiles, and more or less (more on
that later) works, but there's a problem in constructor Iterator(Set*
container, const SetIterator& it). There was a problem with
deferencing container->end(), but even accounting for this I still get
a segmentation fault. I'm also not sure about the semantics of the
boolean operators. Are two Iterators eqivalent merely if they
reference the same set element, or does the local proxy object have to
be the same as well? Also, there is still the problem of concurrency
if there are multiple iterators pointing to the same element.

For now, I think I'm going to be less ambitious and develop a simple
replace() function that operates directly on a container rather than
via an iterator.

[Michael Klatt]

Re: A non-const std::set iterator

"richard.forres t1" <richard.forres t1@ntlworld.com > wrote in message news:<KFhcc.210 $Xi.34@newsfe1-win>...
[color=blue]
> The problem is not so much in the software but in the concept of what it
> means to iterate through a range in a set whilst modifying it. As soon as it
> is modified it is no longer the same range as it may contain a different
> number of different elements in a different order.
>[/color]

After thinking about how I would use this iterator class, I realized
that I probably won't be changing anything that would effect the sort
order. The problem now is, how do I allow only part of the stored
object to change? I had originally thought about using something like
std::map<FooKey , Foo>. But if I do this, how do I enforce the
simulataneous restrictions that a FooKey must be constant and must
reflect the state of a Foo?


// untested code

struct Foo
{
int sort_criterion
float data_member
}

struct FooKey
{
FooKey(const Foo& foo) : sort_criterion( foo.sort_criter ion)
const int& sort_criterion;
}

int main()
{
std::map<FooKey , Foo> container;
Foo foo(10);
FooKey key(foo);
container.inser t(std::make_pai r(key, foo));
std::map<FooKey , Foo>::iterator it(map.find(foo ));
it->second.sort_cr iterion = 83; // container is now invalid
return 0;
}

For now, I think I'm going to try something less complex. I'll use a
seperate replace() function instead of trying to use an iterator to do
this.

[Michael Klatt]

Re: A non-const std::set iterator

"richard.forres t1" <richard.forres t1@ntlworld.com > wrote in message news:<KFhcc.210 $Xi.34@newsfe1-win>...
[color=blue]
> The problem is not so much in the software but in the concept of what it
> means to iterate through a range in a set whilst modifying it. As soon as it
> is modified it is no longer the same range as it may contain a different
> number of different elements in a different order.
>[/color]

After thinking about how I would use this iterator class, I realized
that I probably won't be changing anything that would effect the sort
order. The problem now is, how do I allow only part of the stored
object to change? I had originally thought about using something like
std::map<FooKey , Foo>. But if I do this, how do I enforce the
simulataneous restrictions that a FooKey must be constant and must
reflect the state of a Foo?


// untested code

struct Foo
{
int sort_criterion
float data_member
}

struct FooKey
{
FooKey(const Foo& foo) : sort_criterion( foo.sort_criter ion)
const int& sort_criterion;
}

int main()
{
std::map<FooKey , Foo> container;
Foo foo(10);
FooKey key(foo);
container.inser t(std::make_pai r(key, foo));
std::map<FooKey , Foo>::iterator it(map.find(foo ));
it->second.sort_cr iterion = 83; // container is now invalid
return 0;
}

For now, I think I'm going to try something less complex. I'll use a
seperate replace() function instead of trying to use an iterator to do
this.

[Siemel Naran]

Re: A non-const std::set iterator

"Michael Klatt" <mdklatt@ou.edu > wrote in message
news:2cb75565.0 404050652.53964 18c@posting.goo gle.com...
[color=blue]
> I am trying to write an iterator for a std::set that allows the
> iterator target to be modified. Here is some relvant code:[/color]

Your code is mostly sound. In what scenario do you find this useful?

[color=blue]
> template <class Set> // Set is an instance of std::set<>
> class Iterator
> {
> public :
> typedef typename Set::value_type T;
> typedef typename Set::iterator SetIterator;
> Iterator(Set& container, const SetIterator& it);
> Iterator& operator=(const Iterator& rhs);
> T& operator*() { return m_proxy; }
> T* operator->() { return &m_proxy; }
> Iterator& operator++();
> ~Iterator() { sync(); }[/color]

One major problem is that your destructor may throw, as sync may throw.
This is a problem, because when you have an exception and the stack unwinds,
you could get an exception with an exception, and the program calls
terminate(), which usually calls abort().

What about operator== and operator!=. I guess we want to be able to use
these iterators :).
[color=blue]
> private :
> void sync();
> Set& m_container;
> SetIterator m_iterator;
> T m_proxy;
> };[/color]

I imagine much of the time we won't change the iterator value. But your
design forces a copy of m_proxy always. We'll also call sync() which won't
change the underlying set, but still calls const_cast<T&>( *m_iterator) =
m_proxy which costs time. To fix, we can make m_proxy be either a pointer
to either the set's value, or a pointer to a new value.
[color=blue]
> template <class Set>
> Iterator<Set>:: Iterator(Set& container, const SetIterator& it) :
> m_container(con tainer),
> m_iterator(it)
> m_proxy(*it) {}[/color]

Don't forget to deal with the empty container, which is certainly valid
input :). Also maybe provide a constructor Iterator(Set&) where 'it'
defaults to set.begin().
[color=blue]
> template <class Set>
> Iterator<Set>& Iterator<Set>:: operator++()
> {
> sync();
> ++m_iterator;
> return *this;
> }
>
> template <class Set>
> Iterator<Set>& Iterator<Set>:: operator=(const Iterator& rhs)
> {
> sync();
> m_container = rhs.m_contaner;
> m_iterator = rhs.m_iterator;
> m_proxy = rhs.m_proxy;
> return *this;
> }[/color]

Another major problem. Your operator= and compiler generated copy
constructor do different things. Operator= copies the container itself.
Perhaps you want to turn the type of m_container from Set to Set*, that is
to a pointer to a set?

[color=blue]
> template <class Set>
> void Iterator<Set>:: sync()
> {
> typedef Set::key_compar e Compare;[/color]

Don't forget "typedef typename ...". Anyway, don't you want to call
key_comp()?
[color=blue]
> if (Compare(*m_ite rator, m_proxy) || Compare(m_proxy , *m_iterator))
> {
> // sort order will be changed
> container.erase (m_iterator);
> m_iterator = container.inser t(m_proxy);
> }
> else
> {
> // modify set element directly (should be faster than having to do
> // an insert)
> const_cast<T&>( *m_iterator) = m_proxy;
> }[/color]

In your code the else clause is used whenever *m_iterator equals m_proxy.
But we could use the else clause whenever *(m_iterator-1) < m_proxy <
*(m_iterator+1) , which helps performance. I think this is one of the few
valid uses of const_cast.
[color=blue]
> return;
> }[/color]

It seems strange when iterating over a range. Suppose your set is { 2, 3,
6, 7, 9 }, you're at the 3, and you change it to 8, so the new set is { 2,
6, 7, 8, 9 } which is fine. But the iterator will be pointing to 9. This
may be fine sometimes, but more often than not we'd want the iterator to
point to 6, or the 3rd element in the original set.

Another problem is when to commit. Consider

Set s;
s.insert(1);
s.insert(2);
Iterator<Set> i(s, i.begin());
*i = 3;
s.find(1); // returns something != s.end(), not intuitive
++i; // commits
s.find(1); // returns s.end(), non consistent with call above

Maybe we want immediate commit (at least within our transaction, though
that's another story).

For this, consider using smart references. These are classes that behave
like normal references for readonly access by providing an operator()
conversion that returns a const T&. But they overload operator= to do
something special. In our case this is to change the underlying set and
make the underlying iterator point to something meaningful. The compiler
generated copy constructor is fine. Using smart references you solve the
problem above of commit, throwing destructors, performance problems of
always constructing m_proxy, and the case of an empty set where *it is a
memory access violation.

[color=blue]
> Am I on the right track with this, or is this a really bad idea? One
> concern I have is concurrency. If more than one iterator points to
> the same element it is possible for that element to get out of sync.[/color]

This is a tough one. According to 23.1.2.8, inserting an element into a set
does not invalidate iterators, and erasing an element only invalidates the
erased iterator. Suppose you implement smart references

Set s;
s.insert(1);
s.insert(2);
Iterator<Set> i(s);
Iterator<Set> i2(s);
*i = 3; // commits, i pointing to 2 or 3, i2 invalid

Maybe that's just the way it is, and we'll just do like they do in the
standard, namely modifying the set though Iterator::refer ence::operator=
invalidates all iterators in the set, and using the iterators leads to
undefined behavior.

int * i = new int(3);
int * i2 = i;
delete i; // now i2 is invalid

Sure the problem can be solved. Something like this: the set knows all
iterators it has given out (for example it keeps an array of pointers to
iterators), copy one iterator into another and the set still knows about all
the iterators (including the copied one), when you modify an element through
Iterator::refer ence::operator= the set sends a signal to each of the
iterators.

[Siemel Naran]

Re: A non-const std::set iterator

"Michael Klatt" <mdklatt@ou.edu > wrote in message
news:2cb75565.0 404050652.53964 18c@posting.goo gle.com...
[color=blue]
> I am trying to write an iterator for a std::set that allows the
> iterator target to be modified. Here is some relvant code:[/color]

Your code is mostly sound. In what scenario do you find this useful?

[color=blue]
> template <class Set> // Set is an instance of std::set<>
> class Iterator
> {
> public :
> typedef typename Set::value_type T;
> typedef typename Set::iterator SetIterator;
> Iterator(Set& container, const SetIterator& it);
> Iterator& operator=(const Iterator& rhs);
> T& operator*() { return m_proxy; }
> T* operator->() { return &m_proxy; }
> Iterator& operator++();
> ~Iterator() { sync(); }[/color]

One major problem is that your destructor may throw, as sync may throw.
This is a problem, because when you have an exception and the stack unwinds,
you could get an exception with an exception, and the program calls
terminate(), which usually calls abort().

What about operator== and operator!=. I guess we want to be able to use
these iterators :).
[color=blue]
> private :
> void sync();
> Set& m_container;
> SetIterator m_iterator;
> T m_proxy;
> };[/color]

I imagine much of the time we won't change the iterator value. But your
design forces a copy of m_proxy always. We'll also call sync() which won't
change the underlying set, but still calls const_cast<T&>( *m_iterator) =
m_proxy which costs time. To fix, we can make m_proxy be either a pointer
to either the set's value, or a pointer to a new value.
[color=blue]
> template <class Set>
> Iterator<Set>:: Iterator(Set& container, const SetIterator& it) :
> m_container(con tainer),
> m_iterator(it)
> m_proxy(*it) {}[/color]

Don't forget to deal with the empty container, which is certainly valid
input :). Also maybe provide a constructor Iterator(Set&) where 'it'
defaults to set.begin().
[color=blue]
> template <class Set>
> Iterator<Set>& Iterator<Set>:: operator++()
> {
> sync();
> ++m_iterator;
> return *this;
> }
>
> template <class Set>
> Iterator<Set>& Iterator<Set>:: operator=(const Iterator& rhs)
> {
> sync();
> m_container = rhs.m_contaner;
> m_iterator = rhs.m_iterator;
> m_proxy = rhs.m_proxy;
> return *this;
> }[/color]

Another major problem. Your operator= and compiler generated copy
constructor do different things. Operator= copies the container itself.
Perhaps you want to turn the type of m_container from Set to Set*, that is
to a pointer to a set?

[color=blue]
> template <class Set>
> void Iterator<Set>:: sync()
> {
> typedef Set::key_compar e Compare;[/color]

Don't forget "typedef typename ...". Anyway, don't you want to call
key_comp()?
[color=blue]
> if (Compare(*m_ite rator, m_proxy) || Compare(m_proxy , *m_iterator))
> {
> // sort order will be changed
> container.erase (m_iterator);
> m_iterator = container.inser t(m_proxy);
> }
> else
> {
> // modify set element directly (should be faster than having to do
> // an insert)
> const_cast<T&>( *m_iterator) = m_proxy;
> }[/color]

In your code the else clause is used whenever *m_iterator equals m_proxy.
But we could use the else clause whenever *(m_iterator-1) < m_proxy <
*(m_iterator+1) , which helps performance. I think this is one of the few
valid uses of const_cast.
[color=blue]
> return;
> }[/color]

It seems strange when iterating over a range. Suppose your set is { 2, 3,
6, 7, 9 }, you're at the 3, and you change it to 8, so the new set is { 2,
6, 7, 8, 9 } which is fine. But the iterator will be pointing to 9. This
may be fine sometimes, but more often than not we'd want the iterator to
point to 6, or the 3rd element in the original set.

Another problem is when to commit. Consider

Set s;
s.insert(1);
s.insert(2);
Iterator<Set> i(s, i.begin());
*i = 3;
s.find(1); // returns something != s.end(), not intuitive
++i; // commits
s.find(1); // returns s.end(), non consistent with call above

Maybe we want immediate commit (at least within our transaction, though
that's another story).

For this, consider using smart references. These are classes that behave
like normal references for readonly access by providing an operator()
conversion that returns a const T&. But they overload operator= to do
something special. In our case this is to change the underlying set and
make the underlying iterator point to something meaningful. The compiler
generated copy constructor is fine. Using smart references you solve the
problem above of commit, throwing destructors, performance problems of
always constructing m_proxy, and the case of an empty set where *it is a
memory access violation.

[color=blue]
> Am I on the right track with this, or is this a really bad idea? One
> concern I have is concurrency. If more than one iterator points to
> the same element it is possible for that element to get out of sync.[/color]

This is a tough one. According to 23.1.2.8, inserting an element into a set
does not invalidate iterators, and erasing an element only invalidates the
erased iterator. Suppose you implement smart references

Set s;
s.insert(1);
s.insert(2);
Iterator<Set> i(s);
Iterator<Set> i2(s);
*i = 3; // commits, i pointing to 2 or 3, i2 invalid

Maybe that's just the way it is, and we'll just do like they do in the
standard, namely modifying the set though Iterator::refer ence::operator=
invalidates all iterators in the set, and using the iterators leads to
undefined behavior.

int * i = new int(3);
int * i2 = i;
delete i; // now i2 is invalid

Sure the problem can be solved. Something like this: the set knows all
iterators it has given out (for example it keeps an array of pointers to
iterators), copy one iterator into another and the set still knows about all
the iterators (including the copied one), when you modify an element through
Iterator::refer ence::operator= the set sends a signal to each of the
iterators.