c++ - How to efficiently store equivalences (from Connected-component labeling algorithm)? -

c++ - How to efficiently store equivalences (from Connected-component labeling algorithm)? -

i store equivalences connected-component labeling algorithm. it's making kind of map 1 value (one label's id) multiple values (ids labels equivalent former.)

i have done not work well:

std::map<unsigned short, std::list<unsigned int>> equivalences; for(int = 0; < max_number_of_labels; ++i ) { std::list<unsigned int> temp; temp.push_back(i); // note label equivalent equivalences.insert( std::pair< int, std::list<unsigned int>>(i, temp) ); }

then add together proper equivalence by:

equivalences.at( ).push_back( equivalent_labels_int );

the main drawback of method have declare map's size front end (it has big enough) , big sizes (e.g. 9999) initialization time approximately 2.5s.

anyone have improve idea?

you not need size map up-front in c++ (or languages, matter). maps can dynamically grow having new elements added them, if find new key, can add together map. example:

equivalences[i].push_back(equivalent_labels_int);

this works because map's square brackets operator (operator[]) automatically add together new key/value pair map given key , default value if 1 doesn't exist.

additionally, advise not using list container storing sequence of connected blobs. list when don't need random access , removing elements in middle of sequence, don't think you're doing here. instead, suggest using vector or deque, since structures more space efficient , have improve locality.

finally, depending on particular needs, may want switch info structures entirely. if algorithm works running depth-first search out starting point , storing of results encounters, approach have may quite good. however, if instead algorithm works finding pairs of points similar , merging blobs contain, may interested in disjoint-set forest info structure, has simple implementation extremely performance. said, using construction loses ability check points connected given point, boost in efficiency pretty remarkable.

hope helps!

c++ performance algorithm data-structures