ADC implicitly adds empty entries to all_drawn_copies

[jruderman]

Autoplay in Dry Forest spends a lot of time in drawFlashes, and part of the reason is the way ADC accesses all_drawn_copies.

Current code

#define ADC(V,c) for(const shiftmatrix& V: current_display->all_drawn_copies[c])

When all_drawn_copies lacks an entry for c, this implicitly creates an entry with an empty vector and inserts it into the map.

Possible solution 1: check map::count first

#define ADC(V,c) if (current_display->all_drawn_copies.count(c)) for(const shiftmatrix& V: current_display->all_drawn_copies[c])

This has the disadvantage of searching the map twice: once for count (or contains), once for [] (or at). Still, it seems faster overall.

Possible solution 2: create an outer loop using map::find

#define ADC_helper(V,c,adc) for(auto it = adc.find(c); it != adc.end(); it = adc.end()) for(const shiftmatrix& V: it->second)
#define ADC(V,c) ADC_helper(V, c, current_display->all_drawn_copies)

This only searches the map once, and avoids modifying the map, but there's a lot about map iterators that I don't understand.

• Does this make it contain its own copy of the vector<shiftmatrix>? If so, maybe const auto &it could avoid copying, but that made Clang balk at it = adc.end().
• Does adc.end() contain or point to a fake element with an empty vector? If so, where do these come from?

[zenorogue]

Used Solution 2, but I feel that the suggested ADC_helper did not factor the useful part -- so added a macro which is useful in other places, and also found a cleaner implementation:

/** `IF_KEY_EXISTS(it, map, key) statement` checks whether the map 'map' contain key 'key', and if so, executes statement with it set to the relevant iterator */
#define IF_KEY_EXISTS(it, map, key) for(auto it: {map.find(key)}) if(it != map.end())

and now ADC is:

#define ADC(V,c) IF_KEY_EXISTS(it, current_display->all_drawn_copies, c) for(const shiftmatrix& V: it->second)

(with C++17 it would be nicer: if(auto it=map.find(key); it != map.end()) but the Steam compiler is still stuck at C++11)

[Quuxplusone]

@jruderman asks:

Does this make it contain its own copy of the vector<shiftmatrix>?

No. In auto it = map.find(k), it is an iterator, which is the same idea as a pointer. it points to a map element; that element is the actual, identical std::pair<cell* const, std::vector<shiftmatrix>> whose lifetime is managed by the map. Altering *it (e.g. by appending to (*it).second) alters the actual element in the map.

If so, maybe const auto &it could avoid copying, but that made Clang balk at it = adc.end().

Right, because if it is a reference to a const (iterator, or in fact const anything), then it's not permitted to assign a new value to the (iterator, or anything), because it's const.

Does adc.end() contain or point to a fake element with an empty vector? If so, where do these come from?

No, it doesn't. adc.end() doesn't point at any element; dereferencing it to get at "the element to which it points" is not permitted (it'd be undefined behavior at runtime). In physical reality, adc.end() often points at a sort of truncated stub node (with only "prev" and "next" pointers, but no std::pair payload) that lives inside the memory footprint of the std::map object itself. It needs that "prev" pointer because you're allowed to do it = adc.end(); --it; to get at the last element of the map.