-
how can I re-sort a map
I'm doing a little practice and when I output by traversing the map through iterators, it sorts it alphabetically . For example in my sample program, it takes a file with some words on several lines and then it accesses by iterator each key of the map and outputs how many times it occurs on a certain line. Let's say I want to sort the map by how many times it occurs in total, would I have to use the algorithm sort, or something else.
here's the code.
Code:
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <vector>
#include <sstream>
#include <map>
#include "functions.h"
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
using std::map;
using std::ifstream;
using std::istream;
using std::ostream;
map<string, map<int, int> >
xref(istream&, vector<string> seperate(const string&) = parse);
int main()
{
ifstream in("temp/Sample Block.txt");
map<string, map<int, int> > report = xref(in);
map<int, int> per_line;
//prints the results
typedef map<string, map<int, int> >::const_iterator map_citer;
typedef map<int, int>::const_iterator map_ii_iter;
for(map_citer i = report.begin(); i != report.end(); i++)
{
cout << i->first << " Occurs on lines: ";
per_line = i->second;
for(map_ii_iter j = per_line.begin(); j != per_line.end(); j++)
{
cout << j->first << "-" << j->second << " time(s), ";
}
cout << endl;
}
system("PAUSE");
return 0;
}
map<string, map<int, int> >
xref(istream& in, vector<string> seperate(const string&))
{
typedef vector<string>::const_iterator vec_citer;
//holds the reference table of how many times a word appears on a line
map<string, map<int, int> > ref_table;
int linecount = 0;
string line;
while(getline(in, line))
{
++linecount;
//splits the word into a vector of strings
vector<string> split_words = seperate(line);
//traverses the vector and finds the map associated with it
for(vec_citer i = split_words.begin(); i != split_words.end(); i++)
{
//increments the number of times a word has appeared on the current line
(ref_table[*i])[linecount]++;
}
}
return ref_table;
}
The "functions.h" doesn't have much but some of my other practice functinons and the parse function which parses the current line into a vector of strings.
-
you might want the in-outputs
in:
Code:
the quick brown fox jumps over the lazy dog
the lazy brown dog jumps over the quick fox
over the dog jumps the quick brown fox
the quick lazy fox jumps over the lazy brown fox
out:
Code:
brown Occurs on lines: 1-1 time(s), 2-1 time(s), 3-1 time(s), 4-1 time(s),
dog Occurs on lines: 1-1 time(s), 2-1 time(s), 3-1 time(s),
fox Occurs on lines: 1-1 time(s), 2-1 time(s), 3-1 time(s), 4-2 time(s),
jumps Occurs on lines: 1-1 time(s), 2-1 time(s), 3-1 time(s), 4-1 time(s),
lazy Occurs on lines: 1-1 time(s), 2-1 time(s), 4-2 time(s),
over Occurs on lines: 1-1 time(s), 2-1 time(s), 3-1 time(s), 4-1 time(s),
quick Occurs on lines: 1-1 time(s), 2-1 time(s), 3-1 time(s), 4-1 time(s),
the Occurs on lines: 1-2 time(s), 2-2 time(s), 3-2 time(s), 4-2 time(s),
-
I don't believe you can just resort a map on the fly. Once you create an instance of a map, the sorting criteria used on that map is fixed and based off of the key value. There are some things you could try however...
If you were to use a vector<pair<string,pair<int,int> > > container instead of your map you could pass an appropriate sort functor to the STL sort function (one to sort based on the words, another to sort based on how many times the word appears perhaps) after the container had been populated. You could then sort it over and over on the fly according to different needs whenever you wanted. This would mean changing your xref function however to manually check for existing words so you don't insert duplicates and to do the necessary incrementing of the appropriate line/count values.
You could also create a second map (multimap<int,string>?) to store the data based on this other sorting criteria. Iterate through the first map after it has been popluated and calculate the total times the current word appears and then insert into this second map. You'd need to make sure any time you insert new data into the first map that you clear out and redo this insertion into the second map (or at least just clear and reinsert the single affected key/value entry).
There may be other ideas, those are just a couple thoughts.
-
Ok, I'll keep that in mind when I later learn about multimaps and pairs. Just trying to figure out how to do the one I did itself was confusing, though I could have used a map<string, vector<int> > rather than a map<string, map<int, int> > since the index and the line would be similar, and less dereferencing.
Why can't sort be used with maps?
-
A map sorts automatically based on the key portion of the key/value pair that is stored. If you declare a map<string,int> container then the sorting will automatically be based on ascending values (alphabetically) of the string since it is the key. You cannot take that map and then pass it to the sort function and say "OK, now I want it sorted by the int value instead". maps/multimaps (and sets/multisets) containers are not able to do that... how these containers sort/store their contents is set in stone when you declare an instance of the container.
-
I see.
Maybe I can just seek through the map and find which one has the most incarnations in the sentence, then store the key in a vector from biggest to smallest or something.
-
one approach map with custom key and sort
Kuphryn
-
You could write your own comparison function, and ask your map to use that one instead, by passing it as a functor to the map constructor.
[Edit]
whoops already posted...
If you don't want to deal with the complexity of functors, you can also make a wrapper class for your variables, and overload the comparison operator suitably.
-
