This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
[Patch] First bits of the algo merge
- From: Paolo Carlini <pcarlini at suse dot de>
- To: libstdc++ <libstdc++ at gcc dot gnu dot org>
- Date: Tue, 13 Dec 2005 13:22:16 +0100
- Subject: [Patch] First bits of the algo merge
Hi,
these are the first bits, adding the predefined_ops infrastructure and
changing the algobase functions.
Tested x86-linux, will commit later today.
Paolo.
///////////////////
2005-12-13 Paolo Carlini <pcarlini@suse.de>
Port from libstdcxx_so_7-branch:
2005-06-29 Chris Jefferson <chris@bubblescope.net>
* include/bits/predefined_ops.h (__bind2nd, bind2nd): New.
2005-06-13 Chris Jefferson <chris@bubblescope.net>
* include/bits/stl_algobase.h (mismatch, lexicographical_compare):
Add inline to trivial functions.
2005-03-14 Christopher Jefferson <chris@bubblescope.net>
* include/bits/predefined_ops.h (equal_to::operator(),
less::operator()): Add const.
2005-01-10 Christopher Jefferson <chris@bubblescope.net>
* include/bits/predefined_ops.h: New.
* include/Makefile.am: Add.
* include/Makefile.in: Regenerate.
* include/bits/stl_algobase.h (mismatch, equal,
lexicographical_compare): Make non-predicate version call predicated
version.
Index: include/bits/stl_algobase.h
===================================================================
--- include/bits/stl_algobase.h (revision 108413)
+++ include/bits/stl_algobase.h (working copy)
@@ -72,6 +72,7 @@
#include <bits/stl_iterator_base_types.h>
#include <bits/stl_iterator_base_funcs.h>
#include <bits/stl_iterator.h>
+#include <bits/predefined_ops.h>
#include <bits/concept_check.h>
#include <debug/debug.h>
@@ -671,39 +672,6 @@
* @param first1 An input iterator.
* @param last1 An input iterator.
* @param first2 An input iterator.
- * @return A pair of iterators pointing to the first mismatch.
- *
- * This compares the elements of two ranges using @c == and returns a pair
- * of iterators. The first iterator points into the first range, the
- * second iterator points into the second range, and the elements pointed
- * to by the iterators are not equal.
- */
- template<typename _InputIterator1, typename _InputIterator2>
- pair<_InputIterator1, _InputIterator2>
- mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
- _InputIterator2 __first2)
- {
- // concept requirements
- __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
- __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
- __glibcxx_function_requires(_EqualOpConcept<
- typename iterator_traits<_InputIterator1>::value_type,
- typename iterator_traits<_InputIterator2>::value_type>)
- __glibcxx_requires_valid_range(__first1, __last1);
-
- while (__first1 != __last1 && *__first1 == *__first2)
- {
- ++__first1;
- ++__first2;
- }
- return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
- }
-
- /**
- * @brief Finds the places in ranges which don't match.
- * @param first1 An input iterator.
- * @param last1 An input iterator.
- * @param first2 An input iterator.
* @param binary_pred A binary predicate @link s20_3_1_base functor@endlink.
* @return A pair of iterators pointing to the first mismatch.
*
@@ -733,33 +701,28 @@
}
/**
- * @brief Tests a range for element-wise equality.
+ * @brief Finds the places in ranges which don't match.
* @param first1 An input iterator.
* @param last1 An input iterator.
* @param first2 An input iterator.
- * @return A boolean true or false.
+ * @return A pair of iterators pointing to the first mismatch.
*
- * This compares the elements of two ranges using @c == and returns true or
- * false depending on whether all of the corresponding elements of the
- * ranges are equal.
+ * This compares the elements of two ranges using @c == and returns a pair
+ * of iterators. The first iterator points into the first range, the
+ * second iterator points into the second range, and the elements pointed
+ * to by the iterators are not equal.
*/
template<typename _InputIterator1, typename _InputIterator2>
- inline bool
- equal(_InputIterator1 __first1, _InputIterator1 __last1,
- _InputIterator2 __first2)
+ inline pair<_InputIterator1, _InputIterator2>
+ mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
+ _InputIterator2 __first2)
{
// concept requirements
- __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
- __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
__glibcxx_function_requires(_EqualOpConcept<
typename iterator_traits<_InputIterator1>::value_type,
typename iterator_traits<_InputIterator2>::value_type>)
- __glibcxx_requires_valid_range(__first1, __last1);
-
- for (; __first1 != __last1; ++__first1, ++__first2)
- if (!(*__first1 == *__first2))
- return false;
- return true;
+ return std::mismatch(__first1, __last1, __first2,
+ __gnu_cxx::__ops::equal_to());
}
/**
@@ -779,8 +742,7 @@
typename _BinaryPredicate>
inline bool
equal(_InputIterator1 __first1, _InputIterator1 __last1,
- _InputIterator2 __first2,
- _BinaryPredicate __binary_pred)
+ _InputIterator2 __first2, _BinaryPredicate __binary_pred)
{
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
@@ -794,45 +756,27 @@
}
/**
- * @brief Performs "dictionary" comparison on ranges.
+ * @brief Tests a range for element-wise equality.
* @param first1 An input iterator.
* @param last1 An input iterator.
* @param first2 An input iterator.
- * @param last2 An input iterator.
* @return A boolean true or false.
*
- * "Returns true if the sequence of elements defined by the range
- * [first1,last1) is lexicographically less than the sequence of elements
- * defined by the range [first2,last2). Returns false otherwise."
- * (Quoted from [25.3.8]/1.) If the iterators are all character pointers,
- * then this is an inline call to @c memcmp.
+ * This compares the elements of two ranges using @c == and returns true or
+ * false depending on whether all of the corresponding elements of the
+ * ranges are equal.
*/
template<typename _InputIterator1, typename _InputIterator2>
- bool
- lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
- _InputIterator2 __first2, _InputIterator2 __last2)
+ inline bool
+ equal(_InputIterator1 __first1, _InputIterator1 __last1,
+ _InputIterator2 __first2)
{
// concept requirements
- __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
- __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
- __glibcxx_function_requires(_LessThanOpConcept<
+ __glibcxx_function_requires(_EqualOpConcept<
typename iterator_traits<_InputIterator1>::value_type,
typename iterator_traits<_InputIterator2>::value_type>)
- __glibcxx_function_requires(_LessThanOpConcept<
- typename iterator_traits<_InputIterator2>::value_type,
- typename iterator_traits<_InputIterator1>::value_type>)
- __glibcxx_requires_valid_range(__first1, __last1);
- __glibcxx_requires_valid_range(__first2, __last2);
-
- for (; __first1 != __last1 && __first2 != __last2;
- ++__first1, ++__first2)
- {
- if (*__first1 < *__first2)
- return true;
- if (*__first2 < *__first1)
- return false;
- }
- return __first1 == __last1 && __first2 != __last2;
+ return std::equal(__first1, __last1, __first2,
+ __gnu_cxx::__ops::equal_to());
}
/**
@@ -871,6 +815,36 @@
return __first1 == __last1 && __first2 != __last2;
}
+ /**
+ * @brief Performs "dictionary" comparison on ranges.
+ * @param first1 An input iterator.
+ * @param last1 An input iterator.
+ * @param first2 An input iterator.
+ * @param last2 An input iterator.
+ * @return A boolean true or false.
+ *
+ * "Returns true if the sequence of elements defined by the range
+ * [first1,last1) is lexicographically less than the sequence of elements
+ * defined by the range [first2,last2). Returns false otherwise."
+ * (Quoted from [25.3.8]/1.) If the iterators are all character pointers,
+ * then this is an inline call to @c memcmp.
+ */
+ template<typename _InputIterator1, typename _InputIterator2>
+ inline bool
+ lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
+ _InputIterator2 __first2, _InputIterator2 __last2)
+ {
+ // concept requirements
+ __glibcxx_function_requires(_LessThanOpConcept<
+ typename iterator_traits<_InputIterator1>::value_type,
+ typename iterator_traits<_InputIterator2>::value_type>)
+ __glibcxx_function_requires(_LessThanOpConcept<
+ typename iterator_traits<_InputIterator2>::value_type,
+ typename iterator_traits<_InputIterator1>::value_type>)
+ return std::lexicographical_compare(__first1, __last1, __first2,
+ __last2, __gnu_cxx::__ops::less());
+ }
+
inline bool
lexicographical_compare(const unsigned char* __first1,
const unsigned char* __last1,
Index: include/bits/predefined_ops.h
===================================================================
--- include/bits/predefined_ops.h (revision 0)
+++ include/bits/predefined_ops.h (revision 0)
@@ -0,0 +1,112 @@
+// Default predicates for internal use -*- C++ -*-
+
+// Copyright (C) 2005 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 2, 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 General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING. If not, write to the Free
+// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// As a special exception, you may use this file as part of a free software
+// library without restriction. Specifically, if other files instantiate
+// templates or use macros or inline functions from this file, or you compile
+// this file and link it with other files to produce an executable, this
+// file does not by itself cause the resulting executable to be covered by
+// the GNU General Public License. This exception does not however
+// invalidate any other reasons why the executable file might be covered by
+// the GNU General Public License.
+
+/** @file predefined_ops.h
+ * This is an internal header file, included by other library headers.
+ * You should not attempt to use it directly.
+ */
+
+#ifndef _GLIBCXX_PREDEFINED_OPS_H
+#define _GLIBCXX_PREDEFINED_OPS_H 1
+
+namespace __gnu_cxx
+{
+namespace __ops
+{
+ struct less
+ {
+ template<typename _Lhs, typename _Rhs>
+ bool
+ operator()(const _Lhs& __lhs, const _Rhs& __rhs) const
+ { return __lhs < __rhs; }
+ };
+
+ struct equal_to
+ {
+ template<typename _Lhs, typename _Rhs>
+ bool
+ operator()(const _Lhs& __lhs, const _Rhs& __rhs) const
+ { return __lhs == __rhs; }
+ };
+
+ /**
+ * @if maint
+ * A class inspired by bind2nd and company, which wraps a function or
+ * class and a reference, and produces a unary function object. It has less
+ * requirements than the standard version and is designed to be use to wrap
+ * binary predicates given to algorithms in the standard library.
+ * @endif
+ */
+ template<typename _Comp, typename _Value>
+ class __bind2nd
+ {
+ _Comp _M_comp;
+ const _Value& _M_value;
+
+ public:
+ explicit
+ __bind2nd(_Comp __comp, const _Value& __inval)
+ : _M_comp(__comp), _M_value(__inval) {}
+
+ template<typename _Lhs>
+ bool
+ operator()(const _Lhs& __lhs)
+ { return _M_comp(__lhs, _M_value); }
+ };
+
+ /**
+ * @if maint
+ * Specialisation of __bind2nd for equality.
+ * @endif
+ */
+ template<typename _Value>
+ class __bind2nd<__gnu_cxx::__ops::equal_to, _Value>
+ {
+ const _Value& _M_value;
+
+ public:
+ explicit
+ __bind2nd(__gnu_cxx::__ops::equal_to, const _Value& __inval)
+ : _M_value(__inval) {}
+
+ template<typename _Lhs>
+ bool
+ operator()(const _Lhs& __lhs)
+ { return __lhs == _M_value; }
+ };
+
+ template<typename _Comp, typename _Value>
+ inline __bind2nd<_Comp, _Value>
+ bind2nd(_Comp __comp, const _Value& __value)
+ { return __bind2nd<_Comp, _Value>(__comp, __value); }
+
+} // namespace __ops
+} // namespace __gnu_cxx
+
+#endif
Index: include/Makefile.in
===================================================================
--- include/Makefile.in (revision 108413)
+++ include/Makefile.in (working copy)
@@ -336,6 +336,7 @@
${bits_srcdir}/mask_array.h \
${bits_srcdir}/ostream.tcc \
${bits_srcdir}/postypes.h \
+ ${bits_srcdir}/predefined_ops.h \
${bits_srcdir}/stream_iterator.h \
${bits_srcdir}/streambuf_iterator.h \
${bits_srcdir}/slice_array.h \
Index: include/Makefile.am
===================================================================
--- include/Makefile.am (revision 108413)
+++ include/Makefile.am (working copy)
@@ -119,6 +119,7 @@
${bits_srcdir}/mask_array.h \
${bits_srcdir}/ostream.tcc \
${bits_srcdir}/postypes.h \
+ ${bits_srcdir}/predefined_ops.h \
${bits_srcdir}/stream_iterator.h \
${bits_srcdir}/streambuf_iterator.h \
${bits_srcdir}/slice_array.h \