| 2231 | |
| 2232 | template <class UniqueBool, class BidirIt, class Compare> |
| 2233 | void priv_insert_ordered_range |
| 2234 | (UniqueBool, size_type const n, BidirIt first, BidirIt const last, size_type positions[], Compare comp) |
| 2235 | { |
| 2236 | //Linear: at most N + M -1 comparisons |
| 2237 | //Log: MlogN |
| 2238 | //Average |
| 2239 | //Linear: N + M - 2 |
| 2240 | //Log: MlogN |
| 2241 | //N+M - 2 |
| 2242 | //N |
| 2243 | //(N+M)/2 < MlogN |
| 2244 | //(N/M+1)/2 <= logN |
| 2245 | //bool const linear = !s || !n || (s <= n) || ((s+n)/n/2 < logN); |
| 2246 | size_type const s = this->size(); |
| 2247 | size_type remaining = n; |
| 2248 | T* const pbeg = container_detail::to_raw_pointer(m_holder.start()); |
| 2249 | T* const pend = pbeg + s; |
| 2250 | T* pcur = pbeg; |
| 2251 | size_type *position = positions; |
| 2252 | size_type added_in_middle = 0; |
| 2253 | if(first != last && pcur != pend){ |
| 2254 | while(1){ |
| 2255 | //maintain stability moving external values only if they are strictly less |
| 2256 | if(comp(*first, *pcur)) { |
| 2257 | *position = static_cast<size_type>(pcur - pbeg); |
| 2258 | BOOST_ASSERT((position == positions) || (*(position-1) == size_type(-1)) || (*(position-1) <= *position)); |
| 2259 | ++position; |
| 2260 | ++added_in_middle; |
| 2261 | --remaining; |
| 2262 | if(++first == last) break; |
| 2263 | } |
| 2264 | else if(UniqueBool::value && !comp(*pcur, *first)){ |
| 2265 | *position = size_type(-1); |
| 2266 | ++position; |
| 2267 | --remaining; |
| 2268 | if(++first == last) break; |
| 2269 | } |
| 2270 | else{ |
| 2271 | if(++pcur == pend) break; |
| 2272 | } |
| 2273 | } |
| 2274 | } |
| 2275 | this->insert_ordered_at(added_in_middle, position, first); |
| 2276 | this->insert(this->cend(), remaining, first, last); |
| 2277 | } |
| 2278 | |
| 2279 | template<class UniqueBool, class FwdIt, class Compare> |
| 2280 | void priv_merge_in_new_buffer |