Alternatives for index arrays

Question

I work on a C++ project where I am not really happy with the data structures. The question isn't that specific to C++, I think that I would face a similar issue in say Java or Python.

There are data structures that have no direct relation in the code, although they have a 1-to-N relationship.

struct Element {
    int index;
    T payload;
};

struct Group {
    int index;
    T payload;
}

The instances are held in linear containers.

std::vector<Element> elements;
std::vector<Group> groups;

And then there is an index structure that relates them

std::vector<int> group_index_by_element_index;

In the code one sees patterns like that for access:

groups[group_index_by_element_index[element.index]]

This doesn't feel right, but I cannot put my finger on it. So I here are some alternatives that I came up with.

• Alternative 1: I thought that one could instead change the element structure such that it contains a pointer to the group.

  struct Element {
      int index;
      T payload;
      Group *group;
  };
  

  Then one can just do element.group and has the associated group. The downside is that if the groups vector should ever be reallocated (resize, push_back), all the pointers would become invalid. In this particular case we can give an upper limit and just allocate enough memory right at the start.

• Alternative 2: An alternative to pointers would be to use

  struct Element {
      int index;
      T payload;
      int group_index;
  };
  

  and access via groups[element.group_index].

• Alternative 3: A different way to model the 1-to-N relationship would be to have

  struct Element {
      int index;
      T payload;
      Group *group;
  };
  
  struct Group {
      int index;
      T payload;
      std::vector<Element> elements;
  }
  

  and no global elements vector any more. Elements would have a pointer to their owning group, and there are no lifetime problems.

  This approach makes it harder to view all the elements at the same time, there is no single container with all of them. One would always have to loop over the groups and then loop over the contained elements.

  It doesn't work if there is another 1-to-N relationship where the elements have different associations as with the groups. If the elements would be handles in batches, but each batch is mixed through the groups, I would either define the batch structure as holding Element * (dangerous with reallocation) or would store tuples of group and element indices. With the original approach, I could just add an index vector batch_index_by_element_index and would have it.

I see that the alternatives would give more concise code compared to the current version. Still I want to understand the motivations for the current state of the code. The independent index vectors make it easy to create new relationships between the various objects in the code. Also the index vectors don't necessarily have to have to same scope as the element vector, allowing for local and fine grained relationships. Deeply nested data structures also seem to become a burden at some point, so having it flat appears easier, for some stage at least.

Are there certain patterns that I could look into to better understand which data structure would be good for the codebase at hand?

Answer 1

This doesn't feel right, but I cannot put my finger on it. So I here are some alternatives that I came up with.

It's certainly not the most obvious way of doing it. Your 3 alternatives (or just a multimap) perhaps express the relationship more clearly.

However, note that all your changes make the Element objects larger and/or non-contiguous. The code presented looks like it has been optimized specifically for element size and memory layout.

If you're not sure why this would have been done, look for benchmark tests. It's not sufficient to understand the logical relationships between your data, you also need to understand the access patterns, non-functional requirements and hardware behaviour (in this case, specifically the cache and prefetcher).