c++ - Select elements from a list according to their properties -

i developing application aimed render huge number of shapes. each shape can assigned specific layer.

i input data list of shapes, each shape have string property represents layer shape belongs.

now, need develop method allows me select (draw) shapes belong given list of selected layers. in pseudo-code:

void draw_if(sorted_list shapes, list<string> selected_layers) {    each shape in shapes    {       if (shape.layer in selected_layers)         shape.draw();    } } 

the point perform operation fast possible; therefore need choose right data structures , proper algorithm.

the list of selected layers list of strings (1÷100 different layers), if needed performance reasons, converted other data types.

the shapes sorted according z-order.

basic intrusive solutions overlooked here in search of elaborate data structures , algorithms, fastest.

assuming have no choice keep selection separate, if want fast solution, store boolean selection flag in each layer (could single bit). when form selection, in addition forming list, set flags. deselecting layer not removes selection, sets selection flag false.

next, turn strings used indicate selected layers indices random-access structure (ex: std::vector or plain old array if size can determined @ compile time), (simplified):

struct layer {     string name;      // set true when layer selected, false      // when deselected. use atomics if thread safety      // required.     bool selected; }; 

... , turn shape.layer index (or pointer/iterator) layer. if have no choice start layer string identify layer shape belongs because given string inputs (ex: file loading), translate strings layer index/pointer/iterator creating shapes string inputs. use hash table or @ least std::set/map here (the string search on initial shape construction should logarithmic or better) convert layer strings layer indices/pointers/iterators.

if need layer selection list in addition layer selection state, can (pseudocode):

void select(layer layer, layerlist& layer_selection) {      if (!layer.selected)      {           layer.selected = true;           layer_selection.insert(&layer);      } }  void deselect(layer layer, layerlist& layer_selection) {      if (layer.selected)      {           layer.selected = false;           layer_selection.erase(&layer);      } } 

... layer selection stores indices/pointers/iterators layers. both select , deselect list insertion/removal can done in constant-time (even during worst-case) without hashing overhead , while preserving insertion order if fancy layer selection , use fixed allocator (this complex subject involving placement new, unions, , memory pools i'll delve if desired, omit time being brevity).

now main pseudocode code turns this:

void draw_if(list shapes, list layers) {    each shape in shapes    {       if (layers[shape.layer].selected)         shape.draw();    } } 

... or if use pointers/iterators:

void draw_if(list shapes, list layers) {    each shape in shapes    {       if (shape.layer->selected)         shape.draw();    } } 

it's hard beat in terms of performance optimal hash table cannot beat simple indexed array access memory still have access in addition hash. if can consolidate idea of "selected shapes" , form selected shapes in advance through process of selecting/deselecting layers, can this:

void draw_selected(list selected_shapes) {    each shape in selected_shapes        shape.draw(); } 

... faster provided cost of forming selected shapes list compensated reusing repeatedly before has change. note still want convert strings indices in case, because don't want "selected shapes" list have more simple array. form selected shapes list:

shapelist selected_shapes(shapelist all_shapes, layerlist layers) {      // forming in advance if reused      // numerous drawing frames before needs change (ex:      // before z-order changes, before new elements inserted      // or existing ones removed, before layer selection changes).      shapelist results;      each shape in all_shapes:           if layers[shape.layer].selected)              results.push_back(shape);      return results; } 

... still cheaper form , access (due spatial locality of compact shape selection array) hash table selection state store in layers.

this keeps cache-friendly , avoids expensive (relatively speaking) data structures hash tables except during initial string->index/pointer conversion part (which need when creating shape string input). in case, place ever needs kind of search (logarithmic or constant-time hash/trie) when convert shape layer strings user input indices/pointers/iterators. else o(1) (even worst-case complexity) , doesn't require hashing.