summaryrefslogtreecommitdiffstats
path: root/library/cpp/containers
diff options
context:
space:
mode:
Diffstat (limited to 'library/cpp/containers')
-rw-r--r--library/cpp/containers/paged_vector/README.md33
-rw-r--r--library/cpp/containers/paged_vector/paged_vector.h45
-rw-r--r--library/cpp/containers/paged_vector/ut/paged_vector_ut.cpp220
3 files changed, 298 insertions, 0 deletions
diff --git a/library/cpp/containers/paged_vector/README.md b/library/cpp/containers/paged_vector/README.md
index 1f67a0d1f7a..ae49c0c6523 100644
--- a/library/cpp/containers/paged_vector/README.md
+++ b/library/cpp/containers/paged_vector/README.md
@@ -34,6 +34,7 @@ The interface mirrors a subset of `std::vector`:
| Iterators | `begin()/end()`, `rbegin()/rend()` + const versions; random-access iterators |
| Capacity | `size()`, `empty()`, `explicit operator bool()` (true when non-empty) |
| Modifiers | `push_back()`, `emplace_back()` (returns a reference), `pop_back()`, `append(b, e)`, `erase(it)`, `erase(b, e)`, `resize()`, `clear()` |
+| Iteration helpers | `ForEach(fn)`, `ForEachReverse(fn)` |
| Comparison | `operator==`, `operator<` (lexicographical) |
Notable differences from `std::vector`:
@@ -48,6 +49,37 @@ Iterators are random-access and are implemented as an *(owner pointer, offset)*
- Dereferencing goes through the vector, so an iterator is only valid while its source container is alive.
- To get the current index of an element from an iterator, call `it.GetIndex()` — it returns the offset of the pointed-to element within the container (equivalent to `it - begin()`).
+## Iteration helpers
+
+```cpp
+template <class Function>
+void ForEach(Function fn) const;
+
+template <class Function>
+void ForEachReverse(Function fn) const;
+```
+
+`ForEach` applies `fn` to every element **from the first to the last**; `ForEachReverse` applies `fn` **from the last to the first**.
+
+These are faster than iterating with `begin()/end()` or `rbegin()/rend()`: they walk the pages directly through raw pointers, avoiding the two levels of indirection that the offset-based iterators go through on each dereference. This matters for containers with a large `PageSize` (the default is 1M elements per page), where the inner per-page loop is tight.
+
+```cpp
+TPagedVector<int, 1024> v;
+// ... fill v ...
+
+long long sum = 0;
+v.ForEach([&](int x) { sum += x; });
+
+// process elements back-to-front, e.g. for a stack-like traversal
+v.ForEachReverse([&](int x) {
+ // ...
+});
+```
+
+Notes:
+
+- The order is well-defined and contiguous: `ForEach` visits element `0, 1, ..., size()-1`; `ForEachReverse` visits `size()-1, ..., 1, 0`.
+- Both are O(n) and do not allocate.
## Complexity
@@ -58,6 +90,7 @@ Iterators are random-access and are implemented as an *(owner pointer, offset)*
| `pop_back` | O(1) |
| `erase` | O(n) — shifts all following elements |
| `clear` | O(n) for non-trivially destructible `T`, O(pages) otherwise |
+| `ForEach` / `ForEachReverse` | O(n), no allocations |
## Notes
diff --git a/library/cpp/containers/paged_vector/paged_vector.h b/library/cpp/containers/paged_vector/paged_vector.h
index 5bb8d8eb521..43073852ab3 100644
--- a/library/cpp/containers/paged_vector/paged_vector.h
+++ b/library/cpp/containers/paged_vector/paged_vector.h
@@ -278,6 +278,51 @@ namespace NPagedVector {
std::swap(CurrentPageSize_, v.CurrentPageSize_);
}
+ // Fast iteration over all elements.
+ template <class Function>
+ void ForEach(Function fn) const {
+ if (Pages_.empty()) {
+ return;
+ }
+
+ const auto currentPageIt = Pages_.end() - 1;
+ for (auto it = Pages_.begin(); it != currentPageIt; ++it) {
+ const TPage& page = **it;
+ for (size_t i = 0; i < PageSize; ++i) {
+ fn(page[i]);
+ }
+ }
+
+ const TPage& currentPage = **currentPageIt;
+
+ for (size_t i = 0; i < CurrentPageSize_; ++i) {
+ fn(currentPage[i]);
+ }
+ }
+
+ // Fast iteration over all elements in reverse order.
+ template <class Function>
+ void ForEachReverse(Function fn) const {
+ if (Pages_.empty()) {
+ return;
+ }
+
+ const TPage& currentPage = *Pages_.back();
+
+ for (size_t i = CurrentPageSize_; i > 0;) {
+ --i;
+ fn(currentPage[i]);
+ }
+
+ for (auto it = Pages_.rbegin() + 1; it != Pages_.rend(); ++it) {
+ const TPage& page = **it;
+ for (size_t i = PageSize; i > 0;) {
+ --i;
+ fn(page[i]);
+ }
+ }
+ }
+
private:
static size_t PageNumber(size_t idx) {
return idx / PageSize;
diff --git a/library/cpp/containers/paged_vector/ut/paged_vector_ut.cpp b/library/cpp/containers/paged_vector/ut/paged_vector_ut.cpp
index 4863227e7f1..b0f39f748fe 100644
--- a/library/cpp/containers/paged_vector/ut/paged_vector_ut.cpp
+++ b/library/cpp/containers/paged_vector/ut/paged_vector_ut.cpp
@@ -29,6 +29,8 @@ class TPagedVectorTest: public TTestBase {
UNIT_TEST(TestClear)
UNIT_TEST(TestBack)
UNIT_TEST(TestIterator)
+ UNIT_TEST(TestForEach)
+ UNIT_TEST(TestForEachReverse)
UNIT_TEST_SUITE_END();
private:
@@ -645,6 +647,224 @@ private:
UNIT_ASSERT_VALUES_EQUAL(it.GetIndex(), 6);
UNIT_ASSERT_VALUES_EQUAL(*it, "7");
}
+
+ void TestForEach() {
+ using NPagedVector::TPagedVector;
+
+ // Empty vector: the callback must not be invoked at all.
+ {
+ TPagedVector<int, 3> v;
+ size_t calls = 0;
+ v.ForEach([&](int) {
+ ++calls;
+ });
+ UNIT_ASSERT_VALUES_EQUAL(calls, 0u);
+ }
+
+ // Single element: the only element is visited once.
+ {
+ TPagedVector<int, 3> v;
+ v.push_back(42);
+ TVector<int> visited;
+ v.ForEach([&](int x) {
+ visited.push_back(x);
+ });
+ TVector<int> expected{42};
+ UNIT_ASSERT_VALUES_EQUAL(visited, expected);
+ }
+
+ // Several elements within a single (partially filled) page.
+ {
+ TPagedVector<int, 3> v;
+ for (int i = 0; i < 2; ++i) {
+ v.push_back(i);
+ }
+ TVector<int> visited;
+ int expectedElement = 0;
+ v.ForEach([&](int x) {
+ UNIT_ASSERT_VALUES_EQUAL(x, expectedElement);
+ ++expectedElement;
+ visited.push_back(x);
+ });
+ TVector<int> expected{0, 1};
+ UNIT_ASSERT_VALUES_EQUAL(visited, expected);
+ }
+
+ // A single exactly full page (3 elements): the visit order must be
+ // strictly forward.
+ {
+ TPagedVector<int, 3> v;
+ for (int i = 0; i < 3; ++i) {
+ v.push_back(i);
+ }
+ TVector<int> visited;
+ int expectedElement = 0;
+ v.ForEach([&](int x) {
+ UNIT_ASSERT_VALUES_EQUAL(x, expectedElement);
+ ++expectedElement;
+ visited.push_back(x);
+ });
+ TVector<int> expected{0, 1, 2};
+ UNIT_ASSERT_VALUES_EQUAL(visited, expected);
+ }
+
+ // Multiple pages with a partially filled last page: the visit order
+ // must be strictly forward (from the first element to the last).
+ {
+ TPagedVector<int, 3> v;
+ const int n = 10; // spans 4 pages of size 3: [0..2][3..5][6..8][9]
+ for (int i = 0; i < n; ++i) {
+ v.push_back(i);
+ }
+ TVector<int> visited;
+ visited.reserve(n);
+ int expectedElement = 0;
+ v.ForEach([&](int x) {
+ UNIT_ASSERT_VALUES_EQUAL(x, expectedElement);
+ ++expectedElement;
+ visited.push_back(x);
+ });
+ TVector<int> expected;
+ expected.reserve(n);
+ for (int i = 0; i < n; ++i) {
+ expected.push_back(i);
+ }
+ UNIT_ASSERT_VALUES_EQUAL(visited, expected);
+ }
+
+ // Exactly full pages (no partial tail): every element is visited,
+ // last page is completely filled.
+ {
+ TPagedVector<int, 3> v;
+ const int n = 9; // exactly 3 full pages of size 3
+ for (int i = 0; i < n; ++i) {
+ v.push_back(i);
+ }
+ TVector<int> visited;
+ visited.reserve(n);
+ int expectedElement = 0;
+ v.ForEach([&](int x) {
+ UNIT_ASSERT_VALUES_EQUAL(x, expectedElement);
+ ++expectedElement;
+ visited.push_back(x);
+ });
+ TVector<int> expected;
+ expected.reserve(n);
+ for (int i = 0; i < n; ++i) {
+ expected.push_back(i);
+ }
+ UNIT_ASSERT_VALUES_EQUAL(visited, expected);
+ }
+ }
+
+ void TestForEachReverse() {
+ using NPagedVector::TPagedVector;
+
+ // Empty vector: the callback must not be invoked at all.
+ {
+ TPagedVector<int, 3> v;
+ size_t calls = 0;
+ v.ForEachReverse([&](int) {
+ ++calls;
+ });
+ UNIT_ASSERT_VALUES_EQUAL(calls, 0u);
+ }
+
+ // Single element: the only element is visited once.
+ {
+ TPagedVector<int, 3> v;
+ v.push_back(42);
+ TVector<int> visited;
+ v.ForEachReverse([&](int x) {
+ visited.push_back(x);
+ });
+ TVector<int> expected{42};
+ UNIT_ASSERT_VALUES_EQUAL(visited, expected);
+ }
+
+ // Several elements within a single (partially filled) page.
+ {
+ TPagedVector<int, 3> v;
+ for (int i = 0; i < 2; ++i) {
+ v.push_back(i);
+ }
+ TVector<int> visited;
+ int expectedElement = 1;
+ v.ForEachReverse([&](int x) {
+ UNIT_ASSERT_VALUES_EQUAL(x, expectedElement);
+ --expectedElement;
+ visited.push_back(x);
+ });
+ TVector<int> expected{1, 0};
+ UNIT_ASSERT_VALUES_EQUAL(visited, expected);
+ }
+
+ // A single exactly full page (3 elements): the visit order must be
+ // strictly reverse.
+ {
+ TPagedVector<int, 3> v;
+ for (int i = 0; i < 3; ++i) {
+ v.push_back(i);
+ }
+ TVector<int> visited;
+ int expectedElement = 2;
+ v.ForEachReverse([&](int x) {
+ UNIT_ASSERT_VALUES_EQUAL(x, expectedElement);
+ --expectedElement;
+ visited.push_back(x);
+ });
+ TVector<int> expected{2, 1, 0};
+ UNIT_ASSERT_VALUES_EQUAL(visited, expected);
+ }
+
+ // Multiple pages with a partially filled last page: the visit order
+ // must be strictly reverse (from the last element to the first).
+ {
+ TPagedVector<int, 3> v;
+ const int n = 10; // spans 4 pages of size 3: [0..2][3..5][6..8][9]
+ for (int i = 0; i < n; ++i) {
+ v.push_back(i);
+ }
+ TVector<int> visited;
+ visited.reserve(n);
+ int expectedElement = n - 1;
+ v.ForEachReverse([&](int x) {
+ UNIT_ASSERT_VALUES_EQUAL(x, expectedElement);
+ --expectedElement;
+ visited.push_back(x);
+ });
+ TVector<int> expected;
+ expected.reserve(n);
+ for (int i = n - 1; i >= 0; --i) {
+ expected.push_back(i);
+ }
+ UNIT_ASSERT_VALUES_EQUAL(visited, expected);
+ }
+
+ // Exactly full pages (no partial tail): every element is visited,
+ // last page is completely filled.
+ {
+ TPagedVector<int, 3> v;
+ const int n = 9; // exactly 3 full pages of size 3
+ for (int i = 0; i < n; ++i) {
+ v.push_back(i);
+ }
+ TVector<int> visited;
+ visited.reserve(n);
+ int expectedElement = n - 1;
+ v.ForEachReverse([&](int x) {
+ UNIT_ASSERT_VALUES_EQUAL(x, expectedElement);
+ --expectedElement;
+ visited.push_back(x);
+ });
+ TVector<int> expected;
+ expected.reserve(n);
+ for (int i = n - 1; i >= 0; --i) {
+ expected.push_back(i);
+ }
+ UNIT_ASSERT_VALUES_EQUAL(visited, expected);
+ }
+ }
};
UNIT_TEST_SUITE_REGISTRATION(TPagedVectorTest);
generated by cgit v1.3 (git 2.53.0) at 2026-07-23 16:54:10 +0000