2

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?

9
  • 1
    Not sure. What exactly are the needs of the "codebase at hand"? – candied_orange Feb 2 at 10:58
  • 1
    Do you have a fmap / flat_map / SelectMany to hand, so that you can fmap(groups, &Group::element) in option 3? – Caleth Feb 2 at 11:54
  • It seems you already understood the pros and cons of the different approaches. You said you want to "understand the motivations for the current state of the code", but then provide some possible motivations in the very next two sentences - so I don't see how we can really tell you something you do not know already. – Doc Brown Feb 2 at 14:13
  • 2
    @FrustratedWithFormsDesigner: when someone can use a std::vector, then they can also use a std::map or std::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. – Doc Brown Feb 2 at 19:55
  • 1
    @Neil: It is supposed to mean that that this vector<int> has global_index as values and element_index as keys. It basically is a map where the keys happen to be consecutive integers. – Martin Ueding Feb 4 at 10:32
6

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).

2
  • Yes, the code is a high performance one, albeit these structures are likely not critical. The whole setup looks a bit like an structure-of-array (SoA) thing. — If the only advantage of the current setup is performance, then it pretty clearly sounds like a harder to maintain pattern and shouldn't be used outside of the critical regions. – Martin Ueding Feb 4 at 10:34
  • Note that if you change it to exert more pressure on the cache, that affects the whole program including critical regions. The cache is shared by the whole processor, so effects are not localized to the code you change. – Useless Feb 4 at 10:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.