HelenOS sources
This source file includes following definitions.
- get_allocator
- begin
- begin
- end
- end
- rbegin
- rbegin
- rend
- rend
- cbegin
- cend
- crbegin
- crend
- empty
- max_size
- emplace
- emplace_hint
- insert
- insert
- insert
- insert
- insert
- insert
- erase
- erase
- erase
- swap
- clear
- find
- find
- find
- find
- count
- count
- lower_bound
- lower_bound
- lower_bound
- lower_bound
- upper_bound
- upper_bound
- upper_bound
- upper_bound
- equal_range
- equal_range
- equal_range
- equal_range
- get_allocator
- begin
- begin
- end
- end
- rbegin
- rbegin
- rend
- rend
- cbegin
- cend
- crbegin
- crend
- empty
- max_size
- emplace
- emplace_hint
- insert
- insert
- insert
- insert
- insert
- insert
- erase
- erase
- erase
- swap
- clear
- find
- find
- find
- find
- count
- count
- lower_bound
- lower_bound
- lower_bound
- lower_bound
- upper_bound
- upper_bound
- upper_bound
- upper_bound
- equal_range
- equal_range
- equal_range
- equal_range
#ifndef LIBCPP_BITS_ADT_SET
#define LIBCPP_BITS_ADT_SET
#include <__bits/adt/rbtree.hpp>
#include <functional>
#include <iterator>
#include <memory>
#include <utility>
namespace std
{
template<
class Key,
class Compare = less<Key>,
class Alloc = allocator<Key>
>
class set
{
public:
using key_type = Key;
using value_type = Key;
using key_compare = Compare;
using value_compare = Compare;
using allocator_type = Alloc;
using pointer = typename allocator_traits<allocator_type>::pointer;
using const_pointer = typename allocator_traits<allocator_type>::const_pointer;
using reference = value_type&;
using const_reference = const value_type&;
using size_type = size_t;
using difference_type = ptrdiff_t;
using node_type = aux::rbtree_single_node<value_type>;
using iterator = aux::rbtree_const_iterator<
value_type, const_reference, const_pointer, size_type, node_type
>;
using const_iterator = iterator;
using reverse_iterator = std::reverse_iterator<iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;
set()
: set{key_compare{}}
{ }
explicit set(const key_compare& comp,
const allocator_type& alloc = allocator_type{})
: tree_{comp}, allocator_{alloc}
{ }
template<class InputIterator>
set(InputIterator first, InputIterator last,
const key_compare& comp = key_compare{},
const allocator_type& alloc = allocator_type{})
: set{comp, alloc}
{
insert(first, last);
}
set(const set& other)
: set{other, other.allocator_}
{ }
set(set&& other)
: tree_{move(other.tree_)}, allocator_{move(other.allocator_)}
{ }
explicit set(const allocator_type& alloc)
: tree_{}, allocator_{alloc}
{ }
set(const set& other, const allocator_type& alloc)
: tree_{other.tree_}, allocator_{alloc}
{ }
set(set&& other, const allocator_type& alloc)
: tree_{move(other.tree_)}, allocator_{alloc}
{ }
set(initializer_list<value_type> init,
const key_compare& comp = key_compare{},
const allocator_type& alloc = allocator_type{})
: set{comp, alloc}
{
insert(init.begin(), init.end());
}
template<class InputIterator>
set(InputIterator first, InputIterator last,
const allocator_type& alloc)
: set{first, last, key_compare{}, alloc}
{ }
set(initializer_list<value_type> init,
const allocator_type& alloc)
: set{init, key_compare{}, alloc}
{ }
~set()
{ }
set& operator=(const set& other)
{
tree_ = other.tree_;
allocator_ = other.allocator_;
return *this;
}
set& operator=(set&& other)
noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
is_nothrow_move_assignable<key_compare>::value)
{
tree_ = move(other.tree_);
allocator_ = move(other.allocator_);
return *this;
}
set& operator=(initializer_list<value_type>& init)
{
tree_.clear();
insert(init.begin(), init.end());
return *this;
}
allocator_type get_allocator() const noexcept
{
return allocator_;
}
iterator begin() noexcept
{
return tree_.begin();
}
const_iterator begin() const noexcept
{
return tree_.begin();
}
iterator end() noexcept
{
return tree_.end();
}
const_iterator end() const noexcept
{
return tree_.end();
}
reverse_iterator rbegin() noexcept
{
return tree_.rbegin();
}
const_reverse_iterator rbegin() const noexcept
{
return tree_.rbegin();
}
reverse_iterator rend() noexcept
{
return tree_.rend();
}
const_reverse_iterator rend() const noexcept
{
return tree_.rend();
}
const_iterator cbegin() const noexcept
{
return tree_.cbegin();
}
const_iterator cend() const noexcept
{
return tree_.cend();
}
const_reverse_iterator crbegin() const noexcept
{
return tree_.crbegin();
}
const_reverse_iterator crend() const noexcept
{
return tree_.crend();
}
bool empty() const noexcept
{
return tree_.empty();
}
size_type size() const noexcept
{
return tree_.size();
}
size_type max_size() const noexcept
{
return tree_.max_size(allocator_);
}
template<class... Args>
pair<iterator, bool> emplace(Args&&... args)
{
return tree_.emplace(forward<Args>(args)...);
}
template<class... Args>
iterator emplace_hint(const_iterator, Args&&... args)
{
return emplace(forward<Args>(args)...).first;
}
pair<iterator, bool> insert(const value_type& val)
{
return tree_.insert(val);
}
pair<iterator, bool> insert(value_type&& val)
{
return tree_.insert(forward<value_type>(val));
}
iterator insert(const_iterator, const value_type& val)
{
return insert(val).first;
}
iterator insert(const_iterator, value_type&& val)
{
return insert(forward<value_type>(val)).first;
}
template<class InputIterator>
void insert(InputIterator first, InputIterator last)
{
while (first != last)
insert(*first++);
}
void insert(initializer_list<value_type> init)
{
insert(init.begin(), init.end());
}
iterator erase(const_iterator position)
{
return tree_.erase(position);
}
size_type erase(const key_type& key)
{
return tree_.erase(key);
}
iterator erase(const_iterator first, const_iterator last)
{
while (first != last)
first = erase(first);
return iterator{
first.node(), first.end()
};
}
void swap(set& other)
noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
noexcept(std::swap(declval<key_compare>(), declval<key_compare>())))
{
tree_.swap(other.tree_);
std::swap(allocator_, other.allocator_);
}
void clear() noexcept
{
tree_.clear();
}
key_compare key_comp() const
{
return tree_.key_comp();
}
value_compare value_comp() const
{
return tree_.value_comp();
}
iterator find(const key_type& key)
{
return tree_.find(key);
}
const_iterator find(const key_type& key) const
{
return tree_.find(key);
}
template<class K>
iterator find(
const K& key,
enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
)
{
return tree_.find(key);
}
template<class K>
const_iterator find(
const K& key,
enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
) const
{
return tree_.find(key);
}
size_type count(const key_type& key) const
{
return tree_.count(key);
}
template<class K>
size_type count(
const K& key,
enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
) const
{
return tree_.count(key);
}
iterator lower_bound(const key_type& key)
{
return tree_.lower_bound(key);
}
const_iterator lower_bound(const key_type& key) const
{
return tree_.lower_bound(key);
}
template<class K>
iterator lower_bound(
const K& key,
enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
)
{
return tree_.lower_bound(key);
}
template<class K>
const_iterator lower_bound(
const K& key,
enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
) const
{
return tree_.lower_bound(key);
}
iterator upper_bound(const key_type& key)
{
return tree_.upper_bound(key);
}
const_iterator upper_bound(const key_type& key) const
{
return tree_.upper_bound(key);
}
template<class K>
iterator upper_bound(
const K& key,
enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
)
{
return tree_.upper_bound(key);
}
template<class K>
const_iterator upper_bound(
const K& key,
enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
) const
{
return tree_.upper_bound(key);
}
pair<iterator, iterator> equal_range(const key_type& key)
{
return tree_.equal_range(key);
}
pair<const_iterator, const_iterator> equal_range(const key_type& key) const
{
return tree_.equal_range(key);
}
template<class K>
pair<iterator, iterator> equal_range(
const K& key,
enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
)
{
return tree_.equal_range(key);
}
template<class K>
pair<const_iterator, const_iterator> equal_range(
const K& key,
enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
) const
{
return tree_.equal_range(key);
}
private:
using tree_type = aux::rbtree<
key_type, key_type, aux::key_no_value_key_extractor<key_type>,
key_compare, allocator_type, size_type,
iterator, const_iterator,
aux::rbtree_single_policy, node_type
>;
tree_type tree_;
allocator_type allocator_;
template<class K, class C, class A>
friend bool operator==(const set<K, C, A>&,
const set<K, C, A>&);
};
template<class Key, class Compare, class Allocator>
bool operator==(const set<Key, Compare, Allocator>& lhs,
const set<Key, Compare, Allocator>& rhs)
{
return lhs.tree_.is_eq_to(rhs.tree_);
}
template<class Key, class Compare, class Allocator>
bool operator<(const set<Key, Compare, Allocator>& lhs,
const set<Key, Compare, Allocator>& rhs)
{
return lexicographical_compare(
lhs.begin(), lhs.end(),
rhs.begin(), rhs.end(),
lhs.key_comp()
);
}
template<class Key, class Compare, class Allocator>
bool operator!=(const set<Key, Compare, Allocator>& lhs,
const set<Key, Compare, Allocator>& rhs)
{
return !(lhs == rhs);
}
template<class Key, class Compare, class Allocator>
bool operator>(const set<Key, Compare, Allocator>& lhs,
const set<Key, Compare, Allocator>& rhs)
{
return rhs < lhs;
}
template<class Key, class Compare, class Allocator>
bool operator>=(const set<Key, Compare, Allocator>& lhs,
const set<Key, Compare, Allocator>& rhs)
{
return !(lhs < rhs);
}
template<class Key, class Compare, class Allocator>
bool operator<=(const set<Key, Compare, Allocator>& lhs,
const set<Key, Compare, Allocator>& rhs)
{
return !(rhs < lhs);
}
template<
class Key,
class Compare = less<Key>,
class Alloc = allocator<Key>
>
class multiset
{
public:
using key_type = Key;
using value_type = Key;
using key_compare = Compare;
using value_compare = Compare;
using allocator_type = Alloc;
using pointer = typename allocator_traits<allocator_type>::pointer;
using const_pointer = typename allocator_traits<allocator_type>::const_pointer;
using reference = value_type&;
using const_reference = const value_type&;
using size_type = size_t;
using difference_type = ptrdiff_t;
using node_type = aux::rbtree_multi_node<value_type>;
using iterator = aux::rbtree_const_iterator<
value_type, const_reference, const_pointer, size_type, node_type
>;
using const_iterator = iterator;
using reverse_iterator = std::reverse_iterator<iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;
multiset()
: multiset{key_compare{}}
{ }
explicit multiset(const key_compare& comp,
const allocator_type& alloc = allocator_type{})
: tree_{comp}, allocator_{alloc}
{ }
template<class InputIterator>
multiset(InputIterator first, InputIterator last,
const key_compare& comp = key_compare{},
const allocator_type& alloc = allocator_type{})
: multiset{comp, alloc}
{
insert(first, last);
}
multiset(const multiset& other)
: multiset{other, other.allocator_}
{ }
multiset(multiset&& other)
: tree_{move(other.tree_)}, allocator_{move(other.allocator_)}
{ }
explicit multiset(const allocator_type& alloc)
: tree_{}, allocator_{alloc}
{ }
multiset(const multiset& other, const allocator_type& alloc)
: tree_{other.tree_}, allocator_{alloc}
{ }
multiset(multiset&& other, const allocator_type& alloc)
: tree_{move(other.tree_)}, allocator_{alloc}
{ }
multiset(initializer_list<value_type> init,
const key_compare& comp = key_compare{},
const allocator_type& alloc = allocator_type{})
: multiset{comp, alloc}
{
insert(init.begin(), init.end());
}
template<class InputIterator>
multiset(InputIterator first, InputIterator last,
const allocator_type& alloc)
: multiset{first, last, key_compare{}, alloc}
{ }
multiset(initializer_list<value_type> init,
const allocator_type& alloc)
: multiset{init, key_compare{}, alloc}
{ }
~multiset()
{ }
multiset& operator=(const multiset& other)
{
tree_ = other.tree_;
allocator_ = other.allocator_;
return *this;
}
multiset& operator=(multiset&& other)
noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
is_nothrow_move_assignable<key_compare>::value)
{
tree_ = move(other.tree_);
allocator_ = move(other.allocator_);
return *this;
}
multiset& operator=(initializer_list<value_type>& init)
{
tree_.clear();
insert(init.begin(), init.end());
return *this;
}
allocator_type get_allocator() const noexcept
{
return allocator_;
}
iterator begin() noexcept
{
return tree_.begin();
}
const_iterator begin() const noexcept
{
return tree_.begin();
}
iterator end() noexcept
{
return tree_.end();
}
const_iterator end() const noexcept
{
return tree_.end();
}
reverse_iterator rbegin() noexcept
{
return tree_.rbegin();
}
const_reverse_iterator rbegin() const noexcept
{
return tree_.rbegin();
}
reverse_iterator rend() noexcept
{
return tree_.rend();
}
const_reverse_iterator rend() const noexcept
{
return tree_.rend();
}
const_iterator cbegin() const noexcept
{
return tree_.cbegin();
}
const_iterator cend() const noexcept
{
return tree_.cend();
}
const_reverse_iterator crbegin() const noexcept
{
return tree_.crbegin();
}
const_reverse_iterator crend() const noexcept
{
return tree_.crend();
}
bool empty() const noexcept
{
return tree_.empty();
}
size_type size() const noexcept
{
return tree_.size();
}
size_type max_size() const noexcept
{
return tree_.max_size(allocator_);
}
template<class... Args>
iterator emplace(Args&&... args)
{
return tree_.emplace(forward<Args>(args)...);
}
template<class... Args>
iterator emplace_hint(const_iterator, Args&&... args)
{
return emplace(forward<Args>(args)...);
}
iterator insert(const value_type& val)
{
return tree_.insert(val);
}
iterator insert(value_type&& val)
{
return tree_.insert(forward<value_type>(val));
}
iterator insert(const_iterator, const value_type& val)
{
return insert(val);
}
iterator insert(const_iterator, value_type&& val)
{
return insert(forward<value_type>(val));
}
template<class InputIterator>
void insert(InputIterator first, InputIterator last)
{
while (first != last)
insert(*first++);
}
void insert(initializer_list<value_type> init)
{
insert(init.begin(), init.end());
}
iterator erase(const_iterator position)
{
return tree_.erase(position);
}
size_type erase(const key_type& key)
{
return tree_.erase(key);
}
iterator erase(const_iterator first, const_iterator last)
{
while (first != last)
first = erase(first);
return iterator{
first.node(), first.end()
};
}
void swap(multiset& other)
noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
noexcept(std::swap(declval<key_compare>(), declval<key_compare>())))
{
tree_.swap(other.tree_);
std::swap(allocator_, other.allocator_);
}
void clear() noexcept
{
tree_.clear();
}
key_compare key_comp() const
{
return tree_.key_comp();
}
value_compare value_comp() const
{
return tree_.value_comp();
}
iterator find(const key_type& key)
{
return tree_.find(key);
}
const_iterator find(const key_type& key) const
{
return tree_.find(key);
}
template<class K>
iterator find(
const K& key,
enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
)
{
return tree_.find(key);
}
template<class K>
const_iterator find(
const K& key,
enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
) const
{
return tree_.find(key);
}
size_type count(const key_type& key) const
{
return tree_.count(key);
}
template<class K>
size_type count(
const K& key,
enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
) const
{
return tree_.count(key);
}
iterator lower_bound(const key_type& key)
{
return tree_.lower_bound(key);
}
const_iterator lower_bound(const key_type& key) const
{
return tree_.lower_bound(key);
}
template<class K>
iterator lower_bound(
const K& key,
enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
)
{
return tree_.lower_bound(key);
}
template<class K>
const_iterator lower_bound(
const K& key,
enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
) const
{
return tree_.lower_bound(key);
}
iterator upper_bound(const key_type& key)
{
return tree_.upper_bound(key);
}
const_iterator upper_bound(const key_type& key) const
{
return tree_.upper_bound(key);
}
template<class K>
iterator upper_bound(
const K& key,
enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
)
{
return tree_.upper_bound(key);
}
template<class K>
const_iterator upper_bound(
const K& key,
enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
) const
{
return tree_.upper_bound(key);
}
pair<iterator, iterator> equal_range(const key_type& key)
{
return tree_.equal_range(key);
}
pair<const_iterator, const_iterator> equal_range(const key_type& key) const
{
return tree_.equal_range(key);
}
template<class K>
pair<iterator, iterator> equal_range(
const K& key,
enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
)
{
return tree_.equal_range(key);
}
template<class K>
pair<const_iterator, const_iterator> equal_range(
const K& key,
enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
) const
{
return tree_.equal_range(key);
}
private:
using tree_type = aux::rbtree<
key_type, key_type, aux::key_no_value_key_extractor<key_type>,
key_compare, allocator_type, size_type,
iterator, const_iterator,
aux::rbtree_multi_policy, node_type
>;
tree_type tree_;
allocator_type allocator_;
template<class K, class C, class A>
friend bool operator==(const multiset<K, C, A>&,
const multiset<K, C, A>&);
};
template<class Key, class Compare, class Allocator>
bool operator==(const multiset<Key, Compare, Allocator>& lhs,
const multiset<Key, Compare, Allocator>& rhs)
{
return lhs.tree_.is_eq_to(rhs.tree_);
}
template<class Key, class Compare, class Allocator>
bool operator<(const multiset<Key, Compare, Allocator>& lhs,
const multiset<Key, Compare, Allocator>& rhs)
{
return lexicographical_compare(
lhs.begin(), lhs.end(),
rhs.begin(), rhs.end(),
lhs.value_comp()
);
}
template<class Key, class Compare, class Allocator>
bool operator!=(const multiset<Key, Compare, Allocator>& lhs,
const multiset<Key, Compare, Allocator>& rhs)
{
return !(lhs == rhs);
}
template<class Key, class Compare, class Allocator>
bool operator>(const multiset<Key, Compare, Allocator>& lhs,
const multiset<Key, Compare, Allocator>& rhs)
{
return rhs < lhs;
}
template<class Key, class Compare, class Allocator>
bool operator>=(const multiset<Key, Compare, Allocator>& lhs,
const multiset<Key, Compare, Allocator>& rhs)
{
return !(lhs < rhs);
}
template<class Key, class Compare, class Allocator>
bool operator<=(const multiset<Key, Compare, Allocator>& lhs,
const multiset<Key, Compare, Allocator>& rhs)
{
return !(rhs < lhs);
}
}
#endif
HelenOS homepage, sources at GitHub