about summary refs log tree commit diff
path: root/absl/algorithm
diff options
context:
space:
mode:
authorAbseil Team <absl-team@google.com>2018-11-13T21·22-0800
committerJon Cohen <cohenjon@google.com>2018-11-13T22·56-0500
commit7b46e1d31a6b08b1c6da2a13e7b151a20446fa07 (patch)
tree0e4f4ad83ffb009e5e54004b2f3c003ecd216135 /absl/algorithm
parent070f6e47b33a2909d039e620c873204f78809492 (diff)
Export of internal Abseil changes.
--
07575526242a8e1275ac4223a3d2822795f46569 by CJ Johnson <johnsoncj@google.com>:

Comment cleanup on InlinedVector

PiperOrigin-RevId: 221322176

--
49a5e643f85e34d53c41f5e6cc33357c55c9115d by Matt Kulukundis <kfm@google.com>:

Internal cleanup

PiperOrigin-RevId: 221309185

--
bb35be87ec9c74244b7d902e7e7d2d33ab139d76 by Abseil Team <absl-team@google.com>:

Fix typo in comment.

PiperOrigin-RevId: 221145354

--
afd4d7c106919708004e06aeea068a57c28aec44 by Derek Mauro <dmauro@google.com>:

Update the debugging log message in CallOnceImpl()

PiperOrigin-RevId: 221103254

--
0b9dace8b88113777bf26a6d38f9bc0bcaf053a1 by Abseil Team <absl-team@google.com>:

Workaround an MSVC 2015 bug in compile-time initialization.

PiperOrigin-RevId: 220871483

--
ea0a3854511ed26beab827e5a5113766b334db86 by Marek Gilbert <mcg@google.com>:

Fix ABSL_HAVE_THREAD_LOCAL when compiling for iOS 8 with Xcode 10.

Xcode 10 has moved the check for thread_local to a link time, so
clang reports __has_feature(cxx_thread_local) but then linking fails
with messages like this:

ld: targeted OS version does not support use of thread local variables
PiperOrigin-RevId: 220815885

--
485b6876c158c3dcf37eb32d7e512242d5d4ecc6 by Greg Falcon <gfalcon@google.com>:

Make the absl::c_set_xxxx() algorithms refuse to compile when passed an unordered collection from std:: or absl::.

These algorithms operate on sorted sequences; passing an unordered container to them is nearly certainly a bug.  This change is technically an API break, but it only breaks incorrect code.

We could try to be more clever and detect unordered collections from other libraries, but false positives will break legal code, and this would constitute an API break Abseil cannot afford.

PiperOrigin-RevId: 220794190

--
c47cff7f9cc70a4c1604eee0131af552f40e46d6 by Jon Cohen <cohenjon@google.com>:

MSVC 2017's STL throws a Structured Exception (not a C++ exception, essentially equivalent to SIGSEGV) when variant::emplace calls a throwing constructor when using the debug multithreaded MSVC runtime DLL.  This manifests in dbg mode in Bazel builds.  Disable tests which trigger this bug.

It's impossible to specifically pull out MSVC 2017 -dbg modes because there's no way for Bazel to know when version of MSVC is being used -- you tell Bazel the directory where the MSVC tools live, not which version of MSVC tools to use.  Thus the best we can do is switch on _DEBUG, which is set whenever the debug runtime is selected with the /MDd build flag, as in Bazel -dbg modes.  See https://msdn.microsoft.com/en-us/library/b0084kay.aspx ctrl-f "_DEBUG"

PiperOrigin-RevId: 220706161

--
43993d4af309d92f4ebff38391dcc245f154ecc7 by Shaindel Schwartz <shaindel@google.com>:

Internal change

PiperOrigin-RevId: 220688429

--
2448802972dcc261af153af464f2b022ef54a2a9 by Abseil Team <absl-team@google.com>:

Speed up operator* for uint128 in WIN64.

PiperOrigin-RevId: 220678790

--
7b376403dd05ba10152fb52e40b29d8af79b58bb by Abseil Team <absl-team@google.com>:

Import of CCTZ from GitHub.

PiperOrigin-RevId: 220654834

--
ae08af58111c3f838b8d4de25f501c3559c86002 by Abseil Team <absl-team@google.com>:

CMake: Add absl_cc_test function

PiperOrigin-RevId: 220603940
GitOrigin-RevId: 07575526242a8e1275ac4223a3d2822795f46569
Change-Id: Iba7f53eb394c8a9de564582a976793f9bb0596d9
Diffstat (limited to 'absl/algorithm')
-rw-r--r--absl/algorithm/container.h78
1 files changed, 69 insertions, 9 deletions
diff --git a/absl/algorithm/container.h b/absl/algorithm/container.h
index 53ab15686c6e..6d5f6630f718 100644
--- a/absl/algorithm/container.h
+++ b/absl/algorithm/container.h
@@ -46,6 +46,8 @@
 #include <iterator>
 #include <numeric>
 #include <type_traits>
+#include <unordered_map>
+#include <unordered_set>
 #include <utility>
 #include <vector>
 
@@ -54,7 +56,6 @@
 #include "absl/meta/type_traits.h"
 
 namespace absl {
-
 namespace container_algorithm_internal {
 
 // NOTE: it is important to defer to ADL lookup for building with C++ modules,
@@ -101,6 +102,17 @@ ContainerIter<C> c_begin(C& c) { return begin(c); }
 template <typename C>
 ContainerIter<C> c_end(C& c) { return end(c); }
 
+template <typename T>
+struct IsUnorderedContainer : std::false_type {};
+
+template <class Key, class T, class Hash, class KeyEqual, class Allocator>
+struct IsUnorderedContainer<
+    std::unordered_map<Key, T, Hash, KeyEqual, Allocator>> : std::true_type {};
+
+template <class Key, class Hash, class KeyEqual, class Allocator>
+struct IsUnorderedContainer<std::unordered_set<Key, Hash, KeyEqual, Allocator>>
+    : std::true_type {};
+
 }  // namespace container_algorithm_internal
 
 // PUBLIC API
@@ -1154,7 +1166,13 @@ bool c_includes(const C1& c1, const C2& c2, Compare&& comp) {
 // Container-based version of the <algorithm> `std::set_union()` function
 // to return an iterator containing the union of two containers; duplicate
 // values are not copied into the output.
-template <typename C1, typename C2, typename OutputIterator>
+template <typename C1, typename C2, typename OutputIterator,
+          typename = typename std::enable_if<
+              !container_algorithm_internal::IsUnorderedContainer<C1>::value,
+              void>::type,
+          typename = typename std::enable_if<
+              !container_algorithm_internal::IsUnorderedContainer<C2>::value,
+              void>::type>
 OutputIterator c_set_union(const C1& c1, const C2& c2, OutputIterator output) {
   return std::set_union(container_algorithm_internal::c_begin(c1),
                         container_algorithm_internal::c_end(c1),
@@ -1164,7 +1182,13 @@ OutputIterator c_set_union(const C1& c1, const C2& c2, OutputIterator output) {
 
 // Overload of c_set_union() for performing a merge using a `comp` other than
 // `operator<`.
-template <typename C1, typename C2, typename OutputIterator, typename Compare>
+template <typename C1, typename C2, typename OutputIterator, typename Compare,
+          typename = typename std::enable_if<
+              !container_algorithm_internal::IsUnorderedContainer<C1>::value,
+              void>::type,
+          typename = typename std::enable_if<
+              !container_algorithm_internal::IsUnorderedContainer<C2>::value,
+              void>::type>
 OutputIterator c_set_union(const C1& c1, const C2& c2, OutputIterator output,
                            Compare&& comp) {
   return std::set_union(container_algorithm_internal::c_begin(c1),
@@ -1178,7 +1202,13 @@ OutputIterator c_set_union(const C1& c1, const C2& c2, OutputIterator output,
 //
 // Container-based version of the <algorithm> `std::set_intersection()` function
 // to return an iterator containing the intersection of two containers.
-template <typename C1, typename C2, typename OutputIterator>
+template <typename C1, typename C2, typename OutputIterator,
+          typename = typename std::enable_if<
+              !container_algorithm_internal::IsUnorderedContainer<C1>::value,
+              void>::type,
+          typename = typename std::enable_if<
+              !container_algorithm_internal::IsUnorderedContainer<C2>::value,
+              void>::type>
 OutputIterator c_set_intersection(const C1& c1, const C2& c2,
                                   OutputIterator output) {
   return std::set_intersection(container_algorithm_internal::c_begin(c1),
@@ -1189,7 +1219,13 @@ OutputIterator c_set_intersection(const C1& c1, const C2& c2,
 
 // Overload of c_set_intersection() for performing a merge using a `comp` other
 // than `operator<`.
-template <typename C1, typename C2, typename OutputIterator, typename Compare>
+template <typename C1, typename C2, typename OutputIterator, typename Compare,
+          typename = typename std::enable_if<
+              !container_algorithm_internal::IsUnorderedContainer<C1>::value,
+              void>::type,
+          typename = typename std::enable_if<
+              !container_algorithm_internal::IsUnorderedContainer<C2>::value,
+              void>::type>
 OutputIterator c_set_intersection(const C1& c1, const C2& c2,
                                   OutputIterator output, Compare&& comp) {
   return std::set_intersection(container_algorithm_internal::c_begin(c1),
@@ -1204,7 +1240,13 @@ OutputIterator c_set_intersection(const C1& c1, const C2& c2,
 // Container-based version of the <algorithm> `std::set_difference()` function
 // to return an iterator containing elements present in the first container but
 // not in the second.
-template <typename C1, typename C2, typename OutputIterator>
+template <typename C1, typename C2, typename OutputIterator,
+          typename = typename std::enable_if<
+              !container_algorithm_internal::IsUnorderedContainer<C1>::value,
+              void>::type,
+          typename = typename std::enable_if<
+              !container_algorithm_internal::IsUnorderedContainer<C2>::value,
+              void>::type>
 OutputIterator c_set_difference(const C1& c1, const C2& c2,
                                 OutputIterator output) {
   return std::set_difference(container_algorithm_internal::c_begin(c1),
@@ -1215,7 +1257,13 @@ OutputIterator c_set_difference(const C1& c1, const C2& c2,
 
 // Overload of c_set_difference() for performing a merge using a `comp` other
 // than `operator<`.
-template <typename C1, typename C2, typename OutputIterator, typename Compare>
+template <typename C1, typename C2, typename OutputIterator, typename Compare,
+          typename = typename std::enable_if<
+              !container_algorithm_internal::IsUnorderedContainer<C1>::value,
+              void>::type,
+          typename = typename std::enable_if<
+              !container_algorithm_internal::IsUnorderedContainer<C2>::value,
+              void>::type>
 OutputIterator c_set_difference(const C1& c1, const C2& c2,
                                 OutputIterator output, Compare&& comp) {
   return std::set_difference(container_algorithm_internal::c_begin(c1),
@@ -1230,7 +1278,13 @@ OutputIterator c_set_difference(const C1& c1, const C2& c2,
 // Container-based version of the <algorithm> `std::set_symmetric_difference()`
 // function to return an iterator containing elements present in either one
 // container or the other, but not both.
-template <typename C1, typename C2, typename OutputIterator>
+template <typename C1, typename C2, typename OutputIterator,
+          typename = typename std::enable_if<
+              !container_algorithm_internal::IsUnorderedContainer<C1>::value,
+              void>::type,
+          typename = typename std::enable_if<
+              !container_algorithm_internal::IsUnorderedContainer<C2>::value,
+              void>::type>
 OutputIterator c_set_symmetric_difference(const C1& c1, const C2& c2,
                                           OutputIterator output) {
   return std::set_symmetric_difference(
@@ -1242,7 +1296,13 @@ OutputIterator c_set_symmetric_difference(const C1& c1, const C2& c2,
 
 // Overload of c_set_symmetric_difference() for performing a merge using a
 // `comp` other than `operator<`.
-template <typename C1, typename C2, typename OutputIterator, typename Compare>
+template <typename C1, typename C2, typename OutputIterator, typename Compare,
+          typename = typename std::enable_if<
+              !container_algorithm_internal::IsUnorderedContainer<C1>::value,
+              void>::type,
+          typename = typename std::enable_if<
+              !container_algorithm_internal::IsUnorderedContainer<C2>::value,
+              void>::type>
 OutputIterator c_set_symmetric_difference(const C1& c1, const C2& c2,
                                           OutputIterator output,
                                           Compare&& comp) {