diff options
Diffstat (limited to 'libstdc++-v3/include/bits/stl_queue.h')
| -rw-r--r-- | libstdc++-v3/include/bits/stl_queue.h | 540 |
1 files changed, 290 insertions, 250 deletions
diff --git a/libstdc++-v3/include/bits/stl_queue.h b/libstdc++-v3/include/bits/stl_queue.h index 0bb41acaf9f..441fc55ef4b 100644 --- a/libstdc++-v3/include/bits/stl_queue.h +++ b/libstdc++-v3/include/bits/stl_queue.h @@ -62,20 +62,21 @@ #define _QUEUE_H 1 #include <bits/concept_check.h> +#include <debug/debug.h> namespace std { // Forward declarations of operators < and ==, needed for friend declaration. + template<typename _Tp, typename _Sequence = deque<_Tp> > + class queue; - template <typename _Tp, typename _Sequence = deque<_Tp> > - class queue; - - template <typename _Tp, typename _Seq> - inline bool operator==(const queue<_Tp,_Seq>&, const queue<_Tp,_Seq>&); - - template <typename _Tp, typename _Seq> - inline bool operator<(const queue<_Tp,_Seq>&, const queue<_Tp,_Seq>&); + template<typename _Tp, typename _Seq> + inline bool + operator==(const queue<_Tp,_Seq>&, const queue<_Tp,_Seq>&); + template<typename _Tp, typename _Seq> + inline bool + operator<(const queue<_Tp,_Seq>&, const queue<_Tp,_Seq>&); /** * @brief A standard container giving FIFO behavior. @@ -101,111 +102,133 @@ namespace std * which is a typedef for the second Sequence parameter, and @c push and * @c pop, which are standard %queue/FIFO operations. */ - template <typename _Tp, typename _Sequence> + template<typename _Tp, typename _Sequence> class queue - { - // concept requirements - typedef typename _Sequence::value_type _Sequence_value_type; - __glibcxx_class_requires(_Tp, _SGIAssignableConcept) - __glibcxx_class_requires(_Sequence, _FrontInsertionSequenceConcept) - __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept) - __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept) - - template <typename _Tp1, typename _Seq1> - friend bool operator== (const queue<_Tp1, _Seq1>&, - const queue<_Tp1, _Seq1>&); - template <typename _Tp1, typename _Seq1> - friend bool operator< (const queue<_Tp1, _Seq1>&, - const queue<_Tp1, _Seq1>&); - - public: - typedef typename _Sequence::value_type value_type; - typedef typename _Sequence::reference reference; - typedef typename _Sequence::const_reference const_reference; - typedef typename _Sequence::size_type size_type; - typedef _Sequence container_type; - - protected: - /** - * 'c' is the underlying container. Maintainers wondering why this isn't - * uglified as per style guidelines should note that this name is - * specified in the standard, [23.2.3.1]. (Why? Presumably for the same - * reason that it's protected instead of private: to allow derivation. - * But none of the other containers allow for derivation. Odd.) - */ - _Sequence c; - - public: - /** - * @brief Default constructor creates no elements. - */ - explicit - queue(const _Sequence& __c = _Sequence()) - : c(__c) {} - - /** - * Returns true if the %queue is empty. - */ - bool - empty() const { return c.empty(); } - - /** Returns the number of elements in the %queue. */ - size_type - size() const { return c.size(); } - - /** - * Returns a read/write reference to the data at the first element of the - * %queue. - */ - reference - front() { return c.front(); } - - /** - * Returns a read-only (constant) reference to the data at the first - * element of the %queue. - */ - const_reference - front() const { return c.front(); } - - /** - * Returns a read/write reference to the data at the last element of the - * %queue. - */ - reference - back() { return c.back(); } - - /** - * Returns a read-only (constant) reference to the data at the last - * element of the %queue. - */ - const_reference - back() const { return c.back(); } - - /** - * @brief Add data to the end of the %queue. - * @param x Data to be added. - * - * This is a typical %queue operation. The function creates an element at - * the end of the %queue and assigns the given data to it. - * The time complexity of the operation depends on the underlying - * sequence. - */ - void - push(const value_type& __x) { c.push_back(__x); } - - /** - * @brief Removes first element. - * - * This is a typical %queue operation. It shrinks the %queue by one. - * The time complexity of the operation depends on the underlying - * sequence. - * - * Note that no data is returned, and if the first element's data is - * needed, it should be retrieved before pop() is called. - */ - void - pop() { c.pop_front(); } - }; + { + // concept requirements + typedef typename _Sequence::value_type _Sequence_value_type; + __glibcxx_class_requires(_Tp, _SGIAssignableConcept) + __glibcxx_class_requires(_Sequence, _FrontInsertionSequenceConcept) + __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept) + __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept) + + template<typename _Tp1, typename _Seq1> + friend bool + operator==(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&); + + template<typename _Tp1, typename _Seq1> + friend bool + operator<(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&); + + public: + typedef typename _Sequence::value_type value_type; + typedef typename _Sequence::reference reference; + typedef typename _Sequence::const_reference const_reference; + typedef typename _Sequence::size_type size_type; + typedef _Sequence container_type; + + protected: + /** + * 'c' is the underlying container. Maintainers wondering why + * this isn't uglified as per style guidelines should note that + * this name is specified in the standard, [23.2.3.1]. (Why? + * Presumably for the same reason that it's protected instead + * of private: to allow derivation. But none of the other + * containers allow for derivation. Odd.) + */ + _Sequence c; + + public: + /** + * @brief Default constructor creates no elements. + */ + explicit + queue(const _Sequence& __c = _Sequence()) : c(__c) {} + + /** + * Returns true if the %queue is empty. + */ + bool + empty() const { return c.empty(); } + + /** Returns the number of elements in the %queue. */ + size_type + size() const { return c.size(); } + + /** + * Returns a read/write reference to the data at the first + * element of the %queue. + */ + reference + front() + { + __glibcxx_requires_nonempty(); + return c.front(); + } + + /** + * Returns a read-only (constant) reference to the data at the first + * element of the %queue. + */ + const_reference + front() const + { + __glibcxx_requires_nonempty(); + return c.front(); + } + + /** + * Returns a read/write reference to the data at the last + * element of the %queue. + */ + reference + back() + { + __glibcxx_requires_nonempty(); + return c.back(); + } + + /** + * Returns a read-only (constant) reference to the data at the last + * element of the %queue. + */ + const_reference + back() const + { + __glibcxx_requires_nonempty(); + return c.back(); + } + + /** + * @brief Add data to the end of the %queue. + * @param x Data to be added. + * + * This is a typical %queue operation. The function creates an + * element at the end of the %queue and assigns the given data + * to it. The time complexity of the operation depends on the + * underlying sequence. + */ + void + push(const value_type& __x) { c.push_back(__x); } + + /** + * @brief Removes first element. + * + * This is a typical %queue operation. It shrinks the %queue by one. + * The time complexity of the operation depends on the underlying + * sequence. + * + * Note that no data is returned, and if the first element's + * data is needed, it should be retrieved before pop() is + * called. + */ + void + pop() + { + __glibcxx_requires_nonempty(); + c.pop_front(); + } + }; /** @@ -219,9 +242,10 @@ namespace std * linear in the size of the sequences, and queues are considered equivalent * if their sequences compare equal. */ - template <typename _Tp, typename _Sequence> + template<typename _Tp, typename _Sequence> inline bool - operator==(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y) + operator==(const queue<_Tp,_Sequence>& __x, + const queue<_Tp,_Sequence>& __y) { return __x.c == __y.c; } /** @@ -230,39 +254,43 @@ namespace std * @param y A %queue of the same type as @a x. * @return True iff @a x is lexicographically less than @a y. * - * This is an total ordering relation. Complexity and semantics depend on - * the underlying sequence type, but the expected rules are: this relation - * is linear in the size of the sequences, the elements must be comparable - * with @c <, and std::lexicographical_compare() is usually used to make the + * This is an total ordering relation. Complexity and semantics + * depend on the underlying sequence type, but the expected rules + * are: this relation is linear in the size of the sequences, the + * elements must be comparable with @c <, and + * std::lexicographical_compare() is usually used to make the * determination. */ - template <typename _Tp, typename _Sequence> + template<typename _Tp, typename _Sequence> inline bool operator<(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y) { return __x.c < __y.c; } /// Based on operator== - template <typename _Tp, typename _Sequence> + template<typename _Tp, typename _Sequence> inline bool - operator!=(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y) + operator!=(const queue<_Tp,_Sequence>& __x, + const queue<_Tp,_Sequence>& __y) { return !(__x == __y); } /// Based on operator< - template <typename _Tp, typename _Sequence> + template<typename _Tp, typename _Sequence> inline bool operator>(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y) { return __y < __x; } /// Based on operator< - template <typename _Tp, typename _Sequence> + template<typename _Tp, typename _Sequence> inline bool - operator<=(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y) + operator<=(const queue<_Tp,_Sequence>& __x, + const queue<_Tp,_Sequence>& __y) { return !(__y < __x); } /// Based on operator< - template <typename _Tp, typename _Sequence> + template<typename _Tp, typename _Sequence> inline bool - operator>=(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y) + operator>=(const queue<_Tp,_Sequence>& __x, + const queue<_Tp,_Sequence>& __y) { return !(__x < __y); } @@ -272,157 +300,169 @@ namespace std * @ingroup Containers * @ingroup Sequences * - * This is not a true container, but an @e adaptor. It holds another - * container, and provides a wrapper interface to that container. The - * wrapper is what enforces sorting and first-in-first-out %queue behavior. - * Very few of the standard container/sequence interface requirements are - * met (e.g., iterators). + * This is not a true container, but an @e adaptor. It holds + * another container, and provides a wrapper interface to that + * container. The wrapper is what enforces sorting and + * first-in-first-out %queue behavior. Very few of the standard + * container/sequence interface requirements are met (e.g., + * iterators). * * The second template parameter defines the type of the underlying - * sequence/container. It defaults to std::vector, but it can be any type - * that supports @c front(), @c push_back, @c pop_back, and random-access - * iterators, such as std::deque or an appropriate user-defined type. + * sequence/container. It defaults to std::vector, but it can be + * any type that supports @c front(), @c push_back, @c pop_back, + * and random-access iterators, such as std::deque or an + * appropriate user-defined type. * - * The third template parameter supplies the means of making priority - * comparisons. It defaults to @c less<value_type> but can be anything - * defining a strict weak ordering. + * The third template parameter supplies the means of making + * priority comparisons. It defaults to @c less<value_type> but + * can be anything defining a strict weak ordering. * * Members not found in "normal" containers are @c container_type, - * which is a typedef for the second Sequence parameter, and @c push, - * @c pop, and @c top, which are standard %queue/FIFO operations. + * which is a typedef for the second Sequence parameter, and @c + * push, @c pop, and @c top, which are standard %queue/FIFO + * operations. * - * @note No equality/comparison operators are provided for %priority_queue. + * @note No equality/comparison operators are provided for + * %priority_queue. * - * @note Sorting of the elements takes place as they are added to, and - * removed from, the %priority_queue using the %priority_queue's - * member functions. If you access the elements by other means, and - * change their data such that the sorting order would be different, - * the %priority_queue will not re-sort the elements for you. (How - * could it know to do so?) + * @note Sorting of the elements takes place as they are added to, + * and removed from, the %priority_queue using the + * %priority_queue's member functions. If you access the elements + * by other means, and change their data such that the sorting + * order would be different, the %priority_queue will not re-sort + * the elements for you. (How could it know to do so?) */ - template <typename _Tp, typename _Sequence = vector<_Tp>, + template<typename _Tp, typename _Sequence = vector<_Tp>, typename _Compare = less<typename _Sequence::value_type> > class priority_queue - { - // concept requirements - typedef typename _Sequence::value_type _Sequence_value_type; - __glibcxx_class_requires(_Tp, _SGIAssignableConcept) - __glibcxx_class_requires(_Sequence, _SequenceConcept) - __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept) - __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept) - __glibcxx_class_requires4(_Compare, bool, _Tp, _Tp, _BinaryFunctionConcept) - - public: - typedef typename _Sequence::value_type value_type; - typedef typename _Sequence::reference reference; - typedef typename _Sequence::const_reference const_reference; - typedef typename _Sequence::size_type size_type; - typedef _Sequence container_type; - - protected: - // See queue::c for notes on these names. - _Sequence c; - _Compare comp; - - public: - /** - * @brief Default constructor creates no elements. - */ - explicit - priority_queue(const _Compare& __x = _Compare(), - const _Sequence& __s = _Sequence()) - : c(__s), comp(__x) - { std::make_heap(c.begin(), c.end(), comp); } - - /** - * @brief Builds a %queue from a range. - * @param first An input iterator. - * @param last An input iterator. - * @param x A comparison functor describing a strict weak ordering. - * @param s An initial sequence with which to start. - * - * Begins by copying @a s, inserting a copy of the elements from - * @a [first,last) into the copy of @a s, then ordering the copy - * according to @a x. - * - * For more information on function objects, see the documentation on - * @link s20_3_1_base functor base classes@endlink. - */ - template <typename _InputIterator> - priority_queue(_InputIterator __first, _InputIterator __last, - const _Compare& __x = _Compare(), - const _Sequence& __s = _Sequence()) - : c(__s), comp(__x) - { - c.insert(c.end(), __first, __last); - std::make_heap(c.begin(), c.end(), comp); - } - - /** - * Returns true if the %queue is empty. - */ - bool - empty() const { return c.empty(); } - - /** Returns the number of elements in the %queue. */ - size_type - size() const { return c.size(); } - - /** - * Returns a read-only (constant) reference to the data at the first - * element of the %queue. - */ - const_reference - top() const { return c.front(); } - - /** - * @brief Add data to the %queue. - * @param x Data to be added. - * - * This is a typical %queue operation. - * The time complexity of the operation depends on the underlying - * sequence. - */ - void - push(const value_type& __x) { - try + // concept requirements + typedef typename _Sequence::value_type _Sequence_value_type; + __glibcxx_class_requires(_Tp, _SGIAssignableConcept) + __glibcxx_class_requires(_Sequence, _SequenceConcept) + __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept) + __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept) + __glibcxx_class_requires4(_Compare, bool, _Tp,_Tp,_BinaryFunctionConcept) + + public: + typedef typename _Sequence::value_type value_type; + typedef typename _Sequence::reference reference; + typedef typename _Sequence::const_reference const_reference; + typedef typename _Sequence::size_type size_type; + typedef _Sequence container_type; + + protected: + // See queue::c for notes on these names. + _Sequence c; + _Compare comp; + + public: + /** + * @brief Default constructor creates no elements. + */ + explicit + priority_queue(const _Compare& __x = _Compare(), + const _Sequence& __s = _Sequence()) + : c(__s), comp(__x) + { std::make_heap(c.begin(), c.end(), comp); } + + /** + * @brief Builds a %queue from a range. + * @param first An input iterator. + * @param last An input iterator. + * @param x A comparison functor describing a strict weak ordering. + * @param s An initial sequence with which to start. + * + * Begins by copying @a s, inserting a copy of the elements + * from @a [first,last) into the copy of @a s, then ordering + * the copy according to @a x. + * + * For more information on function objects, see the + * documentation on @link s20_3_1_base functor base + * classes@endlink. + */ + template<typename _InputIterator> + priority_queue(_InputIterator __first, _InputIterator __last, + const _Compare& __x = _Compare(), + const _Sequence& __s = _Sequence()) + : c(__s), comp(__x) + { + __glibcxx_requires_valid_range(__first, __last); + c.insert(c.end(), __first, __last); + std::make_heap(c.begin(), c.end(), comp); + } + + /** + * Returns true if the %queue is empty. + */ + bool + empty() const { return c.empty(); } + + /** Returns the number of elements in the %queue. */ + size_type + size() const { return c.size(); } + + /** + * Returns a read-only (constant) reference to the data at the first + * element of the %queue. + */ + const_reference + top() const + { + __glibcxx_requires_nonempty(); + return c.front(); + } + + /** + * @brief Add data to the %queue. + * @param x Data to be added. + * + * This is a typical %queue operation. + * The time complexity of the operation depends on the underlying + * sequence. + */ + void + push(const value_type& __x) + { + try { c.push_back(__x); std::push_heap(c.begin(), c.end(), comp); } - catch(...) + catch(...) { c.clear(); __throw_exception_again; } - } - - /** - * @brief Removes first element. - * - * This is a typical %queue operation. It shrinks the %queue by one. - * The time complexity of the operation depends on the underlying - * sequence. - * - * Note that no data is returned, and if the first element's data is - * needed, it should be retrieved before pop() is called. - */ - void - pop() - { - try + } + + /** + * @brief Removes first element. + * + * This is a typical %queue operation. It shrinks the %queue + * by one. The time complexity of the operation depends on the + * underlying sequence. + * + * Note that no data is returned, and if the first element's + * data is needed, it should be retrieved before pop() is + * called. + */ + void + pop() + { + __glibcxx_requires_nonempty(); + try { std::pop_heap(c.begin(), c.end(), comp); c.pop_back(); } - catch(...) + catch(...) { c.clear(); __throw_exception_again; } - } - }; + } + }; // No equality/comparison operators are provided for priority_queue. } // namespace std |