Skip to content

<chrono>: std::chrono::locate_zone should use binary search #5547

@cpplearner

Description

@cpplearner

[time.zone.db.tzdb]/1:

Each vector in a tzdb object is sorted to enable fast lookup.

The time zone names are sorted in the tzdb produced by MSVC's STL1, but locate_zone performs a linear search. It could be changed to a binary search, which would be faster.

STL/stl/inc/chrono

Lines 2106 to 2110 in 41ec195

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;
}

This is slightly more advanced than a "good first issue", requiring the contributor to understand how to perform binary search using std::lower_bound (not std::binary_search!).

Footnotes

  1. The data are obtained from ICU, and eventually from the zoneinfo64 resource. zoneinfo64 is generated by tz2icu, which sorts the names by using a std::map.

Metadata

Metadata

Assignees

No one assigned

    Labels

    chronoC++20 chronofixedSomething works now, yay!performanceMust go faster

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions