Safe way to use string_view as key in unordered map

Question

My type Val contains std::string thekey.

struct Val
{
std::string thekey;
float somedata;
}

I would like put my type in an unordered map, with thekey as key. For memory and conversion avoidance reasons I would like to have std::string_view as key type. Is it possible to have the key created to point to val.thekey, while using unique_ptr ?

std::unique_ptr<Val> valptr = ...;
std::unordered_map<std::string_view,std::unique_ptr<Val>> themap;
themap[std::string_view(valptr->thekey)] = std::move(valptr); // is this ok and safe?

This seems like it's unneeded. If you use an `unordered_set`, you can create your own hasher and comparator that just uses `thekey` and then you save the cost of having a `string_view`. — NathanOliver, Oct 22 '21 at 14:50
`themap[std::string_view(valptr->thekey)] = std::move(valptr);` would not be safe if the key is already in the map (the old std::string_view would remain while the old Val gets destructed), apart from that it should be safe if you're very careful - [see other question](https://stackoverflow.com/a/51751115/8411406) — Turtlefight, Oct 22 '21 at 14:51
[Demo](https://godbolt.org/z/9oG1ozbdc) to thing described by @Turtlefight — Marek R, Oct 22 '21 at 14:58
@NathanOliver That would solve the memory part, nice. The second part: I am concerned themap.find(aStringView) would be slow due to the required type conversion of input key. In my case the key I am searching with is string_view. — John, Oct 22 '21 at 15:04
@Johan No conversion is needed. Since C++14, the hasher and comparator are allowed to be "transparent" and have overloads to treat other types as the same type as the key: https://stackoverflow.com/questions/20317413/what-are-transparent-comparators — NathanOliver, Oct 22 '21 at 16:01
@nathan you sure about the unordered containers? I thought that was 20 not 14. — Yakk - Adam Nevraumont, Oct 22 '21 at 17:55
@Yakk-AdamNevraumont Woops. Yep, that was C++20 for the unordered containers. I would have though that was added for all of them in C++14, but I guess not. — NathanOliver, Oct 22 '21 at 19:11

Useless · Accepted Answer · 2021-10-26T11:08:35.287

Safe way to use string_view as key in unordered map

In general there isn't one, because the storage underlying the view might change at any time, invalidating your map invariants.

Associative containers generally own a const key precisely to avoid this.

In your specific case it makes much more sense to use std::unordered_set<Val, ValKeyHash, ValKeyEqual> with suitable hash and equality functors.

Edit, these suitable functors are simply

struct ValKeyHash {
    std::size_t operator() (Val const &v)
    {
        return std::hash<std::string>{}(v.thekey);
    }
};

struct ValKeyEqual {
    bool operator() (Val const& a, Val const& b)
    {
        return a.thekey == b.thekey;
    }
};

Obviously this leaves us with the slightly unhappy requirement of using a temporary Val{key, dummy_data} for lookups, at least until we can use the C++20 transparent/projected version in the other answer.

If this answer would would show suitable functors or point in the right direction for learning about it, then I can mark it as accepted. — John, Oct 26 '21 at 07:11

score 3 · Answer 2 · answered Oct 22 '21 at 20:21

In c++20, you should do this

namespace utils {
  // adl hash function:
  template<class T>
  auto hash( T const& t )
  ->decltype( std::hash<T>{}(t) )
  { return std::hash<T>{}(t); }

  // Projected hasher:
  template<class Proj>
  struct ProjHash {
    template<class T>
    constexpr std::size_t operator()(T const& t)const {
      return hash(Proj{}(t));
    }
    using is_transparent=std::true_type;
  };

  // Projected equality:
  template<class Proj>
  struct ProjEquals {
    template<class T, class U>
    constexpr std::size_t operator()(T const& t, U const& u)const {
      return std::equal_to<>{}( Proj{}(t), Proj{}(u) );
    }
    using is_transparent=std::true_type;
  };
}

// A projection from Val to a string view, or a string view
// to a string view:
struct KeyProj {
  std::string_view operator()(Val const& val) const { return val.thekey; }
  std::string_view operator()(std::string_view sv) const { return sv; }
};

std::unordered_set<Val, ProjHash<KeyProj>, ProjEquals<KeyProj>> theset;

now you can

theset.find("hello")

to find the element of the set whose key is "hello".

A map is fundamentally wrong here, because the features that a map has that the above set does not don't do the right things. Like mymap["hello"], which goes and creates a Val if it isn't found; we now have a dangling string view in the container.

An intrusive map in std is a set with a projection, not a map with a reference into the value as a key.

Safe way to use string_view as key in unordered map

2 Answers2

Linked