#ifndef _GLIBCXX_PROFILE_SET_H
#define _GLIBCXX_PROFILE_SET_H 1
-#include <utility>
+#include <profile/base.h>
+#include <profile/ordered_base.h>
-namespace std _GLIBCXX_VISIBILITY(default)
+namespace std _GLIBCXX_VISIBILITY(default)
{
namespace __profile
{
template<typename _Key, typename _Compare = std::less<_Key>,
typename _Allocator = std::allocator<_Key> >
class set
- : public _GLIBCXX_STD_C::set<_Key,_Compare,_Allocator>
+ : public _GLIBCXX_STD_C::set<_Key,_Compare,_Allocator>,
+ public _Ordered_profile<set<_Key, _Compare, _Allocator> >
{
typedef _GLIBCXX_STD_C::set<_Key, _Compare, _Allocator> _Base;
public:
// types:
- typedef _Key key_type;
- typedef _Key value_type;
- typedef _Compare key_compare;
- typedef _Compare value_compare;
- typedef _Allocator allocator_type;
- typedef typename _Base::reference reference;
- typedef typename _Base::const_reference const_reference;
-
- typedef typename _Base::iterator iterator;
- typedef typename _Base::const_iterator const_iterator;
- typedef typename _Base::reverse_iterator reverse_iterator;
- typedef typename _Base::const_reverse_iterator const_reverse_iterator;
-
- typedef typename _Base::size_type size_type;
- typedef typename _Base::difference_type difference_type;
- typedef typename _Base::pointer pointer;
- typedef typename _Base::const_pointer const_pointer;
+ typedef _Key key_type;
+ typedef _Key value_type;
+ typedef _Compare key_compare;
+ typedef _Compare value_compare;
+ typedef typename _Base::reference reference;
+ typedef typename _Base::const_reference const_reference;
+
+ typedef typename _Base::iterator iterator;
+ typedef typename _Base::const_iterator const_iterator;
+ typedef typename _Base::reverse_iterator reverse_iterator;
+ typedef typename _Base::const_reverse_iterator const_reverse_iterator;
+
+ typedef typename _Base::size_type size_type;
+ typedef typename _Base::difference_type difference_type;
+ typedef typename _Base::pointer pointer;
+ typedef typename _Base::const_pointer const_pointer;
// 23.3.3.1 construct/copy/destroy:
-
+#if __cplusplus < 201103L
set()
: _Base() { }
+ set(const set& __x)
+ : _Base(__x) { }
+ ~set() { }
+#else
+ set() = default;
+ set(const set&) = default;
+ set(set&&) = default;
+ ~set() = default;
+#endif
explicit set(const _Compare& __comp,
const _Allocator& __a = _Allocator())
#else
template<typename _InputIterator>
#endif
- set(_InputIterator __first, _InputIterator __last,
+ set(_InputIterator __first, _InputIterator __last,
const _Compare& __comp = _Compare(),
const _Allocator& __a = _Allocator())
: _Base(__first, __last, __comp, __a) { }
-#if __cplusplus < 201103L
- set(const set& __x)
- : _Base(__x) { }
-#else
- set(const set&) = default;
- set(set&&) = default;
-
+#if __cplusplus >= 201103L
set(initializer_list<value_type> __l,
const _Compare& __comp = _Compare(),
- const allocator_type& __a = allocator_type())
+ const _Allocator& __a = _Allocator())
: _Base(__l, __comp, __a) { }
explicit
- set(const allocator_type& __a)
- : _Base(__a) { }
+ set(const _Allocator& __a)
+ : _Base(__a) { }
- set(const set& __x, const allocator_type& __a)
+ set(const set& __x, const _Allocator& __a)
: _Base(__x, __a) { }
- set(set&& __x, const allocator_type& __a)
- noexcept(is_nothrow_copy_constructible<_Compare>::value
- && _Alloc_traits::_S_always_equal())
+ set(set&& __x, const _Allocator& __a)
+ noexcept( noexcept(_Base(std::move(__x), __a)) )
: _Base(std::move(__x), __a) { }
- set(initializer_list<value_type> __l, const allocator_type& __a)
+ set(initializer_list<value_type> __l, const _Allocator& __a)
: _Base(__l, __a) { }
template<typename _InputIterator>
- set(_InputIterator __first, _InputIterator __last,
- const allocator_type& __a)
- : _Base(__first, __last, __a) { }
+ set(_InputIterator __first, _InputIterator __last,
+ const _Allocator& __a)
+ : _Base(__first, __last, __a) { }
#endif
set(const _Base& __x)
: _Base(__x) { }
- ~set() _GLIBCXX_NOEXCEPT { }
-
#if __cplusplus < 201103L
set&
operator=(const set& __x)
}
#endif
- using _Base::get_allocator;
-
- // iterators:
- iterator
- begin() _GLIBCXX_NOEXCEPT
- { return iterator(_Base::begin()); }
-
- const_iterator
- begin() const _GLIBCXX_NOEXCEPT
- { return const_iterator(_Base::begin()); }
-
- iterator
- end() _GLIBCXX_NOEXCEPT
- { return iterator(_Base::end()); }
-
- const_iterator
- end() const _GLIBCXX_NOEXCEPT
- { return const_iterator(_Base::end()); }
-
reverse_iterator
rbegin() _GLIBCXX_NOEXCEPT
- { return reverse_iterator(end()); }
+ {
+ __profcxx_map_to_unordered_map_invalidate(this);
+ return _Base::rbegin();
+ }
const_reverse_iterator
rbegin() const _GLIBCXX_NOEXCEPT
- { return const_reverse_iterator(end()); }
+ {
+ __profcxx_map_to_unordered_map_invalidate(this);
+ return _Base::rbegin();
+ }
reverse_iterator
rend() _GLIBCXX_NOEXCEPT
- { return reverse_iterator(begin()); }
+ {
+ __profcxx_map_to_unordered_map_invalidate(this);
+ return _Base::rend();
+ }
const_reverse_iterator
rend() const _GLIBCXX_NOEXCEPT
- { return const_reverse_iterator(begin()); }
+ {
+ __profcxx_map_to_unordered_map_invalidate(this);
+ return _Base::rend();
+ }
#if __cplusplus >= 201103L
- const_iterator
- cbegin() const noexcept
- { return const_iterator(_Base::begin()); }
-
- const_iterator
- cend() const noexcept
- { return const_iterator(_Base::end()); }
-
const_reverse_iterator
crbegin() const noexcept
- { return const_reverse_iterator(end()); }
+ {
+ __profcxx_map_to_unordered_map_invalidate(this);
+ return _Base::crbegin();
+ }
const_reverse_iterator
crend() const noexcept
- { return const_reverse_iterator(begin()); }
+ {
+ __profcxx_map_to_unordered_map_invalidate(this);
+ return _Base::crend();
+ }
#endif
- // capacity:
- using _Base::empty;
- using _Base::size;
- using _Base::max_size;
-
// modifiers:
#if __cplusplus >= 201103L
template<typename... _Args>
std::pair<iterator, bool>
emplace(_Args&&... __args)
{
- auto __res = _Base::emplace(std::forward<_Args>(__args)...);
- return std::pair<iterator, bool>(iterator(__res.first),
- __res.second);
+ __profcxx_map_to_unordered_map_insert(this, this->size(), 1);
+ return _Base::emplace(std::forward<_Args>(__args)...);
}
template<typename... _Args>
iterator
emplace_hint(const_iterator __pos, _Args&&... __args)
{
- return iterator(_Base::emplace_hint(__pos,
- std::forward<_Args>(__args)...));
+ auto size_before = this->size();
+ auto __res
+ = _Base::emplace_hint(__pos, std::forward<_Args>(__args)...);
+ __profcxx_map_to_unordered_map_insert(this, size_before,
+ _M_hint_used(__pos, __res) ? 0 : 1);
+ return __res;
}
#endif
std::pair<iterator, bool>
insert(const value_type& __x)
{
- typedef typename _Base::iterator _Base_iterator;
- std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
- return std::pair<iterator, bool>(iterator(__res.first),
- __res.second);
+ __profcxx_map_to_unordered_map_insert(this, this->size(), 1);
+ return _Base::insert(__x);
}
#if __cplusplus >= 201103L
std::pair<iterator, bool>
insert(value_type&& __x)
{
- typedef typename _Base::iterator _Base_iterator;
- std::pair<_Base_iterator, bool> __res
- = _Base::insert(std::move(__x));
- return std::pair<iterator, bool>(iterator(__res.first),
- __res.second);
+ __profcxx_map_to_unordered_map_insert(this, this->size(), 1);
+ return _Base::insert(std::move(__x));
}
#endif
iterator
- insert(const_iterator __position, const value_type& __x)
- { return iterator(_Base::insert(__position, __x)); }
+ insert(const_iterator __pos, const value_type& __x)
+ {
+ size_type size_before = this->size();
+ iterator __res = _Base::insert(__pos, __x);
+ __profcxx_map_to_unordered_map_insert(this, size_before,
+ _M_hint_used(__pos, __res) ? 0 : 1);
+ return __res;
+ }
#if __cplusplus >= 201103L
iterator
#else
template<typename _InputIterator>
#endif
- void
- insert(_InputIterator __first, _InputIterator __last)
- { _Base::insert(__first, __last); }
+ void
+ insert(_InputIterator __first, _InputIterator __last)
+ {
+ for (; __first != __last; ++__first)
+ insert(*__first);
+ }
#if __cplusplus >= 201103L
void
insert(initializer_list<value_type> __l)
- { _Base::insert(__l); }
+ { insert(__l.begin(), __l.end()); }
#endif
#if __cplusplus >= 201103L
iterator
- erase(const_iterator __position)
- { return iterator(_Base::erase(__position)); }
+ erase(const_iterator __pos)
+ {
+ __profcxx_map_to_unordered_map_erase(this, this->size(), 1);
+ return _Base::erase(__pos);
+ }
#else
void
- erase(iterator __position)
- { _Base::erase(__position); }
+ erase(iterator __pos)
+ {
+ __profcxx_map_to_unordered_map_erase(this, this->size(), 1);
+ _Base::erase(__pos);
+ }
#endif
size_type
erase(const key_type& __x)
{
- iterator __victim = find(__x);
- if (__victim == end())
- return 0;
- else
- {
- _Base::erase(__victim);
- return 1;
- }
+ __profcxx_map_to_unordered_map_find(this, this->size());
+ __profcxx_map_to_unordered_map_erase(this, this->size(), 1);
+ return _Base::erase(__x);
}
#if __cplusplus >= 201103L
iterator
erase(const_iterator __first, const_iterator __last)
- { return iterator(_Base::erase(__first, __last)); }
+ {
+ if (__first != __last)
+ {
+ iterator __ret;
+ for (; __first != __last;)
+ __ret = erase(__first++);
+ return __ret;
+ }
+
+ return _Base::erase(__first, __last);
+ }
#else
void
erase(iterator __first, iterator __last)
- { _Base::erase(__first, __last); }
+ {
+ for (; __first != __last;)
+ erase(__first++);
+ }
#endif
void
swap(set& __x)
#if __cplusplus >= 201103L
- noexcept(_Alloc_traits::_S_nothrow_swap())
+ noexcept( noexcept(declval<_Base>().swap(__x)) )
#endif
{ _Base::swap(__x); }
- void
- clear() _GLIBCXX_NOEXCEPT
- { this->erase(begin(), end()); }
-
- // observers:
- using _Base::key_comp;
- using _Base::value_comp;
-
// set operations:
iterator
find(const key_type& __x)
- { return iterator(_Base::find(__x)); }
+ {
+ __profcxx_map_to_unordered_map_find(this, this->size());
+ return _Base::find(__x);
+ }
- // _GLIBCXX_RESOLVE_LIB_DEFECTS
- // 214. set::find() missing const overload
const_iterator
find(const key_type& __x) const
- { return const_iterator(_Base::find(__x)); }
+ {
+ __profcxx_map_to_unordered_map_find(this, this->size());
+ return _Base::find(__x);
+ }
- using _Base::count;
+ size_type
+ count(const key_type& __x) const
+ {
+ __profcxx_map_to_unordered_map_find(this, this->size());
+ return _Base::count(__x);
+ }
iterator
lower_bound(const key_type& __x)
- { return iterator(_Base::lower_bound(__x)); }
+ {
+ __profcxx_map_to_unordered_map_find(this, this->size());
+ __profcxx_map_to_unordered_map_invalidate(this);
+ return _Base::lower_bound(__x);
+ }
- // _GLIBCXX_RESOLVE_LIB_DEFECTS
- // 214. set::find() missing const overload
const_iterator
lower_bound(const key_type& __x) const
- { return const_iterator(_Base::lower_bound(__x)); }
+ {
+ __profcxx_map_to_unordered_map_find(this, this->size());
+ __profcxx_map_to_unordered_map_invalidate(this);
+ return _Base::lower_bound(__x);
+ }
iterator
upper_bound(const key_type& __x)
- { return iterator(_Base::upper_bound(__x)); }
+ {
+ __profcxx_map_to_unordered_map_find(this, this->size());
+ __profcxx_map_to_unordered_map_invalidate(this);
+ return _Base::upper_bound(__x);
+ }
- // _GLIBCXX_RESOLVE_LIB_DEFECTS
- // 214. set::find() missing const overload
const_iterator
upper_bound(const key_type& __x) const
- { return const_iterator(_Base::upper_bound(__x)); }
+ {
+ __profcxx_map_to_unordered_map_find(this, this->size());
+ __profcxx_map_to_unordered_map_invalidate(this);
+ return _Base::upper_bound(__x);
+ }
- std::pair<iterator,iterator>
+ std::pair<iterator, iterator>
equal_range(const key_type& __x)
{
- typedef typename _Base::iterator _Base_iterator;
- std::pair<_Base_iterator, _Base_iterator> __res =
- _Base::equal_range(__x);
- return std::make_pair(iterator(__res.first),
- iterator(__res.second));
+ __profcxx_map_to_unordered_map_find(this, this->size());
+ return _Base::equal_range(__x);
}
- // _GLIBCXX_RESOLVE_LIB_DEFECTS
- // 214. set::find() missing const overload
- std::pair<const_iterator,const_iterator>
+ std::pair<const_iterator, const_iterator>
equal_range(const key_type& __x) const
{
- typedef typename _Base::const_iterator _Base_iterator;
- std::pair<_Base_iterator, _Base_iterator> __res =
- _Base::equal_range(__x);
- return std::make_pair(const_iterator(__res.first),
- const_iterator(__res.second));
+ __profcxx_map_to_unordered_map_find(this, this->size());
+ return _Base::equal_range(__x);
}
_Base&
- _M_base() _GLIBCXX_NOEXCEPT { return *this; }
+ _M_base() _GLIBCXX_NOEXCEPT { return *this; }
const _Base&
- _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
-
+ _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
+
+ private:
+ /** If hint is used we consider that the map and unordered_map
+ * operations have equivalent insertion cost so we do not update metrics
+ * about it.
+ * Note that to find out if hint has been used is libstdc++
+ * implementation dependant.
+ */
+ bool
+ _M_hint_used(const_iterator __hint, iterator __res)
+ {
+ return (__hint == __res ||
+ (__hint == this->end() && ++__res == this->end()) ||
+ (__hint != this->end() && (++__hint == __res ||
+ ++__res == --__hint)));
+ }
};
template<typename _Key, typename _Compare, typename _Allocator>