Use lower_bound instead of find_if to lookup time_zones. (#5548)

YexuanXiao · StephanTLavavej · web-flow · commit fa1448dd8a09 · 2025-05-28T15:49:03.000-07:00
Co-authored-by: Stephan T. Lavavej &lt;stl@microsoft.com&gt;
diff --git a/benchmarks/CMakeLists.txt b/benchmarks/CMakeLists.txt
@@ -114,6 +114,7 @@ add_benchmark(has_single_bit src/has_single_bit.cpp)
 add_benchmark(iota src/iota.cpp)
 add_benchmark(is_sorted_until src/is_sorted_until.cpp)
 add_benchmark(locale_classic src/locale_classic.cpp)
+add_benchmark(locate_zone src/locate_zone.cpp)
 add_benchmark(minmax_element src/minmax_element.cpp)
 add_benchmark(mismatch src/mismatch.cpp)
 add_benchmark(move_only_function src/move_only_function.cpp)
diff --git a/benchmarks/src/locate_zone.cpp b/benchmarks/src/locate_zone.cpp
@@ -0,0 +1,19 @@
+// Copyright (c) Microsoft Corporation.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+
+#include "benchmark/benchmark.h"
+#include <chrono>
+
+void locate_zone(benchmark::State& state) {
+    const auto& db = std::chrono::get_tzdb();
+    for (auto _ : state) {
+        for (const auto& z : db.zones) {
+            auto res = db.locate_zone(z.name());
+            benchmark::DoNotOptimize(res);
+        }
+    }
+}
+
+BENCHMARK(locate_zone);
+
+BENCHMARK_MAIN();
diff --git a/stl/inc/chrono b/stl/inc/chrono
@@ -2105,8 +2105,14 @@ namespace chrono {
 
     template <class _Ty>
     _NODISCARD const _Ty* _Locate_zone_impl(const vector<_Ty>& _Vec, string_view _Name) {
-        const auto _Result = _STD find_if(_Vec.begin(), _Vec.end(), [&](auto& _Tz) { return _Tz.name() == _Name; });
-        return _Result == _Vec.end() ? nullptr : &*_Result;
+        // N5008 [time.zone.db.tzdb]/1: "Each vector in a tzdb object is sorted to enable fast lookup."
+        const auto _Result = _STD lower_bound(
+            _Vec.begin(), _Vec.end(), _Name, [](const auto& _Tz, const auto& _Sv) { return _Tz.name() < _Sv; });
+        if (_Result != _Vec.end() && _Result->name() == _Name) {
+            return &*_Result;
+        } else {
+            return nullptr;
+        }
     }
 
     _EXPORT_STD struct tzdb {
diff --git a/tests/std/tests/P0355R7_calendars_and_time_zones_time_zones/test.cpp b/tests/std/tests/P0355R7_calendars_and_time_zones_time_zones/test.cpp
@@ -393,6 +393,15 @@ void timezone_precision_test() {
     }
 }
 
+void timezone_sorted_vectors_test() {
+    // N5008 [time.zone.db.tzdb]/1: "Each vector in a tzdb object is sorted to enable fast lookup."
+    const auto& my_tzdb = get_tzdb();
+
+    assert(ranges::is_sorted(my_tzdb.zones));
+    assert(ranges::is_sorted(my_tzdb.links));
+    assert(ranges::is_sorted(my_tzdb.leap_seconds));
+}
+
 void test() {
     timezone_tzdb_list_test();
     timezone_version_test();
@@ -401,6 +410,7 @@ void test() {
     timezone_to_local_test();
     timezone_local_info_test();
     timezone_precision_test();
+    timezone_sorted_vectors_test();
 }
 
 int main() {
