Thread: how can I re-sort a map

  1. #1
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901

    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.

  2. #2
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    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),

  3. #3
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    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.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  4. #4
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    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?

  5. #5
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    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.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  6. #6
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    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.

  7. #7
    Registered User
    Join Date
    Nov 2001
    Posts
    1,348
    one approach map with custom key and sort

    Kuphryn

  8. #8
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    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.
    Last edited by jafet; 06-01-2006 at 01:37 AM.
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  9. #9
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    sounds funky.

    Is using this -> http://www.cppreference.com/cppmap/key_comp.html what you mean?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Polynomials and ADT's
    By Emeighty in forum C++ Programming
    Replies: 20
    Last Post: 08-19-2008, 08:32 AM
  2. Straight Insertion Sort function problem
    By StaticKyle in forum C++ Programming
    Replies: 6
    Last Post: 05-12-2008, 04:03 AM
  3. Creating a map engine.
    By suzakugaiden in forum Game Programming
    Replies: 11
    Last Post: 06-21-2005, 05:06 AM
  4. threaded merge sort
    By AusTex in forum Linux Programming
    Replies: 4
    Last Post: 05-04-2005, 04:03 AM
  5. Shell Sort vs Heap Sort vs Quick Sort
    By mackol in forum C Programming
    Replies: 6
    Last Post: 11-22-2002, 08:05 PM