CODEWITHSUNDEEP
c++pointersstruct
santosh-patil
santosh-patil

Reputation: 1550

How to avoid unnecessary copying of data?

I have this function in my code, which takes a few a vectors as arguments, makes a struct from them and push that struct in a queue. Then using a while loop the queue is processed in following manner:

  1. If struct satisfying some predefined condition (condition 1) is found then return true.
  2. If struct satisfying some predefined condition (condition 2) is found, discard the struct and continue.
  3. Else decompose the current struct into several structs and push each of them in queue.

And at last, return false if the whole queue is processed.

Below given code works fine, but I think this code is doing unnecessary copying several times.

struct q_element {
    vector<vector<int> > formula;
    vector<int> assignments;
    vector<int> unknowns;
};

bool solve(vector<vector<int> > init_formula, vector<int> init_unknowns, vector<int> init_assignments) {
    q_element t = {init_formula, init_assignments, init_unknowns, };
    deque<q_element> q;
    q.push_back(t);

    while (!q.empty()) {
        t = q.front(); //1. Copy struct from queue to t
        q.pop_front();
        if(satisfiable(t)){
            return true;
        }else if(unsatisfiable(t){
            continue;
        }else{
        vector<int> set=generateSet(t.unknowns);
        for (int i = 0; i < set.size(); i++) {
            vector<int> term = set[i];
            vector <vector<int> > newFormula=findNewFormula(t.formula, term);
            vector<int> newAssignments=findNewAssignments(t.assignments, term);
            vector<int> newUnknowns=findnewUnknowns(t.unknowns, term);
            q_element temp={ newFormula, newAssignments, newUnknowns }//2. Copy vectors into struct
            q.push_back(temp);//3. Copy struct into queue
            }
        }
    }
    return false;
}

My question is can this unnecessary copying be avoided by using struct of pointers or struct of references or by using queue of struct pointers or any other way?

Upvotes: 2

Views: 719

Answers (1)

Shoe
Shoe

Reputation: 76240

You could pass a q_element by reference:

bool solve(const q_element& t) { ... }

This "copy":

t = q.front(); //1. Copy struct from queue to t
q.pop_front();

can be avoided by always referencing q.front() instead of t and q.pop_front() at the end of the while loop.

I'm afraid the second copy is necessary:

q_element temp={ newFormula, newAssignments, newUnknowns }//2. Copy vectors into struct

and finally, with C++11, the last "copy":

q.push_back(temp);//3. Copy struct into queue

will just be a "move" operation instead.

Also this:

vector<int> term = set[i];
vector <vector<int> > newFormula=findNewFormula(t.formula, term);
vector<int> newAssignments=findNewAssignments(t.assignments, term);
vector<int> newUnknowns=findnewUnknowns(t.unknowns, term);
q_element temp={ newFormula, newAssignments, newUnknowns }//2. Copy vectors into struct
q.push_back(temp);//3. Copy struct into queue

can be reduced to:

q.emplace_back(
    { findNewFormula(t.formula, set[i])
    , findNewAssignments(t.assignments, set[i])
    , findnewUnknowns(t.unknowns, set[i]) }
);

Upvotes: 2

Related Questions