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]

"Michael Klatt" <md*****@ou.edu > wrote in message
news:2c******** *************** ***@posting.goo gle.com...

I am trying to write an iterator for a std::set that allows the
iterator target to be modified. Here is some relvant code: ..... Am I on the right track with this, or is this a really bad idea? One
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
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]

"Michael Klatt" <md*****@ou.edu > wrote in message
news:2c******** *************** ***@posting.goo gle.com...

I am trying to write an iterator for a std::set that allows the
iterator target to be modified. Here is some relvant code: ..... Am I on the right track with this, or is this a really bad idea? One
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
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.

[Leor Zolman]

On Mon, 5 Apr 2004 17:18:40 +0100, "Nick Hounsome" <nh***@blueyond er.co.uk>
wrote:

"Michael Klatt" <md*****@ou.edu > wrote in message
news:2c******* *************** ****@posting.go ogle.com...

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

....

Am I on the right track with this, or is this a really bad idea? One

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

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:
www.bdsoft.com/tools/stlfilt.html

[Leor Zolman]

On Mon, 5 Apr 2004 17:18:40 +0100, "Nick Hounsome" <nh***@blueyond er.co.uk>
wrote:

"Michael Klatt" <md*****@ou.edu > wrote in message
news:2c******* *************** ****@posting.go ogle.com...

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

....

Am I on the right track with this, or is this a really bad idea? One

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

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:
www.bdsoft.com/tools/stlfilt.html

[richard.forrest1]

"Leor Zolman" <le**@bdsoft.co m> wrote in message
news:qt******** *************** *********@4ax.c om...

On Mon, 5 Apr 2004 17:18:40 +0100, "Nick Hounsome" <nh***@blueyond er.co.uk> wrote:
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:

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]

"Leor Zolman" <le**@bdsoft.co m> wrote in message
news:qt******** *************** *********@4ax.c om...

On Mon, 5 Apr 2004 17:18:40 +0100, "Nick Hounsome" <nh***@blueyond er.co.uk> wrote:
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:

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]

On Mon, 5 Apr 2004 18:34:07 +0100, "richard.forres t1"
<ri************ **@ntlworld.com > wrote:

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

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:
www.bdsoft.com/tools/stlfilt.html

[Leor Zolman]

On Mon, 5 Apr 2004 18:34:07 +0100, "richard.forres t1"
<ri************ **@ntlworld.com > wrote:

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

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:
www.bdsoft.com/tools/stlfilt.html

[Michael Klatt]

Leor Zolman <le**@bdsoft.co m> wrote in message news:<qt******* *************** **********@4ax. com>...

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

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.