473,327 Members | 2,071 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,327 software developers and data experts.

A non-const std::set iterator

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(container),
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_compare Compare;
if (Compare(*m_iterator, m_proxy) || Compare(m_proxy, *m_iterator))
{
// sort order will be changed
container.erase(m_iterator);
m_iterator = container.insert(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.
Jul 22 '05 #1
26 8672

"Michael Klatt" <md*****@ou.edu> wrote in message
news:2c**************************@posting.google.c om...
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.

Jul 22 '05 #2

"Michael Klatt" <md*****@ou.edu> wrote in message
news:2c**************************@posting.google.c om...
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.

Jul 22 '05 #3
On Mon, 5 Apr 2004 17:18:40 +0100, "Nick Hounsome" <nh***@blueyonder.co.uk>
wrote:

"Michael Klatt" <md*****@ou.edu> wrote in message
news:2c**************************@posting.google. 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>::iterator 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<int> > 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
Jul 22 '05 #4
On Mon, 5 Apr 2004 17:18:40 +0100, "Nick Hounsome" <nh***@blueyonder.co.uk>
wrote:

"Michael Klatt" <md*****@ou.edu> wrote in message
news:2c**************************@posting.google. 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>::iterator 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<int> > 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
Jul 22 '05 #5

"Leor Zolman" <le**@bdsoft.com> wrote in message
news:qt********************************@4ax.com...
On Mon, 5 Apr 2004 17:18:40 +0100, "Nick Hounsome" <nh***@blueyonder.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


Jul 22 '05 #6

"Leor Zolman" <le**@bdsoft.com> wrote in message
news:qt********************************@4ax.com...
On Mon, 5 Apr 2004 17:18:40 +0100, "Nick Hounsome" <nh***@blueyonder.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


Jul 22 '05 #7
On Mon, 5 Apr 2004 18:34:07 +0100, "richard.forrest1"
<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
Jul 22 '05 #8
On Mon, 5 Apr 2004 18:34:07 +0100, "richard.forrest1"
<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
Jul 22 '05 #9
Leor Zolman <le**@bdsoft.com> 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.
Jul 22 '05 #10
Leor Zolman <le**@bdsoft.com> 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.
Jul 22 '05 #11
"richard.forrest1" <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_criterion)
const int& sort_criterion;
}

int main()
{
std::map<FooKey, Foo> container;
Foo foo(10);
FooKey key(foo);
container.insert(std::make_pair(key, foo));
std::map<FooKey, Foo>::iterator it(map.find(foo));
it->second.sort_criterion = 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.
Jul 22 '05 #12
"richard.forrest1" <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_criterion)
const int& sort_criterion;
}

int main()
{
std::map<FooKey, Foo> container;
Foo foo(10);
FooKey key(foo);
container.insert(std::make_pair(key, foo));
std::map<FooKey, Foo>::iterator it(map.find(foo));
it->second.sort_criterion = 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.
Jul 22 '05 #13
"Michael Klatt" <md*****@ou.edu> wrote in message
news:2c**************************@posting.google.c om...
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(container),
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_compare Compare;
Don't forget "typedef typename ...". Anyway, don't you want to call
key_comp()?
if (Compare(*m_iterator, m_proxy) || Compare(m_proxy, *m_iterator))
{
// sort order will be changed
container.erase(m_iterator);
m_iterator = container.insert(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::reference::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::reference::operator= the set sends a signal to each of the
iterators.
Jul 22 '05 #14
"Michael Klatt" <md*****@ou.edu> wrote in message
news:2c**************************@posting.google.c om...
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(container),
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_compare Compare;
Don't forget "typedef typename ...". Anyway, don't you want to call
key_comp()?
if (Compare(*m_iterator, m_proxy) || Compare(m_proxy, *m_iterator))
{
// sort order will be changed
container.erase(m_iterator);
m_iterator = container.insert(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::reference::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::reference::operator= the set sends a signal to each of the
iterators.
Jul 22 '05 #15
"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.
Jul 22 '05 #16
"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.
Jul 22 '05 #17

"Michael Klatt" <md*****@ou.edu> wrote in message
news:2c*************************@posting.google.co m...
"richard.forrest1" <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
Jul 22 '05 #18

"Michael Klatt" <md*****@ou.edu> wrote in message
news:2c*************************@posting.google.co m...
"richard.forrest1" <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
Jul 22 '05 #19
"Siemel Naran" <Si*********@REMOVE.att.net> wrote in message news:<VN********************@bgtnsc05-news.ops.worldnet.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("dbname"); // manages records from a DBMS
rainfall.retrieve();
RainFile input;
RainRecord record;
while (input >> record)
{
RainSet::Iterator it(rainfall.find(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_compare 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::reference::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. :)
Jul 22 '05 #20
"Siemel Naran" <Si*********@REMOVE.att.net> wrote in message news:<VN********************@bgtnsc05-news.ops.worldnet.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("dbname"); // manages records from a DBMS
rainfall.retrieve();
RainFile input;
RainRecord record;
while (input >> record)
{
RainSet::Iterator it(rainfall.find(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_compare 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::reference::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. :)
Jul 22 '05 #21
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_compare Compare;
if (it == cont.end())
cont.insert(value);

if (Compare(*it, value) || Compare(value, *it))
{
cont.erase(it);
cont.insert(value);
}
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>::iterator 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
Jul 22 '05 #22
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_compare Compare;
if (it == cont.end())
cont.insert(value);

if (Compare(*it, value) || Compare(value, *it))
{
cont.erase(it);
cont.insert(value);
}
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>::iterator 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
Jul 22 '05 #23
"Michael Klatt" <md*****@ou.edu> wrote in message
news:2c**************************@posting.google.c om...
"Siemel Naran" <Si*********@REMOVE.att.net> wrote in message

news:<VN********************@bgtnsc05-news.ops.worldnet.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("dbname"); // manages records from a DBMS
rainfall.retrieve();
RainFile input;
RainRecord record;
while (input >> record)
{
RainSet::Iterator it(rainfall.find(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(record) 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_name. 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(const std::string&);
private:
const std::string d_firstname;
std::string d_favoritecolor;
};

Now just instantiate a std::vector<Record> 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_bound or std::upper_bound 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<boost::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::reference classes I suggested
previously don't even use proxy objects.
Jul 22 '05 #24
"Michael Klatt" <md*****@ou.edu> wrote in message
news:2c**************************@posting.google.c om...
"Siemel Naran" <Si*********@REMOVE.att.net> wrote in message

news:<VN********************@bgtnsc05-news.ops.worldnet.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("dbname"); // manages records from a DBMS
rainfall.retrieve();
RainFile input;
RainRecord record;
while (input >> record)
{
RainSet::Iterator it(rainfall.find(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(record) 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_name. 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(const std::string&);
private:
const std::string d_firstname;
std::string d_favoritecolor;
};

Now just instantiate a std::vector<Record> 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_bound or std::upper_bound 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<boost::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::reference classes I suggested
previously don't even use proxy objects.
Jul 22 '05 #25
"Siemel Naran" <Si*********@REMOVE.att.net> wrote in message news:<Hc********************@bgtnsc05-news.ops.worldnet.att.net>...
"Michael Klatt" <md*****@ou.edu> wrote in message
news:2c**************************@posting.google.c om...
"Siemel Naran" <Si*********@REMOVE.att.net> wrote in message news:<VN********************@bgtnsc05-news.ops.worldnet.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("dbname"); // manages records from a DBMS
rainfall.retrieve();
RainFile input;
RainRecord record;
while (input >> record)
{
RainSet::Iterator it(rainfall.find(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(record) 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("dbname");
RainSet::Filter filter;
filter.timestamp(begin, end).period(daily);
rainfall.filter(filter);
rainfall.retrieve(); // 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.
Jul 22 '05 #26
"Siemel Naran" <Si*********@REMOVE.att.net> wrote in message news:<Hc********************@bgtnsc05-news.ops.worldnet.att.net>...
"Michael Klatt" <md*****@ou.edu> wrote in message
news:2c**************************@posting.google.c om...
"Siemel Naran" <Si*********@REMOVE.att.net> wrote in message news:<VN********************@bgtnsc05-news.ops.worldnet.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("dbname"); // manages records from a DBMS
rainfall.retrieve();
RainFile input;
RainRecord record;
while (input >> record)
{
RainSet::Iterator it(rainfall.find(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(record) 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("dbname");
RainSet::Filter filter;
filter.timestamp(begin, end).period(daily);
rainfall.filter(filter);
rainfall.retrieve(); // 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.
Jul 22 '05 #27

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

5
by: Leif K-Brooks | last post by:
Is there a word for an iterable object which isn't also an iterator, and therefor can be iterated over multiple times without being exhausted? "Sequence" is close, but a non-iterator iterable could...
38
by: Grant Edwards | last post by:
In an interview at http://acmqueue.com/modules.php?name=Content&pa=showpage&pid=273 Alan Kay said something I really liked, and I think it applies equally well to Python as well as the languages...
5
by: Jacob Page | last post by:
I have released interval-0.2.1 at http://members.cox.net/apoco/interval/. IntervalSet and FrozenIntervalSet objects are now (as far as I can tell) functionality equivalent to set and frozenset...
9
by: Alexander Stippler | last post by:
Hi, I've got trouble with some well known issue. Iterator invalidation. My situation: for (it=v.begin(); it!=v.end(); ++it) { f(*it); } Under some circumstances, f may alter the container...
7
by: andreas | last post by:
Hello, I have a problem with iterators in a fairly complex polygonal mesh data structure which is implemented using lists of geometric entities. However, the problem in itself is fairly simple:...
19
by: fungus | last post by:
I mentioned earlier to day that I was moving some code from VC++6 to VC++2005 and having trouble with the new iterators. There's all sorts of problems cropping up in the code thanks to this...
27
by: Steven D'Aprano | last post by:
I thought that an iterator was any object that follows the iterator protocol, that is, it has a next() method and an __iter__() method. But I'm having problems writing a class that acts as an...
1
by: tonylamb | last post by:
Hi All, I seem to be getting an error with my code when running Intel C++ compiler via Visual Studio 2005. The error generated is "Expression:map/set iterator not dereferencable" I've given my code...
13
by: Yosifov Pavel | last post by:
Whats is the way to clone "independent" iterator? I can't use tee(), because I don't know how many "independent" iterators I need. copy and deepcopy doesn't work... --pavel
5
by: Luis Zarrabeitia | last post by:
Hi there. For most use cases I think about, the iterator protocol is more than enough. However, on a few cases, I've needed some ugly hacks. Ex 1: a = iter() # assume you got the iterator...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.