Index: base/containers/flat_tree.h |
diff --git a/base/containers/flat_tree.h b/base/containers/flat_tree.h |
index c3a234fa784c4f0e0e151d9711d0265b756473fd..98b817cf02f941ffb32270a100123f805dbfa55a 100644 |
--- a/base/containers/flat_tree.h |
+++ b/base/containers/flat_tree.h |
@@ -184,8 +184,7 @@ class flat_tree { |
// Insert operations. |
// |
// Assume that every operation invalidates iterators and references. |
- // Insertion of one element can take O(size). See the Notes section in the |
- // class comments on why we do not currently implement range insertion. |
+ // Insertion of one element can take O(size). |
// Capacity of flat_tree grows in an implementation-defined manner. |
// |
// NOTE: Prefer to build a new flat_tree from a std::vector (or similar) |
@@ -197,6 +196,9 @@ class flat_tree { |
iterator insert(const_iterator position_hint, const value_type& x); |
iterator insert(const_iterator position_hint, value_type&& x); |
+ template <class InputIterator> |
+ void insert(InputIterator first, InputIterator last); |
+ |
template <class... Args> |
std::pair<iterator, bool> emplace(Args&&... args); |
@@ -600,6 +602,30 @@ auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::insert( |
} |
template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
+template <class InputIterator> |
+void flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::insert( |
+ InputIterator first, |
+ InputIterator last) { |
+ // Insert the values at the end. |
+ auto size = impl_.body_.size(); |
+ impl_.body_.insert(end(), first, last); |
+ auto mid = begin() + size; |
+ |
+ // Sort the newly inserted elements. |
+ std::stable_sort(mid, end(), impl_.get_value_comp()); |
+ |
+ // Merge the two sublists and unique them. |
+ std::inplace_merge(begin(), mid, end(), impl_.get_value_comp()); |
+ auto comparator = [this](const value_type& lhs, const value_type& rhs) { |
+ // lhs is already <= rhs due to sort, therefore |
+ // !(lhs < rhs) <=> lhs == rhs. |
+ return !impl_.get_value_comp()(lhs, rhs); |
+ }; |
+ auto erase_after = std::unique(begin(), end(), comparator); |
+ erase(erase_after, end()); |
+} |
+ |
+template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
template <class... Args> |
auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::emplace(Args&&... args) |
-> std::pair<iterator, bool> { |