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]

"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. :)

[Leor Zolman]

On 6 Apr 2004 08:50:36 -0700, md*****@ou.edu (Michael Klatt) wrote:

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. :)

Well, I was playing around a bit, thinking a little utility for replacing a
value of an associative container might be useful in its own right, and got
as far as this for sets (warning: For testing, I use some non-standard
utility libs for initializing and displaying contents of containers. These
are all available in my InitUtil distributions):

#include <iostream>
#include <set>

#include "ESTLUtil.h " // Utils for initializing
#include "InitUtil.h " // and displaying containers
using namespace bds;
using namespace ESTLUtils;

using namespace std;

template<class Cont, class It, class T>
void xreplace(Cont &cont, It it, const T &value)
{
typename Cont::key_compa re Compare;
if (it == cont.end())
cont.insert(val ue);

if (Compare(*it, value) || Compare(value, *it))
{
cont.erase(it);
cont.insert(val ue);
}
else
const_cast<T&>( *it) = value;
}

int main()
{
// (From InitUtil: stuff values into a container)
set<int> s = make_cont("1,1, 3,9,143,207, 194, 195, 199, 200");
// (From ESTLUtils: display contents of a container
printContainer( "s Before xreplace: ", s);

set<int>::itera tor it = find(s.begin(), s.end(), 194);
if (it == s.end())
cout << "Whoops, no 194 to replace" << endl;
else
xreplace(s, it, 50);

printContainer( "After xreplacing 194 with 50: ", s);

return 0;
}

So the "xreplace" function template is the boiled-down essence of your
Iterator class (actually, of your sync() function for the most part).

It seems to work for sets and multisets; I tried to get it to work for maps
as well, but didn't quite get to the bottom of why it doesn't (probably
just some stupid fundamental property of maps I'm spacing on, because I'm
getting an error from deep in the bowels of the STL about a missing
operator== somewhere...).

Anyway, perhaps this little xreplace template might be useful to someone,
or least be the basis for something useful.
Cheers,
-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 6 Apr 2004 08:50:36 -0700, md*****@ou.edu (Michael Klatt) wrote:

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. :)

Well, I was playing around a bit, thinking a little utility for replacing a
value of an associative container might be useful in its own right, and got
as far as this for sets (warning: For testing, I use some non-standard
utility libs for initializing and displaying contents of containers. These
are all available in my InitUtil distributions):

#include <iostream>
#include <set>

#include "ESTLUtil.h " // Utils for initializing
#include "InitUtil.h " // and displaying containers
using namespace bds;
using namespace ESTLUtils;

using namespace std;

template<class Cont, class It, class T>
void xreplace(Cont &cont, It it, const T &value)
{
typename Cont::key_compa re Compare;
if (it == cont.end())
cont.insert(val ue);

if (Compare(*it, value) || Compare(value, *it))
{
cont.erase(it);
cont.insert(val ue);
}
else
const_cast<T&>( *it) = value;
}

int main()
{
// (From InitUtil: stuff values into a container)
set<int> s = make_cont("1,1, 3,9,143,207, 194, 195, 199, 200");
// (From ESTLUtils: display contents of a container
printContainer( "s Before xreplace: ", s);

set<int>::itera tor it = find(s.begin(), s.end(), 194);
if (it == s.end())
cout << "Whoops, no 194 to replace" << endl;
else
xreplace(s, it, 50);

printContainer( "After xreplacing 194 with 50: ", s);

return 0;
}

So the "xreplace" function template is the boiled-down essence of your
Iterator class (actually, of your sync() function for the most part).

It seems to work for sets and multisets; I tried to get it to work for maps
as well, but didn't quite get to the bottom of why it doesn't (probably
just some stupid fundamental property of maps I'm spacing on, because I'm
getting an error from deep in the bowels of the STL about a missing
operator== somewhere...).

Anyway, perhaps this little xreplace template might be useful to someone,
or least be the basis for something useful.
Cheers,
-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

[Siemel Naran]

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

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

What does the function rainfall.find(r ecord) do? Does it issue a new SQL
statement to find a particular record? This could be slow if 'input'
contains many records, as you'll issue individual queries to find each
record. Is it possible to open a SQL cursor, and in RainSet::find scan the
cursor to find a particular record, which will normally take O(lg(N)) time
given an appropriate index? Alternately, you could read many records from
the database into memory using a smart WHERE statement (ie. select * from
contact where name in ('Siemel', 'Michael') or select * from contact where
home_city = 'San Francisco').

In any case, the database contains more records than can fit into memory.

Assuming you read many records into memory and that you update columns that
don't affect the sort order, I think the generic class Iterator<Set>
solution is overkill. All you need is a struct of const data and non-const
data, which is what I think John was suggesting in his reply. For example,
suppose we want to update the favorite color of many people, and we query
for people by first_name. Then issue a select statement "select first_name,
favorite_color from contact where home_city = ? order by first_name" which
should use the index on contact.first_n ame. Read all records into memory.

class Record {
public:
Record(const std::string& firstname, const std::string& favoritecolor);
const std::string& firstname() const;
const std::string& favoritecolor() const;
void favoritecolor(c onst std::string&);
private:
const std::string d_firstname;
std::string d_favoritecolor ;
};

Now just instantiate a std::vector<Rec ord> and read the SQL select results
already sorted by first_name into memory. The firstname is readonly, so you
can't possibly screw up the sort order (well, there is placement new and
delete, but that's wizadry). But favorite color is editable. Use
std::lower_boun d or std::upper_boun d to locate records in the vector. Only
one catch: class Record does not have an operator= (for classes with const
data the compiler generated operator= fails to compile), and therefore it
can't be used in a standard container. You could always use a (smart)
pointer to Data though, like a std::vector<boo st::shared_ptr< Record> >.

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.

I think if the first condition is true, then the second condition ought to
be true. The iterator and iterator::refer ence classes I suggested
previously don't even use proxy objects.

[Siemel Naran]

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

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

What does the function rainfall.find(r ecord) do? Does it issue a new SQL
statement to find a particular record? This could be slow if 'input'
contains many records, as you'll issue individual queries to find each
record. Is it possible to open a SQL cursor, and in RainSet::find scan the
cursor to find a particular record, which will normally take O(lg(N)) time
given an appropriate index? Alternately, you could read many records from
the database into memory using a smart WHERE statement (ie. select * from
contact where name in ('Siemel', 'Michael') or select * from contact where
home_city = 'San Francisco').

In any case, the database contains more records than can fit into memory.

Assuming you read many records into memory and that you update columns that
don't affect the sort order, I think the generic class Iterator<Set>
solution is overkill. All you need is a struct of const data and non-const
data, which is what I think John was suggesting in his reply. For example,
suppose we want to update the favorite color of many people, and we query
for people by first_name. Then issue a select statement "select first_name,
favorite_color from contact where home_city = ? order by first_name" which
should use the index on contact.first_n ame. Read all records into memory.

class Record {
public:
Record(const std::string& firstname, const std::string& favoritecolor);
const std::string& firstname() const;
const std::string& favoritecolor() const;
void favoritecolor(c onst std::string&);
private:
const std::string d_firstname;
std::string d_favoritecolor ;
};

Now just instantiate a std::vector<Rec ord> and read the SQL select results
already sorted by first_name into memory. The firstname is readonly, so you
can't possibly screw up the sort order (well, there is placement new and
delete, but that's wizadry). But favorite color is editable. Use
std::lower_boun d or std::upper_boun d to locate records in the vector. Only
one catch: class Record does not have an operator= (for classes with const
data the compiler generated operator= fails to compile), and therefore it
can't be used in a standard container. You could always use a (smart)
pointer to Data though, like a std::vector<boo st::shared_ptr< Record> >.

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.

I think if the first condition is true, then the second condition ought to
be true. The iterator and iterator::refer ence classes I suggested
previously don't even use proxy objects.

[Michael Klatt]

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

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

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

What does the function rainfall.find(r ecord) do? Does it issue a new SQL
statement to find a particular record?

A RainSet is a container for database records, with the usual
container funtionality (such as RainSet::find) plus the ability to
retrieve and store database records via SQL.

Alternately, you could read many records from
the database into memory using a smart WHERE statement (ie. select * from
contact where name in ('Siemel', 'Michael') or select * from contact where
home_city = 'San Francisco').

There is a RainSet::Filter class for this purpose:

RainSet rainfall("dbnam e");
RainSet::Filter filter;
filter.timestam p(begin, end).period(dai ly);
rainfall.filter (filter);
rainfall.retrie ve(); // executes SELECT ... WHERE query on database

Assuming you read many records into memory and that you update columns that
don't affect the sort order, I think the generic class Iterator<Set>
solution is overkill.
Agreed.
All you need is a struct of const data and non-const
data, which is what I think John was suggesting in his reply.

Yes, I am giving this suggestion some thought.

[Michael Klatt]

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

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

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

What does the function rainfall.find(r ecord) do? Does it issue a new SQL
statement to find a particular record?

A RainSet is a container for database records, with the usual
container funtionality (such as RainSet::find) plus the ability to
retrieve and store database records via SQL.

Alternately, you could read many records from
the database into memory using a smart WHERE statement (ie. select * from
contact where name in ('Siemel', 'Michael') or select * from contact where
home_city = 'San Francisco').

There is a RainSet::Filter class for this purpose:

RainSet rainfall("dbnam e");
RainSet::Filter filter;
filter.timestam p(begin, end).period(dai ly);
rainfall.filter (filter);
rainfall.retrie ve(); // executes SELECT ... WHERE query on database

Assuming you read many records into memory and that you update columns that
don't affect the sort order, I think the generic class Iterator<Set>
solution is overkill.
Agreed.
All you need is a struct of const data and non-const
data, which is what I think John was suggesting in his reply.

Yes, I am giving this suggestion some thought.