How to avoid excessive for loops in C++ [closed]

Question

I have been trying to write a small test program and I was trying to think of any potential optimization I could do, especially if there is any chance to avoid some of the for loops.

The program has Dad class, a Child class and a DadChild class that holds the IDs of the Dad and Child objects that are associated based on their DNA.

The requirements are:

1. A Dad object can be associated with multiple Child objects
2. A Child object can NOT be associated with more than 1 Dad objects
3. Out of all Child objects that are associated with the a Dad object, only one has to be marked as bestMatch.

Here is the sample code that I drafted, it works as expected, but I wondering if there is any space for optimizations.

#include<iostream>
#include<vector>
#include<map>
#include <algorithm>
#include <memory>


class Dad
{
public:
    Dad(int a_id, int a_dna): id(a_id), DNA(a_dna) {}

    int id;
    int DNA;
};

class Child
{
public:
    Child(int a_id, int a_dna): id(a_id), DNA(a_dna) {}

    int id;
    int DNA;
};

class DadChild
{
public:
    DadChild(): dnaResult(-1) {}
    DadChild(bool a_bestMatch, int a_childID, int a_dadID, double a_dnaResult):
        bestMatch(a_bestMatch),
        childID(a_childID),
        dadID(a_dadID),
        dnaResult(a_dnaResult) {}

    int dadID;
    int childID;
    double dnaResult;
    bool bestMatch;
};

double compareDNA (int a, int b) {
    return abs(a - b); // 0 indicates a perfect match
}

DadChild createDadChild(Dad d) {
    //Do something for single parents. Not really that important here.
    return DadChild();
}

DadChild createDadChild(Dad d, Child c, double dnaTest) {
    //Construct and return DadChild Object
    DadChild dc;
    dc.bestMatch = false;
    dc.childID = c.id;
    dc.dadID = d.id;
    dc.dnaResult = dnaTest;

    return dc;
}

int main() {

    Dad d1 (1, 1);
    Dad d2 (2, 4);

    Child c0 (0, 4);
    Child c1 (1, 2);
    Child c2 (2, 3);
    Child c3 (3, 1);

    std::vector<Dad> dads;
    std::vector<Child> children;


    dads.push_back(d1);
    dads.push_back(d2);

    children.push_back(c0);
    children.push_back(c1);
    children.push_back(c2);
    children.push_back(c3);

    std::map <int, DadChild> assocMap; // Where the the key is the childID
    std::vector <DadChild> singleDadVector;

    for (auto &dad : dads) {
        bool singleParent = true;
        for (auto &child : children) {
            double dnaTest = compareDNA(dad.DNA, child.DNA);
            if (dnaTest < 2) { // 2 here is an arbitrary threshold for the dna result
                singleParent = false;
                auto search = assocMap.find(child.id);
                if (search != assocMap.end()) {
                    if (assocMap[child.id].dnaResult > dnaTest) {
                        assocMap[child.id] = createDadChild(dad, child, dnaTest);
                    }
                }
                else {
                    assocMap[child.id] = createDadChild(dad, child, dnaTest);
                }
            }
        }
        if (singleParent)
            singleDadVector.push_back(createDadChild(dad));
    }


    // Try to find the bestMatch.
    // I am wondering if there is a better way to do this.
    for (auto const &dad : dads) {
        DadChild dc;
        DadChild *bestDadChild = &dc;
        for (auto &assoc: assocMap) {
            if ((dad.id == assoc.second.dadID) && (bestDadChild->dnaResult == -1)) {
                bestDadChild = &assoc.second;
            } else if ((dad.id == assoc.second.dadID) && assoc.second.dnaResult < bestDadChild->dnaResult) {
                bestDadChild = &assoc.second;
            }
        }
        bestDadChild->bestMatch = true;
    }

    /*
    // I tried to do something like this, but it didn't really work.
    for (auto &dad : dads) {
        auto pr = std::min_element(
            std::begin(assocMap), std::end(assocMap),
            [dad] (const auto &p1, const auto &p2) {
                return ((dad.id == p1.second.dadID) && (dad.id == p2.second.dadID) && (p1.second.dnaResult < p2.second.dnaResult));
            });
        pr->second.bestMatch = true;
        std::cout << dad.id << std::endl;
        std::cout << "Setting: " << pr->second.dadID << std::endl;
    }*/

    for (auto &a : assocMap) {
        std::cout << "DadID: " << a.second.dadID << std::endl;
        std::cout << "ChildID: " << a.second.childID << std::endl;
        std::cout << "bestMatch: " << a.second.bestMatch << std::endl;
        std::cout << "dnaResult: " << a.second.dnaResult << std::endl;
        std::cout << "--------------" << std::endl;
    }

}

Output:

DadID: 2
ChildID: 0
bestMatch: 1
dnaResult: 0
--------------
DadID: 1
ChildID: 1
bestMatch: 0
dnaResult: 1
--------------
DadID: 2
ChildID: 2
bestMatch: 0
dnaResult: 1
--------------
DadID: 1
ChildID: 3
bestMatch: 1
dnaResult: 0
--------------

Answer 1

Documentation

Add documentation.

I had no idea what the goal of this program is, going in, and at the end of the review I still don't, so I can't comment on whether the code is correct or efficient.

• Do we want to output the most likely child for a father? The most likely father for a child?
• What does "singleParent" mean? Often in this context it would mean that one person is raising a child?
• Are higher DNA test results closer matches, or farther?
• What is 'bestMatch'? Is this an ID? And ID of a child or a dad? A DNA test result? What does it mean?

Style

Based on the names, something around paternity testing, but that's it. Is the goal to output the most likely dad for each child? The most likely child for each dad? The paternity test results for every input?

• DadChild is a bad class name. I have no idea what it does without reading your documentation.
• assocMap is a bad name, because it doesn't say what it maps between.
• Replace your entire inner dad loop with std::max. Also, bestDadChild should not be initialized to a bogus object. Use std::optional or a null pointer.

Initialization

• Remove the DadChild empty constructor--the code you have to initialize DadChild is bad and it's because you're not using a single constructor call.
• Replace both versions of createDadChild by constructors.
• Initialize your hardcoded std::vector in one statement

Loops

As far as loops go, the three top-level loops look fine. Don't worry about it. You can unify them but I would say that makes things less readable, and no faster.

If you are worried about the inner loops being slow, you're correct. I don't understand what you're trying to do well enough to know if you're doing it or if there's a better way. Sorry.

Answer 2

General points

• Why does compareDNA return a double when the inputs are both ints and the output thus can only ever be an int.

• The same function compareDNA seams out of place. This can be a method of a person. In rewrite see Person.compareDNA

• Avoid magic numbers. Use a constant to give number (strings, whatever) meaning. eg const int MAX_DNA_DISTANCE{2};

• Break the code into smaller functions. Having long functions doing multiple tasks makes the code hard to read and maintain. Eg your main function

Object design

Dad and Child are identical, so why create two independent classes. Both Dad and Child are people so create a class that holds a Person.

The vectors dads and children define who is who

There is a one to many link from parent to child.

Move the relationship map (map of parent's children by id) to the parent object

Rather than using the awkward DadChild object create an object called Relative that is derived from a Person. Have it hold all related children as a vector or map

See rewrite.

Unique identifiers

Always ensure that identifiers are unique.

You are giving the same ID to both a Dad object and Child object. This will become problematic if ever a Child becomes a Dad. Even if not the case it is far easier to automatically assign IDs than needing to make them up as you go.

In the rewrite the ids (uid for unique identifier) is generated using a function GetUid and is automatic when a person is created.

Protect object's state

Do not expose states that are not needed when using the object.

In the rewrite example I protect states like id and DNA to ensure that outside code can not corrupt the data.

In your code there is nothing stopping the code from changing the id or DNA on purpose or by mistake. If this happens all the related data is useless, further processing will result in undefined behavior.

Using methods as getters and setter helps protect state.

Simple getters

To gain access to these values I use methods so that the values can be read but not changed outside the object.

examples

• Person.dna() as protected methid to give access to dna value only to objects related to Person.

• Person.id() as private method to give access to uid value only to instances of person. Eg Relative can not change the uid

Rewrite

Rather than have the three object types Dad, Child, DadChild the rewrite has two, a Person and a Relative.

A Relative is also a Person.

The relative has methods and properties to keep track of children (closely matching DNA)

Once the people are created it is then just a matter of looping over each child and checking each parent if there is a relationship Relative.isRelated. If so the child is added to the parents list of children.

The check for closest matching DNA is done when the child is checked Relative.isRelated

The parent Relative has a function report that outputs children etc..

#include<iostream>
#include<vector>
#include<map>

const int MAX_DNA_DISTANCE{2};
int GetUid() {
    static int id{1};
    return id++;
}

class Person {
private:     
    int uid{GetUid()};
    int DNA;
protected:
    int dna() { return DNA; }
public:
    Person(int dna): DNA(dna) {}    
    int compareDNA (int _dna) { return dna() >= _dna ? dna() - _dna : _dna - dna(); }
    int id() { return uid; }
};

class Relative: public Person {
private:
    std::map<int, Person *> children;
    size_t childCount{0};
    Person *bestChild{nullptr};
    int bestDNA{-1};
public:
    Relative(int dna): Person(dna) {}
    bool isRelated(Person *child) {
        int DNA_similarity = child->compareDNA(dna());
        if (DNA_similarity < MAX_DNA_DISTANCE && children.find(child->id()) == children.end()) {
            if (bestChild == nullptr || bestDNA > DNA_similarity) {
                bestDNA = DNA_similarity;
                bestChild = child;
            }
            childCount++;
            children[child->id()] = child;
            return true;
        }
        return false;   
    }
    void report() {
        const size_t cc = childCount;
        std::cout << "ParentID: " << id() << " has ";
        if (cc == 0) { std::cout << "no children :)\n"; }
        else {
            if (cc == 1) {  std::cout << "one childID: " << bestChild->id() << " with "; }
            else { std::cout << cc << " children. Best childID: " << bestChild->id() << " having "; }
            std::cout << "a DNA similarity of " << bestDNA << ".\n";
        }
    }
};

std::vector<Relative *> parents;
void parent(int dna) { parents.push_back(new Relative(dna)); }
std::vector<Person *> children;
void child(int dna) { children.push_back(new Person(dna)); }

bool findChildsParent(Person *child) {
    for (auto rel: parents) {
        if (rel->isRelated(child)) { return true; }
    }
    return false;    
}

int main() {
    for (auto dna: {10, 5, 33, 4, 2, 3, 1}) { child(dna); }
    for (auto dna: {1, 4, 11, 20}) { parent(dna); }
    for (auto c: children) {        
        if (!findChildsParent(c)) { std::cout << "ChildID: " << c->id() << " has no known relatives :(\n"; }
    }
    for (auto p: parents) { p->report(); }
    return 0;
}

Expected output

ChildID: 3 has no known relatives :(
ParentID: 8 has 2 children. Best childID: 7 having a DNA similarity of 0.
ParentID: 9 has 3 children. Best childID: 4 having a DNA similarity of 0.
ParentID: 10 has one childID: 1 with a DNA similarity of 1.
ParentID: 11 has no children :)