c++ - std::map<> or std::vector<> when dealing with large sets of flags? -

i working on compiler , have large set of flags. in cases, nodes receive small number of flags (about 12 largest), total number of flags rather large (over 50.) flags integers defined in enum:

enum flags_t {     flag_one,     flag_two,     flag_three,     [...]     max_flag }; 

i thinking using std::map<flags_t, bool> makes more sense because of nodes use 0, 1, or 2 flags , number of nodes large (it can become tenth of thousands.)

// map have check existing on avoid creating // useless entries in map bool node::get_flag(flags_t const f) {     flag_iterator it(f_flags.find(f));     return == f_flags.end() ? false : *it; }  void node::set_flag(flags_t const f, bool const value) {     f_flags[f] = value; } 

but i'm wondering whether std::vector<bool> not end being more effective? although @ first sight looks good:

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; } 

the vector needs allocated (i.e. sized properly) on initialization or get_flag() functions needs test whether f part of vector:

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

the problem can see resize() call allocate / free memory time, if end never using vector (most nodes don't need flags!) testing limit when trade off, need make sure vector large enough on set_flag() call... (in case we'd allocate whole set of flags @ once avoid reallocations.)

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; } 

so... std::vector or std::map better? or possibly std::set better? (i have not used std::set before...)

both std::set , std::map suboptimal choice flags because allocate storage dynamically, causing unnecessary fragmentation.

a simple way represent flags storing them in integral type. unsigned 64-bit type provide room 64 flags. both space-efficient , cpu-efficient, , idiomatic c++ boot. example:

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); } 

if more 64 flags needed, bit manipulation best left expressed std::bitset, offers array-like access individual bits of underlying value:

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]; }