c++ - std::map<> 或 std::vector<> 在处理大量标志时？

Question

我正在开发一个编译器并且有大量的标志。在大多数情况下，我的节点将收到非常少量的标志(最大的大约 12 个)，但标志的总数相当大(超过 50 个)。所有标志都是在枚举中定义的整数:

enum flags_t
{
    FLAG_ONE,
    FLAG_TWO,
    FLAG_THREE,
    [...]
    MAX_FLAG
};

我认为使用 std::map<flags_t, bool>更有意义，因为我的大多数节点都可能使用 0、1 或 2 标志，并且节点数量非常大(很容易变成十分之一。)

// with a map we have to check the existing on a get to avoid creating
// useless entries in the map
bool node::get_flag(flags_t const f)
{
    flag_iterator it(f_flags.find(f));
    return it == f_flags.end() ? false : *it;
}

void node::set_flag(flags_t const f, bool const value)
{
    f_flags[f] = value;
}

但我想知道是否std::vector<bool>实际上最终不会更有效吗？虽然乍一看这看起来不错:

bool node::get_flag(flags_t const f)
{
    return f_flags[f];
}

void node::set_flag(flags_t const f, bool const value)
{
    f_flags[f] = value;
}

vector 需要在初始化时分配(即适当调整大小)或者 get_flag() 函数需要测试 f 是否是 vector 的一部分:

bool node::get_flag(flags_t const f)
{
    return f >= f_flags.size() ? false : f_flags[f];
}

我在 resize() 调用中看到的问题是我们会一直分配/释放内存，即使我们最终从未实际使用 vector (大多数节点不需要任何标志!)所以测试在我们执行 get 时限制可能是一个很好的权衡，但我们还需要确保 vector 在 set_flag() 调用中足够大......(在这种情况下，我们可能会在一次以避免重新分配。)

bool node::set_flag(flags_t const f, bool const value)
{
    if(MAX_FLAG > f_flags.size())
    {
        f_flags.resize(MAX_FLAG);
    }
    f_flags[f] = value;
}

所以... std::vector或 std::map会更好？或者可能 std::set会更好吗？ (我之前没有用过std::set...)

Answer 1

std::set 和 std::map 都不是标志的最佳选择，因为它们动态分配存储，导致不必要的碎片。

表示标志的一种简单方法是将它们存储在整数类型中。无符号的 64 位类型将为 64 个标志提供空间。这将既节省空间又节省 CPU，并且是惯用的 C++ 启动方式。例如:

enum flag_code
{
    FLAG_ONE = 1ULL << 0,
    FLAG_TWO = 1ULL << 1,
    FLAG_THREE = 1ULL << 2,
    [...]
};

typedef uint64_t flags_t;

void node::set_flag(flag_code f, bool value)
{
    if (value)
        f_flags |= f;
    else
        f_flags &= ~f;
}

bool node::get_flag(flag_code f)
{
    return bool(f_flags & f);
}

如果需要超过 64 个标志，位操作最好用 std::bitset 表示，它还提供对基础值的各个位的类似数组的访问:

enum flag_code
{
    FLAG_ONE,
    FLAG_TWO,
    FLAG_THREE,
    [...]
    MAX_FLAG
};

typedef std::bitset<MAX_FLAG - 1> flags_t;

void node::set_flag(flag_code f, bool value)
{
    f_flags[f] = value;
}

bool node::get_flag(flag_code f)
{
    return f_flags[f];
}