From bbf2ed7890615a587f0209c6d7e9b2c08781ee09 Mon Sep 17 00:00:00 2001 From: Evan Brown Date: Mon, 17 Oct 2022 12:56:53 -0700 Subject: Implement btree_iterator::operator-, which is faster than std::distance for btree iterators. Note: btree_iterator::operator- is still O(N) because in the worst case (end()-begin()), we will have at least one operation per node in the tree, and there are at least N/M nodes, where M (a constant) is the maximum number of values per node. PiperOrigin-RevId: 481716874 Change-Id: Ic0225b7509208ed96b75a2dc626d2aa4a24f4946 --- absl/container/btree_map.h | 3 +++ 1 file changed, 3 insertions(+) (limited to 'absl/container/btree_map.h') diff --git a/absl/container/btree_map.h b/absl/container/btree_map.h index 286817f1..479db8b7 100644 --- a/absl/container/btree_map.h +++ b/absl/container/btree_map.h @@ -46,6 +46,9 @@ // reason, `insert()` and `erase()` return a valid iterator at the current // position. Another important difference is that key-types must be // copy-constructible. +// +// Another API difference is that btree iterators can be subtracted, and this +// is faster than using std::distance. #ifndef ABSL_CONTAINER_BTREE_MAP_H_ #define ABSL_CONTAINER_BTREE_MAP_H_ -- cgit v1.2.3