[Bug libstdc++/45488] New: lower_bound iterator must be default constructible

[Bug libstdc++/45488] New: lower_bound iterator must be default constructible

[giecrilj at stegny dot 2a dot pl]

First of all, I understand that this is a requirement imposed by the Standard. 
However, the requirement, in general, is valid only for iterators that do not
refer to any container.  This is not the case with iterators useful in
algorithms; the default value of such an iterator has no meaning.
Moreover, the implementation of the library has no obligation to check this
trait for every algorithm, and I suggest that this check should be removed. 
The code for std::lower_bound does not use this feature in a meaningful way,
and it is straightforward to fix.
The patch below, apart from fixing the problem, also replaces iterator with
std::iterator.

  template<typename _ForwardIterator, typename _Tp>
    _ForwardIterator
    lower_bound(_ForwardIterator __first, _ForwardIterator __last,
                const _Tp& __val)
    {
      typedef typename std:: iterator_traits<_ForwardIterator>::value_type
        _ValueType;
      typedef typename std:: iterator_traits<_ForwardIterator>::difference_type
        _DistanceType;

      // concept requirements
      __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
      __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
      __glibcxx_requires_partitioned_lower(__first, __last, __val);

      _DistanceType __len = std:: distance(__first, __last);
      _DistanceType __half;

      while (__len > 0)
        {
        _ForwardIterator __middle ((__first));
          __half = __len >> 1;
          std::advance(__middle, __half);
          if (*__middle < __val)
            {
              __first = __middle;
              ++__first;
              __len = __len - __half - 1;
            }
          else
            __len = __half;
        }
      return __first;
    }


-- 
           Summary: lower_bound iterator must be default constructible
           Product: gcc
           Version: 4.4.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: giecrilj at stegny dot 2a dot pl
 GCC build triplet: x86_64-suse-linux
  GCC host triplet: x86_64-suse-linux
GCC target triplet: x86_64-suse-linux


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45488

[Bug libstdc++/45488] lower_bound iterator must be default constructible

[paolo dot carlini at oracle dot com]

------- Comment #1 from paolo dot carlini at oracle dot com  2010-09-01 20:44 -------
I do not understand: according to Table 74 *any* forward iterator is default
constructible, and C++0x isn't changing that, is even more explicit. Thus, I
don't see which problem you are trying to solve.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45488

[Bug libstdc++/45488] lower_bound iterator must be default constructible

[paolo dot carlini at oracle dot com]

------- Comment #2 from paolo dot carlini at oracle dot com  2010-09-01 20:53 -------
Granted, __middle is not used after the loop, thus moving the declaration
inside the loop seems a tad cleaner. But then we should do the change
consistently for both lower_bound overloads and for upper_bound. Please test
that, simply use _ForwardIterator __middle = __first; and send to the mailing
list a real patch, if you want your name in the ChangeLog. Thanks.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45488

[Bug libstdc++/45488] lower_bound iterator must be default constructible

[paolo dot carlini at oracle dot com]

------- Comment #3 from paolo dot carlini at oracle dot com  2010-09-01 22:09 -------
Ok, I'll do it, for equal_range too, and __half can also be moved inside the
loop.


-- 

paolo dot carlini at oracle dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |paolo dot carlini at oracle
                   |dot org                     |dot com
             Status|UNCONFIRMED                 |ASSIGNED
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2010-09-01 22:09:34
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45488

[Bug libstdc++/45488] lower_bound iterator must be default constructible

[giecrilj at stegny dot 2a dot pl]

------- Comment #4 from giecrilj at stegny dot 2a dot pl  2010-09-01 22:34 -------
== Test case ==

#include <cassert>
#include <algorithm>

namespace BUG45488 {
class my_iter: 
  public std:: iterator <std:: random_access_iterator_tag, char const >
  { private: typedef my_iter ref;
    private: pointer m_ptr; 
    public: typedef std:: less <value_type > compare;
    public: my_iter (pointer p_ptr): m_ptr (p_ptr) {} 
    public: operator pointer (void) const { return this -> m_ptr; } 
    public: ref operator ++ (void) { ++this -> m_ptr; return *this; } 
    public: 
      ref operator += (difference_type p_d) 
      { this -> m_ptr += p_d; return *this; }};
void test (void) { 
  static char const sc_test [] = { 'a', 'c' }; 
  assert 
  (std:: lower_bound (my_iter (sc_test), my_iter ((&sc_test) [01]), 'a') 
  == my_iter (sc_test)); 
  assert 
  (std:: lower_bound 
  (my_iter (sc_test), my_iter ((&sc_test) [01]), 'a', my_iter:: compare ()) 
  == my_iter (sc_test)); 
  assert 
  (std:: upper_bound (my_iter (sc_test), my_iter ((&sc_test) [01]), 'a') 
  == my_iter (sc_test) + 01);
  assert 
  (std:: upper_bound 
  (my_iter (sc_test), my_iter ((&sc_test) [01]), 'a', my_iter:: compare ()) 
  == my_iter (sc_test) + 01);
}
}

== Patch ==

*** /usr/include/c++/4.4/bits/stl_algo.h        2009-10-23 23:19:15.000000000
+0200
--- bits/stl_algo.h     2010-09-02 00:13:09.200742054 +0200                     
*************** _GLIBCXX_BEGIN_NAMESPACE(std)                                   
*** 2432,2443 ****                                                              

        _DistanceType __len = std::distance(__first, __last);                   
        _DistanceType __half;                                                   
-       _ForwardIterator __middle;                                              

        while (__len > 0)                                                       
        {                                                                       
          __half = __len >> 1;                                                  
-         __middle = __first;                                                   
          std::advance(__middle, __half);                                       
          if (*__middle < __val)                                                
            {                                                                   
--- 2432,2442 ----                                                              

        _DistanceType __len = std::distance(__first, __last);                   
        _DistanceType __half;                                                   

        while (__len > 0)                                                       
        {                                                                       
+         _ForwardIterator __middle = __first;                                  
          __half = __len >> 1;                                                  
          std::advance(__middle, __half);                                       
          if (*__middle < __val)                                                
            {                                                                   
*************** _GLIBCXX_BEGIN_NAMESPACE(std)                                   
*** 2485,2496 ****                                                              

        _DistanceType __len = std::distance(__first, __last);                   
        _DistanceType __half;                                                   
-       _ForwardIterator __middle;                                              

        while (__len > 0)                                                       
        {                                                                       
          __half = __len >> 1;                                                  
-         __middle = __first;                                                   
          std::advance(__middle, __half);                                       
          if (__comp(*__middle, __val))                                         
            {                                                                   
--- 2484,2494 ----                                                              

        _DistanceType __len = std::distance(__first, __last);                   
        _DistanceType __half;                                                   

        while (__len > 0)                                                       
        {                                                                       
+         _ForwardIterator __middle = __first;                                  
          __half = __len >> 1;                                                  
          std::advance(__middle, __half);                                       
          if (__comp(*__middle, __val))                                         
            {                                                                   
*************** _GLIBCXX_BEGIN_NAMESPACE(std)                                   
*** 2532,2543 ****                                                              

        _DistanceType __len = std::distance(__first, __last);                   
        _DistanceType __half;                                                   
-       _ForwardIterator __middle;                                              

        while (__len > 0)                                                       
        {                                                                       
          __half = __len >> 1;                                                  
-         __middle = __first;                                                   
          std::advance(__middle, __half);                                       
          if (__val < *__middle)                                                
            __len = __half;                                                     
--- 2530,2540 ----                                                              

        _DistanceType __len = std::distance(__first, __last);                   
        _DistanceType __half;

        while (__len > 0)
        {
+         _ForwardIterator __middle = __first;
          __half = __len >> 1;
          std::advance(__middle, __half);
          if (__val < *__middle)
            __len = __half;
*************** _GLIBCXX_BEGIN_NAMESPACE(std)
*** 2585,2596 ****

        _DistanceType __len = std::distance(__first, __last);
        _DistanceType __half;
-       _ForwardIterator __middle;

        while (__len > 0)
        {
          __half = __len >> 1;
-         __middle = __first;
          std::advance(__middle, __half);
          if (__comp(__val, *__middle))
            __len = __half;
--- 2582,2592 ----

        _DistanceType __len = std::distance(__first, __last);
        _DistanceType __half;

        while (__len > 0)
        {
+         _ForwardIterator __middle  = __first;
          __half = __len >> 1;
          std::advance(__middle, __half);
          if (__comp(__val, *__middle))
            __len = __half;


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45488

[Bug libstdc++/45488] lower_bound iterator must be default constructible

[paolo dot carlini at oracle dot com]

------- Comment #5 from paolo dot carlini at oracle dot com  2010-09-01 22:37 -------
We are not adding testcases here, because a forward iterator must be default
constructible.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45488

[Bug libstdc++/45488] lower_bound iterator must be default constructible

[giecrilj at stegny dot 2a dot pl]

------- Comment #6 from giecrilj at stegny dot 2a dot pl  2010-09-01 22:39 -------
BTW, why is this implementation so repetitive?
What would be wrong with saying
lower_bound (a_, b_, c_) := lower_bound (a, b, c, less ())?


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45488

[Bug libstdc++/45488] lower_bound iterator must be default constructible

[paolo dot carlini at oracle dot com]

------- Comment #7 from paolo dot carlini at oracle dot com  2010-09-01 22:42 -------
Doesn't always work with proxy iterators.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45488

[Bug libstdc++/45488] lower_bound iterator must be default constructible

[giecrilj at stegny dot 2a dot pl]

------- Comment #8 from giecrilj at stegny dot 2a dot pl  2010-09-01 22:42 -------
(In reply to comment #5)
> We are not adding testcases here, because a forward iterator must be default
> constructible.

On the other hand, unless we are talking concepts and forcing, the standard
library is not prohibited from handling correctly cases when the type passed as
forward iterator is not default constructible and the requirement is bogus. 


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45488

[Bug libstdc++/45488] lower_bound iterator must be default constructible

[paolo dot carlini at oracle dot com]

------- Comment #9 from paolo dot carlini at oracle dot com  2010-09-01 22:49 -------
We are already well beyond the size of change which is not fixing any real bug
and applied without a Copyright Assignment on file. If you are interested in
enhancing the library, please file one and then start posting to the mailing
list, the proper place for enhancements (vs bugs). Thanks again for now, I'm
going to commit the final patch I tested momentarily.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45488

[Bug libstdc++/45488] lower_bound doesn't really require the iterator parameters to be default constructible

[paolo at gcc dot gnu dot org]

------- Comment #11 from paolo at gcc dot gnu dot org  2010-09-01 22:58 -------
Subject: Bug 45488

Author: paolo
Date: Wed Sep  1 22:58:15 2010
New Revision: 163747

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=163747
Log:
2010-09-01  Christopher Yeleighton  <giecrilj@stegny.2a.pl>
            Paolo Carlini  <paolo.carlini@oracle.com>

        PR libstdc++/45488
        * include/bits/stl_algobase.h (lower_bound): Clean-up a tad, move
        two variables inside the main loop.
        * include/bits/stl_algo.h (lower_bound, upper_bound, equal_range):
        Likewise.

Modified:
    trunk/libstdc++-v3/include/bits/stl_algo.h
    trunk/libstdc++-v3/include/bits/stl_algobase.h


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45488

[Bug libstdc++/45488] lower_bound doesn't really require the iterator parameters to be default constructible

[paolo at gcc dot gnu dot org]

------- Comment #10 from paolo at gcc dot gnu dot org  2010-09-01 22:58 -------
Subject: Bug 45488

Author: paolo
Date: Wed Sep  1 22:58:05 2010
New Revision: 163746

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=163746
Log:
2010-09-01  Christopher Yeleighton  <giecrilj@stegny.2a.pl>
            Paolo Carlini  <paolo.carlini@oracle.com>

        PR libstdc++/45488
        * include/bits/stl_algobase.h (lower_bound): Clean-up a tad, move
        two variables inside the main loop.
        * include/bits/stl_algo.h (lower_bound, upper_bound, equal_range):
        Likewise.

Modified:
    trunk/libstdc++-v3/ChangeLog


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45488

[Bug libstdc++/45488] lower_bound doesn't really require the iterator parameters to be default constructible

[paolo dot carlini at oracle dot com]

------- Comment #12 from paolo dot carlini at oracle dot com  2010-09-01 23:00 -------
Done.


-- 

paolo dot carlini at oracle dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.6.0


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45488