How can I push_back a map<string, int> into a vector<map<string, int>> via an iterator?

Question

I'm currently studying the book Accelerated C++ (Koening/Moo) and I'm having trouble with one of the exercises. The task is to write a program which takes as an input some sequence of words which it then stores in a map<string, int>. The strings are the words entered and the associated int is the number of times each word occurs. You then have to sort the words by the number of times they occur; that is, by the value and not the key. You can't sort a map by the value, so I tried to copy the elements to a vector instead, which I intended to sort using a predicate. Unfortunately, all I get is a screen full of errors from g++. They seem to stem from the same place - putting the elements of my map into my vector, which I try to do like this:

int main()
{
    map<string, int> counters;

    cout << "Enter some words followed by end-of-file (ctrl-d): ";
    string word;
    while (cin >> word)
       ++counters[word];

    // Maps cannot be sorted by values, so pass the elements of counters to a vector.
    vector<map<string, int> > vec_counters;

    map<string, int>::const_iterator it = counters.begin();
    while (it != counters.end()) {
       vec_counters.push_back(*it);
       ++it;
    }
}

This is obviously just the first part, but I can't get even this to compile. I get the following error:

32:31: error: no matching function for call to std::vector, int> >::push_back(const std::pair, int>&)’ /usr/include/c++/4.5/bits/stl_vector.h:741:7: note: candidate is: void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::map, int>, _Alloc = std::allocator, int> >, value_type = std::map, int>]

What am I doing wrong?

Answer 1

I'm pretty sure you aren't looking for a vector of maps:

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

using namespace std;
int main()
{
    map<string, int> counters;

    cout << "Enter some words followed by end-of-file (ctrl-d): ";
    string word;
    while (cin >> word)
       ++counters[word];

    vector<std::pair<string, int> > vec(counters.begin(), counters.end());
}

Answer 2

A bit off-topic, but here's a sexy solution using a bimap, which is a map in which both sides work as keys.

#include <iostream>
#include <sstream>
#include <string>
#include <boost/bimap.hpp>
#include <boost/bimap/list_of.hpp>
#include <boost/bimap/set_of.hpp>

int main()
{
    boost::bimap<boost::bimaps::set_of<std::string>, boost::bimaps::list_of<int>> m;

    for (std::string line; std::getline(std::cin, line); )
    {
        ++m.left[line];
    }

    auto & bml = m.left;
    auto & bmr = m.right;

    bmr.sort();

    for (auto const & p : bml) { std::cout << p.first << " => " << p.second << "\n"; }
    for (auto const & p : bmr) { std::cout << p.first << " => " << p.second << "\n"; }
}

Answer 3

You want to put the elements of a map in a vector. Maps are made out of pairs, not other maps. Therefore, your vector should be a vector of pairs.

That said, it looks like the reason you want the vector in the first place is to sort by values in the map. Why not then make your map map< int, string > instead? This will result in it being sorted in ascending order by the ints : Elements in the map are sorted from lower to higher key value following a specific strict weak ordering criterion.

Answer 4

Dereferencing a std::map<std::string, int>::const_iterator gives you a std::pair<std:string, int>, not a std::map<std::string, int>, so instead of this:

vector<map<string, int> > vec_counters;

you want this:

vector<std::pair<string, int> > vec_counters;

Answer 5

If you want to sort your vector after inserting your map entries into it, then you can also use a std::set instead. The elements in a set are always sorted. This is especially helpful if you want to insert new elements at a later time. However, as you want to sort your map entries by value, you have to store flipped key-value pairs into the set. I omitted reading the input in the following C++11 code for the sake of clarity:

int main() {
    std::map<std::string, int> counters{
        {"sorted", 2}, {"value" , 5}, {"is" , 2}, {"by" , 3}, {"this" , 1}
    };

    std::set<std::pair<int, std::string>> s;  // Use a set instead of a vector.

    for (auto const &kv : counters)
        s.emplace(kv.second, kv.first);  // Flip the pairs.

    for (auto const &vk : s)
        std::cout << vk.second << ": " << vk.first << std::endl;

    return 0;
}

Output:

this: 1
is: 2
sorted: 2
by: 3
value: 5

If you want to sort in descending order, you can define the set as follows:

using flippedPair = std::pair<int, std::string>;
std::set<flippedPair, std::greater<flippedPair>> s;

Shorter C++17 code on Coliru