No announcement yet.

TArray<> vs TMap<> lookup speed.

  • Filter
  • Time
  • Show
Clear All
new posts

    TArray<> vs TMap<> lookup speed.

    Scenario is simple.

    I have static list of items, created in editor.
    Items are searched by their name (FName).

    At runtime this list never changes, order is not important (so it can be sorted, prior using).

    What I need is to do with this list is have quick random access to it's elements, by using ItemName (FName).

    List can have potentially hunderds of entires, and will be queried often by various game systems (UI, item looting, item equiping, etc).

    I started implementing it using TMap, but I wonder if I'm not over thinking the problem, and TArray can be used just as well, with some custom code for searching ? - Action RPG Starter kit. Work in Progress. You can use it in whatever way you wish.

    I'd suggest using std::unordered_map, which uses a hash function for fast lookup. You'll have to define the hash<FName> template for it to work. This should be easy since FName is simply an index into a unique table so you can use that.
    Last edited by jCoder; 08-06-2014, 08:32 AM. Reason: Remvoed wrong info on TMap



      According to Steve Robb comment in this thread, TMap is hashed and is equivelant to std::unordered_map.

      Would nice to get some clarification, from person who actually implemented TMap in first place.

      Because right now, I have no idea. - Action RPG Starter kit. Work in Progress. You can use it in whatever way you wish.


        If an developer from Epic says it's hashed, then I'd go with his view over mine, since I only took a brief look at the code and TMap is more complicated then I thought.


          TMap<> is a hashed key/value pair. TArray<> is a contiguous block of memory holding T items and accessed by Index. If the number of items is large and your key hashes well, then a TMap will be faster than a linear search through a TArray. If N is small, then a linear search can be faster depending on the size of T and the size of a cache line