C++实现支持排序的容器属性过滤自定义迭代器方案

你设想的预缓存方案完全可行，只要解决容器元素移动导致的地址失效问题，就能满足无全量扫描迭代、排序后分类可用的需求。

核心设计思路 #

不要预缓存对象裸指针，优先缓存元素在主容器的下标：

• 主存储用std::vector<Employee>存实际对象，内存连续、遍历和排序性能最好
• 额外维护两个std::vector<size_t>，分别存普通员工、管理者在主容器中的下标
• 索引仅在容器增删元素、排序操作后重建，单次全量扫描的开销仅在数据变更时触发，迭代时完全不需要判断is_manager属性，遍历管理者时只会访问对应下标的元素，不会扫描全量数据

1. 基础结构与迭代器实现 #

C++自定义迭代器不需要继承任何基类，只要满足对应迭代器类别要求的操作即可，针对你的场景实现前向迭代器足够用。
先定义基础结构体和集合封装类：

#include <vector>
#include <string>
#include <algorithm>
#include <iterator>

struct Employee {
    std::string name;
    bool is_manager;
};

class EmployeeCollection {
public:
    // 管理者迭代器定义
    class ManagerIterator {
    public:
        using iterator_category = std::forward_iterator_tag;
        using value_type = Employee;
        using difference_type = std::ptrdiff_t;
        using pointer = Employee*;
        using reference = Employee&;

        ManagerIterator(EmployeeCollection* col, std::vector<size_t>::const_iterator idx_it)
            : m_col(col), m_idx_it(idx_it) {}

        reference operator*() const { return m_col->m_main_store[*m_idx_it]; }
        pointer operator->() const { return &m_col->m_main_store[*m_idx_it]; }

        ManagerIterator& operator++() {
            ++m_idx_it;
            return *this;
        }

        ManagerIterator operator++(int) {
            ManagerIterator tmp = *this;
            ++(*this);
            return tmp;
        }

        bool operator==(const ManagerIterator& other) const = default;
        bool operator!=(const ManagerIterator& other) const = default;

    private:
        EmployeeCollection* m_col;
        std::vector<size_t>::const_iterator m_idx_it;
    };

    // 普通员工迭代器实现逻辑和管理者迭代器完全一致，仅对应索引列表不同
    class RegularIterator {
    public:
        using iterator_category = std::forward_iterator_tag;
        using value_type = Employee;
        using difference_type = std::ptrdiff_t;
        using pointer = Employee*;
        using reference = Employee&;

        RegularIterator(EmployeeCollection* col, std::vector<size_t>::const_iterator idx_it)
            : m_col(col), m_idx_it(idx_it) {}

        reference operator*() const { return m_col->m_main_store[*m_idx_it]; }
        pointer operator->() const { return &m_col->m_main_store[*m_idx_it]; }

        RegularIterator& operator++() {
            ++m_idx_it;
            return *this;
        }

        RegularIterator operator++(int) {
            RegularIterator tmp = *this;
            ++(*this);
            return tmp;
        }

        bool operator==(const RegularIterator& other) const = default;
        bool operator!=(const RegularIterator& other) const = default;

    private:
        EmployeeCollection* m_col;
        std::vector<size_t>::const_iterator m_idx_it;
    };

    // 迭代器起止接口
    ManagerIterator manager_begin() { return {this, m_manager_indices.cbegin()}; }
    ManagerIterator manager_end() { return {this, m_manager_indices.cend()}; }
    RegularIterator regular_begin() { return {this, m_regular_indices.cbegin()}; }
    RegularIterator regular_end() { return {this, m_regular_indices.cend()}; }

    // 按name排序接口
    void sort_by_name() {
        std::sort(m_main_store.begin(), m_main_store.end(),
                  [](const Employee& a, const Employee& b) { return a.name < b.name; });
        // 排序后重建索引
        rebuild_indices();
    }

    // 新增元素接口示例
    void add_employee(Employee emp) {
        m_main_store.push_back(std::move(emp));
        // 插入时直接维护索引，不需要全量重建
        size_t new_idx = m_main_store.size() - 1;
        if (m_main_store.back().is_manager) {
            m_manager_indices.push_back(new_idx);
        } else {
            m_regular_indices.push_back(new_idx);
        }
    }

private:
    void rebuild_indices() {
        m_manager_indices.clear();
        m_regular_indices.clear();
        // 管理者占比极低，预留少量空间即可
        m_manager_indices.reserve(64);
        m_regular_indices.reserve(m_main_store.size());
        for (size_t i = 0; i < m_main_store.size(); ++i) {
            if (m_main_store[i].is_manager) {
                m_manager_indices.push_back(i);
            } else {
                m_regular_indices.push_back(i);
            }
        }
    }

    std::vector<Employee> m_main_store;
    std::vector<size_t> m_manager_indices;
    std::vector<size_t> m_regular_indices;
};

2. 使用方式 #

迭代时直接调用对应begin/end接口即可，全程无is_manager判断，遍历管理者时仅访问缓存的下标对应的元素：

int main() {
    EmployeeCollection col;
    // 批量添加员工
    for (int i = 0; i < 100000; ++i) {
        col.add_employee({"employee_" + std::to_string(i), false});
    }
    col.add_employee({"boss", true});
    col.add_employee({"hr_manager", true});

    // 按name排序
    col.sort_by_name();

    // 遍历管理者，仅迭代2次，无全量扫描
    for (auto it = col.manager_begin(); it != col.manager_end(); ++it) {
        // 处理管理者逻辑
    }

    // 遍历普通员工
    for (auto it = col.regular_begin(); it != col.regular_end(); ++it) {
        // 处理普通员工逻辑
    }
}

3. 方案说明 #

• 预缓存下标的方案比存裸指针更稳妥：std::vector扩容、排序时元素移动不会导致下标逻辑错误，仅需在数据变更后重建索引即可，10万元素的重建耗时在微秒级，完全可以忽略。
• 如果你不想在排序/批量删除后全量重建索引，可以把主存储换成std::list<Employee>，链表元素的内存地址不会因排序、插入删除改变，此时缓存可以存Employee*，增删元素时只需要把对应指针加入/移除缓存列表即可，缺点是链表内存不连续，遍历性能比vector差。
• 迭代器实现完全符合C标准要求，可以直接和STL算法搭配使用，如果使用C20及以上版本，只需要加少量概念适配即可直接配合范围for、ranges库使用。

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