summaryrefslogtreecommitdiff
path: root/absl/algorithm
diff options
context:
space:
mode:
authorGravatar Abseil Team <absl-team@google.com>2020-02-25 22:27:31 +0100
committerGravatar CJ Johnson <johnsoncj@google.com>2020-02-25 17:56:58 -0500
commitb832dce8489ef7b6231384909fd9b68d5a5ff2b7 (patch)
tree3ad4be9a9a4105366be714da9458e076a77be18f /absl/algorithm
parentaa844899c937bde5d2b24f276b59997e5b668bde (diff)
Creation of LTS branch "lts_2020_02_25"20200225
- 0033c9ea91a52ade7c6b725aa2ef3cbe15463421 Fix build on FreeBSD/powerpc (#616) by kgotlinux <60880393+kgotlinux@users.noreply.github.com> - 0d5ce2797eb695aee7e019e25323251ef6ffc277 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - b69c7d880caddfc25bf348dbcfe9d45fdd8bc6e6 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 2a5633fc077a58528cdbfe78720f3f6bfdc6044d Merge "Export of internal Abseil changes" by Xiaoyi Zhang <zhangxy@google.com> - f9b3d6e493c1b6ab3dbdab71c5f8fa849db4abaf Add RISCV support to GetProgramCounter() (#621) by Khem Raj <raj.khem@gmail.com> - 0232c87f21c26718aa3eb2d86678070f3b498a4e Add missing ABSL_HAVE_VDSO_SUPPORT conditional (#622) by Sinan Kaya <41809318+franksinankaya@users.noreply.github.com> - 3c814105108680997d0821077694f663693b5382 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - c44657f55692eddf5504156645d1f4ec7b3acabd Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 98eb410c93ad059f9bba1bf43f5bb916fc92a5ea Export of internal Abseil changes by Abseil Team <absl-team@google.com> - bf78e977309c4cb946914b456404141ddac1c302 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - d95d1567165d449e4c213ea31a15cbb112a9865f Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 24713a7036a81498334807fa5c7ad3cb7c643711 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 72382c21fefed981b4b8a2a1b82e2d231c2c2e39 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 08a7e7bf972c8451855a5022f2faf3d3655db015 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 36bcd9599b3f48c99357ba61cf33584889306d6a Fix pointer format specifier in documentation (#614) by Andre Nguyen <andre-nguyen@users.noreply.github.com> - 0f86336b6939ea673cc1cbe29189286cae67d63a Export of internal Abseil changes by Abseil Team <absl-team@google.com> - c512f118dde6ffd51cb7d8ac8804bbaf4d266c3a Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 37dd2562ec830d547a1524bb306be313ac3f2556 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 44427702614d7b86b064ba06a390f5eb2f85dbf6 fix: Add support for more ARM processors detection (#608) by Andre Nguyen <andre-nguyen@users.noreply.github.com> - 159bf2bf6d1cc8087e02468d071e94d1177d1bae Export of internal Abseil changes by Abseil Team <absl-team@google.com> - a2e6adecc294dc4cd98cc285a9134ce58e0f2ad0 Use https links. (#586) by nlewycky <nicholas@mxc.ca> - 564001ae506a17c51fa1223684a78f05f91d3d91 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - b3aaac8a37c467a1125c794196caa90d0957bdc3 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 63ee2f8877915a3565c29707dba8fe4d7822596a Export of internal Abseil changes by Abseil Team <absl-team@google.com> - a048203a881f11f4b7b8df5fb563aec85522f8db Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 1de0166368e2ae67347f92099d6dca3ab3a4a496 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - ad904b6cd3906ddf79878003d92b7bc08d7786ae Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 29235139149790f5afc430c11cec8f1eb1677607 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - bf86cfe165ef7d70dfe68f0b8fc0c018bc79a577 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 12bc53e0318d80569270a5b26ccbc62b52022b89 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 1e39f8626a4dadec1f56920b999dd4c3cfae333e Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 77f87009a34c745255bd84d8f2647040d831a2b3 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - d659fe54b35ab9b8e35c72e50a4b8814167d5a84 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - a4b757b5d42694306a9de853cee0a5fba9c7bbe9 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 0514227d2547793b23e209809276375e41c76617 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 7f4fe64af80fe3c84db8ea938276c3690573c45e Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 16d9fd58a51c6083234e2e9f8f50e49ed5ed02e4 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - bcaae6009c0833b73c6fa7bdd972921d8081a724 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 8ba96a8244bbe334d09542e92d566673a65c1f78 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 2103fd9acdf58279f739860bff3f8c9f4b845605 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 3df7b52a6ada51a72a23796b844549a7b282f1b8 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - fa8c75182fbfdeddb2485fc0d53baeda3f40b7a3 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 85092b4b648ca729c6263c4a302a41dfff28705e Fix Conan builds (#400) by Adrian Ostrowski <adr.ostrowski@gmail.com> - e96ae2203b80d5ae2e0b7abe0c77b722b224b16d Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 20de2db748ca0471cfb61cb53e813dd12938c12b Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 846e5dbedac123d12455adcfe6f53c8b5dcbfeef Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 8207907f4f7fbaeeaa2b7340c76875e06fd345ba Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 078b89b3c046d230ef3ad39494e5852184eb528b Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 19b021cb3ff23048dfbe236a4e611925d8930831 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - ecc0033b54847f6c9ee37dbb0be8aa17e5b6d37b Always enable proper symbolize implementation on Windows ... by Loo Rong Jie <loorongjie@gmail.com> - 2796d500aea5a31d26b8b24a33fab7a1c8fa2f32 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - e4c8d0eb8ef4acb5d7a4252b3b87feb391ef7e41 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - a15364ce4d88534ae2295127e5d8e32aefb6b446 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - ab3552a18964e7063c8324f45b3896a6a20b08a8 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - e9f9000c7c80993cb589d011616b7a8016e42f4a Fix ABSL_WAITER_MODE detection for mingw (#342) by Joe Sylve <Joe.Sylve@gmail.com> - abea769b551f7a100f540967cb95debdb0080df8 Fix ABSL_HAVE_ALARM check on mingw (#341) by Joe Sylve <Joe.Sylve@gmail.com> - 25597bdfc148e91e27678ec30efa52f4fc8c164f Export of internal Abseil changes by Abseil Team <absl-team@google.com> - aad33fefaa8f744d71ce747a53717b835bdf8e84 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 8fe7214fe2d7a45ecc4d85f6a524c6b1532426de Export of internal Abseil changes by Abseil Team <absl-team@google.com> - debac94cfb5a0fa75d1d97c399682bd1c72e3191 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 882b3501a31eb0e4ae4213afb91a0e43feda7d5f Fix spelling errors (#384) by Sungmann Cho <55860394+chosungmann@users.noreply.github.com> - 502efe6d7841bff82b1aeef5500491fe9a48c635 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - ccdd1d57b6386ebc26fb0c7d99b604672437c124 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - ddf8e52a2918dd0ccec75d3e2426125fa3926724 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 6ec136281086b71da32b5fb068bd6e46b78a5c79 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - ac78ffc3bc0a8b295cab9a03817760fd460df2a1 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 5374c56e5196320681993869e3126b51edac2a43 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 97c1664b4bbab5f78fac2b151ab02656268fb34b Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 325fd7b042ff4ec34f7dd32e602cd81ad0e24b22 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 83c1d65c90a92aa49632b9ac5a793214bb0768bc Export of internal Abseil changes by Abseil Team <absl-team@google.com> - eb6b7bd23bc0815bfd784e1a74021ce166765280 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 9ddac555b7861dc178d0dbe758a1cfbed718784b Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 1948f6f967e34db9793cfa8b4bcbaf370d039fd8 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - a0d1e098c2f99694fa399b175a7ccf920762030e Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 2d2d7fbc283315b676159716376e739d3d23ed94 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 0302d1e5fa4fcdd1763b7d1bb3212943b1ae911d supppress unused variable warning for gcc (#372) by Martin <pizzard@users.noreply.github.com> - 262d74ba81b1fc4d71f459555cde8ecb39786d68 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - f0afae0d49af3e15a7169e019634d7719143d94d Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 0e7afdcbd24c7e5b7cab4e0217d8886f1525b520 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 9a41ffdd3a0ccbcdd29c4e3886b28e06f2cd9c66 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 36910d3d7e9fccadd6603f232d0c4f54dcd47c7e [bazel] Add fixes for --incompatible_load_cc_rules_from_b... by Yannic <contact@yannic-bonenberger.com> - aae8143cf9aa611f70d7ea9b95b8b8b383b2271a Export of internal Abseil changes by Abseil Team <absl-team@google.com> - d9aa92d7fb324314f9df487ac23d32a25650b742 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 321ab5303023c86cd15d9ddc5740fb4b4fde32e1 Export of internal Abseil changes by Abseil Team <absl-team@google.com> - 4ef574064e75b86f115549e9eb4c7e806781b3ab Export of internal Abseil changes by Abseil Team <absl-team@google.com> GitOrigin-RevId: 0033c9ea91a52ade7c6b725aa2ef3cbe15463421 Change-Id: I8a2b70063cb3ab40c6943a6db0fe40cae71ed8d7
Diffstat (limited to 'absl/algorithm')
-rw-r--r--absl/algorithm/BUILD.bazel2
-rw-r--r--absl/algorithm/CMakeLists.txt2
-rw-r--r--absl/algorithm/algorithm.h17
-rw-r--r--absl/algorithm/container.h25
-rw-r--r--absl/algorithm/container_test.cc6
5 files changed, 42 insertions, 10 deletions
diff --git a/absl/algorithm/BUILD.bazel b/absl/algorithm/BUILD.bazel
index c506f3b9..6a96420b 100644
--- a/absl/algorithm/BUILD.bazel
+++ b/absl/algorithm/BUILD.bazel
@@ -14,6 +14,7 @@
# limitations under the License.
#
+load("@rules_cc//cc:defs.bzl", "cc_library", "cc_test")
load(
"//absl:copts/configure_copts.bzl",
"ABSL_DEFAULT_COPTS",
@@ -30,6 +31,7 @@ cc_library(
hdrs = ["algorithm.h"],
copts = ABSL_DEFAULT_COPTS,
linkopts = ABSL_DEFAULT_LINKOPTS,
+ deps = ["//absl/base:config"],
)
cc_test(
diff --git a/absl/algorithm/CMakeLists.txt b/absl/algorithm/CMakeLists.txt
index 9fbe36f6..56cd0fb8 100644
--- a/absl/algorithm/CMakeLists.txt
+++ b/absl/algorithm/CMakeLists.txt
@@ -21,6 +21,8 @@ absl_cc_library(
"algorithm.h"
COPTS
${ABSL_DEFAULT_COPTS}
+ DEPS
+ absl::config
PUBLIC
)
diff --git a/absl/algorithm/algorithm.h b/absl/algorithm/algorithm.h
index 7c2b787e..e9b47338 100644
--- a/absl/algorithm/algorithm.h
+++ b/absl/algorithm/algorithm.h
@@ -26,8 +26,10 @@
#include <iterator>
#include <type_traits>
+#include "absl/base/config.h"
+
namespace absl {
-inline namespace lts_2019_08_08 {
+ABSL_NAMESPACE_BEGIN
namespace algorithm_internal {
@@ -85,6 +87,8 @@ It RotateImpl(It first, It middle, It last, std::false_type) {
} // namespace algorithm_internal
+// equal()
+//
// Compares the equality of two ranges specified by pairs of iterators, using
// the given predicate, returning true iff for each corresponding iterator i1
// and i2 in the first and second range respectively, pred(*i1, *i2) == true
@@ -105,8 +109,8 @@ bool equal(InputIter1 first1, InputIter1 last1, InputIter2 first2,
typename std::iterator_traits<InputIter2>::iterator_category{});
}
-// Performs comparison of two ranges specified by pairs of iterators using
-// operator==.
+// Overload of equal() that performs comparison of two ranges specified by pairs
+// of iterators using operator==.
template <typename InputIter1, typename InputIter2>
bool equal(InputIter1 first1, InputIter1 last1, InputIter2 first2,
InputIter2 last2) {
@@ -114,6 +118,8 @@ bool equal(InputIter1 first1, InputIter1 last1, InputIter2 first2,
algorithm_internal::EqualTo{});
}
+// linear_search()
+//
// Performs a linear search for `value` using the iterator `first` up to
// but not including `last`, returning true if [`first`, `last`) contains an
// element equal to `value`.
@@ -127,6 +133,8 @@ bool linear_search(InputIterator first, InputIterator last,
return std::find(first, last, value) != last;
}
+// rotate()
+//
// Performs a left rotation on a range of elements (`first`, `last`) such that
// `middle` is now the first element. `rotate()` returns an iterator pointing to
// the first element before rotation. This function is exactly the same as
@@ -136,7 +144,6 @@ bool linear_search(InputIterator first, InputIterator last,
// The complexity of this algorithm is the same as that of `std::rotate`, but if
// `ForwardIterator` is not a random-access iterator, then `absl::rotate`
// performs an additional pass over the range to construct the return value.
-
template <typename ForwardIterator>
ForwardIterator rotate(ForwardIterator first, ForwardIterator middle,
ForwardIterator last) {
@@ -146,7 +153,7 @@ ForwardIterator rotate(ForwardIterator first, ForwardIterator middle,
ForwardIterator>());
}
-} // inline namespace lts_2019_08_08
+ABSL_NAMESPACE_END
} // namespace absl
#endif // ABSL_ALGORITHM_ALGORITHM_H_
diff --git a/absl/algorithm/container.h b/absl/algorithm/container.h
index 16389be7..d72532de 100644
--- a/absl/algorithm/container.h
+++ b/absl/algorithm/container.h
@@ -55,7 +55,7 @@
#include "absl/meta/type_traits.h"
namespace absl {
-inline namespace lts_2019_08_08 {
+ABSL_NAMESPACE_BEGIN
namespace container_algorithm_internal {
// NOTE: it is important to defer to ADL lookup for building with C++ modules,
@@ -113,6 +113,18 @@ template <class Key, class Hash, class KeyEqual, class Allocator>
struct IsUnorderedContainer<std::unordered_set<Key, Hash, KeyEqual, Allocator>>
: std::true_type {};
+// container_algorithm_internal::c_size. It is meant for internal use only.
+
+template <class C>
+auto c_size(C& c) -> decltype(c.size()) {
+ return c.size();
+}
+
+template <class T, std::size_t N>
+constexpr std::size_t c_size(T (&)[N]) {
+ return N;
+}
+
} // namespace container_algorithm_internal
// PUBLIC API
@@ -257,7 +269,8 @@ container_algorithm_internal::ContainerIter<Sequence1> c_find_end(
// c_find_first_of()
//
// Container-based version of the <algorithm> `std::find_first_of()` function to
-// find the first elements in an ordered set within a container.
+// find the first element within the container that is also within the options
+// container.
template <typename C1, typename C2>
container_algorithm_internal::ContainerIter<C1> c_find_first_of(C1& container,
C2& options) {
@@ -366,7 +379,8 @@ c_mismatch(C1& c1, C2& c2, BinaryPredicate&& pred) {
template <typename C1, typename C2>
bool c_equal(const C1& c1, const C2& c2) {
- return ((c1.size() == c2.size()) &&
+ return ((container_algorithm_internal::c_size(c1) ==
+ container_algorithm_internal::c_size(c2)) &&
std::equal(container_algorithm_internal::c_begin(c1),
container_algorithm_internal::c_end(c1),
container_algorithm_internal::c_begin(c2)));
@@ -376,7 +390,8 @@ bool c_equal(const C1& c1, const C2& c2) {
// the function's test condition.
template <typename C1, typename C2, typename BinaryPredicate>
bool c_equal(const C1& c1, const C2& c2, BinaryPredicate&& pred) {
- return ((c1.size() == c2.size()) &&
+ return ((container_algorithm_internal::c_size(c1) ==
+ container_algorithm_internal::c_size(c2)) &&
std::equal(container_algorithm_internal::c_begin(c1),
container_algorithm_internal::c_end(c1),
container_algorithm_internal::c_begin(c2),
@@ -1706,7 +1721,7 @@ OutputIt c_partial_sum(const InputSequence& input, OutputIt output_first,
output_first, std::forward<BinaryOp>(op));
}
-} // inline namespace lts_2019_08_08
+ABSL_NAMESPACE_END
} // namespace absl
#endif // ABSL_ALGORITHM_CONTAINER_H_
diff --git a/absl/algorithm/container_test.cc b/absl/algorithm/container_test.cc
index 86bf9d3e..0a4abe94 100644
--- a/absl/algorithm/container_test.cc
+++ b/absl/algorithm/container_test.cc
@@ -163,23 +163,29 @@ TEST_F(NonMutatingTest, MismatchWithPredicate) {
TEST_F(NonMutatingTest, Equal) {
EXPECT_TRUE(absl::c_equal(vector_, sequence_));
EXPECT_TRUE(absl::c_equal(sequence_, vector_));
+ EXPECT_TRUE(absl::c_equal(sequence_, array_));
+ EXPECT_TRUE(absl::c_equal(array_, vector_));
// Test that behavior appropriately differs from that of equal().
std::vector<int> vector_plus = {1, 2, 3};
vector_plus.push_back(4);
EXPECT_FALSE(absl::c_equal(vector_plus, sequence_));
EXPECT_FALSE(absl::c_equal(sequence_, vector_plus));
+ EXPECT_FALSE(absl::c_equal(array_, vector_plus));
}
TEST_F(NonMutatingTest, EqualWithPredicate) {
EXPECT_TRUE(absl::c_equal(vector_, sequence_, Equals));
EXPECT_TRUE(absl::c_equal(sequence_, vector_, Equals));
+ EXPECT_TRUE(absl::c_equal(array_, sequence_, Equals));
+ EXPECT_TRUE(absl::c_equal(vector_, array_, Equals));
// Test that behavior appropriately differs from that of equal().
std::vector<int> vector_plus = {1, 2, 3};
vector_plus.push_back(4);
EXPECT_FALSE(absl::c_equal(vector_plus, sequence_, Equals));
EXPECT_FALSE(absl::c_equal(sequence_, vector_plus, Equals));
+ EXPECT_FALSE(absl::c_equal(vector_plus, array_, Equals));
}
TEST_F(NonMutatingTest, IsPermutation) {