二维vector容器中State元素唯一快速插入功能实现问询

首先，我们需要解决两个核心问题：跟踪每个State的唯一性和处理deepness更新时的元素迁移。由于std::unique_ptr是独占所有权的智能指针，直接遍历整个二维容器查找元素效率太低，所以我们需要一个辅助结构来快速定位元素位置。

核心思路 #

1. 辅助映射表：用哈希表记录每个State对象的地址（天然唯一）对应的当前deepness和在对应vector中的迭代器，把元素查找复杂度从O(N*M)降到O(1)。
2. 插入逻辑分支：
   • 元素不存在：直接插入到目标deepness的vector中，并更新映射表。
   • 元素已存在：仅当新deepness小于旧deepness时，将元素从旧位置迁移到新位置，同时更新映射表；否则不做操作。

完整代码实现 #

先给出一个示例State类（你可以替换成自己的实际定义），再实现容器和插入函数：

#include <vector>
#include <memory>
#include <unordered_map>

// 示例State类，可根据需求修改成员和构造函数
class State {
public:
    int id; // 示例唯一标识，也可以用对象地址替代
    State(int id_val) : id(id_val) {}
};

class StateContainer {
private:
    // 二维容器：存储不同deepness层级的unique_ptr<State>
    std::vector<std::vector<std::unique_ptr<State>>> m_container;
    // 辅助映射表：State对象地址 -> (当前所在deepness, 对应vector中的迭代器)
    std::unordered_map<State*, std::pair<std::size_t, std::vector<std::unique_ptr<State>>::iterator>> m_state_map;

public:
    bool insert(State && value, std::size_t deepness) {
        // 用std::move接管传入的State所有权，生成unique_ptr
        auto new_state = std::make_unique<State>(std::move(value));
        State* state_ptr = new_state.get();

        // 检查元素是否已存在于容器中
        auto map_iter = m_state_map.find(state_ptr);
        if (map_iter != m_state_map.end()) {
            auto [old_deepness, vec_iter] = map_iter->second;

            // 新deepness不小于旧值，无需操作，返回false
            if (deepness >= old_deepness) {
                return false;
            }

            // --- 迁移元素到新的deepness层级 ---
            // 1. 从旧vector中转移unique_ptr的所有权，避免erase时销毁元素
            auto moved_state = std::move(*vec_iter);
            // 2. 从旧vector中删除该位置
            m_container[old_deepness].erase(vec_iter);
            // 3. 确保目标deepness对应的vector已存在
            if (m_container.size() <= deepness) {
                m_container.resize(deepness + 1);
            }
            // 4. 将元素插入到新的vector中
            auto new_vec_iter = m_container[deepness].emplace(m_container[deepness].end(), std::move(moved_state));
            // 5. 更新映射表中的位置记录
            map_iter->second = {deepness, new_vec_iter};
            return true;
        } else {
            // --- 插入全新元素 ---
            // 确保目标deepness对应的vector已存在
            if (m_container.size() <= deepness) {
                m_container.resize(deepness + 1);
            }
            // 插入到目标vector并获取迭代器
            auto vec_iter = m_container[deepness].emplace(m_container[deepness].end(), std::move(new_state));
            // 记录元素的位置信息到映射表
            m_state_map[state_ptr] = {deepness, vec_iter};
            return true;
        }
    }

    // 可选：添加打印方法用于验证容器状态
    void print_container() const {
        for (std::size_t i = 0; i < m_container.size(); ++i) {
            std::cout << "Deepness " << i << ": ";
            for (const auto& ptr : m_container[i]) {
                std::cout << ptr->id << " ";
            }
            std::cout << "\n";
        }
    }
};

关键细节说明 #

1. 辅助映射表的必要性：

   • 直接遍历二维容器查找元素效率极低，尤其是当容器规模较大时，映射表能让我们在O(1)时间内定位元素的位置。
   • 用State对象的地址作为键，不需要给State额外添加唯一标识字段，天然保证唯一性。

2. unique_ptr的所有权处理：

   • 所有涉及unique_ptr的操作必须用std::move转移所有权，符合它的独占语义。
   • 迁移元素时，先通过std::move(*vec_iter)把所有权转移出来，再调用erase，避免元素被意外销毁。

3. 容器大小的保证：

   • 插入前检查m_container的大小，如果目标deepness超过当前最大索引，就调用resize扩展容器，确保m_container[deepness]是有效的vector。

4. 返回值逻辑：

   • 插入新元素成功，或者迁移旧元素成功时返回true。
   • 元素已存在且新deepness不小于旧值时返回false。

测试示例 #

#include <iostream>

int main() {
    StateContainer container;

    // 插入新元素到deepness 2
    container.insert(State(100), 2);
    container.print_container(); // 输出：Deepness 0: ; Deepness 1: ; Deepness 2: 100 

    // 尝试将同一元素插入到deepness 3（返回false，因为3>=2）
    bool result = container.insert(State(100), 3);
    std::cout << "Insert to deepness 3: " << std::boolalpha << result << "\n"; // 输出false
    container.print_container(); // 容器无变化

    // 将元素迁移到deepness 1（返回true）
    result = container.insert(State(100), 1);
    std::cout << "Move to deepness 1: " << std::boolalpha << result << "\n"; // 输出true
    container.print_container(); // 输出：Deepness 0: ; Deepness 1: 100 ; Deepness 2: 

    return 0;
}

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