Use of Vectors of vectors in C++ & push_back( )

Question

I am new to C++ and might be missing something very basic here but I am trying to create a vector of vectors

#include <iostream>
#include <stack>
#include <string>
#include <map>
#include <vector>
#include <algorithm>


using namespace std;

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs)
    {
        vector<vector<string>> result;
        map<string,vector<string>> myMap;

        if(strs.size() == 0)
        {
            return result;
        }

        for(string s : strs)
        {
            string temp = s;
            sort(temp.begin(),temp.end());
            auto it = myMap.find(temp);
            if(it != myMap.end())
            {
                it->second.push_back(s);
            }
            else
            {
                vector<string> newVector;
                newVector.push_back(s);
                myMap.insert(pair<string,vector<string>>(temp,newVector));
                result.push_back(newVector);
            }
        }
        cout<< myMap["abt"].size() <<endl;
        return result;
    }
};


int main(int argc, const char * argv[])
{
    Solution mySolution;
    vector<string> myStrings {"eat", "tea", "tan", "ate", "nat", "bat"};
    auto result = mySolution.groupAnagrams(myStrings);

    for(vector<string> v: result)
    {
        //cout << v.size() << endl;
        for(string s: v)
        {
            cout << s << " ";
        }
        cout << endl;
    }
    return 0;
}

I am expecting an output which looks like this

[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

When I try to print the vector of vectors in main() I get all the size of the vectors as 1.

Well when I print the sizes of the vectors in the map, the sizes look okay to me there. What am I missing here?

UPDATE -

Fixed it with below change

for(string s : strs)
{
    string temp = s;
    sort(temp.begin(),temp.end());
    auto it = myMap.find(temp);
    if(it != myMap.end())
    {
        it->second.push_back(s);
    }
    else
    {
        vector<string> newVector;
        newVector.push_back(s);
        myMap.insert(pair<string,vector<string>>(temp,newVector));
    }
}
for(auto it: myMap)
{
    result.push_back(it.second);
}

I would still be interested to know if there is a way to avoid looping through the map in the end and achieve something which I initially intended to do?

Be aware that `for(string s : strs)` makes a copy of every string in `strs`. — kfsone, Jul 14 '16 at 05:56
"... if there is a way to avoid looping through the map in the end" - I don't want to answer in that direction simply because it's easy to be wrong (very wrong) when getting into `vector< vector & >` territory. Even for my own uses I try to avoid passing around containers of reference types as it is a source of bad memory management if you are generating the values at the same time only to hand them over to "outer" scope. You may as well use pointers, and it should be apparent why that's dangerous. — Xeren Narcy, Jul 14 '16 at 06:13

score 5 · Accepted Answer · edited May 23 '17 at 11:51

5

It's this part:

{
    vector<string> newVector;
    newVector.push_back(s);
    myMap.insert(pair<string,vector<string>>(temp,newVector));
    result.push_back(newVector);
}

Each time result is being given a new vector that has one element. The reason the changes to the map's vector work and not the vector of vectors, is because vector::push_back creates a copy each time.

To solve this there's two ways.

You can try to update the result at the same time as the map, and get the vector to store some reference to the map's copy.
Since you do not use result for the processing step, only for results, you can compile the vector after you're finished with the map.

I prefer method #2 for this since you never return the map itself. Furthermore there is an art to transforming from one container type to the next, eg this question gives some ideas on what's involved.

edited May 23 '17 at 11:51

Community

1
1

answered Jul 14 '16 at 05:38

Xeren Narcy

875
5
15

1

The part that causes the problem is that the `it->second.push_back(s)` line only pushes into the map, not the `result` vector, as they are separate things (even though they were both copied from `newVector`) – The Dark Jul 14 '16 at 05:51
so you are saying that the vector which is stored in the map & which is stored in the result are different? And all the updates are being made on the vector which is stored in the map but not on the one which is in result since they are different? – kimi Jul 14 '16 at 05:51
@ghanta_engineer exactly, yes. your map is being updated, and you're directly modifying the vector stored in the map. however the result just takes a copy with one element filled, and is never referred to again. – Xeren Narcy Jul 14 '16 at 05:52
I see, so how do I not make different copies & make sure it points to the same vector the one I am updating? – kimi Jul 14 '16 at 05:55
@TheDark agree to disagree - the problem is there's two vector instances in play, we're updating `A` but returning `B`. Personally I feel the issue is with the result, since the map is used for data processing first and foremost. – Xeren Narcy Jul 14 '16 at 06:00
Actually I was agreeing with you, just clarifying that having two vector instances isn't a problem, unless you are expecting that updating one will update the other (as the OP was). – The Dark Jul 14 '16 at 06:02
@TheDark ok fair enough :) I figured that much was implied so it looked a touch aggressive to me and in need of clarification of my own. – Xeren Narcy Jul 14 '16 at 06:08

score 0 · Answer 2 · answered Jul 14 '16 at 06:08

The problem is with this part of the code:

vector<string> newVector;
newVector.push_back(s);
myMap.insert(pair<string,vector<string>>(temp,newVector));
result.push_back(newVector);

Broken down:

vector<string> newVector;

Creates a new, local, temporary vector.

newVector.push_back(s);

allocates space for a string at the back of newVector and copies s into it.

myMap.insert(pair<string,vector<string>>(temp,newVector));

Creates a std::pair containing a copy of temp and a copy of newVector - as is, then allocates room for a matching pair in the map and copies the temporary pair (i.e. copies the string and the vector, again) into it.

result.push_back(newVector);

This allocates space for a new vector at the back of result and copies newVector into it.

result and myMap contain independent snapshots of newVector at this point. The rest of your code updates the vector in myMap but result is untouched.

You can fix this by not building result on the fly, but only building it when all the work is done:

    // take a reference to each string in the vector,
    // const indicates it will be immutable
    for(const string& s : strs)
    {
        string temp = s;
        sort(temp.begin(),temp.end());
        std::vector<string>& dest = myMap[temp];
        dest.emplace_back(s);
    }

    cout<< myMap["abt"].size() <<endl;

    for (auto& kv : myMap)  // kv: key value
    {
        // std::move tells 'emplace_back' it can steal the
        // vector's data right out of kv.second.
        result.emplace_back(std::move(kv.second));
    }

The resulting code is demonstrated here: http://ideone.com/eofloM

#include <iostream>
#include <stack>
#include <string>
#include <map>
#include <vector>
#include <algorithm>


using namespace std;

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs)
    {
        vector<vector<string>> result;
        map<string,vector<string>> myMap;

        if(strs.size() == 0)
        {
            return result;
        }

        for(const string& s : strs)
        {
            string temp = s;
            sort(temp.begin(),temp.end());
            std::vector<string>& dest = myMap[temp];
            dest.emplace_back(s);
        }

        cout<< myMap["abt"].size() <<endl;

        for (auto& kv : myMap)  // kv: key value
        {
            result.emplace_back(std::move(kv.second));
        }

        return result;
    }
};


int main(int argc, const char * argv[])
{
    Solution mySolution;
    vector<string> myStrings {"eat", "tea", "tan", "ate", "nat", "bat"};
    auto result = mySolution.groupAnagrams(myStrings);

    for(vector<string> v: result)
    {
        //cout << v.size() << endl;
        for(string s: v)
        {
            cout << s << " ";
        }
        cout << endl;
    }
    return 0;
}

score 0 · Answer 3 · answered Jul 14 '16 at 13:02

I would still be interested to know if there is a way to avoid looping through the map in the end and achieve something which I initially intended to do?

class Solution {

private:
        vector<vector<string>*> result;
        map<string,vector<string>> myMap;

public:
    vector<vector<string>*> groupAnagrams(vector<string>& strs)
    {
//        vector<vector<string>*> result;
//        map<string,vector<string>> myMap;

simply make the result and map the members of the class. See the type changed to vector of pointers of vector.

        else
        {
            vector<string> newVector;
            newVector.push_back(s);
            auto p = myMap.insert(pair<string,vector<string>>(temp,newVector));

            //p is pair<iterator, bool>
            //where iterator is pointing to the inserted element
            //so p.first->second is the new vector

            result.push_back(&(p.first->second));
        }

notice here we put address of the vector in the map.

for(vector<string>* v: result)
{
    for(string s: *v)
    {
        cout << s << " ";
    }
    cout << endl;
}

iterating the vector and considering the pointer type gives the result as:

eat tea ate 
tan nat 
bat

This takes away the second loop and uses less space but makes the code a bit complicated.

Use of Vectors of vectors in C++ & push_back( )

3 Answers3