11 #ifndef UTIL_SET_VECTOR_H 12 #define UTIL_SET_VECTOR_H 21 # include <initializer_list> 22 # define NOEXCEPT noexcept 23 # define STD_FORWARD(T, V) std::forward<T>(V) 26 # define STD_FORWARD(T, V) (V) 37 template <
typename Key,
typename Compare = std::less<Key>,
class Allocator = std::allocator<Key> >
39 typedef std::vector<Key, Allocator> content_t;
46 typedef Compare key_compare;
47 typedef Compare value_compare;
48 typedef Allocator allocator_type;
53 typedef typename std::allocator_traits<allocator_type>::pointer pointer;
54 typedef typename std::allocator_traits<allocator_type>::const_pointer const_pointer;
56 typedef typename allocator_type::pointer pointer;
57 typedef typename allocator_type::const_pointer const_pointer;
60 typedef typename content_t::const_iterator
iterator;
62 typedef typename content_t::size_type size_type;
63 typedef typename content_t::difference_type difference_type;
65 typedef std::reverse_iterator<iterator> reverse_iterator;
66 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
69 explicit multiset_vector(
const Compare& comp = Compare(),
const Allocator& alloc = Allocator())
76 template <
typename InputIterator>
77 multiset_vector(InputIterator first, InputIterator last,
const Compare& comp = Compare(),
78 const Allocator& alloc = Allocator())
79 : _content(first, last, alloc)
90 : _content(copy._content)
91 , _compare(copy._compare)
103 : _content(copy._content, alloc)
104 , _compare(copy._compare)
110 : _content(std::move(copy), alloc)
111 , _compare(std::move(copy._compare))
115 multiset_vector(std::initializer_list<value_type> values,
const Compare& comp = Compare(),
116 const Allocator& alloc = Allocator())
130 _content.assign(content.begin(), content.end());
137 _content = copy._content;
138 _compare = copy._compare;
143 allocator_type get_allocator()
const NOEXCEPT {
144 return _content.get_allocator();
151 iterator begin() NOEXCEPT {
152 return _content.begin();
154 iterator end() NOEXCEPT {
155 return _content.end();
158 const_iterator begin()
const NOEXCEPT {
159 return _content.begin();
161 const_iterator end()
const NOEXCEPT {
162 return _content.end();
165 reverse_iterator rbegin() NOEXCEPT {
166 return _content.rbegin();
168 reverse_iterator rend() NOEXCEPT {
169 return _content.rend();
172 const_reverse_iterator rbegin()
const NOEXCEPT {
173 return _content.rbegin();
175 const_reverse_iterator rend()
const NOEXCEPT {
176 return _content.rend();
179 const_iterator cbegin()
const NOEXCEPT {
180 return _content.begin();
182 const_iterator cend()
const NOEXCEPT {
183 return _content.end();
186 const_reverse_iterator crbegin()
const NOEXCEPT {
187 return _content.rbegin();
189 const_reverse_iterator crend()
const NOEXCEPT {
190 return _content.rend();
198 const_reference operator[](size_type i)
const {
202 const_reference at(size_type i)
const {
203 return _content.at(i);
206 const_pointer data()
const NOEXCEPT {
207 return _content.data();
210 const_reference front()
const {
211 return _content.front();
214 const_reference back()
const {
215 return _content.back();
228 bool empty()
const NOEXCEPT {
229 return _content.empty();
231 size_type size()
const NOEXCEPT {
232 return _content.size();
234 size_type max_size()
const NOEXCEPT {
235 return _content.max_size();
239 void shrink_to_fit() {
240 _content.shrink_to_fit();
244 void reserve(size_type n) {
253 template <
typename ... Args> iterator emplace(Args&& ... args)
255 auto value = value_type(std::forward<Args>(args) ...);
256 return this->_insert(std::move(value));
258 template <
typename ... Args> iterator emplace_hint(const_iterator hint, Args&& ... args)
260 auto value = value_type(std::forward<Args>(args) ...);
261 return this->_insert_hint(hint, std::move(value));
264 iterator insert(value_type&& value) {
265 return this->_insert(std::move(value));
268 iterator insert(const_iterator pos, value_type&& value) {
269 return this->_insert_hint(pos, value);
272 void insert(std::initializer_list<value_type> values)
274 for(
const value_type& v : values)
280 iterator insert(
const value_type& value) {
281 return this->_insert(value);
284 iterator insert(const_iterator pos,
const value_type& value) {
285 return this->_insert_hint(pos, value);
288 template <
typename InputIterator>
void insert(InputIterator first, InputIterator last)
291 _content.assign(first, last);
294 for(InputIterator it = first; it != last; ++it)
299 iterator erase(const_iterator position) {
300 return _content.erase(this->remove_iterator_const(position));
303 size_type erase(
const key_type& x)
305 const_iterator low = this->lower_bound(x);
306 const_iterator up = this->upper_bound(x);
308 size_type n = std::distance(low, up);
309 this->erase(low, up);
315 iterator erase(const_iterator first, const_iterator last)
317 return _content.erase(remove_iterator_const(first), remove_iterator_const(last));
323 swap(_content, other._content);
326 void clear() NOEXCEPT {
334 key_compare key_comp()
const {
337 value_compare value_comp()
const {
346 iterator find(
const key_type& k)
348 return this->remove_iterator_const(const_cast<const multiset_vector*>(
this)->find(k));
351 const_iterator find(
const key_type& k)
const 353 const_iterator pos = std::lower_bound(this->begin(), this->end(), k, this->key_comp());
354 if(pos != this->end() and this->equiv_keys(*pos, k))
359 size_type count(
const key_type& k)
const 361 const_iterator low = this->lower_bound(k);
362 const_iterator up = this->upper_bound(k);
363 return std::distance(low, up);
366 iterator lower_bound(
const key_type& k)
368 return this->remove_iterator_const(const_cast<const multiset_vector*>(
this)->lower_bound(k));
371 const_iterator lower_bound(
const key_type& k)
const 373 return std::lower_bound(this->begin(), this->end(), k, this->key_comp());
376 iterator upper_bound(
const key_type& k)
378 return this->remove_iterator_const(const_cast<const multiset_vector*>(
this)->upper_bound(k));
381 const_iterator upper_bound(
const key_type& k)
const 383 return std::upper_bound(this->begin(), this->end(), k, this->key_comp());
386 std::pair<iterator, iterator> equal_range(
const key_type& k)
388 typedef std::pair<const_iterator, const_iterator> const_result_t;
389 const_result_t res =
const_cast<const multiset_vector*
>(
this)->equal_range(k);
390 typedef std::pair<iterator, iterator> result_t;
391 return result_t(this->remove_iterator_const(res.first), this->remove_iterator_const(res.second));
394 std::pair<const_iterator, const_iterator> equal_range(
const key_type& k)
const 396 typedef std::pair<const_iterator, const_iterator> result_t;
397 return result_t(this->lower_bound(k), this->upper_bound(k));
402 if(v1.size() != v2.size())
404 for(const_iterator it1 = v1.begin(), it2 = v2.begin(); it1 != v1.end(); ++it1, ++it2)
405 if(v1.differ_keys(*it1, *it2))
411 return not (v1 == v2);
416 const_iterator it1 = v1.begin(), it2 = v2.begin();
417 const_iterator last_v1 = v1.end(), last_v2 = v2.end();
418 for(; it1 != last_v1 and it2 != last_v2; ++it1, ++it2) {
419 if(v1.compare(*it1, *it2))
421 else if(v1.compare(*it2, *it1))
431 const_iterator it1 = v1.begin(), it2 = v2.begin();
432 const_iterator last_v1 = v1.end(), last_v2 = v2.end();
433 for(; it1 != last_v1 and it2 != last_v2; ++it1, ++it2) {
434 if(v1.compare(*it1, *it2))
436 else if(v1.compare(*it2, *it1))
445 return not (v1 > v2);
449 return not (v1 < v2);
453 typename content_t::iterator remove_iterator_const(const_iterator it) {
454 return _content.begin() + (it - begin());
459 if(_content.size() == 0)
461 std::sort(_content.begin(), _content.end(), this->key_comp());
464 iterator _find_insert_range(const_iterator first, const_iterator last,
const value_type& value)
const 466 return std::upper_bound(first, last, value, this->key_comp());
469 const_iterator _find_insert_hint(const_iterator hint,
const value_type& value)
471 if(hint == this->end()) {
473 if(this->compare(this->back(), value))
476 return this->_find_insert_range(this->begin(), this->end(), value);
480 if(this->compare(value, *hint)) {
481 if(hint == this->begin())
483 const_iterator before = hint;
484 if(this->compare(*(--before), value))
486 return this->_find_insert_range(this->begin(), before, value);
487 }
else if(this->compare(*hint, value)) {
488 const_iterator after = hint;
489 if(++after == this->end() or this->compare(value, *after))
491 return this->_find_insert_range(after, this->end(), value);
496 template <
typename T>
498 iterator _insert_vector(const_iterator it, T&& value)
500 iterator _insert_vector(const_iterator it,
const T& value)
503 return _content.insert(this->remove_iterator_const(it), STD_FORWARD(T, value));
506 template <
typename T>
508 iterator _insert(T&& value)
510 iterator _insert(
const T& value)
513 iterator found = this->_find_insert_range(this->begin(), this->end(), value);
514 return this->_insert_vector(found, STD_FORWARD(T, value));
517 template <
typename T>
519 iterator _insert_hint(const_iterator hint, T&& value)
521 iterator _insert_hint(const_iterator hint,
const T& value)
524 iterator found = this->_find_insert_hint(hint, value);
525 return this->_insert_vector(found, STD_FORWARD(T, value));
528 bool equiv_keys(
const key_type& k1,
const key_type& k2)
const 530 return not (this->compare(k1, k2) or this->compare(k2, k1));
533 bool differ_keys(
const key_type& k1,
const key_type& k2)
const 535 return this->compare(k1, k2) or this->compare(k2, k1);
538 bool compare(
const key_type& k1,
const key_type& k2)
const {
539 return _compare(k1, k2);
543 template <
typename Key,
typename Compare,
typename Allocator>
554 template <
typename Key,
typename Compare = std::less<Key>,
class Allocator = std::allocator<Key> >
561 typedef typename super_type::key_compare key_compare;
562 typedef typename super_type::value_compare value_compare;
563 typedef typename super_type::allocator_type allocator_type;
567 typedef typename super_type::pointer pointer;
568 typedef typename super_type::const_pointer const_pointer;
570 typedef typename super_type::iterator
iterator;
572 typedef typename super_type::size_type size_type;
573 typedef typename super_type::difference_type difference_type;
575 typedef typename super_type::reverse_iterator reverse_iterator;
576 typedef typename super_type::const_reverse_iterator const_reverse_iterator;
579 explicit set_vector(
const Compare& comp = Compare(),
const Allocator& alloc = Allocator())
581 : super_type(comp, alloc)
585 template <
typename InputIterator>
586 set_vector(InputIterator first, InputIterator last,
const Compare& comp = Compare(),
587 const Allocator& alloc = Allocator())
588 : super_type(first, last, comp, alloc)
609 : super_type(copy, alloc)
615 : super_type(std::move(copy), alloc)
619 set_vector(std::initializer_list<value_type> values,
const Compare& comp = Compare(),
620 const Allocator& alloc = Allocator())
621 :
set_vector(values.begin(), values.end(), comp, alloc)
632 set_vector& operator=(std::initializer_list<value_type> content)
634 super_type::operator=(content);
641 super_type::operator=(copy);
652 template <
typename ... Args> std::pair<iterator, bool> emplace(Args&& ... args)
654 auto value = value_type(std::forward<Args>(args) ...);
655 return this->_insert(std::move(value));
657 template <
typename ... Args> std::pair<iterator, bool> emplace_hint(const_iterator hint, Args&& ... args)
659 auto value = value_type(std::forward<Args>(args) ...);
660 return this->_insert_hint(hint, std::move(value));
663 std::pair<iterator, bool> insert(value_type&& value) {
664 return this->_insert(std::move(value));
667 std::pair<iterator, bool> insert(const_iterator pos, value_type&& value) {
668 return this->_insert_hint(pos, value);
671 void insert(std::initializer_list<value_type> values)
673 for(
const value_type& v : values)
679 std::pair<iterator, bool> insert(
const value_type& value) {
680 return this->_insert(value);
683 std::pair<iterator, bool> insert(const_iterator pos,
const value_type& value)
685 return this->_insert_hint(pos, value);
688 template <
typename InputIterator>
void insert(InputIterator first, InputIterator last)
690 for(InputIterator it = first; it != last; ++it)
694 using super_type::erase;
696 size_type erase(
const key_type& x)
698 const_iterator it = std::lower_bound(this->begin(), this->end(), x, this->key_comp());
699 if(it != this->end() and this->equiv_keys(*it, x)) {
707 super_type::swap(other);
715 size_type s = this->size();
718 for(
size_t i = s - 1; i > 0; --i) {
719 if(this->equiv_keys((*
this)[i], (*
this)[i - 1]))
720 this->erase(this->begin() + i);
724 std::pair<iterator, bool> _find_insert_range(const_iterator first, const_iterator last,
725 const value_type& value)
const 727 typedef std::pair<const_iterator, bool> result_t;
728 const_iterator pos = std::lower_bound(first, last, value, this->key_comp());
729 return result_t(pos, (pos == last or this->differ_keys(*pos, value)));
732 std::pair<const_iterator, bool> _find_insert_hint(const_iterator hint,
const value_type& value)
734 typedef std::pair<iterator, bool> result_t;
735 if(hint == this->end()) {
736 if(this->size() > 0) {
737 if(this->compare(this->back(), value))
738 return result_t(this->end(),
true);
740 return _find_insert_range(this->begin(), this->end(), value);
742 return result_t(this->end(), value);
744 if(this->compare(value, *hint)) {
745 if(hint == this->begin())
746 return result_t(hint,
true);
747 const_iterator before = hint;
748 if(this->compare(*(--before), value))
749 return result_t(hint,
true);
750 return this->_find_insert_range(this->begin(), before, value);
751 }
else if(this->compare(*hint, value)) {
752 const_iterator after = hint;
753 if(++after == this->end() or this->compare(value, *after))
754 return result_t(after,
true);
755 return this->_find_insert_range(after, this->end(), value);
757 return result_t(hint,
false);
761 template <
typename T> std::pair<iterator, bool> _insert(T&& value)
763 std::pair<iterator, bool> _insert(
const value_type& value)
766 std::pair<iterator, bool> found = this->_find_insert_range(this->begin(), this->end(), value);
768 found.first = this->_insert_vector(found.first, STD_FORWARD(T, value));
773 template <
typename T> std::pair<iterator, bool> _insert_hint(const_iterator hint, T&& value)
775 std::pair<iterator, bool> _insert_hint(const_iterator hint,
const value_type& value)
778 std::pair<iterator, bool> found = this->_find_insert_hint(hint, value);
780 found.first = this->_insert_vector(found.first, STD_FORWARD(T, value));
785 template <
typename Key,
typename Compare,
typename Allocator>
795 #endif // UTIL_SET_VECTOR_H
Implementation of a set using a sorted vector as container.
Definition: SetVector.hpp:555
This namespace contains all the API of MorphoGraphX.
Definition: Assert.hpp:26
Implementation of a multiset using a sorted vector as container.
Definition: SetVector.hpp:38
const content_t & vector() const
Return the underlying vector.
Definition: SetVector.hpp:219