1

I am assigned to implement a core database for a game.

It is a 1:N map of int X <--> int Y. (e.g. pirateship<->its turrets)
I know for sure that 0<=X<=1000 and 0<=Y<=10000.
Most indices are used/occupied i.e. dense.

A certain X can be mapped to many Ys.
A certain Y can be mapped to 0-1 X.

I dream for a datastructure that :-

  • allocate memory very infrequently
  • query X->Y (return Array<int>) and Y->X (return int) very fast
  • For iterating, I don't mind iterating 0-10000 of value of Y.

Question:

  • How should I implement it?
  • Is there std library that fit my need?
  • Does this datastructure have its own name?

My poor solutions

  1. std::unordered_multimap<int,int> (probably red-black tree) or std::unordered_map<int, std::vector<int>> (Edit: Thank Some programmer dude)

    • it is slow (profiled) :(
    • not cache friendly
    • not fully utilize the index

  2. std::vector<int, std::vector<int>> - my current approach

    • the value (std::vector<int>) require a lot of dynamic allocation
    • potential cache miss and fragmentation
      e.g. vector to store X=0 -> Y=? would be far away from vector to store X=1 -> Y=?

Are there any better approaches?

Sorry if it is a common question,
I couldn't find any that exactly matches this one.

cppBeginner
  • 1,114
  • 9
  • 27
  • Regarding `multimap` and `map`, you know that those are ordered? Have you tried the hashed [`unordered_multimap`](http://en.cppreference.com/w/cpp/container/unordered_multimap) or [`unordered_map`](http://en.cppreference.com/w/cpp/container/unordered_map)? – Some programmer dude Aug 08 '17 at 05:41
  • @Some programmer dude oh yes, sorry, I mistyped, I will edit the question. I mean `unordered_...` – cppBeginner Aug 08 '17 at 05:41
  • 2
    Also, first of all you should concentrate on making something that works, is readable and most importantly *maintainable*. And after profiling and measuring, is it "good enough"? In most cases "good enough" really *is* good enough. Remember that any kind of optimization will lead to code that is harder to read, understand and maintain without proper documentation. Furthermore using non-standard data-structures means you can lose many of the functions available to you in the standard library, which mean you have to implement them yourself leading to code-bloat and more bugs. – Some programmer dude Aug 08 '17 at 05:44
  • 1
    Okay, but then remember that the unordered maps are *hashed* not trees. – Some programmer dude Aug 08 '17 at 05:48
  • @Some programmer dude I totally agree. I will get some bugs. It has lived in a low-priority TODO list for a half year. It is used in various part in the codebase (more incentive to optimize). I would like to know, probably mainly for educational purpose, whether there is any well known solution for it. If not, I will close this wished-feature. Thank. :) – cppBeginner Aug 08 '17 at 05:50

1 Answers1

2

How about this?

typedef vector< int > Turrets;

struct PirateShip
{
    int ship;
    Turrets turrets;
};

typedef vector< PirateShip > Ships;

Ships pirates;

Done that way, each ship has 0 to N turrets.

You can put from 0 to ships inside a container.

You can change the container just by changing the typedef.

typedef set< PirateShip > Ships;

or

typedef list< PirateShip > Ships;

or

typedef deque< PirateShip > Ships;

You get the idea. :-)

RichS
  • 540
  • 1
  • 6
  • 12
  • still suffer cache-miss : `std::vector turrets` tends to allocate every far away address for different instance of `PirateShip`. – cppBeginner Aug 08 '17 at 05:52
  • @cppBeginner You can override the allocator template parameter in any STL container so that the container's memory handler allocates where you want it to. You can write an allocator that uses the same memory for Turrets container as it does for Ships container. – RichS Aug 08 '17 at 05:53
  • I understand, but what type of custom allocators should I use? heap? one-frame? stack? I am blind at this point. More example/link (for allocator?) would be really useful. – cppBeginner Aug 08 '17 at 05:55
  • 1
    @cppBeginner Not sure which CPU your code will run on, but if it runs on Intel chips, set the memory block size for your allocators to be 32K or 256K since the L1 and L2 caches on those chips are those sizes. – RichS Aug 08 '17 at 05:55
  • @cppBeginner What kind of memory handler you use depends on how often your program will allocate and release these objects. Knowing what kind of memory handler to use is a very complex topic. – RichS Aug 08 '17 at 05:57
  • Thank, I will investigate about allocator further. – cppBeginner Aug 08 '17 at 07:32