The previous implementation was, what is best described as a flat-graph, linked lists over vector(s), using indexes for linking up the various components.
Okay, that's not actually the same as what we're talking about here- I'm talking about comparing a vector of pointers/indexes where you directly iterate over the pointers, vs an intrusive list. You're talking about, as far as I can tell, using a vector of nodes with pointers to the elements to iterate. That's always going to be slower compared to an intrusive list because you're wastin space and creating an additional indirection. By contrast a vector of pointers/indexes will be faster to iterate due to the CPU being able to cache the jump locations/offsets, whereas it can't with a linked list of any type. That's what my graphs show.