Hi
Is it me or the patch isn't an attachment ? It is far more
convenient to provide something easy to extract and apply locally.
On 2/4/20 3:07 AM, Patrick Palka wrote:
This patch implements the C++20 ranges overloads for the algorithms in
[algorithms]. Most of the algorithms were reimplemented, with each of their
implementations very closely following the existing implementation in
bits/stl_algo.h and bits/stl_algobase.h. The reason for reimplementing most of
the algorithms instead of forwarding to their STL-style overload is because
forwarding cannot be conformantly and efficiently performed for algorithms that
operate on non-random-access iterators. But algorithms that operate on random
access iterators can safely and efficiently be forwarded to the STL-style
implementation, and this patch does so for push_heap, pop_heap, make_heap,
sort_heap, sort, stable_sort, nth_element, inplace_merge and stable_partition.
What's missing from this patch is debug-iterator
Always the 5th wheel of the car like we say in French :-)
I'll be looking at this point once I manage to apply the patch.
and container specializations
that are present for some of the STL-style algorithms that need to be ported
over to the ranges algos. I marked them missing at TODO comments. There are
also some other minor outstanding TODOs.
The code that could use the most thorough review is ranges::__copy_or_move,
ranges::__copy_or_move_backward, ranges::__equal and
ranges::__lexicographical_compare. In the tests, I tried to test the interface
of each new overload, as well as the correctness of the new implementation.
diff --git a/libstdc++-v3/include/bits/ranges_algo.h
b/libstdc++-v3/include/bits/ranges_algo.h
new file mode 100644
index 00000000000..2e177ce7f7a
--- /dev/null
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -0,0 +1,3640 @@
+// Core algorithmic facilities -*- C++ -*-
+
+// Copyright (C) 2019-2020 Free Software Foundation, Inc.
Copyright for new files is wrong, should be only 2020. I know it is
painful to maintain that when you work on patch on several years.
+//
+// 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 3, 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.
+
+// Under Section 7 of GPL version 3, you are granted additional
+// permissions described in the GCC Runtime Library Exception, version
+// 3.1, as published by the Free Software Foundation.
+
+// You should have received a copy of the GNU General Public License and
+// a copy of the GCC Runtime Library Exception along with this program;
+// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
+// <http://www.gnu.org/licenses/>.
+
+/** @file bits/ranges_algo.h
+ * This is an internal header file, included by other library headers.
+ * Do not attempt to use it directly. @headername{algorithm}
+ */
+
+#ifndef _RANGES_ALGO_H
+#define _RANGES_ALGO_H 1
+
+#if __cplusplus > 201703L
+
+#include <compare>
+#include <cmath>
+#include <iterator>
+// #include <bits/range_concepts.h>
+#include <ranges>
+#include <bits/invoke.h>
+#include <bits/cpp_type_traits.h> // __is_byte
+#include <bits/random.h> // concept uniform_random_bit_generator
+
+#if __cpp_lib_concepts
+namespace std _GLIBCXX_VISIBILITY(default)
+{
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+namespace ranges
+{
+ namespace __detail
+ {
+ template<typename _Tp>
+ constexpr inline bool __is_normal_iterator = false;
+
+ template<typename _Iterator, typename _Container>
+ constexpr inline bool
+ __is_normal_iterator<__gnu_cxx::__normal_iterator<_Iterator, _Container>>
+ = true;
+
+ template<typename _Tp>
+ constexpr inline bool __is_reverse_iterator = false;
+
+ template<typename _Iterator>
+ constexpr inline bool
+ __is_reverse_iterator<reverse_iterator<_Iterator>> = true;
+
+ template<typename _Tp>
+ constexpr inline bool __is_move_iterator = false;
+
+ template<typename _Iterator>
+ constexpr inline bool
+ __is_move_iterator<move_iterator<_Iterator>> = true;
Did you consider the __is_move_iterator in stl_iterator.h ?
At least this version will also detect a move_iterator in different
situation. I haven't check yet what you are doing with that but it might
be an easy way to get better debug iterators integration for instance.
François
