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 thegroups
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 vectorbatch_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?
fmap
/flat_map
/SelectMany
to hand, so that you canfmap(groups, &Group::element)
in option 3?std::vector
, then they can also use astd::map
orstd::unordered_map
in C++. But when the map key is just an integer in the range from 0 to N, one can use a vector as well, that is usually more efficient in terms of space and running time. So what you suggest does not address the problems described in this question.vector<int>
hasglobal_index
as values andelement_index
as keys. It basically is a map where the keys happen to be consecutive integers.