Based on C++ map key using pointer problem

  • 2020-04-01 23:36:18
  • OfStack

Map is often used in the actual development of C++. Map is a key-value value pair, key is unique, can be used to find quickly. Its time complexity is O(logN), if the for loop is used to traverse the data, the time complexity is O(N). If the amount of data in the map is relatively small, the efficiency of loop traversal using find and for is basically the same. However, in the actual development process, the data stored in the map is often large, and the efficiency of map using find is much higher than that of traversal.

Once we decide to use find to find the data, we need to consider the spatial complexity of storing the map, which we won't discuss here for data of the underlying data type (int char, etc.). This article discusses the case of a data structure struct stored in a map.
1. If the key in the map is struct, the struct needs to be overloaded as an operator. For this part, please refer to the example of C++ overloaded operators
2. The key in the map can only be an object, not a pointer. This is especially important.

The following three map definitions are given to illustrate:

STD: : map < NHSymbolkey, Stru_NHSymbol > *     pmapNHSymbolInfo1
STD: : map < NHSymbolkey Stru_NHSymbol * > *   pmapNHSymbolInfo2
STD: : map < Stru_NHSymbol NHSymbolkey *, * > *   pmapNHSymbolInfo2

Among them, pmapNHSymbolInfo1, pmapNHSymbolInfo2 USES find normally, the traversal is also normal, pmapNHSymbolInfo3 USES find to find the corresponding data (the data already exists, can not find, traversal can find)

The reason: STD: : map < Stru_NHSymbol NHSymbolkey *, * > *   PmapNHSymbolInfo2 looks up by pointer when it finds. On the other hand, when data is inserted, the data is all new, each new out of the address is not the same, in the find data, according to the address search results can not find the data. The data can be found by iterating through the contents of the address and comparing them one by one.

PmapNHSymbolInfo1, pmapNHSymbolInfo2 two ways can use find method to find data, but pmapNHSymbolInfo1 in the Stru_NHSymbol as an object, this will make the map occupies a large space, pmapNHSymbolInfo2's Stru_NHSymbol as a pointer, storage address occupies a small space, but every time is new processing, all must remember to use must delete, or memory leak.

3. Comparison of methods in map insertion data 2  
STD: : map < NHSymbolkey Stru_NHSymbol * > *   pmapNHSymbolInfo
PmapNHSymbolInfo - > Insert (STD: : make_pair (pNHSymbolkey pNHSymbol)); If the key of this mode is repeated, data insertion will fail.

(* pmapNHSymbolInfo) [objNHSymbolkey] = pNHSymbol; If the key of this method is repeated, the original data will be overwritten directly, and the insertion failure will never occur.
Conclusion: do not use Pointers for key in C++ map. Use objects directly.


Related articles: