Tangent: cases like these make me think we're often working on too low level of abstraction, reimplementing relational databases poorly without realizing it.
Like, if you're thinking, "Hey, I need a key-value map so I can efficiently look up Bars given some Foos", then this isn't equivalent to "I need std::map<Foo,Bar>" - it's closer much closer to "I need a table with Foos and Bars, where Foo is a key, and I need an index on it". Now that may translate to more than one object - e.g. like two arrays, one with Foos, other with pointers to Bars. That achieves the intended data locality.
Now, imagine a new requirement, "I also want to efficiently look up Foos corresponding to a given Bar". Should you add another array to support reverse mapping? Well, in database terms, you've said, "I also need an index on Bar". So yes, add one. And add standard boilerplate to keeping all the arrays in sync.
It feels tedious and arbitrary, and people may call it "premature optimization", but the problem really is that we don't have those basic database concepts built into languages. "I need to map Foos to Bars, primarily for efficient lookup, but also for efficient back-referencing" is a lot of work, we're tempted to skip the efficiency bits to keep the code simple; however all that just translates to something like `auto m_bars = Table<Foo, Bar> index(Foo) index(Bar)`; if we could express that directly, we'd skip the boilerplate and compilers could give us very efficient implementations (and we couldn't accidentally break pieces of them out of sync).
I encourage everyone to try and look out for this pattern. I find it shows up frequently, especially in more complex cases, possibly across object boundaries. I first realized this when I was making a roguelike game with Entity Component System, and realized I need fast lookup of entities based on X/Y coordinates in the game world. I started adding some data structures to support that, and then it hit me - I'm just adding a spatial index to the entity list; this isn't complex idea, it's an atomic concept - if you think in database terms, instead of usual programming terms.