"Hans Aberg" <remove.haberg@matematik.su.se> wrote in message
news:remove.haberg-1212012241170001@du139-226.ppp.su-anst.tninet.se...

>
> Now the question that comes to my mind: Why is the part "or a.end() if
> such an element is not found" excluded from the lower_bound/upper_bound
> requirements, is it a defect report or intentional?

Totally intentional. It's much more useful to know where the item would be
inserted than to know that it's not there, since you can always see whether
it's there if you have the iterator to its would-be position.

> Checking the implementation of my compiler, it behaves as though that part
> was be included -- and it would sure help to know when writing programs.

What compiler are you using?? Report a bug immediately!


---
[ 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://www.research.att.com/~austern/csc/faq.html                ]

Hans Aberg wrote:
>
> In the C++ standard, Table 69 of section 23.1.2, "Associative containers",
> it is said:
>
> a.find(k): returns an iterator pointing to an element with the key equivalent to
> k, or a.end() if such an element is not found.
>
> a.lower_bound(k): returns an iterator pointing to the first element with
> key not less than k.
>
> a.upper_bound(k): returns an iterator pointing to the first element with
> key greater than k.
>
> Now the question that comes to my mind: Why is the part "or a.end() if
> such an element is not found" excluded from the lower_bound/upper_bound
> requirements, is it a defect report or intentional?

I think that lower_bound() and upper_bound() must each return a.end() if
there is no key meeting the specified criteria; I can't figure out any
other value they could return which would work as intended in typical
algorithms. It would also be consistent with the definition of the
std::lower_bound() algorithm. However, I agree that the standard does
not say so explicitly. I don't think it was left out intentionally.

---
[ 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://www.research.att.com/~austern/csc/faq.html                ]

David Abrahams wrote:
>
> "Hans Aberg" <remove.haberg@matematik.su.se> wrote in message
> news:remove.haberg-1212012241170001@du139-226.ppp.su-anst.tninet.se...
>
> >
> > Now the question that comes to my mind: Why is the part "or a.end() if
> > such an element is not found" excluded from the lower_bound/upper_bound
> > requirements, is it a defect report or intentional?
>
> Totally intentional. It's much more useful to know where the item would be
> inserted than to know that it's not there, since you can always see whether
> it's there if you have the iterator to its would-be position.

True, but you're missing the point. The standard specifies that
lower_bound(k) "returns an iterator pointing to the first element with
key not less than k." What should lower_bound(k) return if there is no
such element? The standard doesn't say. As a practical matter, it should
return a.end(), but a.end() does NOT point "to the first element with
key not less than k", since a.end() does not point to any element in the
container.

> > Checking the implementation of my compiler, it behaves as though that part
> > was be included -- and it would sure help to know when writing programs.
>
> What compiler are you using?? Report a bug immediately!

Where's the bug? It's undefined behavior, since the standard does not
provide a  definition of the return value that is applicable to that
case.

---
[ 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://www.research.att.com/~austern/csc/faq.html                ]

In article <9v8sk5$656$2@bob.news.rcn.net>, "David Abrahams"
<david.abrahams@rcn.com> wrote:
> Now the question that comes to my mind: Why is the part "or a.end() if
> such an element is not found" excluded from the lower_bound/upper_bound
> requirements, is it a defect report or intentional?
Totally intentional. It's much more useful to know where the item would be
inserted than to know that it's not there, since you can always see whether
it's there if you have the iterator to its would-be position.

In article <3C18033A.18453848@wizard.net>, "James Kuyper Jr."
<kuyper@wizard.net> wrote:
>True, but you're missing the point. The standard specifies that
>lower_bound(k) "returns an iterator pointing to the first element with
>key not less than k." What should lower_bound(k) return if there is no
>such element? The standard doesn't say. As a practical matter, it should
>return a.end(), but a.end() does NOT point "to the first element with
>key not less than k", since a.end() does not point to any element in the
>container.

This is my conclusion, or rather:

The standard says that if no iterator exists, it shall still return such
an iterator.

So the only possibility seems to be to insert a new element into the
container, so that the requirement on the returned iterator can be
fulfilled.

This seems hardly to be the intention of the standard.

>> What compiler are you using?? Report a bug immediately!
>
>Where's the bug? It's undefined behavior, since the standard does not
>provide a  definition of the return value that is applicable to that
>case.

Or rather a bug in the standard: a defect report, it seems.

  Hans Aberg      * Anti-spam: remove "remove." from email address.
                  * Email: Hans Aberg <remove.haberg@member.ams.org>
                  * Home Page: <http://www.matematik.su.se/~haberg/>
                  * AMS member listing: <http://www.ams.org/cml/>

---
[ 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://www.research.att.com/~austern/csc/faq.html                ]

David Abrahams wrote:
>
> "Hans Aberg" <remove.haberg@matematik.su.se> wrote in message
> news:remove.haberg-1212012241170001@du139-226.ppp.su-anst.tninet.se...
>
> >
> > Now the question that comes to my mind: Why is the part "or a.end() if
> > such an element is not found" excluded from the lower_bound/upper_bound
> > requirements, is it a defect report or intentional?
>
> Totally intentional. It's much more useful to know where the item would be
> inserted than to know that it's not there, since you can always see whether
> it's there if you have the iterator to its would-be position.

I cannot see how the addition Hans proposed would prevent that. AFAIKS
the function will only return end() if there is no element with a key
greater or equal than 'k'. It only defines this case and leaves other
cases untouched. In any way you now have the iterator to insert the new
element with key 'k'.

> What compiler are you using?? Report a bug immediately!

I'd go for the defect report :)

Regards, Daniel

--
Daniel Frey

aixigo AG - financial training, research and technology
Schlo   -Rahe-Stra   e 15, 52072 Aachen, Germany
fon: +49 (0)241 936737-42, fax: +49 (0)241 936737-99
eMail: daniel.frey@aixigo.de, web: http://www.aixigo.de

---
[ 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://www.research.att.com/~austern/csc/faq.html                ]

"Hans Aberg" <remove.haberg@matematik.su.se> wrote in message
news:remove.haberg-1312011052450001@du132-226.ppp.su-anst.tninet.se...

>
> The standard says that if no iterator exists, it shall still return such
> an iterator.
>
> So the only possibility seems to be to insert a new element into the
> container, so that the requirement on the returned iterator can be
> fulfilled.
>
> This seems hardly to be the intention of the standard.

You're right! My language lawyering muscles must be atrophied ;-)

-Dave



---
[ 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://www.research.att.com/~austern/csc/faq.html                ]

In the C++ standard, Table 69 of section 23.1.2, "Associative containers",
it is said:

a.find(k): returns an iterator pointing to an element with the key equivalent to
k, or a.end() if such an element is not found.

a.lower_bound(k): returns an iterator pointing to the first element with
key not less than k.

a.upper_bound(k): returns an iterator pointing to the first element with
key greater than k.

Now the question that comes to my mind: Why is the part "or a.end() if
such an element is not found" excluded from the lower_bound/upper_bound
requirements, is it a defect report or intentional?

Checking the implementation of my compiler, it behaves as though that part
was be included -- and it would sure help to know when writing programs.

  Hans Aberg      * Anti-spam: remove "remove." from email address.
                  * Email: Hans Aberg <remove.haberg@member.ams.org>
                  * Home Page: <http://www.matematik.su.se/~haberg/>
                  * AMS member listing: <http://www.ams.org/cml/>

---
[ 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://www.research.att.com/~austern/csc/faq.html                ]