5
\$\begingroup\$

I am trying to solve the Travelling Salesman Problem. This function creates the first level in the form of a linked list.

This is what the levels look like:

enter image description here

This is the code that creates it:

vector<pot> noviNivo;
    int tempInt = vozliscaG - 1;


    for (int i = 0; i < vozliscaG-1; i++) {

        pot temp;
        temp.iz_vozlisca = tempInt;
        temp.v_vozlisce = 0;
        temp.cena = mat[tempInt][temp.v_vozlisce];
        temp.mnozica.push_back(false);
        tempInt--;
        noviNivo.push_back(temp);

    }

    for (int i = 1; i < vozliscaG - 1; i++) {
        noviNivo[i-1].naslednji = &noviNivo[i];
    }

Also, sorry that the variables names are in another language, but I think aren't really relevant to the question. My question is, am I using the pointers and dereferencing them correctly or will I run into problems further on in the code? Also, I am doing it this way because I don't want to end up with a vector of pointers to the struct, I just want the vector of the structs.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ No. When you push temp onto your vector, a copy is created that now resides inside the memory managed by your vector, and the original temp is destroyed when the function exits. Thus, head and tail will point to invalid memory. Still, since you don't do anything with either of those, you don't invoke UB, but I wonder what the point of those two variables is. \$\endgroup\$ Jun 3, 2017 at 14:12
  • \$\begingroup\$ @BenSteffan Oh yeah, I was doing the list with pointers earlier so I didn't realise I don't nead the head and tail anymore. The only thing I need is to make the temp.naslednji(it means next) point to the next "pot" I create. How would I go about doing that with the current format of the code? \$\endgroup\$
    – HelloImJon
    Jun 3, 2017 at 14:32
  • \$\begingroup\$ Well, you would need to find the pot in your vector and assign its address. \$\endgroup\$ Jun 3, 2017 at 14:34
  • \$\begingroup\$ @BenSteffan Right! Thanks for your help, I edited the post with the new and improved code if you're interested. \$\endgroup\$
    – HelloImJon
    Jun 3, 2017 at 14:55

1 Answer 1

3
\$\begingroup\$

Here are some things that may help you improve your code.

Provide complete code to reviewers

This is not so much a change to the code as a change in how you present it to other people. Without the full context of the code and an example of how to use it, it takes more effort for other people to understand your code. This affects not only code reviews, but also maintenance of the code in the future, by you or by others. One good way to address that is by the use of comments. Another good technique is to include test code showing how your code is intended to be used. With that said, here's the code I used to exercise yours:

#include <vector>

struct pot {
    int iz_vozlisca;  // from node
    int v_vozlisce;   // to node
    int cena;         // cost
    std::vector<bool> mnozica; // group
    pot* naslednji = nullptr;
};

constexpr int vozliscaG{5};
constexpr int Max{999};
constexpr int mat[vozliscaG-1][vozliscaG-1] = {
    /*          1    2    3    4 */
    /* 1 */ {  11,  12,  13,  14 },
    /* 2 */ {  21,  22,  23,  24 },
    /* 3 */ {  31,  32,  33,  34 },
    /* 4 */ {  41,  42,  43,  44 },
};

using namespace std;

int main() {
    // your code here
}

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid. I infer that this was done here because the code won't compile without it.

Simplify your code using emplace_back

Here's an alternative to your code which shows how much simpler it could be if you use emplace_back:

vector<pot> noviNivo;
for (int i = 0; i < vozliscaG-1; i++) {
    noviNivo.emplace_back(vozliscaG-i-2, 0, mat[vozliscaG-i-2][0]);
}
for (int i = 1; i < vozliscaG - 1; i++) {
    noviNivo[i-1].naslednji = &noviNivo[i];
}

Reconsider the data structure

You wrote:

My question is, am I using the pointers and dereferencing them correctly or will I run into problems further on in the code? Also, I am doing it this way because I don't want to end up with a vector of pointers to the struct, I just want the vector of the structs.

Since you're using a linked list anyway, it would make more sense to me to use a std::list instead of a std::vector. This would remove the need to handle raw pointers in your code and provides a way to use just your pot class without having to think too much about the mechanics of list creation and maintenance.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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