Is it possible to have a fixed size array as a unordered_map key

user_741711 0
Viewed 296

I am wondering if it is possible to have a std::unordered_map use a fixed size array as a key. For example, here is a simple cache that holds strings as the value but needs a uint8_t[] as the key:

using UserKeyV1 = uint8_t[16];
using UserKeyV2 = uint8_t[32];

template <typename T>
class StringCache
{
   public:
      bool addString(const T &userKey, const std::string &value)
      {
         auto [it, result] = m_cache.try_emplace(userKey, value);
         // ^^^^^^^ this line won't compile: array initializer must be an initializer list or string literal

      }
   private:
      struct EqualToFn {
        bool operator()(const T &left, const T &right) const {
            return std::memcmp(&left[0],
                               &right[0],
                               sizeof(T)) == 0;
        }
      };

      struct HashFn {
        size_t operator()(const T &k) const {
            return std::_Hash_impl::hash(k);
        }
      };

      std::unordered_map<T, std::string, HashFn, EqualToFn> cache_;
}

And in use would be something like:

StringCache<UserKey1> cache1;

uint8_t uniqueKey[16];  // this key was provided by 3rd party lib
cache1.addString(uniqueKey, strUsername)

This won't compile due to the error listed above but I'm not sure why. I created the custom hasher and equality functions for the array so that it knew how to handle such a key. I could probably solve this with std::array and copy the key to it first but wanted to avoid that if possible as it would involve a copy and this code will be potentially called 1000s of times a second.

Is what I am trying to achieve possible or do I just use std::array as a key?

c++
3 Answers

it works fine with std::array

  #include <cstdlib>                                                                 
  #include <iostream>                                                                
  #include <unordered_map>                                                           
  #include <cstring>                                                                 
  #include <array>                                                                   
                                                                                     
  using UserKeyV1 = std::array<unsigned char,16>;                                    
                                                                                     
  template <typename T>                                                              
  class StringCache                                                                  
  {                                                                                  
     public:                                                                         
        bool addString(const T &userKey, const std::string &value)                   
        {                                                                            
           auto [it, result] = m_cache.try_emplace(userKey, value);                  
           // ^^^^^^^ this line won't compile: array initializer must be an initializer list or string literal
           return result;                                                         
                                                                                  
        }                                                                         
     private:                                                                        
        struct EqualToFn {                                                           
          bool operator()(const T &left, const T &right) const {                     
              return std::memcmp(&left[0],                                           
                                 &right[0],                                          
                                 sizeof(T)) == 0;                                    
          }                                                                          
        };                                                                           
                                                                                     
        struct HashFn {                                                              
          size_t operator()(const T &k) const {                                      
              return std::_Hash_impl::hash(k);                                       
          }                                                                          
        };                                                                           
                                                                                     
        std::unordered_map<T, std::string, HashFn, EqualToFn> m_cache;               
  };                                                                                 
                                                                                     
  int main()                                                                         
  {                                                                                  
      StringCache<UserKeyV1> cache1;                                                 
                                                                                     
      //uint8_t uniqueKey[16];  // this key was provided by 3rd party lib            
      UserKeyV1 uniqueKey;                                                           
      std::string strUsername = "username";                                          
      cache1.addString(uniqueKey, strUsername);                                      
  }
user_34616170

I think if you want to avoid copy you can just use std::string_view class, the code becomes simpler.

  #include <unordered_map>                                                           
  #include <string_view>                                                             

  using UserKeyV1 = std::string_view;                                                
                                                                                     
  template <typename T>                                                              
  class StringCache                                                                  
  {                                                                                  
     public:                                                                         
        bool addString(const T &userKey, const std::string &value)                   
        {                                                                            
           auto [it, result] = m_cache.try_emplace(userKey, value);                  
           return result;                                                            
                                                                                     
        }                                                                            
                                                                        
        std::unordered_map<T, std::string> m_cache;                                  
  };                                                                                 
                                                                                     
  int main()                                                                         
  {                                                                                  
      StringCache<UserKeyV1> cache1;                                                 
                                                                                     
      uint8_t uniqueKey[16];  // this key was provided by 3rd party lib              
      std::string strUsername = "username";                                          
                                                                                     
                                                                                     
      cache1.addString(std::string_view{(const char*)uniqueKey, sizeof(uniqueKey)}, strUsername);
  }

for c++20 you can probably use std::span, or to implement your own wrapper for earlier standards.

user_34616170

I think the best way of doing this (without copying the value as you requested) would be to calculate an hash using the uint8_t[16] array and use the hash as key. You can choose one among the many hashing algorithms already existing (xxhash, md5, sha32, crc32 etc...). The best match with your case would be crc32.

Any of these usually takes a const void* and a size_t to calculate the memory hash, you can pass your key address and size without copying it as you requested.

An example would be to use crc32 hash (basically an uint32_t) and to use it as key for the unordered_map.

So you can still keep your class, by adding one line in your example.

StringCache<uint32_t> cache1;
uint8_t uniqueKey[16];
cache1.addString(GetArrayHash(uniqueKey), strUsername);

You can't use this solution if you need to get back the uint8_t[16] from your cache. Based on your class code you posted there are no uses of the actual key value.

Note: an unordered_map with uint32_t as key will use an identify function as hash algorithm, in short by using crc32 hashing you are probably not losing efficiency but this is not guaranteed by the standard since it does not define exactly which algorithm to use to hash an array of uint8_t (but the msvc and gcc implementations I have been able to test use crc32).

using this approach you can definitely remove your HashFn and EqualToFn to your StringCache class.

template <typename T>
class StringCache
{
   public:
      bool addString(const T &userKey, const std::string &value)
      {
         auto [it, result] = m_cache.try_emplace(userKey, value);
      }
   private:
      std::unordered_map<T, std::string> cache_;
}
user_146283040
Related