如何避免end方法返回的iterator无需的cache_字段额外内存开销？

在C++里，给类实现begin()/end()就能支持范围for循环，但如果迭代器里有只给起始迭代器用的大缓存，end返回的哨兵迭代器也会带着这个缓存，平白浪费内存。比如下面的代码里，begin和end迭代器的大小都是8200字节，明显end完全不需要那1024个size_t的缓存：

#include <cstddef>
#include <cstdio>

class A
{
private:

    size_t N_;

    struct iterator
    {
        size_t idx_;
    
        size_t cache_[1024];
    
        iterator (size_t idx) : idx_(idx) {}
        
        bool operator != (const iterator & other) const { return idx_ != other.idx_; }

        void operator ++ ()  {  ++ idx_;  }

        size_t operator* () const  { return idx_; }
    };


public:

    iterator begin()  { return iterator( 0); }
    iterator end()    { return iterator(N_); }
    
    A (size_t N) : N_(N) {}
};


int main ()
{
    A a(10);
    printf ("begin: %zu\n", sizeof(a.begin()));  // begin: 8200
    printf ("end  : %zu\n", sizeof(a.end()));    // end  : 8200
}

下面给你几个实用的解决办法：

方法1：拆分出独立的哨兵类型（最推荐） #

直接把end返回的迭代器做成一个极简的哨兵类型，只存终止索引，然后重载operator!=让它能和正常迭代器比较。这样end的内存开销直接降到sizeof(size_t)，逻辑也清晰。

修改后的代码：

#include <cstddef>
#include <cstdio>

class A
{
private:
    size_t N_;

    // 带缓存的正常迭代器，给begin用
    struct iterator
    {
        size_t idx_;
        size_t cache_[1024];

        iterator(size_t idx) : idx_(idx) {}
        
        // 支持和哨兵比较
        bool operator!=(const struct sentinel& other) const { 
            return idx_ != other.end_idx_; 
        }

        void operator++() { ++idx_; }
        size_t operator*() const { return idx_; }
    };

    // 哨兵类型，只存终止索引，给end用
    struct sentinel
    {
        size_t end_idx_;
        explicit sentinel(size_t idx) : end_idx_(idx) {}
    };

public:
    iterator begin() { return iterator(0); }
    sentinel end() { return sentinel(N_); }
    
    A(size_t N) : N_(N) {}
};

// 补充反向比较的重载，避免编译器报错
inline bool operator!=(const A::sentinel& s, const A::iterator& it) {
    return it != s;
}

int main()
{
    A a(10);
    printf("begin: %zu\n", sizeof(a.begin()));  // 输出8200
    printf("end  : %zu\n", sizeof(a.end()));    // 输出8，仅一个size_t的大小
    for (auto x : a) {
        printf("%zu ", x);
    }
}

这个方案完全兼容范围for循环，而且没有任何多余开销，代码改动也不大。

方法2：用空基类优化（EBO）实现 #

如果不想拆分两个类型，可以用继承+空基类优化的方式，让end迭代器继承空基类，begin迭代器继承带缓存的基类。C++的空基类优化会让空基类不占用额外内存，所以end迭代器的大小就是一个size_t的大小。

代码示例：

#include <cstddef>
#include <cstdio>

class A
{
private:
    size_t N_;

    // 空基类，给哨兵迭代器用
    struct empty_base {};
    // 带缓存的基类，给正常迭代器用
    struct cache_base { size_t cache_[1024]; };

    // 模板迭代器，继承不同基类实现不同功能
    template <typename Base>
    struct iterator_impl : Base
    {
        size_t idx_;
        iterator_impl(size_t idx) : idx_(idx) {}
        
        bool operator!=(const iterator_impl& other) const { 
            return idx_ != other.idx_; 
        }
        void operator++() { ++idx_; }
        size_t operator*() const { return idx_; }
    };

public:
    using iterator = iterator_impl<cache_base>;   // 带缓存的迭代器
    using sentinel = iterator_impl<empty_base>;  // 哨兵迭代器

    iterator begin() { return iterator(0); }
    sentinel end() { return sentinel(N_); }
    
    A(size_t N) : N_(N) {}
};

int main()
{
    A a(10);
    printf("begin: %zu\n", sizeof(a.begin()));  // 8200
    printf("end  : %zu\n", sizeof(a.end()));    // 8
    for (auto x : a) {
        printf("%zu ", x);
    }
}

这个方案的好处是迭代器的核心逻辑只写一次，但可读性不如方法1直观。

总结 #

最推荐用方法1，拆分哨兵类型，不仅彻底消除了end迭代器的多余内存开销，代码逻辑也清晰易懂，对原有代码的改动也很小。

内容的提问来源于stack exchange，提问作者abcdefg