RAM高效存储容器的双指针嵌套迭代器实现疑问

I'm building a RAM-efficient container for storing sorted unsigned integers, using a grouping strategy based on a common radix. Instead of using a std::vector<unsigned int> like this:

std::vector<unsigned int> V = {1234,1254,1264,1265,1267,1268,1271,1819,1832,1856,1867,1892,3210,3214,3256,3289};

My MyContainer groups values by radix (e.g., grouping by 100 or more logically by 2^16) to save significant memory. The container structure is:

class MyContainer { 
    std::vector<Block> data; 
}; 
class Block { 
    unsigned short radix; 
    std::vector<unsigned short> suffixs; 
};

The core challenge now is implementing iterators that support forward traversal and random access. My current Iterator class holds:

std::vector<Block>::iterator bigP;
std::vector<unsigned short>::iterator smallP;
std::vector<Block>::iterator bigPEnd;

I have three key questions:

1. Should MyContainer::iterator store iterators or pointers? Why?
2. Do I need to store an iterator pointing to the end of data? How can I avoid it if possible?
3. How should I handle smallP when there's no target object (e.g., at the end iterator)?

Great question—this is a clever memory-efficient approach for sorted unsigned integers, and iterators are definitely the trickiest part to get right. Let's break down your three questions with practical, STL-aligned solutions:

Q1: Iterators vs. Pointers for MyContainer::iterator #

Go with iterators, not raw pointers—here's why this is the right call:

• Iterators are the STL's standard abstraction for traversing containers. Using them keeps your iterator consistent with how developers expect STL-style containers to work, making it easier to integrate with existing code (like std::for_each, std::lower_bound, etc.).
• Pointers lock you into the exact memory layout of std::vector. If you ever decide to switch the backing container (say, to std::deque for better insertion performance in the middle), raw pointers would break immediately, while iterators would only need minor tweaks.
• Many STL implementations add debug checks to iterators (like bounds checking) that raw pointers don't offer, which can catch bugs early during development.
• The only scenario where pointers might make sense is if you're optimizing for an extremely performance-critical path, but the difference is negligible for most use cases—and iterators give you way better maintainability in return.

Q2: Do We Need to Store the data End Iterator? How to Avoid It? #

You don't have to store bigPEnd as a member—here are two solid approaches to avoid it:

1. Store a pointer to the parent MyContainer's data vector: This lets you fetch data->end() whenever you need to check if your iterator has reached the end. The tradeoff is a tiny bit of indirection, but it eliminates redundant state and prevents issues if the data vector is resized (though you still need to follow STL iterator invalidation rules—if the container modifies data in a way that invalidates iterators, your iterator will be invalid just like STL iterators).
2. For read-only/immutable containers: If your MyContainer is built once and never modified after construction, storing bigPEnd is safe and slightly more efficient. But for mutable containers, the pointer approach is better because it avoids holding onto potentially invalidated end iterators.

Also, remember that your MyContainer's end iterator only needs bigP to point to data.end()—the smallP value doesn't matter here, since dereferencing an end iterator is undefined behavior (just like with STL iterators). So you don't need to track bigPEnd during normal traversal; you only need to compare bigP to the container's current data.end() when checking for the end state.

Q3: Handling smallP When There's No Target Object #

When your iterator is in a state where there's no valid element (like the end iterator, or before the first element), follow STL conventions to keep things simple:

• Leave smallP in a default-constructed state for end iterators: Since you'll never dereference an end iterator (that's a bug, just like with STL), it doesn't matter what smallP points to here. You just need to ensure that your iterator's equality checks work correctly (e.g., two end iterators are equal if their bigP values are both data.end(), regardless of smallP).
• Enforce validity for non-end iterators: For any iterator that's not at the end, bigP must point to a valid Block, and smallP must point to a valid element in bigP->suffixs. This way, you only have to worry about "invalid" smallP values in the end state, which you never use anyway.
• Avoid boolean flags: Resist the urge to add a is_end flag to your iterator—this adds unnecessary state and deviates from STL norms. Instead, use the bigP value to signal the end state.

Bonus Random Access Iterator Tips #

Since you need random access, here are a few key things to keep in mind:

• Calculate element offsets correctly: To find the index of the current element, sum the size of all suffixs vectors in blocks before bigP, then add the distance from bigP->suffixs.begin() to smallP.
• Jump to indices efficiently: When implementing operator+ or operator[], iterate through the blocks until you find the one that contains the target index, then set bigP to that block and smallP to the correct position in its suffixs.
• Implement iterator traits: Make sure to define the required traits for your iterator (value_type = unsigned int, difference_type = std::ptrdiff_t, iterator_category = std::random_access_iterator_tag, etc.) so STL algorithms recognize it as a random access iterator.

内容的提问来源于stack exchange，提问作者Remi.b