Re: [Boost-bugs] [Boost C++ Libraries] #2810: Optimization for list::merge performance

Subject: Re: [Boost-bugs] [Boost C++ Libraries] #2810: Optimization for list::merge performance
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2009-02-28 17:49:34


#2810: Optimization for list::merge performance
---------------------------+------------------------------------------------
  Reporter: andysem | Owner: igaztanaga
      Type: Patches | Status: new
 Milestone: Boost 1.39.0 | Component: intrusive
   Version: Boost 1.38.0 | Severity: Optimization
Resolution: | Keywords: list merge performance
---------------------------+------------------------------------------------

Comment(by igaztanaga):

 I think your proposal has a bug in the first loop (it shouldn't be
 "!p(*bx, b)"?). I've tested the following:

    template<class Predicate>
    void merge(list_impl& x, Predicate p)
    {
       const_iterator e(this->cend()), ex(x.cend());
       const_iterator b(this->cbegin());
       while(!x.empty()){
          const_iterator ix(x.cbegin());
          while (b != e && !p(*ix, *b)){
             ++b;
          }
          if(b == e){
             //Now transfer the rest to the end of the container
             this->splice(e, x);
             break;
          }
          else{
             size_type n(0);
             do{
                ++ix; ++n;
             } while(ix != ex && p(*ix, *b));
             this->splice(b, x, x.begin(), ix, n);
          }
       }
    }

 And similarly for slist:

    template<class Predicate>
    iterator merge(slist_impl& x, Predicate p)
    {
       const_iterator e(this->cend()), ex(x.cend()),
 bb(this->cbefore_begin()),
                      bb_next, last_inserted(e);
       while(!x.empty()){
          const_iterator ibx_next(x.cbefore_begin()), ibx(ibx_next++);
          while (++(bb_next = bb) != e && !p(*ibx_next, *bb_next)){
             bb = bb_next;
          }
          if(bb_next == e){
             //Now transfer the rest to the end of the container
             last_inserted = this->splice_after(bb, x);
             break;
          }
          else{
             size_type n(0);
             do{
                ibx = ibx_next; ++n;
             } while(++(ibx_next = ibx) != ex && p(*ibx_next, *bb_next));
             this->splice_after(bb, x, x.before_begin(), ibx, n);
             last_inserted = ibx;
          }
       }
       return last_inserted.unconst();
    }

 Those are not thorougly tested so let me know if you find any error.

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/2810#comment:1>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.

This archive was generated by hypermail 2.1.7 : 2017-02-16 18:49:59 UTC