Std :: map get value - find vs handcrafted loop

Question

I have a std :: map map<string , Property*> _propertyMap , where string is the name of the property and Property* contains the values ​​of the properties.

I need to process the values ​​of the properties and convert them to a specific data format - each property has its own format, for example, if the initialization of the map is as follows:

 _propertyMap["id"] = new Property(Property::UUID, "12345678"); _propertyMap["name"] = new Property(Property::STRING, "name"); .... 

then "id" should be handled differently than "name" , etc.

This means that I need to search for each property on the map and process its values ​​accordingly.

I thought of two ways of doing this.

One, use the std::map::find method to get a specific property, for example:

 map<string , Property*>::iterator it1 = _propertyMap.find("id"); if(it1 != _propertyMap.end()) { //element found - process id values } map<string , Property*>::iterator it2 = _propertyMap.find("name"); if(it2 != _propertyMap.end()) { //element found - process name values } .... 

Two, iterate over the map and for each record check what the name of the property is and do it accordingly:

 for (it = _propertyMap.begin(); it != _propertyMap.end(); ++it ) { //if it is events - append the values to the matching nodes if (it->first == "id") { //process id values } else if (it->first == "name") { //process name values } ..... } 

Given that the time complexity std :: map :: find is O (logN) , the complexity of the first solution is O(NlogN) . I'm not sure about the complexity of the second solution, because it iterates over the map once ( O(N) ), but it does a lot of if-else each iteration. I tried to spread general map::find() google questions, but could not find any useful information; most of them just have to get one value from the map, and then find() does it with better complexity ( O(logN) vs O(N) ).

What is the best approach? or maybe there is another one that I have not thought about?

In addition, the styling code says, which one is better and more understandable code?

Answer 1

Here I see several different use cases, depending on what you mean:

Fixed properties

(Just for completeness, I think this is not what you want). If the name and type of possible properties need to be fixed, the best version is to use a simple class / structure, possibly using boost::optional ( std::optional with C ++ 17) for values ​​that may or may not be present

 struct Data{ int id = 0; std::string name = ""; boost::optional<int> whatever = boost::none; } 

Pros:

• All "search queries" are allowed at compile time.

Minuses:

• Lack of flexibility to expand at runtime

Processing only certain options depending on their key

If you want to handle only a specific subset of options, but keep the option to have (unprocessed) custom keys, your approaches look appropriate.

In this case, remember that using find:

 it1 = _propertyMap.find("id"); 

has complexity O (logN), but it is used M times, and M is the number of processed options. This is not the size of your map, this is the number of times you use find() to get a specific property. In your (shortened) example, this means O (2 * logN) complexity, since you are only looking for 2 keys.

So basically using M-times find() scales better than a loop when only the map size increases, but worse if you increase the number of finds in the same way. But only profiling can tell you which one is faster for your size and use.

Process all parameters depending on type

Since your map is very similar to keys, they can be customizable, but types are from a small subset, consider looping around the map and use types instead of names to determine how to handle them. Something like that:

 for (it = _propertyMap.begin(); it != _propertyMap.end(); ++it ) { if (it->first.type() == Property::UUID) { //process UUID values } else if (it->first.type() == Property::STRING) { //process STRING values } ..... } 

This has the advantage that you do not need any information about which keys of your card really are, only the types that they can store.

Answer 2

Suppose that we have a mapping of properties N, and we are looking for a subset of properties P. Here is a rough analysis, not knowing the statistical distribution of keys:

• In the clean map approach, you search P times with complexity O (log (n)), i.e. O (p * log (n))

• Chained-if you're going to cross the map. This is O (N). But you must not forget that the if-then chain is also a (hidden) traversal of the list of elements of P. Therefore, for each of the elements of N, you search potentially up to P elements. So you have O (p * n) complexity here.

This means that the map approach will exceed your bypass, and the performance gap will widen significantly with n. Of course, this does not take into account the service overhead on the card, which you do not have in the if-chain. Thus, if P and N are small, your approach can still be compared to a theoretical comparison.

Ultimately, you could increase performance to use unordered_map , which is equal to O (1) in complexity, reducing the complexity of the problem to O (P).

Answer 3

There is another option that combines the best of both. For such a function (which is an adaptation of std::set_intersection ):

 template<class InputIt1, class InputIt2, class Function, class Compare> void match(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, Function f, Compare comp) { while (first1 != last1 && first2 != last2) { if (comp(*first1,*first2)) { ++first1; } else { if (!comp(*first2,*first1)) { f(*first1++,*first2); } ++first2; } } } 

You can use it to process all your properties in O (N + M) time. Here is an example:

 #include <map> #include <string> #include <functional> #include <cassert> using std::map; using std::string; using std::function; struct Property { enum Type { UUID, STRING }; Type type; string value; }; int main() { map<string,Property> properties; map<string,function<void(Property&)>> processors; properties["id"] = Property{Property::UUID,"12345678"}; properties["name"] = Property{Property::STRING,"name"}; bool id_found = false; bool name_found = false; processors["id"] = [&](Property&){ id_found = true; }; processors["name"] = [&](Property&){ name_found = true; }; match( properties.begin(),properties.end(), processors.begin(),processors.end(), [](auto &a,auto &b){ b.second(a.second); }, [](auto &a,auto &b) { return a.first < b.first; } ); assert(id_found && name_found); } 

Card processors can be built separately and reused to reduce overhead.