C++中支持负索引的类数组数据结构咨询

嗨，很高兴能帮到你！针对你需要跟踪元素存在状态的需求，这里有几个C++里的实用方案，不用手动做索引映射也能轻松处理-1000到1000的元素范围：

1. 使用哈希集合（最直接的存在性跟踪） #

如果你只需要记录元素是否存在，不需要额外关联数据，std::unordered_set（或者有序的std::set）是绝佳选择。它天然支持负数作为元素，不需要任何索引转换：

#include <unordered_set>
#include <iostream>

int main() {
    std::unordered_set<int> existingElements;
    
    // 标记元素存在
    existingElements.insert(-1000);
    existingElements.insert(500);
    existingElements.insert(0);
    
    // 检查元素是否存在
    if (existingElements.contains(500)) { // C++20及以上支持contains，旧版本用count() > 0
        std::cout << "500 exists!\n";
    }
    if (!existingElements.contains(-999)) {
        std::cout << "-999 does NOT exist!\n";
    }
    
    return 0;
}

• 优点：无需关心索引映射，只存储实际存在的元素，节省空间（当存在的元素数量远小于2001时）。
• 缺点：访问速度略慢于数组（哈希表的平均O(1) vs 数组的O(1)）。

2. 使用哈希映射（需要额外关联数据时） #

如果你除了存在性，还需要存储和元素相关的其他信息，可以用std::unordered_map（或std::map），键直接用元素的正负值：

#include <unordered_map>

std::unordered_map<int, bool> presenceMap;

// 标记存在
presenceMap[-300] = true;
presenceMap[1000] = true;

// 检查存在性
if (presenceMap.count(-300)) {
    // -300存在
}

• 适用场景：需要扩展存储更多元素相关数据时（比如存在次数、时间戳等）。

3. 封装偏移数组（性能最优方案） #

如果你的元素覆盖范围固定（-1000到1000），且大部分元素都可能存在，数组依然是性能最好的选择。你可以封装一个简单的类来隐藏索引偏移的细节，让使用更直观：

#include <cstring>

class PresenceTracker {
private:
    static constexpr int MIN_VAL = -1000;
    static constexpr int MAX_VAL = 1000;
    static constexpr int ARRAY_SIZE = MAX_VAL - MIN_VAL + 1;
    bool presence[ARRAY_SIZE] = {false}; // 默认初始化全为false

public:
    void markExists(int val) {
        if (val >= MIN_VAL && val <= MAX_VAL) {
            presence[val - MIN_VAL] = true; // 偏移计算：val - (-1000) = val + 1000
        }
        // 可选：添加越界处理逻辑
    }

    bool isExists(int val) const {
        if (val < MIN_VAL || val > MAX_VAL) {
            return false;
        }
        return presence[val - MIN_VAL];
    }
};

• 优点：访问速度最快（直接内存寻址），内存开销固定且可控（2001个bool值，仅约2KB）。
• 缺点：需要预先分配固定大小的内存，元素范围变化时需要修改代码。

总结 #

• 追求简单直观、元素稀疏：选std::unordered_set
• 需要关联额外数据：选std::unordered_map
• 追求极致性能、元素范围固定：选封装后的偏移数组

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