NJ Biggs (njb1441@ggr.co.uk) wrote:
: I am new to STL and am after a little help.

Join the club...

: Can anyone please post a short example of using the set_union algorithm on
: two set<int> objects that places the result in a third set<int>.

: Sort of...
: set<int> s1;
: set<int> s2;
: set<int> result;

: set_union(s1.begin(), s1.end(), s2.begin(), s2.end(), result.end());

Firstly, you should have the destination iterator (the 5th arg) being at
the start of where you wish the output to go. Secondly, the container must
have space to put the items in. Thirdly, I can't see how it can work for
ordered containers.

Re-forming your code:
    set<int> s1;
    set<int> s2;
    vector<int> result(s1.size() + s2.size());
    vector<int>::const_iterator it_last;
    ostream_iterator it_out(cout, "\n");

    it_last = set_union(s1.begin(), s1.end(),
        s2.begin(), s2.end(), result.begin());

    // Display the result:
    copy(result.begin(), it_last, it_out);

    // or make a new set:
    set<int> s3(result.begin(), it_last);

In this code, I made the destination big enough to hold the largest
possible number of elements. It seems terribly kludgy though.

I wish there was a better way to do this though. What I would like is to
have some pseudo-iterator which knows about the whole container, so can
therefore call container->insert() when the set_union() code assigns to
it. In fact, I would like to be able to do what ostream_iterator does:

    set_union(s1.begin(), s1.end(), s2.begin(), s2.end(), it_out);

Can any gurus tell me how I can get this to occur for iterators for sets,
etc ?

TIA,
Andrew
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <6i9dgp$a2n$1@mulga.cs.mu.oz.au>,
Andrew_J ROBBIE <ajrobb@ecr.mu.oz.au> wrote:
>NJ Biggs (njb1441@ggr.co.uk) wrote:
>
>: Can anyone please post a short example of using the set_union algorithm on
>: two set<int> objects that places the result in a third set<int>.
>
>: Sort of...
>: set<int> s1;
>: set<int> s2;
>: set<int> result;
>
>: set_union(s1.begin(), s1.end(), s2.begin(), s2.end(), result.end());
>
>Firstly, you should have the destination iterator (the 5th arg) being at
>the start of where you wish the output to go. Secondly, the container must
>have space to put the items in. Thirdly, I can't see how it can work for
>ordered containers.
>
>Re-forming your code:
>    set<int> s1;
>    set<int> s2;
>    vector<int> result(s1.size() + s2.size());
>    vector<int>::const_iterator it_last;
>    ostream_iterator it_out(cout, "\n");
>
>    it_last = set_union(s1.begin(), s1.end(),
>        s2.begin(), s2.end(), result.begin());
>
>    set<int> s3(result.begin(), it_last);
>


Andrew's diagnosis is correct, but there is a simpler solution.

The inserter<> template produces an iterator that, when written to,
invokes a container's insert() function.

set<int> s1;
set<int> s2;
set<int> result;
  ...
set_union(s1.begin(), s1.end(),
          s2.begin(), s2.end(),
          inserter(result, result.end());

SJZ



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <6i9dgp$a2n$1@mulga.cs.mu.OZ.AU>#1/1,
  ajrobb@ecr.mu.oz.au (Andrew_J ROBBIE) wrote:
>
> NJ Biggs (njb1441@ggr.co.uk) wrote:
>
   [-cut-]
> Firstly, you should have the destination iterator (the 5th arg) being at
> the start of where you wish the output to go. Secondly, the container must
> have space to put the items in. Thirdly, I can't see how it can work for
> ordered containers.
   [-cut-]
> I wish there was a better way to do this though. What I would like is to
> have some pseudo-iterator which knows about the whole container, so can
> therefore call container->insert() when the set_union() code assigns to
> it. In fact, I would like to be able to do what ostream_iterator does:
>
>     set_union(s1.begin(), s1.end(), s2.begin(), s2.end(), it_out);
>
> Can any gurus tell me how I can get this to occur for iterators for sets,
> etc ?

What you are looking for are "instert iterators".  These iterators know
how to insert elements into a container.  There are back insert iterators
(which basically do a push_back()), front insert iterators, and plain
ol' insert iterators.

Re-forming your code:
    std::set<int> s1;
    std::set<int> s2;
    std::set<int> result_set;
    std::ostream_iterator it_out( std::cout, "\n" );

    std::set_union( s1.begin(), s1.end(), s2.begin(), s2.end(),
                    std::back_inserter( result_set ) );

    copy(result.begin(), result.end(), it_out);

If you don't want to put the result of set_union into a temporary
set, but would rather send the results directly to a ostream, then
you can just use it_out instead of the back insert iterator:

    std::set_union( s1.begin(), s1.end(), s2.begin(), s2.end(),
                    it_out );

The set algorithms in the STL are very useful.  I wrote a little command
line utility that takes two files, reads them each into a set of strings
(one line per string), then performs a set algorithm (specified on the
command line) and sends the result to std::cout.

I have some data files and I want to see the intersection, difference, etc.
of the data in the files.  I found it easier to write a little C++ program
to solve this problem then importing the data into Excel and munging the
data in there.  I found it easier to write this utility in C++ rather than
a scripting language (such as Perl) mainly becuase of the set alogirthms
in C++.


Aaron



-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/   Now offering spam-free web-based newsreading
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

James Kuyper <kuyper@wizard.net> writes:

> Oleg Zabluda wrote:
> >
> > James Kuyper <kuyper@wizard.net> wrote:

> > : If a non-const iterator were implementable for set<>, then (*i)=b should
> > : be the equivalent of erase(i) followed by an insert(b). This would be of
> > : neglible importance in typical uses of sets, but would allow modifying
> > : algorithms to be applied to sets without being aware of the special
> > : characteristics of sets.
> >
> > You can easily provide such an iterator yourself. Call it
> > replace_iterator<Iterator>. And the corresponding function
> > replacer(Iterator).
> >
> > Just a thought.
>
> What operator overload do you place the insert() call in?

Let's call the new iterator 'mutable_set_iterator'.

You can overload mutable_set_iterator::operator=
(const element_type&).

mutable_set_iterator::operator* can return *this (as
in insert_iterator).

This is technically possible but:
- IMO changing set::iterator to mutable_set_iterator
  is a bad idea
- it breaks the iterator requirements (already broken by
  insert_iterator, I know)

--

Valentin Bonnard                mailto:bonnardv@pratique.fr
info about C++/a propos du C++: http://pages.pratique.fr/~bonnardv/


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

James Kuyper <kuyper@wizard.net> writes:

> If you override mutable_set_iterator::operator*() to return *this, then
> how do you do the following:
>
> void func(mutable_set_iterator i)
> {
>  (*i)->member_function();
> }
>
> You could make this work by defining set<T>::iterator to be a
> mutable_set_iterator derived from T. However, when T is a class type
> such as 'long' or 'MyClass *', you cannot derive from it.

You could define mutable_set_iterator::operator T(). But as
no conversion will be done for (*i).member and operator. can't
be overloaded, this isn't very good.

I have never said that it was a good idea to
create mutable_set_iterator.

--

Valentin Bonnard                mailto:bonnardv@pratique.fr
info about C++/a propos du C++: http://pages.pratique.fr/~bonnardv/


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

James Kuyper wrote:
>
> > James Kuyper <kuyper@wizard.net> writes:
> >
> > > Oleg Zabluda wrote:
> > > >
> > > > James Kuyper <kuyper@wizard.net> wrote:
> >
> > > > : If a non-const iterator were implementable for set<>, then (*i)=b should
> > > > : be the equivalent of erase(i) followed by an insert(b). This would be of
> > > > : neglible importance in typical uses of sets, but would allow modifying
> > > > : algorithms to be applied to sets without being aware of the special
> > > > : characteristics of sets.
> > > >
> > > > You can easily provide such an iterator yourself. Call it
> > > > replace_iterator<Iterator>. And the corresponding function
> > > > replacer(Iterator).
> > > >
> > > > Just a thought.
> > >
> > > What operator overload do you place the insert() call in?
> >
> > Let's call the new iterator 'mutable_set_iterator'.
> >
> > You can overload mutable_set_iterator::operator=
> > (const element_type&).
> >
> > mutable_set_iterator::operator* can return *this (as
> > in insert_iterator).
> >
> > This is technically possible but:
> > - IMO changing set::iterator to mutable_set_iterator
> >   is a bad idea
> > - it breaks the iterator requirements (already broken by
> >   insert_iterator, I know)
> >
>
> If you override mutable_set_iterator::operator*() to return *this, then
> how do you do the following:
>
> void func(mutable_set_iterator i)
> {
>         (*i)->member_function();
> }

Sorry, I got a little mixed up. The '->' should have been '.'. As such,
it cannot be gotten around by defining an appropriate cast function. The
result of *i is supposed to be a T&, and no C++ class can be a true
reference object.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

James Kuyper <kuyper@wizard.net> wrote:
: Matt Austern wrote:
: ...
: > I can understand wanting set<>::iterator and set<>::const_iterator to
: > be distinct types, just for the sake of stricter type-checking.  (The
: > standard neither requires nor forbids them to be distinct types.)
: >
: > I can't, though, understand wanting set<>::iterator to be a modifiable
: > iterator.  The whole point of set<> (and all of the other associative

: If a non-const iterator were implementable for set<>, then (*i)=b should
: be the equivalent of erase(i) followed by an insert(b). This would be of
: neglible importance in typical uses of sets, but would allow modifying
: algorithms to be applied to sets without being aware of the special
: characteristics of sets.

You can easily provide such an iterator yourself. Call it
replace_iterator<Iterator>. And the corresponding function
replacer(Iterator).

Just a thought.

Oleg.
--
Life is a sexually transmitted, 100% lethal disease.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

James Kuyper <kuyper@wizard.net> writes:

> Matt Austern wrote:

> > I can't, though, understand wanting set<>::iterator to be a modifiable
> > iterator.  The whole point of set<> (and all of the other associative
>
> If a non-const iterator were implementable for set<>, then (*i)=b should
> be the equivalent of erase(i) followed by an insert(b).

What you describe isn't exactly an iterator, as all iterator
operations are O(1), not O(ln(n)).

--

Valentin Bonnard                mailto:bonnardv@pratique.fr
info about C++/a propos du C++: http://pages.pratique.fr/~bonnardv/
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Valentin Bonnard <bonnardv@pratique.fr> wrote:
: James Kuyper <kuyper@wizard.net> writes:

: > Matt Austern wrote:

: > > I can't, though, understand wanting set<>::iterator to be a modifiable
: > > iterator.  The whole point of set<> (and all of the other associative
: >
: > If a non-const iterator were implementable for set<>, then (*i)=b should
: > be the equivalent of erase(i) followed by an insert(b).

: What you describe isn't exactly an iterator, as all iterator
: operations are O(1), not O(ln(n)).

Operations on insert_iterator, for example, can be O(anything).

Oleg.
--
Life is a sexually transmitted, 100% lethal disease.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Oleg Zabluda wrote:
>
> Valentin Bonnard <bonnardv@pratique.fr> wrote:
> : James Kuyper <kuyper@wizard.net> writes:
>
> : > Matt Austern wrote:
>
> : > > I can't, though, understand wanting set<>::iterator to be a modifiable
> : > > iterator.  The whole point of set<> (and all of the other associative
> : >
> : > If a non-const iterator were implementable for set<>, then (*i)=b should
> : > be the equivalent of erase(i) followed by an insert(b).
>
> : What you describe isn't exactly an iterator, as all iterator
> : operations are O(1), not O(ln(n)).
>
> Operations on insert_iterator, for example, can be O(anything).

However, all required iterator functions are supposed to take constant
amortized time. insert_iterators are supposed to meet the Output
iterator requirements in table 74, and *a=t is one of those
requirements. How this can be achieved when the target container is, for
instance, vector<int>, is unclear to me.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Oleg Zabluda wrote:
>
> James Kuyper <kuyper@wizard.net> wrote:
> : Matt Austern wrote:
> : ...
> : > I can understand wanting set<>::iterator and set<>::const_iterator to
> : > be distinct types, just for the sake of stricter type-checking.  (The
> : > standard neither requires nor forbids them to be distinct types.)
> : >
> : > I can't, though, understand wanting set<>::iterator to be a modifiable
> : > iterator.  The whole point of set<> (and all of the other associative
>
> : If a non-const iterator were implementable for set<>, then (*i)=b should
> : be the equivalent of erase(i) followed by an insert(b). This would be of
> : neglible importance in typical uses of sets, but would allow modifying
> : algorithms to be applied to sets without being aware of the special
> : characteristics of sets.
>
> You can easily provide such an iterator yourself. Call it
> replace_iterator<Iterator>. And the corresponding function
> replacer(Iterator).
>
> Just a thought.

What operator overload do you place the insert() call in?
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

James Kuyper <kuyper@wizard.net> wrote:
: Oleg Zabluda wrote:
: >
: > James Kuyper <kuyper@wizard.net> wrote:

: > : If a non-const iterator were implementable for set<>, then (*i)=b should
: > : be the equivalent of erase(i) followed by an insert(b). This would be of
: > : neglible importance in typical uses of sets, but would allow modifying
: > : algorithms to be applied to sets without being aware of the special
: > : characteristics of sets.
: >
: > You can easily provide such an iterator yourself. Call it
: > replace_iterator<Iterator>. And the corresponding function
: > replacer(Iterator).
: >
: > Just a thought.

: What operator overload do you place the insert() call in?

You'd have to use a typical proxy idiom, just like any other
output iterator does now.

Oleg.
--
Life is a sexually transmitted, 100% lethal disease.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

> James Kuyper <kuyper@wizard.net> writes:
>
> > Oleg Zabluda wrote:
> > >
> > > James Kuyper <kuyper@wizard.net> wrote:
>
> > > : If a non-const iterator were implementable for set<>, then (*i)=b should
> > > : be the equivalent of erase(i) followed by an insert(b). This would be of
> > > : neglible importance in typical uses of sets, but would allow modifying
> > > : algorithms to be applied to sets without being aware of the special
> > > : characteristics of sets.
> > >
> > > You can easily provide such an iterator yourself. Call it
> > > replace_iterator<Iterator>. And the corresponding function
> > > replacer(Iterator).
> > >
> > > Just a thought.
> >
> > What operator overload do you place the insert() call in?
>
> Let's call the new iterator 'mutable_set_iterator'.
>
> You can overload mutable_set_iterator::operator=
> (const element_type&).
>
> mutable_set_iterator::operator* can return *this (as
> in insert_iterator).
>
> This is technically possible but:
> - IMO changing set::iterator to mutable_set_iterator
>   is a bad idea
> - it breaks the iterator requirements (already broken by
>   insert_iterator, I know)
>

If you override mutable_set_iterator::operator*() to return *this, then
how do you do the following:

void func(mutable_set_iterator i)
{
 (*i)->member_function();
}

You could make this work by defining set<T>::iterator to be a
mutable_set_iterator derived from T. However, when T is a class type
such as 'long' or 'MyClass *', you cannot derive from it.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Valentin Bonnard <bonnardv@pratique.fr> wrote:
: Oleg Zabluda wrote:

: > I just want it to be non-convertible to set<>::const_iterator.

: I understand your opinion. You may also want cont<T>::iterator
: not to be convertible to cont<U>::iterator, for any T != U,
: which would mean that vector::iterator can't be a pointer.

Right. The often used ``typedef T* vector<T>::iterator''
is a disaster, because it does not preclude
vector<Derived>::iterator ==> vector<Base>::iterator
conversions.

However, I wouldn't mind a conversion from
cont<Derived*>::iterator to cont<Base*>::iterator. But
since there is no way to express it in C++, I don't
wish for it.

Note also that the standard does not say that if
cont1 and cont2 are different containers, then
cont1<T>::iterator must be non-convertible to
cont2<T>::iterator (see later).

: I think it's should be possible to avoid direct use of primitive
: types entirely, but it's too early to impose that given the fact
: that using an object (class) instead of a built-in incurs a penalty
: under a number of compilers.

Well, at least the non-convertability from const_iterator to
iterator can be imposed. It's the single largest defect in
STL, I know of.

STL is a curious part of C++ in this respect. In the rest of the
language and stdlib, a lot of work was put into a stronger type
system and const correctness. Many old C functions were duplicated
to provide const-correct versions. While in STL elementary
const-correctness is not mandated. The most notable manifestation
of this is the Plauger's library, shipped with MSVC++, where
const_iterator's are freely convertible to iterator's for all
containers, and it's 100% compliant. To add insult to injury,
set<T>::iterator is convertible to map<U>::iterator for all
T and U. No kidding. And, again, it's 100% compliant.

Oleg.
--
Life is a sexually transmitted, 100% lethal disease.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Matt Austern wrote:

> I can't, though, understand wanting set<>::iterator to be a modifiable
> iterator.  The whole point of set<> (and all of the other associative
> containers) is that the position of an element depends on the
> element's key.  In the case of set<>, for example, the two crucial
> class invariants are
>   -- No element appears more than once;
>   -- The elements are sorted in strictly ascending order.
>
> If you could modify the elements once they had been inserted, then
> there would be no way for set<> to maintain those two invariants.
> Part of the design of set<> is that elements may be inserted and
> erased, but, once inserted, they may not be changed.

There are still some rare cases where one wants to operate a
transformation on all the elements of the set knowing that the
ordering  will not be changed by the operation....  This might be not
so uncommnon with complex  data structures and partial ordering on
those. We actually run on this problem very recently  (for representing
big sparse polynomials and multiplying them by a constant scale factor)
and it was quite annoying because a work-around involves a lot of
penalty, implies playing with const_cast a lot or requires a modified
set class (which is the ugly solution we have chosen for now).

Now, I understand that the provided behavior is safer  but:

- Is the stl is required to be totally foolproof or is it meant to be
  flexible ?
- With the standard not specifying the proper choice, what is the risk of
  ending up with uncompatible set designs with this respect. I (maybe)
  wrongly interpret the lack of constraint on set<>::iterator in the
  standard as to have it behave like other container::iterator i.e. to
  allow modification. This will be error prone for sure but more
  orthogonal and it can be useful.
- My prefered choice would be  to add another iterator to each  of the
  container which will always allow modifications (let's call it
  container<>::mutable_iterator) and define iterator as either
  const_iterator or mutable_iterator depending on the safety of the
  class.  Can this scheme be in compliance with the standard ?

Theo.
--
--------------------------------------------------------------------------------
        Theodore Papadopoulo (papadop@sophia.inria.fr)

   Projet Robotvis, INRIA - Sophia Antipolis,
   2004, route des Lucioles, BP 93, 06902 Sophia Antipolis Cedex -- FRANCE
   Phone: (33) 04 92 38 76 01, Fax: (33) 04 92 38 78 45
--------------------------------------------------------------------------------
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Matt Austern wrote:
...
> I can understand wanting set<>::iterator and set<>::const_iterator to
> be distinct types, just for the sake of stricter type-checking.  (The
> standard neither requires nor forbids them to be distinct types.)
>
> I can't, though, understand wanting set<>::iterator to be a modifiable
> iterator.  The whole point of set<> (and all of the other associative

If a non-const iterator were implementable for set<>, then (*i)=b should
be the equivalent of erase(i) followed by an insert(b). This would be of
neglible importance in typical uses of sets, but would allow modifying
algorithms to be applied to sets without being aware of the special
characteristics of sets.

> containers) is that the position of an element depends on the
> element's key.  In the case of set<>, for example, the two crucial
> class invariants are
>   -- No element appears more than once;
>   -- The elements are sorted in strictly ascending order.
>
> If you could modify the elements once they had been inserted, then
> there would be no way for set<> to maintain those two invariants.
> Part of the design of set<> is that elements may be inserted and
> erased, but, once inserted, they may not be changed.

If so, there should be an explicit statement in the standard making the
restrictions clear. My preferred solution would be a statement that
set<>::iterator is not provided. That would provide a compile-time
warning whenever something is attempted that isn't safe or wouldn't
work. Alternatively, there should at least be a statement somewhere that
a container::iterator might not be useable for modifying the contained
values.



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

I am new to STL and am after a little help.

Can anyone please post a short example of using the set_union algorithm on
two set<int> objects that places the result in a third set<int>.

Sort of...
set<int> s1;
set<int> s2;
set<int> result;

set_union(s1.begin(), s1.end(), s2.begin(), s2.end(), result.end());

My compiler refuses to compile this due to the result.end() iterator being
returned as a const_iterator.

So far I have worked around this by putting the result into a vector<int>
and afterwards I coerce the results back into a set<int> again. This seems
like a kludge to me so I thought I would try to get some guru type guidance
here?

So just how do I go about using set_union with set<int> objects?
--
Nicholas J Biggs
Principle Analyst Programmer
Work: mailto:njb1441@ggr.co.uk
Home: mailto:snark@pawn.demon.co.uk
--
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Thanks to all who answered. Here is the solution that I got...

Simply use the inserter function (this is a iterator template function). So
the set_union then looks like this

set<int> s1;
set<int> s2;
set<int> result;
...
set_union(s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(result,
result.end()));

--
Nicholas J Biggs
Principle Analyst Programmer
Work: mailto:njb1441@ggr.co.uk
Home: mailto:snark@pawn.demon.co.uk
--
NJ Biggs wrote in message <6g2te9$a7n$1@ukwsv3.ggr.co.uk>...
>I am new to STL and am after a little help.
>
>Can anyone please post a short example of using the set_union algorithm on
>two set<int> objects that places the result in a third set<int>.
>
>Sort of...
>set<int> s1;
>set<int> s2;
>set<int> result;
>
>set_union(s1.begin(), s1.end(), s2.begin(), s2.end(), result.end());
>
>My compiler refuses to compile this due to the result.end() iterator being
>returned as a const_iterator.
>
>So far I have worked around this by putting the result into a vector<int>
>and afterwards I coerce the results back into a set<int> again. This seems
>like a kludge to me so I thought I would try to get some guru type guidance
>here?
>
>So just how do I go about using set_union with set<int> objects?
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

NJ Biggs wrote:
>
> I am new to STL and am after a little help.
>
> Can anyone please post a short example of using the set_union algorithm on
> two set<int> objects that places the result in a third set<int>.
>
> Sort of...
> set<int> s1;
> set<int> s2;
> set<int> result;
>
> set_union(s1.begin(), s1.end(), s2.begin(), s2.end(), result.end());
>
> My compiler refuses to compile this due to the result.end() iterator being
> returned as a const_iterator.

set<T>::end() on a non-const set<T> object is supposed to return
set<T>::iterator, not set<T>::const_iterator. You have a defective
implementation of STL.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

James Kuyper wrote:

> set<T>::end() on a non-const set<T> object is supposed to return
> set<T>::iterator, not set<T>::const_iterator. You have a defective
> implementation of STL.

set<T>::iterator IS set<T>::const_iterator. You have a defective
knowledge of the STL. ;-)

--

Valentin Bonnard                mailto:bonnardv@pratique.fr
info about C++/a propos du C++: http://pages.pratique.fr/~bonnardv/
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Valentin Bonnard <bonnardv@pratique.fr> wrote:
: James Kuyper wrote:

: > set<T>::end() on a non-const set<T> object is supposed to return
: > set<T>::iterator, not set<T>::const_iterator. You have a defective
: > implementation of STL.

: set<T>::iterator IS set<T>::const_iterator. You have a defective
: knowledge of the STL. ;-)

No such requirement exist in CD2. I don't think it was introduced
in FDIS. It would be pure madness. I'd like to see a requirement
that not only set<T>::iterator IS NOT set<T>::const_iterator,
but that set<T>::const_iterator is not even convertible to
set<T>::iterator. Just like I'd like to see this requirement for
all other containers. I consider any implementation, which does not
adhere to these requirements to be defective in this respect.

Oleg.
--
Life is a sexually transmitted, 100% lethal disease.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Valentin Bonnard wrote:
>
> James Kuyper wrote:
>
> > set<T>::end() on a non-const set<T> object is supposed to return
> > set<T>::iterator, not set<T>::const_iterator. You have a defective
> > implementation of STL.
>
> set<T>::iterator IS set<T>::const_iterator. You have a defective
> knowledge of the STL. ;-)

It doesn't say that anywhere in the standard. I would think that it's
implied that container::iterator is a non-const iterator for all STL
containers, though I can't find explicit wording to that effect.However,
if I'm right, this leads to problems. Consider:

#include <set>
#include <cassert>

int main(void)
{
        using std;
        set<int> s;

        set<int>::iterator i, j;

        i = s.insert(1).first;
        j = s.insert(2).first;
        (*i)=3; // problem
        assert(i==++j);

        return 0;
}

Where does the implementor of an STL set<> insert the code which
reorganises the iterators after 1 is replaced by 3? As far as I can
figure out, that assignment doesn't occur until after all STL code that
could be associated with the problem statement has finished executing.
With a set of class objects, you can cause the same problem by calling
i->member(), where T::member() can change the ordering. I have to admit
that non-const iterators for set<T> seem like a bad idea. I'm starting
to feel dizzy just thinking about it :-}.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Oleg Zabluda wrote:
>
> Valentin Bonnard <bonnardv@pratique.fr> wrote:
> : James Kuyper wrote:
>
> : > set<T>::end() on a non-const set<T> object is supposed to return
> : > set<T>::iterator, not set<T>::const_iterator. You have a defective
> : > implementation of STL.
>
> : set<T>::iterator IS set<T>::const_iterator. You have a defective
> : knowledge of the STL. ;-)
>
> No such requirement exist in CD2.

Sorry, I meant that such a thing is allowed and common practice.

It is NOT required.

> I'd like to see a requirement
> that not only set<T>::iterator IS NOT set<T>::const_iterator,
> but that set<T>::const_iterator is not even convertible to
> set<T>::iterator. Just like I'd like to see this requirement for
> all other containers. I consider any implementation, which does not
> adhere to these requirements to be defective in this respect.

That isn't part of the current *philosophy* of generic programming
in the standard.

Anyway you can write a static testsuite for each requirement
cathegory which test these requirements. So you can instantiate
an algo you are writing on test_const_iterator, test_iterator
in order to test if you are assigning a test_const_iterator to
a test_iterator.

--

Valentin Bonnard                mailto:bonnardv@pratique.fr
info about C++/a propos du C++: http://pages.pratique.fr/~bonnardv/
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Oleg Zabluda <zabluda@math.psu.edu> writes:

> Valentin Bonnard <bonnardv@pratique.fr> wrote:
> : James Kuyper wrote:
>
> : > set<T>::end() on a non-const set<T> object is supposed to return
> : > set<T>::iterator, not set<T>::const_iterator. You have a defective
> : > implementation of STL.
>
> : set<T>::iterator IS set<T>::const_iterator. You have a defective
> : knowledge of the STL. ;-)
>
> No such requirement exist in CD2. I don't think it was introduced
> in FDIS. It would be pure madness. I'd like to see a requirement
> that not only set<T>::iterator IS NOT set<T>::const_iterator,
> but that set<T>::const_iterator is not even convertible to
> set<T>::iterator. Just like I'd like to see this requirement for
> all other containers. I consider any implementation, which does not
> adhere to these requirements to be defective in this respect.

I can understand wanting set<>::iterator and set<>::const_iterator to
be distinct types, just for the sake of stricter type-checking.  (The
standard neither requires nor forbids them to be distinct types.)

I can't, though, understand wanting set<>::iterator to be a modifiable
iterator.  The whole point of set<> (and all of the other associative
containers) is that the position of an element depends on the
element's key.  In the case of set<>, for example, the two crucial
class invariants are
  -- No element appears more than once;
  -- The elements are sorted in strictly ascending order.

If you could modify the elements once they had been inserted, then
there would be no way for set<> to maintain those two invariants.
Part of the design of set<> is that elements may be inserted and
erased, but, once inserted, they may not be changed.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Matt Austern <austern@sgi.com> wrote:
: Oleg Zabluda <zabluda@math.psu.edu> writes:

: > Valentin Bonnard <bonnardv@pratique.fr> wrote:
: > : James Kuyper wrote:
: >
: > : > set<T>::end() on a non-const set<T> object is supposed to return
: > : > set<T>::iterator, not set<T>::const_iterator. You have a defective
: > : > implementation of STL.
: >
: > : set<T>::iterator IS set<T>::const_iterator. You have a defective
: > : knowledge of the STL. ;-)
: >
: > No such requirement exist in CD2. I don't think it was introduced
: > in FDIS. It would be pure madness. I'd like to see a requirement
: > that not only set<T>::iterator IS NOT set<T>::const_iterator,
: > but that set<T>::const_iterator is not even convertible to
: > set<T>::iterator. Just like I'd like to see this requirement for
: > all other containers. I consider any implementation, which does not
: > adhere to these requirements to be defective in this respect.

: I can understand wanting set<>::iterator and set<>::const_iterator to
: be distinct types, just for the sake of stricter type-checking.  (The
: standard neither requires nor forbids them to be distinct types.)

: I can't, though, understand wanting set<>::iterator to be a modifiable
: iterator.

I don't want it to be modifiable. I just want it to be non-convertible
to set<>::const_iterator. You still should not be able to modify
a set<> through set<>::iterator, and the diagnostic must be compile-time.

If set<> was the only container, I wouldn't worry about it.
In fact, if set<> was the only container, there would be
no reason whatsover to introduce set<>::iterator. It was
introduced for interface compatibility with other
containers. Therefore it must be indeed compatible.

If the ``non-convertibility'' property holds for all containers,
either because the Standard will mandate it, or because an
implementation did it this way, I'd like the same to hold
for set<>. For the same reason set<>::iterator was introduced
in the first place -- interface compatibility.

I would also understand the decision to remove set<>::iterator,
but wouldn't support it.

: The whole point of set<> (and all of the other associative
: containers) is that the position of an element depends on the
: element's key.  In the case of set<>, for example, the two crucial
: class invariants are
:   -- No element appears more than once;
:   -- The elements are sorted in strictly ascending order.

: If you could modify the elements once they had been inserted, then
: there would be no way for set<> to maintain those two invariants.
: Part of the design of set<> is that elements may be inserted and
: erased, but, once inserted, they may not be changed.

Right. I can imagine a modifiable set<>::iterator. An assignement
would reoder elements of set appropriately. For this,
set<>::iterator should carry enough information to find the
corresponding set. That's against the spirit of STL, and would
introduce unnesessary performance penalty. Although such info can be
successfully used for debugging purposes, for example, like detecting
dereferencing dangling iterators, or invalid iterator ranges.

Oleg.
--
Life is a sexually transmitted, 100% lethal disease.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Oleg Zabluda wrote:

> I just want it to be non-convertible to set<>::const_iterator.

I understand your opinion. You may also want cont<T>::iterator
not to be convertible to cont<U>::iterator, for any T != U,
which would mean that vector::iterator can't be a pointer.

I think it's should be possible to avoid direct use of primitive
types entirely, but it's too early to impose that given the fact
that using an object (class) instead of a built-in incurs a penalty
under a number of compilers.

--

Valentin Bonnard                mailto:bonnardv@pratique.fr
info about C++/a propos du C++: http://pages.pratique.fr/~bonnardv/
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]