How to access the values of a map<string, vector<int>> in C++?

user_3853201 0
Viewed 923

I am working on my version of a genetic algorithm to solve the knapsack problem in C++. I have a map of string to vector like

map<string, vector<int>> objects
{
    {"Object 1", {7, 20, 15}},
    {"Object 2", {3, 50, 10}},
    {"Object 3", {5, 80, 12}},
    {"Object 4", {4, 80, 8}},
    {"Object 5", {2, 40, 11}}
};

and a vector of vectors

vector<vector<int>> population;

where I will store information such as

population[0] = {0, 0, 1, 1, 0};
population[1] = {1, 0, 0, 0, 1};
population[2] = {1, 0, 1, 0, 1};
...

Each vector is called an individual, and each element of a given individual indicates the presence (1) or the absence (0) of the corresponding object. So, for example, the third individual (population[2]) has Object 1, Object 3 and Object 5.

What I want to do is write a function which will receive an index from population and return the sum of the corresponding values from objects. In the case of population[2] I'd like to have another vector containing {14, 140, 38} (7+5+2, 20+80+40, 15+12+11).

But I'm struggling to access the values of the objects map.

map<string, vector<int>> objects {/*...*/}

vector<vector<int>> population;

void initializePopulation() {/*...*/}

void getScore(vector<int> individual, vector<int>& sum)
{
    for(int i = 0; i < 3; i++)
    {
        sum.push_back(0);
        for(int j = 0; j < 5; j++)
        {
            if(individual[j] == 1)
            {
                sum[i] += ???;
            }
        }
    }

int main()
{
   /*...*/
   initializePopulation();
   vector<int> sum;
   getScore(population[2], sum);

}

So, as you can see, I'm not sure how to proceed with sum[i]. Any suggestions? I'm not very fluent in C++, so a more detailed answer would be appreciated!

knapsack-problem genetic-algorithm c++
3 Answers

For both vector of vectors as well as a map, you can use for each loop! When your map is filled with value

for(auto x: objects){
    cout<<x.first<<" "<<x.second<<endl;
}

This will print key-value pairs in a map with space in between!

In this problem you'll have to iterate values (i.e. the second) in map too!

{"Object 1", {7, 20, 15}}
{"Object 2", {3, 50, 10}}
{"Object 3", {5, 80, 12}}
{"Object 4", {4, 80, 8}}}
{"Object 5", {2, 40, 11}}

For something like this the following code should work:

for(auto x: objects){
    cout<<x.first<<" ";
    for(auto y: x.second){
        cout<<y<<" ";
    }
    cout<<endl;
}

For vector of vectors, you can use the same concept!

Try renaming Object 1, Object 2, .... to just 1,2, .... This will allow you to access values in map by using j from your for loop!

user_134466330

For a more simplified version consider this prototype instead, since you are using words like population and genetic, I assume your data to be humungous, so you are better off using const reference while passing data around (const&, they won't be copied and will become read-only). global variable is a bad idea in general.

void getScore(map<string, vector<int>> const& objects, vector<int> const& individual, vector<int>& sum)
{
    // iterate over each object for the individual
    for(int i = 0; i < 5; i++)
    {
            // are you sure you want sum as {14, 140, 38} (7+5+2, 20+80+40, 15+12+11) 
            // not {14,0, 140,0, 38} (7+5+2, 0, 20+80+40, 0, 15+12+11)
            // use else part for later
            if(individual[i] == 1)
            {
                // compute sum for each object
                // retrieve object vector
                auto it = objects.find("KEY"); // KEY generation discussed later
                if(it!=objects.end()){ // validate key :::: important
                  vector<int> ob = objects["KEY"];      //it->second
                  sum.push_back(std::accumulate(ob.begin(),ob.end(),0) ); //  https://www.cplusplus.com/reference/numeric/accumulate/
                }
            } /*else {
                sum.push_back(0);
            }*/
        }
    }

KEY generation:

1). generating "Object 1" :

string key = "Object " + to_string(i+1)
auto it = objects.find(key);

2). suggested : use integers as key or go with an enum like

enum ObjList{
    OBJECT_1,
    OBJECT_2,
    OBJECT_3
}
auto it = objects.find(i); //mind your indexes

hope it helps, happy coding XD

user_65532620

I think that with some little linear algebra your problem has an easy solution: indeed, if you store the numerical data related to your objects into a matrix A, then for each population vector p your desired result is simply p^T A (or equivalently, A^T p) where ^T denotes the transpose of a matrix or of a vector.

If you are not planning to employ any linear algebra library, you could implement the scalar product by yourself. Down below there is the code implementing the above idea.

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <numeric>

std::vector<int> SP(std::vector<std::vector<int>> const &M, std::vector<int> const &P){
    
    std::vector<int> sums(3,0);

    // perform p^T * A operation
    for (int j=0;j<3;j++)
        for (int i=0;i<5;i++)
            sums[j] += M[i][j] * P[i];

    return sums;
}
int main(){
    
    std::map<std::string, std::vector<int>> objects {
    {"Object 1", {7, 20, 15}},
    {"Object 2", {3, 50, 10}},
    {"Object 3", {5, 80, 12}},
    {"Object 4", {4, 80, 8}},
    {"Object 5", {2, 40, 11}}
    };

    std::vector<std::vector<int>> population(3);
    population[0] = {0, 0, 1, 1, 0};
    population[1] = {1, 0, 0, 0, 1};
    population[2] = {1, 0, 1, 0, 1};


    std::vector<std::vector<int>> A;
    // Extract the numerical data from the map 
    for (auto const& [key, val] : objects)
        A.push_back(val);

    // vector in which the desired values are stored for the 3rd element of the population 
    std::vector<int> s = SP(A,population[2]);

    // Just for checking
    for (int it=0; it<s.size(); it++)
        std::cout << s[it] << std::endl;
    

    return 0;
}
user_131562610
Related