如何实现迭代返回对象指针且容量受限的std::map？

需要实现一个具备以下特性的std::map变体：

• 基于公司内部池容器限制容量，完全避免动态内存分配
• 迭代时返回对象指针而非对象本身

现有测试类A用于实例追踪：

class A{
public:
    A():classData(count++){std::cout<<"In A constructor()"<<std::endl;}
    int classData;
    inline static int count = 0;
};

尝试过自定义分配器但方案失败，分配器代码如下：

template <typename T, typename OBJ = void>
class CustomAllocator {
public:
    using value_type = T;
    using OBJ_VAL = std::remove_pointer_t<OBJ>;
   
    CustomAllocator() = default;
 
    template <typename U>
    constexpr CustomAllocator(const CustomAllocator<U>&) noexcept {}
 
    [[nodiscard]] T* allocate(std::size_t n) {
        if (n > std::size_t(-1) / sizeof(T)){
            throw std::bad_alloc();
        }     
        if (auto p = static_cast<T*>(std::malloc(n * sizeof(T)))) {
            std::cout << "Allocated " << n * sizeof(T) << " bytes"<<std::endl;
            return p;
        }
        throw std::bad_alloc();
    }
 
    void deallocate(T* p, std::size_t n) noexcept {
        std::cout << "Deallocated " << n * sizeof(T) << " bytes\n";
        std::free(p);
    }
 
    template <typename U, typename... Args>
    void construct(U* p, Args&&... args) {
            new(p) T();
            A*& tmp = ((U&)(*p)).second;
            tmp = &dataArr[i++];
    }
 
    template <typename U>
    void destroy(U* p) noexcept {
        p->~U();
    }
    std::atomic_int i = 0;
 
 
    std::array<A, 3> dataArr;
};

尝试使用该分配器的代码：

template <typename T, typename U>
using CustomAllocMap = std::map<T, U, std::less<T>, CustomAllocator<std::pair<const T, U>, U>>;
 
int main() {
    CustomAllocMap<int, A*> customMap;
   
    customMap[1];
    std::cout<<"Created first"<<std::endl;
    customMap[2];
    std::cout<<"Created second"<<std::endl;
    customMap[3];
    std::cout<<"Created third"<<std::endl;
 
    for (const auto& pair : customMap) {
        std::cout << pair.first << ": " << pair.second->classData << '\n';
    }
 
    return 0;
}

核心疑问：如何实现满足上述两个需求的std::map变体？

一、实现基于内存池的分配器（限制容量+避免动态分配） #

std::map的每个内部节点由分配器管理，因此需要替换依赖malloc的分配器，改用预分配的固定内存池。以下是基于std::array模拟公司内部池的实现：

#include <array>
#include <atomic>
#include <stdexcept>
#include <cstddef>

template <typename T, std::size_t MAX_NODES = 3>
class PoolAllocator {
public:
    using value_type = T;

    PoolAllocator() = default;
    template <typename U>
    constexpr PoolAllocator(const PoolAllocator<U, MAX_NODES>&) noexcept {}

    [[nodiscard]] T* allocate(std::size_t n) {
        // std::map每次仅分配单个节点，拒绝批量分配请求
        if (n != 1) throw std::bad_alloc();
        
        std::size_t idx = m_next_idx.fetch_add(1);
        if (idx >= MAX_NODES) throw std::runtime_error("Map node pool exhausted");
        
        return reinterpret_cast<T*>(&m_pool[idx]);
    }

    void deallocate(T* p, std::size_t n) noexcept {
        // 池分配无需真正释放，若需复用可添加回收逻辑，此处简化处理
    }

    template <typename U, typename... Args>
    void construct(U* p, Args&&... args) {
        new(p) U(std::forward<Args>(args)...);
    }

    template <typename U>
    void destroy(U* p) noexcept {
        p->~U();
    }

private:
    using PoolType = std::array<std::byte, sizeof(T) * MAX_NODES>;
    PoolType m_pool;
    std::atomic_size_t m_next_idx = 0;
};

// 分配器等价性判断（标准要求）
template <typename T, typename U, std::size_t MAX>
constexpr bool operator==(const PoolAllocator<T, MAX>&, const PoolAllocator<U, MAX>&) noexcept {
    return true;
}

template <typename T, typename U, std::size_t MAX>
constexpr bool operator!=(const PoolAllocator<T, MAX>&, const PoolAllocator<U, MAX>&) noexcept {
    return false;
}

二、实现迭代器返回对象指针 #

std::map的迭代器返回类型无法直接修改，可通过两种方式实现需求：

方式1：让Map直接存储对象指针（最简单方案）

让std::map的Value类型为对象指针，结合独立的对象池存储业务实例，迭代时直接取pair.second即可得到目标指针：

#include <map>
#include <iostream>

class A{
public:
    A():classData(count++){std::cout<<"In A constructor()"<<std::endl;}
    int classData;
    inline static int count = 0;
};

// 定义基于池分配器的Map类型
template <typename Key, typename Value>
using PoolMap = std::map<Key, Value, std::less<Key>, PoolAllocator<std::pair<const Key, Value>, 3>>;

// 模拟公司内部的A实例池
class AObjectPool {
public:
    static A* get() {
        if (s_next_idx >= s_pool.size()) throw std::runtime_error("A instance pool exhausted");
        return &s_pool[s_next_idx++];
    }
private:
    static inline std::array<A, 3> s_pool;
    static inline std::size_t s_next_idx = 0;
};

int main() {
    try {
        PoolMap<int, A*> customMap;

        customMap[1] = AObjectPool::get();
        std::cout<<"Created first"<<std::endl;
        customMap[2] = AObjectPool::get();
        std::cout<<"Created second"<<std::endl;
        customMap[3] = AObjectPool::get();
        std::cout<<"Created third"<<std::endl;

        // 迭代直接获取A*
        for (const auto& pair : customMap) {
            std::cout << pair.first << ": " << pair.second->classData << '\n';
        }

        // 尝试插入第四个元素会触发池容量超限异常
        // customMap[4] = AObjectPool::get();
    } catch (const std::exception& e) {
        std::cerr << "Error: " << e.what() << std::endl;
    }
    return 0;
}

方式2：迭代器适配器包装（不修改Map存储类型）

若不想让Map存储指针，可编写迭代器适配器，将原Map迭代器返回的std::pair<const K, V>转换为V*：

#include <iterator>

template <typename MapIterator>
class ObjectPointerIterator {
public:
    using iterator_category = typename MapIterator::iterator_category;
    using value_type = typename MapIterator::value_type::second_type*;
    using difference_type = typename MapIterator::difference_type;
    using pointer = value_type*;
    using reference = value_type&;

    explicit ObjectPointerIterator(MapIterator it) : m_it(it) {}

    value_type operator*() const { return &(m_it->second); }
    value_type operator->() const { return &(m_it->second); }

    ObjectPointerIterator& operator++() { ++m_it; return *this; }
    ObjectPointerIterator operator++(int) { auto temp = *this; ++m_it; return temp; }

    bool operator==(const ObjectPointerIterator& other) const { return m_it == other.m_it; }
    bool operator!=(const ObjectPointerIterator& other) const { return m_it != other.m_it; }

private:
    MapIterator m_it;
};

// 包装Map的类，对外提供自定义迭代器
template <typename Map>
class MapWithPointerIterators {
public:
    using iterator = ObjectPointerIterator<typename Map::iterator>;
    using const_iterator = ObjectPointerIterator<typename Map::const_iterator>;

    MapWithPointerIterators(Map map) : m_map(std::move(map)) {}

    iterator begin() { return iterator(m_map.begin()); }
    iterator end() { return iterator(m_map.end()); }
    const_iterator begin() const { return const_iterator(m_map.begin()); }
    const_iterator end() const { return const_iterator(m_map.end()); }

    // 暴露原Map的核心接口
    template <typename Key>
    auto& operator[](Key&& key) { return m_map[std::forward<Key>(key)]; }

private:
    Map m_map;
};

// 使用示例
int main() {
    try {
        PoolMap<int, A> objMap;
        MapWithPointerIterators<decltype(objMap)> wrappedMap(std::move(objMap));

        wrappedMap[1];
        std::cout<<"Created first"<<std::endl;
        wrappedMap[2];
        std::cout<<"Created second"<<std::endl;
        wrappedMap[3];
        std::cout<<"Created third"<<std::endl;

        // 迭代直接获取A*
        for (A* ptr : wrappedMap) {
            std::cout << ptr->classData << '\n';
        }
    } catch (const std::exception& e) {
        std::cerr << "Error: " << e.what() << std::endl;
    }
    return 0;
}

三、关键注意事项 #

• 内存池分配器需严格限制MAX_NODES，超出容量时必须抛出异常或处理，避免内存越界
• 节点池（管理Map内部节点）与对象池（管理业务实例）需分开维护，避免耦合
• 迭代器适配器需完整实现标准迭代器的所有必要类型与操作，确保兼容STL算法

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