X-Git-Url: http://plrg.eecs.uci.edu/git/?p=folly.git;a=blobdiff_plain;f=folly%2Fsorted_vector_types.h;h=255b451834f8afa8ee18a5651500dc7dc0363432;hp=d55038499f02f984fdee12f524637c1c8ef38f6f;hb=4aa405ec8db137b29d403aa204a91ed50aab5bb4;hpb=78f3142f51b4fd555664936701f49da7dea86b7e

diff --git a/folly/sorted_vector_types.h b/folly/sorted_vector_types.h
index d5503849..255b4518 100644
--- a/folly/sorted_vector_types.h
+++ b/folly/sorted_vector_types.h
@@ -1,5 +1,5 @@
 /*
- * Copyright 2013 Facebook, Inc.
+ * Copyright 2017 Facebook, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -57,16 +57,18 @@
  *     std::vector<>, which requires it to be Assignable.)
  */
 
-#ifndef FOLLY_SORTED_VECTOR_TYPES_H_
-#define FOLLY_SORTED_VECTOR_TYPES_H_
+#pragma once
 
-#include <vector>
 #include <algorithm>
-#include <utility>
+#include <initializer_list>
 #include <iterator>
+#include <stdexcept>
+#include <type_traits>
+#include <utility>
+#include <vector>
+
 #include <boost/operators.hpp>
-#include <boost/bind.hpp>
-#include <boost/type_traits/is_same.hpp>
+#include <folly/portability/BitsFunctexcept.h>
 
 namespace folly {
 
@@ -105,44 +107,72 @@ namespace detail {
   template<class Iterator>
   int distance_if_multipass(Iterator first, Iterator last) {
     typedef typename std::iterator_traits<Iterator>::iterator_category categ;
-    if (boost::is_same<categ,std::input_iterator_tag>::value)
+    if (std::is_same<categ,std::input_iterator_tag>::value)
       return -1;
     return std::distance(first, last);
   }
 
   template<class OurContainer, class Vector, class GrowthPolicy>
-  std::pair<typename OurContainer::iterator,bool>
+  typename OurContainer::iterator
   insert_with_hint(OurContainer& sorted,
                    Vector& cont,
                    typename OurContainer::iterator hint,
-                   typename OurContainer::value_type value,
+                   typename OurContainer::value_type&& value,
                    GrowthPolicy& po)
   {
     const typename OurContainer::value_compare& cmp(sorted.value_comp());
     if (hint == cont.end() || cmp(value, *hint)) {
       if (hint == cont.begin()) {
         po.increase_capacity(cont, cont.begin());
-        return std::make_pair(cont.insert(cont.begin(), value), true);
+        return cont.insert(cont.begin(), std::move(value));
       }
       if (cmp(*(hint - 1), value)) {
         hint = po.increase_capacity(cont, hint);
-        return std::make_pair(cont.insert(hint, value), true);
+        return cont.insert(hint, std::move(value));
       }
-      return sorted.insert(value);
+      return sorted.insert(std::move(value)).first;
     }
 
     if (cmp(*hint, value)) {
       if (hint + 1 == cont.end() || cmp(value, *(hint + 1))) {
         typename OurContainer::iterator it =
           po.increase_capacity(cont, hint + 1);
-        return std::make_pair(cont.insert(it, value), true);
+        return cont.insert(it, std::move(value));
       }
     }
 
     // Value and *hint did not compare, so they are equal keys.
-    return std::make_pair(hint, false);
+    return hint;
   }
 
+  template <class OurContainer, class Vector, class InputIterator>
+  void bulk_insert(
+      OurContainer& sorted,
+      Vector& cont,
+      InputIterator first,
+      InputIterator last) {
+    // prevent deref of middle where middle == cont.end()
+    if (first == last) {
+      return;
+    }
+
+    auto const& cmp(sorted.value_comp());
+
+    int const d = distance_if_multipass(first, last);
+    if (d != -1) {
+      cont.reserve(cont.size() + d);
+    }
+    auto const prev_size = cont.size();
+
+    std::copy(first, last, std::back_inserter(cont));
+    auto const middle = cont.begin() + prev_size;
+    if (!std::is_sorted(middle, cont.end(), cmp)) {
+      std::sort(middle, cont.end(), cmp);
+    }
+    if (middle != cont.begin() && cmp(*middle, *(middle - 1))) {
+      std::inplace_merge(cont.begin(), middle, cont.end(), cmp);
+    }
+  }
 }
 
 //////////////////////////////////////////////////////////////////////
@@ -214,12 +244,39 @@ public:
     insert(first, last);
   }
 
+  /* implicit */ sorted_vector_set(
+      std::initializer_list<value_type> list,
+      const Compare& comp = Compare(),
+      const Allocator& alloc = Allocator())
+    : m_(comp, alloc)
+  {
+    insert(list.begin(), list.end());
+  }
+
+  // Construct a sorted_vector_set by stealing the storage of a prefilled
+  // container. The container need not be sorted already. This supports
+  // bulk construction of sorted_vector_set with zero allocations, not counting
+  // those performed by the caller. (The iterator range constructor performs at
+  // least one allocation).
+  //
+  // Note that `sorted_vector_set(const ContainerT& container)` is not provided,
+  // since the purpose of this constructor is to avoid an unnecessary copy.
+  explicit sorted_vector_set(
+      ContainerT&& container,
+      const Compare& comp = Compare())
+      : m_(comp, container.get_allocator()) {
+    std::sort(container.begin(), container.end(), value_comp());
+    m_.cont_.swap(container);
+  }
+
   key_compare key_comp() const { return m_; }
   value_compare value_comp() const { return m_; }
 
   iterator begin()                      { return m_.cont_.begin();  }
   iterator end()                        { return m_.cont_.end();    }
+  const_iterator cbegin() const         { return m_.cont_.cbegin(); }
   const_iterator begin() const          { return m_.cont_.begin();  }
+  const_iterator cend() const           { return m_.cont_.cend();   }
   const_iterator end() const            { return m_.cont_.end();    }
   reverse_iterator rbegin()             { return m_.cont_.rbegin(); }
   reverse_iterator rend()               { return m_.cont_.rend();   }
@@ -231,35 +288,38 @@ public:
   size_type max_size() const    { return m_.cont_.max_size(); }
   bool empty() const            { return m_.cont_.empty();    }
   void reserve(size_type s)     { return m_.cont_.reserve(s); }
+  void shrink_to_fit()          { m_.cont_.shrink_to_fit();   }
   size_type capacity() const    { return m_.cont_.capacity(); }
 
   std::pair<iterator,bool> insert(const value_type& value) {
+    return insert(std::move(value_type(value)));
+  }
+
+  std::pair<iterator,bool> insert(value_type&& value) {
     iterator it = lower_bound(value);
     if (it == end() || value_comp()(value, *it)) {
       it = get_growth_policy().increase_capacity(m_.cont_, it);
-      return std::make_pair(m_.cont_.insert(it, value), true);
+      return std::make_pair(m_.cont_.insert(it, std::move(value)), true);
     }
     return std::make_pair(it, false);
   }
 
-  std::pair<iterator,bool> insert(iterator hint, const value_type& value) {
-    return detail::insert_with_hint(*this, m_.cont_, hint, value,
+  iterator insert(iterator hint, const value_type& value) {
+    return insert(hint, std::move(value_type(value)));
+  }
+
+  iterator insert(iterator hint, value_type&& value) {
+    return detail::insert_with_hint(*this, m_.cont_, hint, std::move(value),
       get_growth_policy());
   }
 
   template<class InputIterator>
   void insert(InputIterator first, InputIterator last) {
-    int d = detail::distance_if_multipass(first, last);
-    if (d != -1) {
-      m_.cont_.reserve(m_.cont_.size() + d);
-    }
-    for (; first != last; ++first) {
-      insert(end(), *first);
-    }
+    detail::bulk_insert(*this, m_.cont_, first, last);
   }
 
   size_type erase(const key_type& key) {
-    iterator it = lower_bound(key);
+    iterator it = find(key);
     if (it == end()) {
       return 0;
     }
@@ -401,10 +461,7 @@ public:
   typedef std::pair<key_type,mapped_type>           value_type;
   typedef Compare                                   key_compare;
 
-  struct value_compare
-    : std::binary_function<value_type,value_type,bool>
-    , private Compare
-  {
+  struct value_compare : private Compare {
     bool operator()(const value_type& a, const value_type& b) const {
       return Compare::operator()(a.first, b.first);
     }
@@ -440,12 +497,39 @@ public:
     insert(first, last);
   }
 
+  explicit sorted_vector_map(
+      std::initializer_list<value_type> list,
+      const Compare& comp = Compare(),
+      const Allocator& alloc = Allocator())
+    : m_(value_compare(comp), alloc)
+  {
+    insert(list.begin(), list.end());
+  }
+
+  // Construct a sorted_vector_map by stealing the storage of a prefilled
+  // container. The container need not be sorted already. This supports
+  // bulk construction of sorted_vector_map with zero allocations, not counting
+  // those performed by the caller. (The iterator range constructor performs at
+  // least one allocation).
+  //
+  // Note that `sorted_vector_map(const ContainerT& container)` is not provided,
+  // since the purpose of this constructor is to avoid an unnecessary copy.
+  explicit sorted_vector_map(
+      ContainerT&& container,
+      const Compare& comp = Compare())
+      : m_(value_compare(comp), container.get_allocator()) {
+    std::sort(container.begin(), container.end(), value_comp());
+    m_.cont_.swap(container);
+  }
+
   key_compare key_comp() const { return m_; }
   value_compare value_comp() const { return m_; }
 
   iterator begin()                      { return m_.cont_.begin();  }
   iterator end()                        { return m_.cont_.end();    }
+  const_iterator cbegin() const         { return m_.cont_.cbegin(); }
   const_iterator begin() const          { return m_.cont_.begin();  }
+  const_iterator cend() const           { return m_.cont_.cend();   }
   const_iterator end() const            { return m_.cont_.end();    }
   reverse_iterator rbegin()             { return m_.cont_.rbegin(); }
   reverse_iterator rend()               { return m_.cont_.rend();   }
@@ -457,31 +541,34 @@ public:
   size_type max_size() const    { return m_.cont_.max_size(); }
   bool empty() const            { return m_.cont_.empty();    }
   void reserve(size_type s)     { return m_.cont_.reserve(s); }
+  void shrink_to_fit()          { m_.cont_.shrink_to_fit();   }
   size_type capacity() const    { return m_.cont_.capacity(); }
 
   std::pair<iterator,bool> insert(const value_type& value) {
+    return insert(std::move(value_type(value)));
+  }
+
+  std::pair<iterator,bool> insert(value_type&& value) {
     iterator it = lower_bound(value.first);
     if (it == end() || value_comp()(value, *it)) {
       it = get_growth_policy().increase_capacity(m_.cont_, it);
-      return std::make_pair(m_.cont_.insert(it, value), true);
+      return std::make_pair(m_.cont_.insert(it, std::move(value)), true);
     }
     return std::make_pair(it, false);
   }
 
-  std::pair<iterator,bool> insert(iterator hint, const value_type& value) {
-    return detail::insert_with_hint(*this, m_.cont_, hint, value,
+  iterator insert(iterator hint, const value_type& value) {
+    return insert(hint, std::move(value_type(value)));
+  }
+
+  iterator insert(iterator hint, value_type&& value) {
+    return detail::insert_with_hint(*this, m_.cont_, hint, std::move(value),
       get_growth_policy());
   }
 
   template<class InputIterator>
   void insert(InputIterator first, InputIterator last) {
-    int d = detail::distance_if_multipass(first, last);
-    if (d != -1) {
-      m_.cont_.reserve(m_.cont_.size() + d);
-    }
-    for (; first != last; ++first) {
-      insert(end(), *first);
-    }
+    detail::bulk_insert(*this, m_.cont_, first, last);
   }
 
   size_type erase(const key_type& key) {
@@ -515,28 +602,56 @@ public:
     return end();
   }
 
+  mapped_type& at(const key_type& key) {
+    iterator it = find(key);
+    if (it != end()) {
+      return it->second;
+    }
+    std::__throw_out_of_range("sorted_vector_map::at");
+  }
+
+  const mapped_type& at(const key_type& key) const {
+    const_iterator it = find(key);
+    if (it != end()) {
+      return it->second;
+    }
+    std::__throw_out_of_range("sorted_vector_map::at");
+  }
+
   size_type count(const key_type& key) const {
     return find(key) == end() ? 0 : 1;
   }
 
   iterator lower_bound(const key_type& key) {
-    return std::lower_bound(begin(), end(), key,
-      boost::bind(key_comp(), boost::bind(&value_type::first, _1), _2));
+    auto c = key_comp();
+    auto f = [&](const value_type& a, const key_type& b) {
+      return c(a.first, b);
+    };
+    return std::lower_bound(begin(), end(), key, f);
   }
 
   const_iterator lower_bound(const key_type& key) const {
-    return std::lower_bound(begin(), end(), key,
-      boost::bind(key_comp(), boost::bind(&value_type::first, _1), _2));
+    auto c = key_comp();
+    auto f = [&](const value_type& a, const key_type& b) {
+      return c(a.first, b);
+    };
+    return std::lower_bound(begin(), end(), key, f);
   }
 
   iterator upper_bound(const key_type& key) {
-    return std::upper_bound(begin(), end(), key,
-      boost::bind(key_comp(), _1, boost::bind(&value_type::first, _2)));
+    auto c = key_comp();
+    auto f = [&](const key_type& a, const value_type& b) {
+      return c(a, b.first);
+    };
+    return std::upper_bound(begin(), end(), key, f);
   }
 
   const_iterator upper_bound(const key_type& key) const {
-    return std::upper_bound(begin(), end(), key,
-      boost::bind(key_comp(), _1, boost::bind(&value_type::first, _2)));
+    auto c = key_comp();
+    auto f = [&](const key_type& a, const value_type& b) {
+      return c(a, b.first);
+    };
+    return std::upper_bound(begin(), end(), key, f);
   }
 
   std::pair<iterator,iterator> equal_range(const key_type& key) {
@@ -544,8 +659,11 @@ public:
     // argument types different from the iterator value_type, so we
     // have to do this.
     iterator low = lower_bound(key);
-    iterator high = std::upper_bound(low, end(), key,
-      boost::bind(key_comp(), _1, boost::bind(&value_type::first, _2)));
+    auto c = key_comp();
+    auto f = [&](const key_type& a, const value_type& b) {
+      return c(a, b.first);
+    };
+    iterator high = std::upper_bound(low, end(), key, f);
     return std::make_pair(low, high);
   }
 
@@ -566,7 +684,7 @@ public:
   mapped_type& operator[](const key_type& key) {
     iterator it = lower_bound(key);
     if (it == end() || key_comp()(key, it->first)) {
-      return insert(it, value_type(key, mapped_type())).first->second;
+      return insert(it, value_type(key, mapped_type()))->second;
     }
     return it->second;
   }
@@ -601,6 +719,3 @@ inline void swap(sorted_vector_map<K,V,C,A,G>& a,
 //////////////////////////////////////////////////////////////////////
 
 }
-
-#endif
-