vector- algorithm const problem

[cmom]

Hi this is my first time posting to this forum - please forgive me in advance if any part of this request is inappropriate. I am compiling free source code in cygwin g++ and I am getting the following error message:

In file included from /usr/lib/gcc/i686-pc-cygwin/4.5.3/include/c++/algorithm:63:0,
from saMultiChoiceKnapsack.cpp:27:
/usr/lib/gcc/i686-pc-cygwin/4.5.3/include/c++/bits/stl_algo.h: In function ‘_RandomAccessIterator std::__unguarded_partition(_RandomAccessIterator, _RandomAccessIterator, const _Tp&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<GreedyObject*, std::vector<GreedyObject> >, _Tp = GreedyObject]’:
/usr/lib/gcc/i686-pc-cygwin/4.5.3/include/c++/bits/stl_algo.h:2249:70: instantiated from ‘_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<GreedyObject*, std::vector<GreedyObject> >]’
/usr/lib/gcc/i686-pc-cygwin/4.5.3/include/c++/bits/stl_algo.h:2280:54: instantiated from ‘void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<GreedyObject*, std::vector<GreedyObject> >, _Size = int]’
/usr/lib/gcc/i686-pc-cygwin/4.5.3/include/c++/bits/stl_algo.h:5212:4: instantiated from ‘void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<GreedyObject*, std::vector<GreedyObject> >]’
saMultiChoiceKnapsack.cpp:121:43: instantiated from here
/usr/lib/gcc/i686-pc-cygwin/4.5.3/include/c++/bits/stl_algo.h:2211:4: error: passing ‘const GreedyObject’ as ‘this’ argument of ‘bool GreedyObject:perator<(const GreedyObject&)’ discards qualifiers

I am doing research on Multiple Dimension Multiple Choice Knapsack problems. I need the results from several tests to continue my research. I do program, but I am not a C++ programmer. The link to the source code can be found here:

http://shah.freeshell.org/samulticho...ceKnapsack.cpp

Any help would be appreciated.

Frustrated grad student

[ZuK]

The operators < and > of GreedyObject and MNode should be declared const.
Also you have to #include <ctime> and <cstring>
Kurt

[Paul McKenzie]

Any help would be appreciated.

Also, you included <vector>, but you don't use it for what it's designed for -- namely dynamic arrays. You used it for Groups, but you refused to use it for int or other types. Why?

Your code uses new[]/delete[] instead of using the convenient std::vector. It's like having a car and instead of driving to your destination, you decided to walk. For example:

int *CAPACITIES; // populated in processData()
CAPACITIES = new int[NUMBER_CONSTRAINTS];

Instead the above, this is the same thing:

std::vector<int>  CAPACITIES; // populated in processData(
...
CAPACITIES.resize(NUMBER_CONSTRAINTS)

An overview of the changes would be something like this:

typedef std::vector<int> IntArray;
typedef std::vector<IntArray> IntArray2D;
typedef std::vector<IntArray2D> IntArray3D;

IntArray3D  CONSTRAINTS; // populated in processData()
IntArray    CAPACITIES; // populated in processData()
IntArray2D  VALUES; // populated in processData()

Then that loop you wrote now looks like this:

    VALUES.resize(NUMBER_GROUPS, IntArray(NUMBER_OBJECTS_IN_GROUP));
    CONSTRAINTS.resize(NUMBER_GROUPS, IntArray2D(NUMBER_OBJECTS_IN_GROUP, IntArray(NUMBER_CONSTRAINTS)));

    fgets(line, 1000, file);
    for (i=0; i<NUMBER_GROUPS; i++)
    {
        fgets(line, 1000, file);
        tok = strtok(line, " ");
        for (int g=0; g<NUMBER_OBJECTS_IN_GROUP; g++)
        {
            int value = atoi(tok);
            VALUES[i][g] = value;
            for (int c=0; c<NUMBER_CONSTRAINTS; c++)
            {
                tok = strtok(NULL, " ");
                CONSTRAINTS[i][g][c] = atoi(tok);
            }
            fgets(line, 1000, file);
            tok = strtok(line, " ");
        }
    }

Note how I use resize() to create the full arrays, and not new[]/delete[] in a loop. Two lines of code is equivalent to all of those lines of new[]/delete[] you were doing. In addition, the calls later on to free the memory using delete[] can be removed from the program.

Doing this reduces, if not eliminates memory leaks. The vector class was designed so that all of that code you're doing with new[]/delete[] need not be done. With the code you wrote now, how can you know if you don't have memory leaks or if you're mismanaging pointers? The vector class will ensure that when it goes out of scope, the memory used internally by vector is cleaned up, i.e. no need to issue delete[] calls.

Another example -- your MNode class need not have copy constructor, assignment operator, or destructor coded if you used vector:

typedef std::vector<int> IntArray;
class MNode
{
public:
    IntArray objects;
    IntArray weights;
    int value;

    /* Constructor */
    MNode() { }

   /* Calculate the objective function value */
    void calculateValue()
    {
        value = 0;
        for (int i=0; i<NUMBER_GROUPS; i++)
        {
            value+=VALUES[i][objects[i]];
        }
    }

    /* Calculate the weights array */
    void calculateWeights()
    {
        weights.resize(NUMBER_CONSTRAINTS);
        for (int i=0; i<NUMBER_CONSTRAINTS; i++)
        {
            weights[i] = 0;
            for (int j=0; j<NUMBER_GROUPS; j++)
            {
                int aas = objects[j];
                weights[i]+=CONSTRAINTS[j][aas][i];
            }
        }
    }

    /* Does this solution violate any constraints? */
    bool violatesConstraints() const
    {
        for (int i=0; i<NUMBER_CONSTRAINTS; i++)
        {
            if (weights[i] > CAPACITIES[i])
                return true;
        }
        return false;
    }

    /* How much is the constraint violation? */
    int constraintViolation() const
    {
        int violation = 0;
        for (int i=0; i<NUMBER_CONSTRAINTS; i++)
        {
            if (weights[i] > CAPACITIES[i])
                violation+=(weights[i]-CAPACITIES[i]);
        }
        return violation;
    }

    /* Change the selection of the passed in group to the passed in assignment */
    void changeSelection(int group, int assignment)
    {
        if (objects[group] == assignment)
            return;

        int previous = objects[group];
        for (int i=0; i<NUMBER_CONSTRAINTS; i++)
        {
            weights[i]-=CONSTRAINTS[group][previous][i];
        }

        value-=VALUES[group][previous];

        for (int i=0; i<NUMBER_CONSTRAINTS; i++)
        {
            weights[i]+=CONSTRAINTS[group][assignment][i];
        }

        value+=VALUES[group][assignment];

        objects[group] = assignment;
    }

    int fitness()
    {
        if (violatesConstraints())
        {
            return -100;
        }
        else
        {
            return value;
        }
    }

    /* Get the selection of passed in group */
    int getValueOfIndex(int index)
    {
        return objects[index];
    }
};

I don't know what "clone" is supposed to do, but I don't think you even need this function if you used container classes instead of pointers. The code is now reduced (no destructor, no user-defined copy ctor or assignment operator, etc.).

In addition, I'm highly suspicious of user-defined copy constructors that call functions that could potentially not create an exact copy of the object being passed in. Those calls to calculateWeights and calculateValues in your copy constructor should not be done in a function such as a copy constructor, as they have a potential of causing side effects. If a copy constructor or assignment operator creates bogus or "semi" copies, then the potential for very hard-to-find bugs becomes great. This is especially the case if you start returning MNode's by value (or pass them by value). Since the code above doesn't need copy constructor written, then the potential for that bug to appear now goes away.

Another thing is that for some reason, you use new[] to create the memory for line, but why do this when you know the array is going to be 1000 characters?

void processData()
{
    FILE * file;
    file = fopen("data.dat", "r");
    if (file == NULL)
    {
        printf("data.dat File Not Found in Current Directory.");
        exit(1);
    }
    char  line[1000];

There is no need to call new[] here -- you know the exact number of characters, so just use an array of char as I did above.

Also, what is the purpose of operator >? STL algorithms require either operator < or operator ==. If you're going to write operators, then those two ( <, == ) are the ones you should write, and any other operator can be written in terms of those two operators.

Last, in C++ it is convention to not use UPPER CASE for variable names. UPPER CASE names are used for macros or other constants.

Regards,

Paul McKenzie

[cmom]

The operators < and > of GreedyObject and MNode should be declared const.
Also you have to #include <ctime> and <cstring>
Kurt

Thanks so much! It worked!

[cmom]

Paul thanks for the detailed analysis. While I got the code to work with minor adjustments - your suggestions will greatly improve the program. I will apply them and let you know how it works.