STL Map: Sorting options?

[Steve Edwards]

Hi,

I'm using a map with the key of type string, and value of type int.

typedef map<string, int, less<string> >concordance;

I'm finding words within some text and keeping a count of their
frequency.
I'm new to STL, but I've just read through the headers and can't see a
way to sort the results by value. (Maybe there's a way to modify less<>?)

Or... Should I create a second multimap (a copy) and have the int as the
key, and the string as the value, and then trivaially keep that sorted.
Or am I just using inappropriate container types to start with?

As I'm dealing with very large text files, speed is a concern too.

Thanks

Steve

[Michiel.Salters]

Steve Edwards wrote:

Hi,

I'm using a map with the key of type string, and value of type int.

typedef map<string, int, less<string> >concordance;

I'm finding words within some text and keeping a count of their
frequency.
I'm new to STL, but I've just read through the headers and can't see a
way to sort the results by value. (Maybe there's a way to modify less<>?)
"Results" is a misleading word here. std::map<Key, Value> is used to
keep
one (composite) value per key. It's a container, and containers do not
have
results. Functions have results=return values.
Or... Should I create a second multimap (a copy) and have the int as the
key, and the string as the value, and then trivaially keep that sorted.
That's one solution, if you often need that representation too, and the
keys
and values don't change. (basic caching pattern).
Or am I just using inappropriate container types to start with?
It's a good container to use when determining the int values, but it
may not
be the best container to keep those int values in.
As I'm dealing with very large text files, speed is a concern too.

Speed of what? Building the collection, or using it? And if the latter,
how?
(And if you talk files, you often are I/O limited anyway)

HTH,
Michiel Salters

[Daniel T.]

In article <gf************ ***********@new s.btinternet.co m>,
Steve Edwards <gf*@lineone.ne t> wrote:

Hi,

I'm using a map with the key of type string, and value of type int.

typedef map<string, int, less<string> >concordance;

I'm finding words within some text and keeping a count of their
frequency.
I'm new to STL, but I've just read through the headers and can't see a
way to sort the results by value. (Maybe there's a way to modify less<>?)

Or... Should I create a second multimap (a copy) and have the int as the
key, and the string as the value, and then trivaially keep that sorted.
Or am I just using inappropriate container types to start with?

As I'm dealing with very large text files, speed is a concern too.

I'm think rather than a multimap, one could use "map<int, set<string> >"
That way, the strings will stay alphabetized.

--
Magic depends on tradition and belief. It does not welcome observation,
nor does it profit by experiment. On the other hand, science is based
on experience; it is open to correction by observation and experiment.

[Steve Edwards]

I'm new to STL, but I've just read through the headers and can't see a
way to sort the results by value. (Maybe there's a way to modify
less<>?)

"Results" is a misleading word here. std::map<Key, Value> is used to
keep
one (composite) value per key. It's a container, and containers do not
have
My mistake... I meant contents.
As I'm dealing with very large text files, speed is a concern too.

Speed of what? Building the collection, or using it? And if the latter,
how?
(And if you talk files, you often are I/O limited anyway)

I've already loaded my large text file in to memory as a simple array
of strings (one per word/token). I'm doing various lexical analyses on
these data. For some of these functions I need to quickly look up the
word as the key (hence my choice of <map>) to get the associated data;
other functions then require that the value mapped to the key can be
retrieved rapidly in order (hence my original question).

Since reading your reply I've built a copy as a multimap with the
key/value swapped, and using both containers together seems to be
working quite well in retrieving by either key or value rapidly.
(Though I don't have an alternative strategy to compare speed with, so
who knows.)

Building the structures is naturally slower, now, but it is an
acceptable tradeoff.

------------------------

In my original map

typedef map<string, int, less<string> >concordance;

every time I find another occurrence of the string key, is there a
quicker way to increment it's value count, than:

myConcordance[theWord] = myConcordance [theWord]+1;

It seems I'm doing 2 lookups of [theWord], can I change the value
in-place instead?

Thanks for your help.

[Daniel T.]

In article <gf************ ***********@new s.btinternet.co m>,
Steve Edwards <gf*@lineone.ne t> wrote:

In my original map

typedef map<string, int, less<string> >concordance;

every time I find another occurrence of the string key, is there a
quicker way to increment it's value count, than:

myConcordance[theWord] = myConcordance [theWord]+1;

It seems I'm doing 2 lookups of [theWord], can I change the value
in-place instead?

++myConcordance[theWord];

--
Magic depends on tradition and belief. It does not welcome observation,
nor does it profit by experiment. On the other hand, science is based
on experience; it is open to correction by observation and experiment.

[Steve Edwards]

In article <po************ *************** ***@news.east.e arthlink.net>,
"Daniel T." <po********@ear thlink.net> wrote:

In article <gf************ ***********@new s.btinternet.co m>,
Steve Edwards <gf*@lineone.ne t> wrote:

Hi,

I'm using a map with the key of type string, and value of type int.

typedef map<string, int, less<string> >concordance;

I'm finding words within some text and keeping a count of their
frequency.
I'm new to STL, but I've just read through the headers and can't see a
way to sort the results by value. (Maybe there's a way to modify less<>?)

Or... Should I create a second multimap (a copy) and have the int as the
key, and the string as the value, and then trivaially keep that sorted.
Or am I just using inappropriate container types to start with?

As I'm dealing with very large text files, speed is a concern too.

I'm think rather than a multimap, one could use "map<int, set<string> >"
That way, the strings will stay alphabetized.

Thanks, I'll try that, see if it's quicker for my lookup needs.

[Daniel T.]

In article <gf************ ***********@new s.btinternet.co m>,
Steve Edwards <gf*@lineone.ne t> wrote:

In article <po************ *************** ***@news.east.e arthlink.net>,
"Daniel T." <po********@ear thlink.net> wrote:

I'm think rather than a multimap, one could use "map<int, set<string> >"
That way, the strings will stay alphabetized.

Thanks, I'll try that, see if it's quicker for my lookup needs.

If nothing else, it will make it faster to determine how many words have
the same occurrence count.

--
Magic depends on tradition and belief. It does not welcome observation,
nor does it profit by experiment. On the other hand, science is based
on experience; it is open to correction by observation and experiment.

[Steve Edwards]

In article <po************ *************** ***@news.east.e arthlink.net>,
"Daniel T." <po********@ear thlink.net> wrote:

myConcordance[theWord] = myConcordance [theWord]+1;

++myConcordance[theWord];

Over 100 million insertions it dropped from 20s to 12.5s. Thanks.

"map<int, set<string> >"

If nothing else, it will make it faster to determine how many words
have
the same occurrence count.

That's a benefit, and it's cleaner to iterate through, too.

[Neil Cerutti]

On 2006-02-21, Steve Edwards <gf*@lineone.ne t> wrote:

Hi,

I'm using a map with the key of type string, and value of type int.

typedef map<string, int, less<string> >concordance;

I'm finding words within some text and keeping a count of their
frequency.
I'm new to STL, but I've just read through the headers and can't see
a way to sort the results by value. (Maybe there's a way to modify
less<>?) > Or... Should I create a second multimap (a copy) and
have the int as the key, and the string as the value, and then
trivaially keep that sorted.
Or am I just using inappropriate container types to start with?

As I'm dealing with very large text files, speed is a concern too.

Here's another idea, which turned out to be more complicated than I at
first thought. The original plan was to store actual map iterators in
the vector, but then calling equal range became problematic, because I
had no iterator to pass in as the value to search for.

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

using std::map;
using std::string;
using std::vector;
using std::cout;
using std::pair;

bool less_first(pair <int, string> const& lhs, pair<int, string> const& rhs)
{
return lhs.first < rhs.first;
}

vector<pair<int , string> > mirror_map(map< string, int> const& m)
{
vector<pair<int , string> > mirror;
for (map<string, int>::const_ite rator i = m.begin(); i != m.end(); ++i)
{
mirror.push_bac k(pair<int, string>(i->second, i->first));
}
std::sort(mirro r.begin(), mirror.end(), less_first);
return mirror;
}

typedef vector<pair<int , string> >::iterator viter;
pair<viter, viter> word_range(vect or<pair<int, string> >& v, int n)
{
return std::equal_rang e(v.begin(),
v.end(),
pair<int, string>(n, ""),
less_first);
}

int main()
{
map<string, int> words;
words["love"] = 4;
words["like"] = 3;
words["the"] = 10;
words["hate"] = 4;
words["toodles"] = 1;

vector<pair<int , string> > mirror = mirror_map(word s);

// The whole mirror
for (viter i = mirror.begin() ; i != mirror.end() ; ++i)
{
cout << i->first << ": " << i->second << "\n";
}
std::cout << "----\n";

// The part of the mirror with value 4.
std::pair<viter , viter> range = word_range(mirr or, 4);
for (viter i = range.first ; i != range.second ; ++i)
{
cout << i->first << ": " << i->second << "\n";
}
return 0;
}
It is more lightweight than a multimap<int, string>, but not by as
much as I had originally hoped. I assumed that the map would not
change after it had been built up, i.e., you don't need the mirror
while building the map.

--
Neil Cerutti

[Steve Edwards]

In article <sl************ *********@FIAD0 6.norwich.edu>,
Neil Cerutti <le*******@emai l.com> wrote:

Here's another idea, which turned out to be more complicated than I at
first thought. The original plan was to store actual map iterators in
the vector, but then calling equal range became problematic, because I
had no iterator to pass in as the value to search for.

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

using std::map;
using std::string;
using std::vector;
using std::cout;
using std::pair;

bool less_first(pair <int, string> const& lhs, pair<int, string> const& rhs)
{
return lhs.first < rhs.first;
}

vector<pair<int , string> > mirror_map(map< string, int> const& m)
{
vector<pair<int , string> > mirror;
for (map<string, int>::const_ite rator i = m.begin(); i != m.end(); ++i)
{
mirror.push_bac k(pair<int, string>(i->second, i->first));
}
std::sort(mirro r.begin(), mirror.end(), less_first);
return mirror;
}

typedef vector<pair<int , string> >::iterator viter;
pair<viter, viter> word_range(vect or<pair<int, string> >& v, int n)
{
return std::equal_rang e(v.begin(),
v.end(),
pair<int, string>(n, ""),
less_first);
}

int main()
{
map<string, int> words;
words["love"] = 4;
words["like"] = 3;
words["the"] = 10;
words["hate"] = 4;
words["toodles"] = 1;

vector<pair<int , string> > mirror = mirror_map(word s);

// The whole mirror
for (viter i = mirror.begin() ; i != mirror.end() ; ++i)
{
cout << i->first << ": " << i->second << "\n";
}
std::cout << "----\n";

// The part of the mirror with value 4.
std::pair<viter , viter> range = word_range(mirr or, 4);
for (viter i = range.first ; i != range.second ; ++i)
{
cout << i->first << ": " << i->second << "\n";
}
return 0;
}
It is more lightweight than a multimap<int, string>, but not by as
much as I had originally hoped. I assumed that the map would not
change after it had been built up, i.e., you don't need the mirror
while building the map.

Whoa... thanks for this... I've been staring at it for 20 minutes trying
to get my head around it (I'm new to the stl.) Sorry I can't say
anything more constructive at the moment, until I can understand whether
doing it this way is going to be beneficial. Not having any STL text
book, I'd only found <map> code snippets on the web that seemed to suit
my needs. Having read this and googled for 'pair', I'm amazed I got as
far as I did without understanding them. (Up until now I'd been using
Objective-C which has NSDictionary and similar structures, that hide the
guts of this kind of stuff behind a lot of really intuitive convenience
functions... but I prefer C++ so here I am!)