diff options
| author |  Evan Brown <ezb@google.com> | 2022-10-17 12:56:53 -0700 |
|---|---|---|
| committer |  Copybara-Service <copybara-worker@google.com> | 2022-10-17 12:58:14 -0700 |
| commit | bbf2ed7890615a587f0209c6d7e9b2c08781ee09 (patch) | |
| tree | 3ae3ec73b24f430ff747dd3af7f0c0a5717f4d6d /absl/container/btree_map.h | |
| parent | 7ab917ec21efb6cdb3c3946fbecb9522ff2af100 (diff) | |
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
Diffstat (limited to 'absl/container/btree_map.h')
| -rw-r--r-- | absl/container/btree_map.h | 3 |
1 files changed, 3 insertions, 0 deletions
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_ |