1 #ifndef UTIL_SET_VECTOR_H
2 #define UTIL_SET_VECTOR_H
11 # include <initializer_list>
12 # define NOEXCEPT noexcept
13 # define STD_FORWARD(T, V) std::forward<T>(V)
16 # define STD_FORWARD(T, V) (V)
27 template <
typename Key,
typename Compare = std::less<Key>,
class Allocator = std::allocator<Key> >
29 typedef std::vector<Key, Allocator> content_t;
36 typedef Compare key_compare;
37 typedef Compare value_compare;
38 typedef Allocator allocator_type;
43 typedef typename std::allocator_traits<allocator_type>::pointer pointer;
44 typedef typename std::allocator_traits<allocator_type>::const_pointer const_pointer;
46 typedef typename allocator_type::pointer pointer;
47 typedef typename allocator_type::const_pointer const_pointer;
50 typedef typename content_t::const_iterator
iterator;
52 typedef typename content_t::size_type size_type;
53 typedef typename content_t::difference_type difference_type;
55 typedef std::reverse_iterator<iterator> reverse_iterator;
56 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
59 explicit multiset_vector(
const Compare& comp = Compare(),
const Allocator& alloc = Allocator())
66 template <
typename InputIterator>
67 multiset_vector(InputIterator first, InputIterator last,
const Compare& comp = Compare(),
68 const Allocator& alloc = Allocator())
69 : _content(first, last, alloc)
80 : _content(copy._content)
81 , _compare(copy._compare)
93 : _content(copy._content, alloc)
94 , _compare(copy._compare)
100 : _content(std::move(copy), alloc)
101 , _compare(std::move(copy._compare))
105 multiset_vector(std::initializer_list<value_type> values,
const Compare& comp = Compare(),
106 const Allocator& alloc = Allocator())
120 _content.assign(content.begin(), content.end());
127 _content = copy._content;
128 _compare = copy._compare;
133 allocator_type get_allocator()
const NOEXCEPT {
134 return _content.get_allocator();
142 return _content.begin();
145 return _content.end();
149 return _content.begin();
152 return _content.end();
155 reverse_iterator rbegin() NOEXCEPT {
156 return _content.rbegin();
158 reverse_iterator rend() NOEXCEPT {
159 return _content.rend();
162 const_reverse_iterator rbegin()
const NOEXCEPT {
163 return _content.rbegin();
165 const_reverse_iterator rend()
const NOEXCEPT {
166 return _content.rend();
170 return _content.begin();
173 return _content.end();
176 const_reverse_iterator crbegin()
const NOEXCEPT {
177 return _content.rbegin();
179 const_reverse_iterator crend()
const NOEXCEPT {
180 return _content.rend();
193 return _content.at(i);
196 const_pointer data()
const NOEXCEPT {
197 return _content.data();
201 return _content.front();
205 return _content.back();
218 bool empty() const NOEXCEPT {
219 return _content.empty();
221 size_type size() const NOEXCEPT {
222 return _content.size();
224 size_type max_size() const NOEXCEPT {
225 return _content.max_size();
229 void shrink_to_fit() {
230 _content.shrink_to_fit();
234 void reserve(size_type n) {
243 template <
typename ... Args>
iterator emplace(Args&& ... args)
245 auto value = value_type(std::forward<Args>(args) ...);
246 return this->_insert(std::move(value));
250 auto value = value_type(std::forward<Args>(args) ...);
251 return this->_insert_hint(hint, std::move(value));
254 iterator insert(value_type&& value) {
255 return this->_insert(std::move(value));
259 return this->_insert_hint(pos, value);
262 void insert(std::initializer_list<value_type> values)
264 for(
const value_type& v : values)
270 iterator insert(
const value_type& value) {
271 return this->_insert(value);
275 return this->_insert_hint(pos, value);
278 template <
typename InputIterator>
void insert(InputIterator first, InputIterator last)
281 _content.assign(first, last);
284 for(InputIterator it = first; it != last; ++it)
290 return _content.erase(this->remove_iterator_const(position));
293 size_type erase(
const key_type& x)
298 size_type n = std::distance(low, up);
299 this->erase(low, up);
307 return _content.erase(remove_iterator_const(first), remove_iterator_const(last));
310 void swap(multiset_vector& other)
313 swap(_content, other._content);
316 void clear() NOEXCEPT {
324 key_compare key_comp()
const {
327 value_compare value_comp()
const {
338 return this->remove_iterator_const(const_cast<const multiset_vector*>(
this)->find(k));
343 const_iterator pos = std::lower_bound(this->begin(), this->end(), k, this->key_comp());
344 if(pos != this->end() and this->equiv_keys(*pos, k))
349 size_type count(
const key_type& k)
const
353 return std::distance(low, up);
356 iterator lower_bound(
const key_type& k)
358 return this->remove_iterator_const(const_cast<const multiset_vector*>(
this)->lower_bound(k));
363 return std::lower_bound(this->begin(), this->end(), k, this->key_comp());
366 iterator upper_bound(
const key_type& k)
368 return this->remove_iterator_const(const_cast<const multiset_vector*>(
this)->upper_bound(k));
373 return std::upper_bound(this->begin(), this->end(), k, this->key_comp());
376 std::pair<iterator, iterator> equal_range(
const key_type& k)
378 typedef std::pair<const_iterator, const_iterator> const_result_t;
379 const_result_t res =
const_cast<const multiset_vector*
>(
this)->equal_range(k);
380 typedef std::pair<iterator, iterator> result_t;
381 return result_t(this->remove_iterator_const(res.first), this->remove_iterator_const(res.second));
384 std::pair<const_iterator, const_iterator> equal_range(
const key_type& k)
const
386 typedef std::pair<const_iterator, const_iterator> result_t;
387 return result_t(this->lower_bound(k), this->upper_bound(k));
390 friend bool operator==(
const multiset_vector& v1,
const multiset_vector& v2)
392 if(v1.size() != v2.size())
394 for(
const_iterator it1 = v1.begin(), it2 = v2.begin(); it1 != v1.end(); ++it1, ++it2)
395 if(v1.differ_keys(*it1, *it2))
400 friend bool operator!=(
const multiset_vector& v1,
const multiset_vector& v2) {
401 return not (v1 == v2);
404 friend bool operator<(
const multiset_vector& v1,
const multiset_vector& v2)
408 for(; it1 != last_v1 and it2 != last_v2; ++it1, ++it2) {
409 if(v1.compare(*it1, *it2))
411 else if(v1.compare(*it2, *it1))
419 friend bool operator>(
const multiset_vector& v1,
const multiset_vector& v2)
423 for(; it1 != last_v1 and it2 != last_v2; ++it1, ++it2) {
424 if(v1.compare(*it1, *it2))
426 else if(v1.compare(*it2, *it1))
434 friend bool operator<=(
const multiset_vector& v1,
const multiset_vector& v2) {
435 return not (v1 > v2);
438 friend bool operator>=(
const multiset_vector& v1,
const multiset_vector& v2) {
439 return not (v1 < v2);
443 typename content_t::iterator remove_iterator_const(
const_iterator it) {
444 return _content.begin() + (it - begin());
449 if(_content.size() == 0)
451 std::sort(_content.begin(), _content.end(), this->key_comp());
456 return std::upper_bound(first, last, value, this->key_comp());
461 if(hint == this->end()) {
463 if(this->compare(this->back(), value))
466 return this->_find_insert_range(this->begin(), this->end(), value);
470 if(this->compare(value, *hint)) {
471 if(hint == this->begin())
474 if(this->compare(*(--before), value))
476 return this->_find_insert_range(this->begin(), before, value);
477 }
else if(this->compare(*hint, value)) {
479 if(++after == this->end() or this->compare(value, *after))
481 return this->_find_insert_range(after, this->end(), value);
486 template <
typename T>
493 return _content.insert(this->remove_iterator_const(it), STD_FORWARD(T, value));
496 template <
typename T>
503 iterator found = this->_find_insert_range(this->begin(), this->end(), value);
504 return this->_insert_vector(found, STD_FORWARD(T, value));
507 template <
typename T>
514 iterator found = this->_find_insert_hint(hint, value);
515 return this->_insert_vector(found, STD_FORWARD(T, value));
518 bool equiv_keys(
const key_type& k1,
const key_type& k2)
const
520 return not (this->compare(k1, k2) or this->compare(k2, k1));
523 bool differ_keys(
const key_type& k1,
const key_type& k2)
const
525 return this->compare(k1, k2) or this->compare(k2, k1);
528 bool compare(const key_type& k1, const key_type& k2)
const {
529 return _compare(k1, k2);
533 template <
typename Key,
typename Compare,
typename Allocator>
534 void swap(multiset_vector<Key, Compare, Allocator>& v1, multiset_vector<Key, Compare, Allocator>& v2)
544 template <
typename Key,
typename Compare = std::less<Key>,
class Allocator = std::allocator<Key> >
551 typedef typename super_type::key_compare key_compare;
552 typedef typename super_type::value_compare value_compare;
553 typedef typename super_type::allocator_type allocator_type;
557 typedef typename super_type::pointer pointer;
558 typedef typename super_type::const_pointer const_pointer;
560 typedef typename super_type::iterator
iterator;
562 typedef typename super_type::size_type size_type;
563 typedef typename super_type::difference_type difference_type;
565 typedef typename super_type::reverse_iterator reverse_iterator;
566 typedef typename super_type::const_reverse_iterator const_reverse_iterator;
569 explicit set_vector(
const Compare& comp = Compare(),
const Allocator& alloc = Allocator())
575 template <
typename InputIterator>
576 set_vector(InputIterator first, InputIterator last,
const Compare& comp = Compare(),
577 const Allocator& alloc = Allocator())
609 set_vector(std::initializer_list<value_type> values,
const Compare& comp = Compare(),
610 const Allocator& alloc = Allocator())
611 :
set_vector(values.begin(), values.end(), comp, alloc)
622 set_vector& operator=(std::initializer_list<value_type> content)
624 super_type::operator=(content);
631 super_type::operator=(copy);
642 template <
typename ... Args> std::pair<iterator, bool> emplace(Args&& ... args)
644 auto value =
value_type(std::forward<Args>(args) ...);
645 return this->_insert(std::move(value));
647 template <
typename ... Args> std::pair<iterator, bool> emplace_hint(
const_iterator hint, Args&& ... args)
649 auto value =
value_type(std::forward<Args>(args) ...);
650 return this->_insert_hint(hint, std::move(value));
653 std::pair<iterator, bool> insert(
value_type&& value) {
654 return this->_insert(std::move(value));
658 return this->_insert_hint(pos, value);
661 void insert(std::initializer_list<value_type> values)
669 std::pair<iterator, bool> insert(
const value_type& value) {
670 return this->_insert(value);
675 return this->_insert_hint(pos, value);
678 template <
typename InputIterator>
void insert(InputIterator first, InputIterator last)
680 for(InputIterator it = first; it != last; ++it)
684 using super_type::erase;
688 const_iterator it = std::lower_bound(this->begin(), this->end(), x, this->key_comp());
689 if(it != this->end() and this->equiv_keys(*it, x)) {
697 super_type::swap(other);
705 size_type s = this->size();
708 for(
size_t i = s - 1; i > 0; --i) {
709 if(this->equiv_keys((*
this)[i], (*
this)[i - 1]))
710 this->erase(this->begin() + i);
717 typedef std::pair<const_iterator, bool> result_t;
718 const_iterator pos = std::lower_bound(first, last, value, this->key_comp());
719 return result_t(pos, (pos == last or this->differ_keys(*pos, value)));
724 typedef std::pair<iterator, bool> result_t;
725 if(hint == this->end()) {
726 if(this->size() > 0) {
727 if(this->compare(this->back(), value))
728 return result_t(this->end(),
true);
730 return _find_insert_range(this->begin(), this->end(), value);
732 return result_t(this->end(), value);
734 if(this->compare(value, *hint)) {
735 if(hint == this->begin())
736 return result_t(hint,
true);
738 if(this->compare(*(--before), value))
739 return result_t(hint,
true);
740 return this->_find_insert_range(this->begin(), before, value);
741 }
else if(this->compare(*hint, value)) {
743 if(++after == this->end() or this->compare(value, *after))
744 return result_t(after,
true);
745 return this->_find_insert_range(after, this->end(), value);
747 return result_t(hint,
false);
751 template <
typename T> std::pair<iterator, bool> _insert(T&& value)
753 std::pair<iterator, bool> _insert(
const value_type& value)
756 std::pair<iterator, bool> found = this->_find_insert_range(this->begin(), this->end(), value);
758 found.first = this->_insert_vector(found.first, STD_FORWARD(T, value));
763 template <
typename T> std::pair<iterator, bool> _insert_hint(
const_iterator hint, T&& value)
768 std::pair<iterator, bool> found = this->_find_insert_hint(hint, value);
770 found.first = this->_insert_vector(found.first, STD_FORWARD(T, value));
775 template <
typename Key,
typename Compare,
typename Allocator>
785 #endif // UTIL_SET_VECTOR_H
Implementation of a set using a sorted vector as container.
Definition: SetVector.hpp:545
Implementation of a multiset using a sorted vector as container.
Definition: SetVector.hpp:28
const content_t & vector() const
Return the underlying vector.
Definition: SetVector.hpp:209