[Boost-commit] svn:boost r77895 - trunk/boost/container/detail

Subject: [Boost-commit] svn:boost r77895 - trunk/boost/container/detail
From: igaztanaga_at_[hidden]
Date: 2012-04-10 16:14:31

Author: igaztanaga
Date: 2012-04-10 16:14:31 EDT (Tue, 10 Apr 2012)
New Revision: 77895
URL: http://svn.boost.org/trac/boost/changeset/77895

Log:
Changed ordered insertion function and added comments
Text files modified: 
   trunk/boost/container/detail/flat_tree.hpp |    52 +++++++++++++++++++++++++++++++++------ 
   1 files changed, 44 insertions(+), 8 deletions(-)

Modified: trunk/boost/container/detail/flat_tree.hpp
==============================================================================
--- trunk/boost/container/detail/flat_tree.hpp	(original)
+++ trunk/boost/container/detail/flat_tree.hpp	2012-04-10 16:14:31 EDT (Tue, 10 Apr 2012)
@@ -301,7 +301,6 @@
       return ret;
    }
 
-
    iterator insert_equal(const value_type& val)
    {
       iterator i = this->upper_bound(KeyOfValue()(val));
@@ -339,14 +338,14 @@
    iterator insert_equal(const_iterator pos, const value_type& val)
    {
       insert_commit_data data;
-      priv_insert_equal_prepare(pos, val, data);
+      this->priv_insert_equal_prepare(pos, val, data);
       return priv_insert_commit(data, val);
    }
 
    iterator insert_equal(const_iterator pos, BOOST_RV_REF(value_type) mval)
    {
       insert_commit_data data;
-      priv_insert_equal_prepare(pos, mval, data);
+      this->priv_insert_equal_prepare(pos, mval, data);
       return priv_insert_commit(data, boost::move(mval));
    }
 
@@ -362,7 +361,15 @@
    {
       typedef typename 
          std::iterator_traits<InIt>::iterator_category ItCat;
-      priv_insert_equal(first, last, ItCat());
+      this->priv_insert_equal(first, last, ItCat());
+   }
+
+   template <class InIt>
+   void insert_equal(ordered_range_t, InIt first, InIt last)
+   {
+      typedef typename 
+         std::iterator_traits<InIt>::iterator_category ItCat;
+      this->priv_insert_equal(ordered_range_t(), first, last, ItCat());
    }
 
    #ifdef BOOST_CONTAINER_PERFECT_FORWARDING
@@ -406,7 +413,7 @@
    {
       value_type &&val = value_type(boost::forward<Args>(args)...);
       insert_commit_data data;
-      priv_insert_equal_prepare(hint, val, data);
+      this->priv_insert_equal_prepare(hint, val, data);
       return priv_insert_commit(data, boost::move(val));
    }
 
@@ -466,7 +473,7 @@
             BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _) BOOST_PP_RPAREN_IF(n);  \
       value_type &val = vval;                                                             \
       insert_commit_data data;                                                            \
-      priv_insert_equal_prepare(hint, val, data);                                         \
+      this->priv_insert_equal_prepare(hint, val, data);                                   \
       return priv_insert_commit(data, boost::move(val));                                  \
    }                                                                                      \
    //!
@@ -746,10 +753,39 @@
       return std::pair<RanIt, RanIt>(first, first);
    }
 
-   template <class FwdIt>
-   void priv_insert_equal(FwdIt first, FwdIt last, std::forward_iterator_tag)
+   template <class BidirIt>
+   void priv_insert_equal(ordered_range_t, BidirIt first, BidirIt last, std::bidirectional_iterator_tag)
    {
       size_type len = static_cast<size_type>(std::distance(first, last));
+      const size_type BurstSize = 16;
+      size_type positions[BurstSize];
+
+      while(len){
+         const size_type burst = len < BurstSize ? len : BurstSize;
+         len -= burst;
+         const iterator beg(this->cbegin());
+         iterator pos;
+         for(size_type i = 0; i != burst; ++i){
+            pos = this->upper_bound(KeyOfValue()(*first));
+            positions[i] = static_cast<size_type>(pos - beg);
+            ++first;
+         }
+         this->m_data.m_vect.insert_ordered_at(burst, positions + burst, first);
+      }
+   }
+
+   template <class FwdIt>
+   void priv_insert_equal_forward(ordered_range_t, FwdIt first, FwdIt last, std::forward_iterator_tag)
+   {  this->priv_insert_equal(first, last, std::forward_iterator_tag());   }
+
+   template <class InIt>
+   void priv_insert_equal(ordered_range_t, InIt first, InIt last, std::input_iterator_tag)
+   {  this->priv_insert_equal(first, last, std::input_iterator_tag());  }
+
+   template <class FwdIt>
+   void priv_insert_equal_forward(FwdIt first, FwdIt last, std::forward_iterator_tag)
+   {
+      const size_type len = static_cast<size_type>(std::distance(first, last));
       this->reserve(this->size()+len);
       this->priv_insert_equal(first, last, std::input_iterator_tag());
    }