diff options
Diffstat (limited to 'misc/uClibc++/include/uClibc++/associative_base')
| -rw-r--r-- | misc/uClibc++/include/uClibc++/associative_base | 1266 |
1 files changed, 696 insertions, 570 deletions
diff --git a/misc/uClibc++/include/uClibc++/associative_base b/misc/uClibc++/include/uClibc++/associative_base index 27ae0ef9f..67122691b 100644 --- a/misc/uClibc++/include/uClibc++/associative_base +++ b/misc/uClibc++/include/uClibc++/associative_base @@ -1,47 +1,46 @@ -/* Copyright (C) 2007 Garrett A. Kajmowicz - This file is part of the uClibc++ Library. - - This library is free software; you can redistribute it and/or - modify it under the terms of the GNU Lesser General Public - License as published by the Free Software Foundation; either - version 2.1 of the License, or (at your option) any later version. - - This library is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - Lesser General Public License for more details. - - You should have received a copy of the GNU Lesser General Public - License along with this library; if not, write to the Free Software - Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA -*/ - - - -#include<memory> -#include<utility> -#include<iterator> -#include<functional> -#include<list> +/* Copyright (C) 2007 Garrett A. Kajmowicz + * This file is part of the uClibc++ Library. + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ +#include <memory> +#include <utility> +#include <iterator> +#include <functional> +#include <list> #ifndef __STD_HEADER_ASSOCIATIVE_BASE #define __STD_HEADER_ASSOCIATIVE_BASE #pragma GCC visibility push(default) -namespace std{ +extern "C++" +{ +namespace std +{ -/* - * The basic premise here is that most of the code used by map, multimap, set and - * multiset is really common. There are a number of interface additions, and - * considerations about how to address multiple entries with the same key. - * The goal is that the tree/storage code should be here, and managing - * single or multiple counts will be left to subclasses. - * Yes, inheritence for the purpose of code sharing is usually a bad idea. - * However, since our goal is to reduce the total amount of code written - * and the overall binary size, this seems to be the best approach possible. +/* The basic premise here is that most of the code used by map, multimap, set and + * multiset is really common. There are a number of interface additions, and + * considerations about how to address multiple entries with the same key. + * The goal is that the tree/storage code should be here, and managing + * single or multiple counts will be left to subclasses. + * Yes, inheritence for the purpose of code sharing is usually a bad idea. + * However, since our goal is to reduce the total amount of code written + * and the overall binary size, this seems to be the best approach possible. */ template<class Key, class ValueType, class Compare = less<Key>, class Allocator = allocator<ValueType> > class __base_associative; @@ -56,585 +55,712 @@ template<class Key, class ValueType, class Compare, class Allocator> class _UCXX protected: public: - typedef Key key_type; - typedef ValueType value_type; - typedef Compare key_compare; - typedef Allocator allocator_type; - typedef typename Allocator::reference reference; - typedef typename Allocator::const_reference const_reference; - typedef typename Allocator::size_type size_type; - typedef typename Allocator::difference_type difference_type; - typedef typename Allocator::pointer pointer; - typedef typename Allocator::const_pointer const_pointer; - typedef __base_associative<Key, ValueType, Compare, Allocator> associative_type; - - typedef _associative_iter<value_type, Compare, Allocator> iterator; - typedef _associative_citer<value_type, Compare, Allocator> const_iterator; - typedef typename std::reverse_iterator<iterator> reverse_iterator; - typedef typename std::reverse_iterator<const_iterator> const_reverse_iterator; - - - explicit __base_associative(const Compare& comp, const Allocator& A, const key_type (*v_to_k)(const value_type)) - : c(comp), value_to_key(v_to_k) { } + typedef Key key_type; + typedef ValueType value_type; + typedef Compare key_compare; + typedef Allocator allocator_type; + typedef typename Allocator::reference reference; + typedef typename Allocator::const_reference const_reference; + typedef typename Allocator::size_type size_type; + typedef typename Allocator::difference_type difference_type; + typedef typename Allocator::pointer pointer; + typedef typename Allocator::const_pointer const_pointer; + typedef __base_associative<Key, ValueType, Compare, Allocator> associative_type; + + typedef _associative_iter<value_type, Compare, Allocator> iterator; + typedef _associative_citer<value_type, Compare, Allocator> const_iterator; + typedef typename std::reverse_iterator<iterator> reverse_iterator; + typedef typename std::reverse_iterator<const_iterator> const_reverse_iterator; + + explicit __base_associative(const Compare& comp, const Allocator& A, const key_type (*v_to_k)(const value_type)) + : c(comp), value_to_key(v_to_k) { } + protected: - __base_associative(const associative_type& x) - : c(x.c), backing(x.backing), value_to_key(x.value_to_key) { } + __base_associative(const associative_type& x) + : c(x.c), backing(x.backing), value_to_key(x.value_to_key) { } public: - ~__base_associative(){ - } - - bool empty() const{ - return backing.empty(); - } - size_type size() const{ - return backing.size(); - } - size_type max_size() const{ - return backing.max_size(); - } - - iterator begin(){ - return iterator(backing.begin()); - } - - const_iterator begin() const{ - return const_iterator(backing.begin()); - } - - iterator end() { - return iterator(backing.end()); - } - - const_iterator end() const{ - return const_iterator(backing.end()); - } - - reverse_iterator rbegin(){ - return reverse_iterator(end()); - } - - const_reverse_iterator rbegin() const{ - return const_reverse_iterator(end()); - } - - reverse_iterator rend(){ - return reverse_iterator(begin()); - } - - const_reverse_iterator rend() const{ - return const_reverse_iterator(begin()); - } - - - iterator lower_bound(const key_type &x); - const_iterator lower_bound(const key_type &x) const; - iterator upper_bound(const key_type &x); - const_iterator upper_bound(const key_type &x) const; - - pair<iterator,iterator> equal_range(const key_type& x){ - pair<iterator, iterator> retval; - retval.first = lower_bound(x); - retval.second = retval.first; - while(retval.second != end() && !c(x, value_to_key(*retval.second))){ - ++retval.second; - } - return retval; - } - pair<const_iterator,const_iterator> equal_range(const key_type& x) const{ - pair<const_iterator, const_iterator> retval; - retval.first = lower_bound(x); - retval.second = retval.first; - while(retval.second != end() && !c(x, value_to_key(*retval.second))){ - ++retval.second; - } - return retval; - } - - iterator find(const key_type& x){ - iterator retval = lower_bound(x); - if(retval == end()){ - return retval; - } - if(c(x, value_to_key(*retval))){ - return end(); - } - return retval; - } - const_iterator find(const key_type& x) const{ - const_iterator retval = lower_bound(x); - if(retval == end()){ - return retval; - } - if(c(x, value_to_key(*retval))){ - return end(); - } - return retval; - } - size_type count(const key_type& x) const{ - size_type retval(0); - const_iterator first = lower_bound(x); - while(first != end() && !c(x, value_to_key(*first))){ - ++retval; - ++first; - } - return retval; - } - - void clear(){ - backing.clear(); - } - - void erase(iterator pos){ - backing.erase(pos.base_iterator()); - } - size_type erase(const key_type& x){ - size_type count(0); - iterator start = lower_bound(x); - iterator end = upper_bound(x); - while(start != end){ - start = backing.erase(start.base_iterator()); - ++count; - } - return count; - } - void erase(iterator first, iterator last){ - while(first != last){ - backing.erase(first.base_iterator()); - ++first; - } - } - - key_compare key_comp() const{ - return c; - } - - __base_associative &operator=(const __base_associative & x){ - c = x.c; - backing = x.backing; - value_to_key = x.value_to_key; - return *this; - } - bool operator==(const __base_associative & x){ - return x.backing == backing; - } - bool operator!=(const __base_associative & x){ - return !(x.backing == backing); - } + ~__base_associative() + { + } + + bool empty() const + { + return backing.empty(); + } + + size_type size() const + { + return backing.size(); + } + + size_type max_size() const + { + return backing.max_size(); + } + + iterator begin() + { + return iterator(backing.begin()); + } + + const_iterator begin() const + { + return const_iterator(backing.begin()); + } + + iterator end() + { + return iterator(backing.end()); + } + + const_iterator end() const + { + return const_iterator(backing.end()); + } + + reverse_iterator rbegin() + { + return reverse_iterator(end()); + } + + const_reverse_iterator rbegin() const + { + return const_reverse_iterator(end()); + } + + reverse_iterator rend() + { + return reverse_iterator(begin()); + } + + const_reverse_iterator rend() const + { + return const_reverse_iterator(begin()); + } + + iterator lower_bound(const key_type &x); + const_iterator lower_bound(const key_type &x) const; + iterator upper_bound(const key_type &x); + const_iterator upper_bound(const key_type &x) const; + + pair<iterator,iterator> equal_range(const key_type& x) + { + pair<iterator, iterator> retval; + retval.first = lower_bound(x); + retval.second = retval.first; + while (retval.second != end() && !c(x, value_to_key(*retval.second))) + { + ++retval.second; + } + + return retval; + } + + pair<const_iterator,const_iterator> equal_range(const key_type& x) const + { + pair<const_iterator, const_iterator> retval; + retval.first = lower_bound(x); + retval.second = retval.first; + while (retval.second != end() && !c(x, value_to_key(*retval.second))) + { + ++retval.second; + } + + return retval; + } + + iterator find(const key_type& x) + { + iterator retval = lower_bound(x); + if (retval == end()) + { + return retval; + } + + if (c(x, value_to_key(*retval))) + { + return end(); + } + + return retval; + } + + const_iterator find(const key_type& x) const + { + const_iterator retval = lower_bound(x); + if (retval == end()) + { + return retval; + } + + if (c(x, value_to_key(*retval))) + { + return end(); + } + + return retval; + } + + size_type count(const key_type& x) const + { + size_type retval(0); + const_iterator first = lower_bound(x); + while (first != end() && !c(x, value_to_key(*first))) + { + ++retval; + ++first; + } + + return retval; + } + + void clear() + { + backing.clear(); + } + + void erase(iterator pos) + { + backing.erase(pos.base_iterator()); + } + + size_type erase(const key_type& x) + { + size_type count(0); + iterator start = lower_bound(x); + iterator end = upper_bound(x); + while (start != end) + { + start = backing.erase(start.base_iterator()); + ++count; + } + + return count; + } + + void erase(iterator first, iterator last) + { + while (first != last) + { + backing.erase(first.base_iterator()); + ++first; + } + } + + key_compare key_comp() const + { + return c; + } + + __base_associative &operator=(const __base_associative & x) + { + c = x.c; + backing = x.backing; + value_to_key = x.value_to_key; + return *this; + } + + bool operator==(const __base_associative & x) + { + return x.backing == backing; + } + + bool operator!=(const __base_associative & x) + { + return !(x.backing == backing); + } protected: - void swap(__base_associative & x); - - Compare c; - std::list<value_type> backing; + void swap(__base_associative & x); - const key_type (*value_to_key)(const value_type); + Compare c; + std::list<value_type> backing; + const key_type (*value_to_key)(const value_type); }; - -/* - * Tree iterators for the base associative class - */ +/* Tree iterators for the base associative class */ template<class ValueType, class Compare, class Allocator> class _associative_citer - : public std::iterator< - bidirectional_iterator_tag, - ValueType, - typename Allocator::difference_type, - ValueType*, - ValueType& - > + : public std::iterator< + bidirectional_iterator_tag, + ValueType, + typename Allocator::difference_type, + ValueType*, + ValueType& + > { protected: - typedef std::list<ValueType> listtype; + typedef std::list<ValueType> listtype; + + typename listtype::const_iterator base_iter; + friend class _associative_iter<ValueType, Compare, Allocator>; - typename listtype::const_iterator base_iter; - friend class _associative_iter<ValueType, Compare, Allocator>; public: - _associative_citer() { } - _associative_citer(const _associative_citer & m) - : base_iter(m.base_iter) { } - _associative_citer(const typename listtype::const_iterator & m) - : base_iter(m) { } - ~_associative_citer() { } - ValueType operator*() const{ - return *base_iter; - } - const ValueType * operator->() const{ - return &(*base_iter); - } - _associative_citer & operator=(const _associative_citer & m){ - base_iter = m.base_iter; - return *this; - } - bool operator==(const _associative_citer & m) const{ - return m.base_iter == base_iter; - } - bool operator!=(const _associative_citer & m) const{ - return m.base_iter != base_iter; - } - _associative_citer & operator++(){ - ++base_iter; - return *this; - } - _associative_citer operator++(int){ - //The following approach ensures that we only need to - //provide code for ++ in one place (above) - _associative_citer temp(base_iter); - ++base_iter; - return temp; - } - _associative_citer & operator--(){ - --base_iter; - return *this; - } - _associative_citer operator--(int){ - //The following approach ensures that we only need to - //provide code for -- in one place (above) - _associative_citer temp(base_iter); - --base_iter; - return temp; - } - - //This is an implementation-defined function designed to make internals work correctly - typename listtype::const_iterator base_iterator(){ - return base_iter; - } + _associative_citer() { } + _associative_citer(const _associative_citer & m) + : base_iter(m.base_iter) { } + _associative_citer(const typename listtype::const_iterator & m) + : base_iter(m) { } + ~_associative_citer() { } + + ValueType operator*() const + { + return *base_iter; + } + + const ValueType * operator->() const + { + return &(*base_iter); + } + + _associative_citer & operator=(const _associative_citer & m) + { + base_iter = m.base_iter; + return *this; + } + + bool operator==(const _associative_citer & m) const + { + return m.base_iter == base_iter; + } + + bool operator!=(const _associative_citer & m) const{ + return m.base_iter != base_iter; + } + + _associative_citer & operator++() + { + ++base_iter; + return *this; + } + + _associative_citer operator++(int) + { + // The following approach ensures that we only need to + // provide code for ++ in one place (above) + + _associative_citer temp(base_iter); + ++base_iter; + return temp; + } + + _associative_citer & operator--() + { + --base_iter; + return *this; + } + + _associative_citer operator--(int) + { + // The following approach ensures that we only need to + // provide code for -- in one place (above) + + _associative_citer temp(base_iter); + --base_iter; + return temp; + } + + // This is an implementation-defined function designed to make internals work correctly + + typename listtype::const_iterator base_iterator() + { + return base_iter; + } }; - template<class ValueType, class Compare, class Allocator> class _associative_iter - : public std::iterator< - bidirectional_iterator_tag, - ValueType, - typename Allocator::difference_type, - ValueType*, - ValueType& - > + : public std::iterator< + bidirectional_iterator_tag, + ValueType, + typename Allocator::difference_type, + ValueType*, + ValueType& + > { protected: - typedef std::list<ValueType> listtype; + typedef std::list<ValueType> listtype; - typename listtype::iterator base_iter; - typedef _associative_citer<ValueType, Compare, Allocator> __associative_citer; + typename listtype::iterator base_iter; + typedef _associative_citer<ValueType, Compare, Allocator> __associative_citer; public: - _associative_iter() { } - _associative_iter(const _associative_iter & m) - : base_iter(m.base_iter) { } - _associative_iter(const typename listtype::iterator & m) - : base_iter(m) { } - ~_associative_iter() { } - const ValueType & operator*() const{ - return *base_iter; - } - ValueType & operator*(){ - return *base_iter; - } - ValueType * operator->(){ - return &(*base_iter); - } - const ValueType * operator->() const{ - return &(*base_iter); - } - _associative_iter & operator=(const _associative_iter & m){ - base_iter = m.base_iter; - return *this; - } - bool operator==(const _associative_iter & m) const{ - return m.base_iter == base_iter; - } - bool operator==(const __associative_citer & m) const{ - return m.base_iter == base_iter; - } - bool operator!=(const _associative_iter & m) const{ - return m.base_iter != base_iter; - } - bool operator!=(const __associative_citer & m) const{ - return m.base_iter != base_iter; - } - _associative_iter & operator++(){ - ++base_iter; - return *this; - } - _associative_iter operator++(int){ - //The following approach ensures that we only need to - //provide code for ++ in one place (above) - _associative_iter temp(base_iter); - ++base_iter; - return temp; - } - _associative_iter & operator--(){ - --base_iter; - return *this; - } - _associative_iter operator--(int){ - //The following approach ensures that we only need to - //provide code for -- in one place (above) - _associative_iter temp(base_iter); - --base_iter; - return temp; - } - operator __associative_citer() const{ - return __associative_citer(base_iter); - } - typename listtype::iterator base_iterator(){ - return base_iter; - } - const typename listtype::iterator base_iterator() const{ - return base_iter; - } - + _associative_iter() { } + _associative_iter(const _associative_iter & m) + : base_iter(m.base_iter) { } + _associative_iter(const typename listtype::iterator & m) + : base_iter(m) { } + ~_associative_iter() { } + + const ValueType & operator*() const + { + return *base_iter; + } + + ValueType & operator*() + { + return *base_iter; + } + + ValueType * operator->() + { + return &(*base_iter); + } + + const ValueType * operator->() const + { + return &(*base_iter); + } + + _associative_iter & operator=(const _associative_iter & m) + { + base_iter = m.base_iter; + return *this; + } + + bool operator==(const _associative_iter & m) const + { + return m.base_iter == base_iter; + } + + bool operator==(const __associative_citer & m) const + { + return m.base_iter == base_iter; + } + + bool operator!=(const _associative_iter & m) const + { + return m.base_iter != base_iter; + } + + bool operator!=(const __associative_citer & m) const + { + return m.base_iter != base_iter; + } + + _associative_iter & operator++() + { + ++base_iter; + return *this; + } + + _associative_iter operator++(int) + { + // The following approach ensures that we only need to + // provide code for ++ in one place (above) + + _associative_iter temp(base_iter); + ++base_iter; + return temp; + } + + _associative_iter & operator--() + { + --base_iter; + return *this; + } + + _associative_iter operator--(int) + { + // The following approach ensures that we only need to + // provide code for -- in one place (above) + + _associative_iter temp(base_iter); + --base_iter; + return temp; + } + + operator __associative_citer() const + { + return __associative_citer(base_iter); + } + + typename listtype::iterator base_iterator() + { + return base_iter; + } + + const typename listtype::iterator base_iterator() const + { + return base_iter; + } }; - - // The lower_bound code is really crappy linear search. However, it is a dead - // simple implementation (easy to audit). It can also be easily replaced. - - - template <class Key, class ValueType, class Compare, class Allocator> - typename __base_associative<Key, ValueType, Compare, Allocator>::iterator - __base_associative<Key, ValueType, Compare, Allocator>::lower_bound(const key_type &x) - { - iterator retval = begin(); - while(retval != end() && c(value_to_key(*retval), x)){ - ++retval; - } - return retval; - } - - template <class Key, class ValueType, class Compare, class Allocator> - typename __base_associative<Key, ValueType, Compare, Allocator>::const_iterator - __base_associative<Key, ValueType, Compare, Allocator>::lower_bound(const key_type &x) const - { - const_iterator retval = begin(); - while(retval != end() && c(value_to_key(*retval), x)){ - ++retval; - } - return retval; - } - - // Upper bound search is linear from the point of lower_bound. This is likely the best solution - // in all but the most pathological of cases. - - template <class Key, class ValueType, class Compare, class Allocator> - typename __base_associative<Key, ValueType, Compare, Allocator>::iterator - __base_associative<Key, ValueType, Compare, Allocator>::upper_bound(const key_type &x) - { - iterator retval = lower_bound(x); - while(retval != end() && !c(x, value_to_key(*retval))){ - ++retval; - } - return retval; - } - - template <class Key, class ValueType, class Compare, class Allocator> - typename __base_associative<Key, ValueType, Compare, Allocator>::const_iterator - __base_associative<Key, ValueType, Compare, Allocator>::upper_bound(const key_type &x) const - { - const_iterator retval = begin(); - while(retval != end() && !c(x, value_to_key(*retval))){ - ++retval; - } - return retval; - } - - - template <class Key, class ValueType, class Compare, class Allocator> - void __base_associative<Key, ValueType, Compare, Allocator>::swap(__base_associative<Key, ValueType, Compare, Allocator>& m) - { - Compare n = c; - c = m.c; - m.c = n; - - m.backing.swap(backing); - } - + // The lower_bound code is really crappy linear search. However, it is a dead + // simple implementation (easy to audit). It can also be easily replaced. + + + template <class Key, class ValueType, class Compare, class Allocator> + typename __base_associative<Key, ValueType, Compare, Allocator>::iterator + __base_associative<Key, ValueType, Compare, Allocator>::lower_bound(const key_type &x) + { + iterator retval = begin(); + while (retval != end() && c(value_to_key(*retval), x)) + { + ++retval; + } + + return retval; + } + + template <class Key, class ValueType, class Compare, class Allocator> + typename __base_associative<Key, ValueType, Compare, Allocator>::const_iterator + __base_associative<Key, ValueType, Compare, Allocator>::lower_bound(const key_type &x) const + { + const_iterator retval = begin(); + while (retval != end() && c(value_to_key(*retval), x)) + { + ++retval; + } + + return retval; + } + + // Upper bound search is linear from the point of lower_bound. This is likely the best solution + // in all but the most pathological of cases. + + template <class Key, class ValueType, class Compare, class Allocator> + typename __base_associative<Key, ValueType, Compare, Allocator>::iterator + __base_associative<Key, ValueType, Compare, Allocator>::upper_bound(const key_type &x) + { + iterator retval = lower_bound(x); + while (retval != end() && !c(x, value_to_key(*retval))) + { + ++retval; + } + + return retval; + } + + template <class Key, class ValueType, class Compare, class Allocator> + typename __base_associative<Key, ValueType, Compare, Allocator>::const_iterator + __base_associative<Key, ValueType, Compare, Allocator>::upper_bound(const key_type &x) const + { + const_iterator retval = begin(); + while (retval != end() && !c(x, value_to_key(*retval))) + { + ++retval; + } + + return retval; + } + + template <class Key, class ValueType, class Compare, class Allocator> + void __base_associative<Key, ValueType, Compare, Allocator>::swap(__base_associative<Key, ValueType, Compare, Allocator>& m) + { + Compare n = c; + c = m.c; + m.c = n; + + m.backing.swap(backing); + } template<class Key, class ValueType, class Compare, class Allocator> class _UCXXEXPORT __single_associative : - public __base_associative<Key, ValueType, Compare, Allocator> + public __base_associative<Key, ValueType, Compare, Allocator> { protected: - typedef __base_associative<Key, ValueType, Compare, Allocator> base; - using base::backing; + typedef __base_associative<Key, ValueType, Compare, Allocator> base; + using base::backing; - using base::c; + using base::c; public: - typedef typename base::key_type key_type; - typedef typename base::value_type value_type; - typedef typename base::key_compare key_compare; - typedef typename base::allocator_type 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::size_type size_type; - typedef typename base::difference_type difference_type; - typedef typename base::pointer pointer; - typedef typename base::const_pointer const_pointer; - typedef typename base::reverse_iterator reverse_iterator; - typedef typename base::const_reverse_iterator const_reverse_iterator; - - using base::begin; - using base::end; - using base::rbegin; - using base::rend; - - using base::empty; - using base::size; - using base::max_size; - - using base::find; - using base::count; - using base::lower_bound; - using base::upper_bound; - using base::equal_range; - - using base::operator=; - using base::operator==; - using base::operator!=; - - explicit __single_associative(const Compare& comp, const Allocator& A, const key_type (*v_to_k)(const value_type)) - : base(comp, A, v_to_k) { } - - template <class InputIterator> __single_associative( - InputIterator first, - InputIterator last, - const Compare& comp, - const Allocator& A, - const key_type (*v_to_k)(const value_type) - ) : base(comp, A, v_to_k) { - insert(first, last); - } - - pair<iterator, bool> insert(const value_type& x){ - pair<iterator, bool> retval; - iterator location = lower_bound(this->value_to_key(x)); - retval.second = true; - //Empty list or need to insert at end - if(end() == location){ - backing.push_back(x); - retval.first = --(end()); - return retval; - } - //Something in the list - if(c(this->value_to_key(x), this->value_to_key(*location))){ - location = backing.insert(location.base_iterator(), x); - retval.first = location; - }else{ - retval.second = false; - retval.first = location; - } - return retval; - } - - iterator insert(iterator position, const value_type& x){ - // FIXME - this is cheating and probably should be more efficient since we are - // now log(n) to find for inserts - return insert(x).first; - } - - template <class InputIterator> void insert(InputIterator first, InputIterator last){ - while(first != last){ - insert(*first); - ++first; - } - } - + typedef typename base::key_type key_type; + typedef typename base::value_type value_type; + typedef typename base::key_compare key_compare; + typedef typename base::allocator_type 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::size_type size_type; + typedef typename base::difference_type difference_type; + typedef typename base::pointer pointer; + typedef typename base::const_pointer const_pointer; + typedef typename base::reverse_iterator reverse_iterator; + typedef typename base::const_reverse_iterator const_reverse_iterator; + + using base::begin; + using base::end; + using base::rbegin; + using base::rend; + + using base::empty; + using base::size; + using base::max_size; + + using base::find; + using base::count; + using base::lower_bound; + using base::upper_bound; + using base::equal_range; + + using base::operator=; + using base::operator==; + using base::operator!=; + + explicit __single_associative(const Compare& comp, const Allocator& A, const key_type (*v_to_k)(const value_type)) + : base(comp, A, v_to_k) { } + + template <class InputIterator> __single_associative( + InputIterator first, + InputIterator last, + const Compare& comp, + const Allocator& A, + const key_type (*v_to_k)(const value_type) + ) : base(comp, A, v_to_k) + { + insert(first, last); + } + + pair<iterator, bool> insert(const value_type& x) + { + pair<iterator, bool> retval; + iterator location = lower_bound(this->value_to_key(x)); + retval.second = true; + + // Empty list or need to insert at end + + if (end() == location) + { + backing.push_back(x); + retval.first = --(end()); + return retval; + } + + // Something in the list + + if (c(this->value_to_key(x), this->value_to_key(*location))) + { + location = backing.insert(location.base_iterator(), x); + retval.first = location; + } + else + { + retval.second = false; + retval.first = location; + } + + return retval; + } + + iterator insert(iterator position, const value_type& x) + { + // FIXME - this is cheating and probably should be more efficient since we are + // now log(n) to find for inserts + + return insert(x).first; + } + + template <class InputIterator> void insert(InputIterator first, InputIterator last) + { + while (first != last) + { + insert(*first); + ++first; + } + } }; template<class Key, class ValueType, class Compare, class Allocator> class _UCXXEXPORT __multi_associative : - public __base_associative<Key, ValueType, Compare, Allocator> + public __base_associative<Key, ValueType, Compare, Allocator> { protected: - typedef __base_associative<Key, ValueType, Compare, Allocator> base; - using base::backing; + typedef __base_associative<Key, ValueType, Compare, Allocator> base; + using base::backing; - using base::c; + using base::c; public: - typedef typename base::key_type key_type; - typedef typename base::value_type value_type; - typedef typename base::key_compare key_compare; - typedef typename base::allocator_type 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::size_type size_type; - typedef typename base::difference_type difference_type; - typedef typename base::pointer pointer; - typedef typename base::const_pointer const_pointer; - typedef typename base::reverse_iterator reverse_iterator; - typedef typename base::const_reverse_iterator const_reverse_iterator; - - using base::begin; - using base::end; - using base::rbegin; - using base::rend; - - using base::empty; - using base::size; - using base::max_size; - - using base::find; - using base::count; - using base::lower_bound; - using base::upper_bound; - using base::equal_range; - - using base::operator=; - using base::operator==; - - - explicit __multi_associative(const Compare& comp, const Allocator& A, const key_type (*v_to_k)(const value_type)) - : base(comp, A, v_to_k) { } - - template <class InputIterator> __multi_associative( - InputIterator first, - InputIterator last, - const Compare& comp, - const Allocator& A, - const key_type (*v_to_k)(const value_type) - ) : base(comp, A, v_to_k) { - insert(first, last); - } - - iterator insert(const value_type& x){ - iterator location = lower_bound(this->value_to_key(x)); - - if(location == begin()){ - backing.push_front(x); - location = begin(); - }else{ - location = backing.insert(location.base_iterator(), x); - } - return location; - } - - iterator insert(iterator position, const value_type& x){ - // FIXME - this is cheating and probably should be more efficient since we are - // now log(n) to find for inserts - return insert(x); - } - - template <class InputIterator> void insert(InputIterator first, InputIterator last){ - while(first != last){ - insert(*first); - ++first; - } - } + typedef typename base::key_type key_type; + typedef typename base::value_type value_type; + typedef typename base::key_compare key_compare; + typedef typename base::allocator_type 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::size_type size_type; + typedef typename base::difference_type difference_type; + typedef typename base::pointer pointer; + typedef typename base::const_pointer const_pointer; + typedef typename base::reverse_iterator reverse_iterator; + typedef typename base::const_reverse_iterator const_reverse_iterator; + + using base::begin; + using base::end; + using base::rbegin; + using base::rend; + + using base::empty; + using base::size; + using base::max_size; + + using base::find; + using base::count; + using base::lower_bound; + using base::upper_bound; + using base::equal_range; + + using base::operator=; + using base::operator==; + + + explicit __multi_associative(const Compare& comp, const Allocator& A, const key_type (*v_to_k)(const value_type)) + : base(comp, A, v_to_k) { } + + template <class InputIterator> __multi_associative( + InputIterator first, + InputIterator last, + const Compare& comp, + const Allocator& A, + const key_type (*v_to_k)(const value_type) + ) : base(comp, A, v_to_k) + { + insert(first, last); + } + + iterator insert(const value_type& x) + { + iterator location = lower_bound(this->value_to_key(x)); + + if (location == begin()) + { + backing.push_front(x); + location = begin(); + } + else + { + location = backing.insert(location.base_iterator(), x); + } + + return location; + } + + iterator insert(iterator position, const value_type& x) + { + // FIXME - this is cheating and probably should be more efficient since we are + // now log(n) to find for inserts + + return insert(x); + } + + template <class InputIterator> void insert(InputIterator first, InputIterator last) + { + while (first != last) + { + insert(*first); + ++first; + } + } }; - - - -} +} // namespace +} // extern "C++" #pragma GCC visibility pop -#endif //__STD_HEADER_ASSOCIATIVE_BASE +#endif //__STD_HEADER_ASSOCIATIVE_BASE |