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?

Answer 1

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.

Answer 2

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;
}       

Answer 3

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.

1. 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.
2. 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.