88 lines
5.5 KiB
C++
88 lines
5.5 KiB
C++
// This file is part of the uSTL library, an STL implementation.
|
|
//
|
|
// Copyright (c) 2005 by Mike Sharov <msharov@users.sourceforge.net>
|
|
// This file is free software, distributed under the MIT License.
|
|
|
|
#pragma once
|
|
#include "uvector.h"
|
|
#include "ualgo.h"
|
|
|
|
namespace ustl {
|
|
|
|
/// \class multiset umultiset.h ustl.h
|
|
/// \ingroup AssociativeContainers
|
|
///
|
|
/// \brief Multiple sorted container.
|
|
/// Unlike set, it may contain multiple copies of each element.
|
|
///
|
|
template <typename T, typename Comp = less<T> >
|
|
class multiset : public vector<T> {
|
|
public:
|
|
typedef const multiset<T,Comp>& rcself_t;
|
|
typedef vector<T> base_class;
|
|
typedef typename base_class::value_type value_type;
|
|
typedef typename base_class::size_type size_type;
|
|
typedef typename base_class::pointer pointer;
|
|
typedef typename base_class::const_pointer const_pointer;
|
|
typedef typename base_class::reference reference;
|
|
typedef typename base_class::const_reference const_reference;
|
|
typedef typename base_class::const_iterator const_iterator;
|
|
typedef typename base_class::iterator iterator;
|
|
typedef typename base_class::reverse_iterator reverse_iterator;
|
|
typedef typename base_class::const_reverse_iterator const_reverse_iterator;
|
|
typedef pair<iterator,iterator> range_t;
|
|
typedef pair<const_iterator,const_iterator> const_range_t;
|
|
typedef std::initializer_list<value_type> initlist_t;
|
|
public:
|
|
inline multiset (void) : base_class() {}
|
|
inline explicit multiset (size_type n) : base_class (n) {}
|
|
inline explicit multiset (rcself_t v) : base_class (v) {}
|
|
inline multiset (const_iterator i1, const_iterator i2) : base_class() { insert (i1, i2); }
|
|
inline rcself_t operator= (rcself_t v) { base_class::operator= (v); return (*this); }
|
|
inline size_type size (void) const { return (base_class::size()); }
|
|
inline iterator begin (void) { return (base_class::begin()); }
|
|
inline const_iterator begin (void) const { return (base_class::begin()); }
|
|
inline const_iterator cbegin (void) const { return (base_class::cbegin()); }
|
|
inline iterator end (void) { return (base_class::end()); }
|
|
inline const_iterator end (void) const { return (base_class::end()); }
|
|
inline const_iterator cend (void) const { return (base_class::cend()); }
|
|
inline Comp value_comp (void) const { return (Comp()); }
|
|
inline Comp key_comp (void) const { return (value_comp()); }
|
|
inline void assign (const_iterator i1, const_iterator i2) { clear(); insert (i1, i2); }
|
|
inline const_iterator find (const_reference v) const { const_iterator i = ::ustl::lower_bound (begin(), end(), v, Comp()); return ((i != end() && *i == v) ? i : end()); }
|
|
inline iterator find (const_reference v) { return (const_cast<iterator>(const_cast<rcself_t>(*this).find (v))); }
|
|
inline const_iterator lower_bound (const_reference v) const { return (::ustl::lower_bound (begin(), end(), v, Comp())); }
|
|
inline iterator lower_bound (const_reference v) { return (const_cast<iterator>(const_cast<rcself_t>(*this).lower_bound (v))); }
|
|
inline const_iterator upper_bound (const_reference v) const { return (::ustl::upper_bound (begin(), end(), v, Comp())); }
|
|
inline iterator upper_bound (const_reference v) { return (const_cast<iterator>(const_cast<rcself_t>(*this).upper_bound (v))); }
|
|
inline const_range_t equal_range (const_reference v) const { return (::ustl::equal_range (begin(), end(), v, Comp())); }
|
|
inline range_t equal_range (const_reference v) { return (::ustl::equal_range (begin(), end(), v, Comp())); }
|
|
inline size_type count (const_reference v) const { const_range_t r = equal_range(v); return (distance(r.first,r.second)); }
|
|
inline void push_back (const_reference v) { insert (v); }
|
|
inline iterator insert (const_reference v) { return (base_class::insert (upper_bound(v), v)); }
|
|
inline iterator insert (const_iterator, const_reference v) { return (insert(v)); }
|
|
void insert (const_iterator i1, const_iterator i2) { for (; i1 < i2; ++i1) insert (*i1); }
|
|
inline iterator erase (const_iterator ep) { return (base_class::erase (ep)); }
|
|
inline iterator erase (const_iterator ep1, const_iterator ep2) { return (base_class::erase (ep1, ep2)); }
|
|
inline size_type erase (const_reference v) { range_t epr = equal_range (v); erase (epr.first, epr.second); return (distance(epr.first, epr.second)); }
|
|
inline void clear (void) { base_class::clear(); }
|
|
inline void swap (multiset& v) { base_class::swap (v); }
|
|
#if HAVE_CPP11
|
|
inline explicit multiset (multiset&& v) : base_class (forward<multiset>(v)) {}
|
|
inline multiset (initlist_t v) : base_class() { insert (v.begin(), v.end()); }
|
|
inline multiset& operator= (multiset&& v) { base_class::operator= (forward<multiset>(v)); return (*this); }
|
|
inline iterator insert (T&& v) { return (base_class::insert (upper_bound(v), forward<T>(v))); }
|
|
inline iterator insert (const_iterator, T&& v) { return (insert (forward<T>(v))); }
|
|
inline void insert (initlist_t v) { insert (v.begin(), v.end()); }
|
|
template <typename... Args>
|
|
inline iterator emplace (Args&&... args) { return (insert (T(forward<Args>(args)...))); }
|
|
template <typename... Args>
|
|
inline iterator emplace_hint (const_iterator h, Args&&... args) { return (insert (h, T(forward<Args>(args)...))); }
|
|
template <typename... Args>
|
|
inline iterator emplace_back (Args&&... args) { return (insert (T(forward<Args>(args)...))); }
|
|
inline void swap (multiset&& v) { base_class::swap (forward<multiset>(v)); }
|
|
#endif
|
|
};
|
|
|
|
} // namespace ustl
|