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_set.h | |
| parent | 7ab917ec21efb6cdb3c3946fbecb9522ff2af100 (diff) | |
| download | abseil-bbf2ed7890615a587f0209c6d7e9b2c08781ee09.tar.gz abseil-bbf2ed7890615a587f0209c6d7e9b2c08781ee09.tar.bz2 abseil-bbf2ed7890615a587f0209c6d7e9b2c08781ee09.zip | |
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_set.h')
| -rw-r--r-- | absl/container/btree_set.h | 3 |
1 files changed, 3 insertions, 0 deletions
diff --git a/absl/container/btree_set.h b/absl/container/btree_set.h index e823a2a0..bbff65d1 100644 --- a/absl/container/btree_set.h +++ b/absl/container/btree_set.h @@ -45,6 +45,9 @@ // more than one iterator, pointer, or reference simultaneously. For this // reason, `insert()` and `erase()` return a valid iterator at the current // position. +// +// Another API difference is that btree iterators can be subtracted, and this +// is faster than using std::distance. #ifndef ABSL_CONTAINER_BTREE_SET_H_ #define ABSL_CONTAINER_BTREE_SET_H_ |