map question

[1vf9z8AR]

Complicated errors :/
Not telling which line has problem.

https://www.hackerearth.com/practice/data-structures/hash-tables/basics-of-hash-tables/practice-problems/algorithm/suzakus-festivals-14dacd7c/

  #include<iostream>
#include<map>
#include<vector>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t>0)
    {
        int n;
        cin>>n;
        map<string,vector<int,greater<int>>>m;
        string str;
        int value;
        while(n>0)
        {
            cin>>str>>value;
            m[str].push_back(value);
            n--;
        }
        long long int ans=0;
        string fest;
        for(map<string,vector<int,greater<int>>>::iterator it=m.begin();it!=m.end();it++)
        {
            int i=0,sum=0;
            for(auto x:m[it->first])
            {
                i++;
                sum+=x;
                if(i==3)
                    break;
            }
            if(sum>ans)
            {
                fest=it->first;
                ans=sum;
            }
        }
        cout<<fest<<" "<<ans<<endl;
        t--;
    }
}

[Peter87]

Instead of

map<string, vector<int, greater<int>>>

perhaps you meant

map<string, vector<int>, greater<string>>

?

[1vf9z8AR]

@Peter87

no. i want the vector in descending order

[Grime]

That snippet seems very wrong to me.. I don't know why Peter87 did not mention any of it so I'm not sure that I'm correct myself. So don't rely on what I say because I'm a newbie and I haven't used maps that much. These are just thoughts.

map<string,vector<int,greater<int>>>m;
I'm not sure what you were trying to do here. What is "greater" supposed to be/do? The compiler is looking for a structure defined under the identifier "greater" with that line.

Proper way to declare two dimensional array: vector < vector<int> >;
Sorting is to be done afterwards.


So, map <string, vector < vector<int> >>m; would create a mapping of string to 2D vector.

But this has no elements yet!!

So calling an index of the mappingm[str] would be illegal because it currently has 0 indexes.

m[str].push_back(value);
I have no clue what you were trying to do in this line..

1) m[str] is illegal like I said
2) std::map doesn't have member function .push_back()
3) value is of type int, so if you were to push it, where??

std::insert() is used to insert elements to a map.

In

      for(auto x:m[it->first])
            {
                i++;
                sum+=x;
                if(i==3)
                    break;
            }

for(auto x:m[it->first])
should be
for(auto x: m)

sum+=x;
should be
sum+=x.first;
Note that it's not x is not a pointer.

[dhayden]

What is the program supposed to do? I can't explain how to fix it without knowing what it should do.

[Peter87]

What is "greater" supposed to be/do?

std::greater is a class template that can be used with std::map, std::sort and other templates to specify that the elements should be compared using greater than (>), instead of less than (<) which is the default.

It doesn't work with std::vector though, so if you want the elements of each vector to be sorted you would either have to make sure to insert each element at the correct position, or do the sorting (e.g. by using std::sort) after all elements has been inserted.

http://www.cplusplus.com/reference/functional/greater/
http://www.cplusplus.com/reference/algorithm/sort/

But this has no elements yet!! So calling an index of the mapping m[str] would be illegal because it currently has 0 indexes.

The subscript operator of std::map automatically inserts an element if the key is not found so m[str].push_back(value) is perfectly fine.

2) std::map doesn't have member function .push_back()

push_back is called on the vector that is returned from m[str].

for(auto x:m[it->first])
should be
for(auto x: m)

It should be for (auto x : it->second).

You could use m[it->first] but it's unnecessary to look up the value when you already have it.

[Grime]

The subscript operator of std::map automatically inserts an element if the key is not found so m[str].push_back(value) is perfectly fine.

Umgh but
1) 'm' is the map
2) push_back() is not a member function of map
right?

If it were say vector <int> m; (<int> because value is int) then it still would not work because the map is from string to vector and vectors cannot be evaluated to an integer..

Now that I think about it he probably meant:
m[str] = 5; and that's probably also what you meant! :P

Right?

for(auto x : it->second) Can you summarize this loop in a sentence?
edit: Oh okay I get it.. I completely ignored 'it'..! My bad!

[Peter87]

1) 'm' is the map

Yes.

m is defined as

map<string, vector<int>> m; // ignoring greater<int> 

This means that the keys are strings, and for each string there is a vector of ints.

m[str] returns the vector that belongs to str. If it doesn't already exist it will be created.

2) push_back() is not a member function of map

True, but push_back here is called on a vector.

Now that I think about it he probably meant:
m[str] = 5; and that's probably also what you meant! :P

For this to work m would have to be defined as

map<string, int> m;

It doesn't look like what he wants.

for(auto x : it->second)
Can you summarize this loop in a sentence?

it is an iterator to a key-value pair in map m.

it->first is the key (the string).
it->second is the value (the vector<int>).

x is the loop variable that will hold each element in the vector. The type of x is int.

In other words, the outer loop (starting on line 24) loops over each key-value pair (i.e. the string-vector pairs) in the map, and the inner loop (starting on line 27) loops over the elements of each value (i.e. the vector elements).

[1vf9z8AR]

ok i solved the issue by using map in map instead of vector in map

[Grime]

Thanks for baring with me.

m[str] returns the vector that belongs to str. If it doesn't already exist it will be created.

Ah I get it. It's the same as m[str] = {to_be_pushed};. I don't know why I thought the mapping was to an integer..

[Peter87]

Yes, the end result is the same.