find_by_first.h 2.2 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758
  1. // Copyright 2020 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #ifndef CRDTP_FIND_BY_FIRST_H_
  5. #define CRDTP_FIND_BY_FIRST_H_
  6. #include <algorithm>
  7. #include <cstdint>
  8. #include <memory>
  9. #include <vector>
  10. #include "export.h"
  11. #include "span.h"
  12. namespace crdtp {
  13. // =============================================================================
  14. // FindByFirst - Retrieval from a sorted vector that's keyed by span<uint8_t>.
  15. // =============================================================================
  16. // Given a vector of pairs sorted by the first element of each pair, find
  17. // the corresponding value given a key to be compared to the first element.
  18. // Together with std::inplace_merge and pre-sorting or std::sort, this can
  19. // be used to implement a minimalistic equivalent of Chromium's flat_map.
  20. // In this variant, the template parameter |T| is a value type and a
  21. // |default_value| is provided.
  22. template <typename T>
  23. T FindByFirst(const std::vector<std::pair<span<uint8_t>, T>>& sorted_by_first,
  24. span<uint8_t> key,
  25. T default_value) {
  26. auto it = std::lower_bound(
  27. sorted_by_first.begin(), sorted_by_first.end(), key,
  28. [](const std::pair<span<uint8_t>, T>& left, span<uint8_t> right) {
  29. return SpanLessThan(left.first, right);
  30. });
  31. return (it != sorted_by_first.end() && SpanEquals(it->first, key))
  32. ? it->second
  33. : default_value;
  34. }
  35. // In this variant, the template parameter |T| is a class or struct that's
  36. // instantiated in std::unique_ptr, and we return either a T* or a nullptr.
  37. template <typename T>
  38. T* FindByFirst(const std::vector<std::pair<span<uint8_t>, std::unique_ptr<T>>>&
  39. sorted_by_first,
  40. span<uint8_t> key) {
  41. auto it = std::lower_bound(
  42. sorted_by_first.begin(), sorted_by_first.end(), key,
  43. [](const std::pair<span<uint8_t>, std::unique_ptr<T>>& left,
  44. span<uint8_t> right) { return SpanLessThan(left.first, right); });
  45. return (it != sorted_by_first.end() && SpanEquals(it->first, key))
  46. ? it->second.get()
  47. : nullptr;
  48. }
  49. } // namespace crdtp
  50. #endif // CRDTP_FIND_BY_FIRST_H_