}
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;
}
}
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(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, 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());
}
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(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, 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());
}
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;
}
return a.swap(b);
}
-/*
- * Efficiently moves all elements from b into a by taking advantage of sorted
- * inputs. Any keys that belong to both a and b will have the value from b.
- * Assumes that C and A can be constructed using the default constructor.
- *
- * std::merge cannot be used for this use case because in the event of equal
- * keys belonging to both a and b, it undefined which element will be inserted
- * into the output map last (and therefore be present in the map).
- */
-template<class K, class V, class C, class A, class G>
-inline void merge(sorted_vector_map<K,V,C,A,G>& a,
- sorted_vector_map<K,V,C,A,G>& b) {
- auto size = a.size();
- auto it_a = a.begin();
- auto it_b = b.begin();
- while (it_a != a.end() && it_b != b.end()) {
- auto comp = a.key_comp()(it_a->first, it_b->first);
- if (!comp) {
- if (!a.key_comp()(it_b->first, it_a->first)) {
- ++it_a;
- ++it_b;
- } else {
- ++size;
- ++it_b;
- }
- } else {
- ++it_a;
- }
- }
- if (it_b != b.end()) {
- size += b.end() - it_b;
- }
-
- sorted_vector_map<K,V,C,A,G> c;
- c.reserve(size);
- it_a = a.begin();
- it_b = b.begin();
- while (it_a != a.end() && it_b != b.end()) {
- auto comp = a.key_comp()(it_a->first, it_b->first);
- if (!comp) {
- if (!a.key_comp()(it_b->first, it_a->first)) {
- c.insert(c.end(), std::move(*it_b));
- ++it_a;
- ++it_b;
- } else {
- c.insert(c.end(), std::move(*it_b));
- ++it_b;
- }
- } else {
- c.insert(c.end(), std::move(*it_a));
- ++it_a;
- }
- }
- while (it_a != a.end()) {
- c.insert(c.end(), std::move(*it_a));
- ++it_a;
- }
- while (it_b != b.end()) {
- c.insert(c.end(), std::move(*it_b));
- ++it_b;
- }
- a.swap(c);
- b.clear();
-}
-
//////////////////////////////////////////////////////////////////////
}
#endif
-