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.

[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.

[Michael Klatt]

"richard.forres t1" <ri************ **@ntlworld.com > wrote in message news:<KFhcc.210 $Xi.34@newsfe1-win>...

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.

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]

"richard.forres t1" <ri************ **@ntlworld.com > wrote in message news:<KFhcc.210 $Xi.34@newsfe1-win>...

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.

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]

"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:
Your code is mostly sound. In what scenario do you find this useful?

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(); }
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 :).
private :
void sync();
Set& m_container;
SetIterator m_iterator;
T m_proxy;
};
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.
template <class Set>
Iterator<Set>:: Iterator(Set& container, const SetIterator& it) :
m_container(con tainer),
m_iterator(it)
m_proxy(*it) {}
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().
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;
}
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?

template <class Set>
void Iterator<Set>:: sync()
{
typedef Set::key_compar e Compare;
Don't forget "typedef typename ...". Anyway, don't you want to call
key_comp()?
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;
}
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.
return;
}
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.

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.

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]

"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:
Your code is mostly sound. In what scenario do you find this useful?

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(); }
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 :).
private :
void sync();
Set& m_container;
SetIterator m_iterator;
T m_proxy;
};
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.
template <class Set>
Iterator<Set>:: Iterator(Set& container, const SetIterator& it) :
m_container(con tainer),
m_iterator(it)
m_proxy(*it) {}
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().
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;
}
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?

template <class Set>
void Iterator<Set>:: sync()
{
typedef Set::key_compar e Compare;
Don't forget "typedef typename ...". Anyway, don't you want to call
key_comp()?
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;
}
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.
return;
}
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.

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.

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]

"Michael Klatt" <md*****@ou.edu > wrote in message

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.

Sometimes a less ambitious solution is better than an over-engineered
solution. The code will probably be easier to write and understand and
maintain, and will have fewer bugs, and might even run faster though it
could very well run slower too. Pre-mature optimization also falls into
this category.

[Siemel Naran]

"Michael Klatt" <md*****@ou.edu > wrote in message

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.

Sometimes a less ambitious solution is better than an over-engineered
solution. The code will probably be easier to write and understand and
maintain, and will have fewer bugs, and might even run faster though it
could very well run slower too. Pre-mature optimization also falls into
this category.

[John Harrison]

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

"richard.forres t1" <ri************ **@ntlworld.com > wrote in message news:<KFhcc.210 $Xi.34@newsfe1-win>...

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.

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?

1) Break Foo up into FooKey and FooValue.

2) Use pointers, std::set and std::map won't be fussy about changing what's
at the end of a pointer provided the pointer itself doesn't change.

3) Use const_cast.

1 is of course the correct solution.

john

[John Harrison]

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

"richard.forres t1" <ri************ **@ntlworld.com > wrote in message news:<KFhcc.210 $Xi.34@newsfe1-win>...

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.

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?

1) Break Foo up into FooKey and FooValue.

2) Use pointers, std::set and std::map won't be fussy about changing what's
at the end of a pointer provided the pointer itself doesn't change.

3) Use const_cast.

1 is of course the correct solution.

john

[Michael Klatt]

"Siemel Naran" <Si*********@RE MOVE.att.net> wrote in message news:<VN******* *************@b gtnsc05-news.ops.worldn et.att.net>...

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

This is all part of a database framework. When I add a record to the
database I need to determine if it's a new record or a correction for
an existing record. In the latter case I need to overwrite parts of
the existing record while preserving the key information:

RainSet rainfall("dbnam e"); // manages records from a DBMS
rainfall.retrie ve();
RainFile input;
RainRecord record;
while (input >> record)
{
RainSet::Iterat or it(rainfall.fin d(record));
if (it != rainfall.end())
{
// update existing record
it->amount(record. amount());
}
else
{
rainfall.insert (record);
}
}
rainfall.store( );

I currently use a std::list as the underlying container for a RainSet,
but I have to rely on the DBMS for all of my sorting. This, as well
as finding specific records, is too slow for large datasets. Thus, I
would like to use a sorted container like a std::set or std::map. In
the example I gave above, the changes I make to a record will not
effect its sort order.

template <class Set> // Set is an instance of std::set<>
class Iterator

I posted this example mainly as an illustration of what I was trying
to with the snyc() function. I should have mentioned that it wasn't
intended to be fully functional yet.


What about operator== and operator!=. I guess we want to be able to use
these iterators :).

Of course, and the following question arises: What should the
semantics of comparison be? Are two Iterators equivalent if they
point to the same element (m_iterator == rhs.m_iterator) or does the
proxy object have to be the same too?
I can imagine cases where either comparison is desired.

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().
Yes, I forgot to account for an empty container in the constructor at
first and got a segmentation fault. Using set.begin() as a default
value is a good idea.


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?
Yet another problem I found yesterday. I did indeed change
m_container from a reference to a pointer.

template <class Set>
void Iterator<Set>:: sync()
{
typedef Set::key_compar e Compare;
Don't forget "typedef typename ...". Anyway, don't you want to call
key_comp()?

Yes and yes. Two more problems fixed.
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.
This is a good idea, but since I'm potentially accessing ~2 million
(and growing) records from a DBMS and inserting them into a std::set I
don't know how much time it will save.
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.
At this time, the only use I have for modifying values through an
Iterator is similar to my example above where an Iterator is obtained
through a find(). Of course, that doesn't mean I won't try to do
something silly with it in the future. For now, I think I'm going to
add a replace() method to my container instead of trying to make
modifications through an iterator.

Another problem is when to commit.

And yet another reason, I think, to shelve my mutable iterator.

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.

I had orinially wanted to create a simple (ha!) and straightforward
(ha!) way to modify elements of a set. Now that we've started talking
about smart references I know that I'm on the wrong track.

After reading this thread and thinking about it some more, I don't
have a really compelling reason for a mutable set iterator. It turns
out that the people who put together the Standard Library are smarter
than me after all. :)