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@tomtom.com]

Re: STL Map: Sorting options?


Steve Edwards wrote:[color=blue]
> 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<>?)[/color]

"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.
[color=blue]
> 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.[/color]

That's one solution, if you often need that representation too, and the
keys
and values don't change. (basic caching pattern).
[color=blue]
> Or am I just using inappropriate container types to start with?[/color]

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.
[color=blue]
> As I'm dealing with very large text files, speed is a concern too.[/color]

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.]

Re: STL Map: Sorting options?

In article <gfx-807595.09475121 022006@news.bti nternet.com>,
Steve Edwards <gfx@lineone.ne t> wrote:
[color=blue]
> 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.[/color]

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]

Re: STL Map: Sorting options?

[color=blue][color=green]
>> 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<>?)[/color][/color]
[color=blue]
> "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[/color]

My mistake... I meant contents.
[color=blue][color=green]
>> As I'm dealing with very large text files, speed is a concern too.[/color][/color]
[color=blue]
>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)[/color]

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.]

Re: STL Map: Sorting options?

In article <gfx-AE7330.12031421 022006@news.bti nternet.com>,
Steve Edwards <gfx@lineone.ne t> wrote:
[color=blue]
> 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?[/color]

++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]

Re: STL Map: Sorting options?

In article <postmaster-4DB291.06552321 022006@news.eas t.earthlink.net >,
"Daniel T." <postmaster@ear thlink.net> wrote:
[color=blue]
> In article <gfx-807595.09475121 022006@news.bti nternet.com>,
> Steve Edwards <gfx@lineone.ne t> wrote:
>[color=green]
> > 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.[/color]
>
> I'm think rather than a multimap, one could use "map<int, set<string> >"
> That way, the strings will stay alphabetized.[/color]

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

[Daniel T.]

Re: STL Map: Sorting options?

In article <gfx-124497.12191621 022006@news.bti nternet.com>,
Steve Edwards <gfx@lineone.ne t> wrote:
[color=blue]
> In article <postmaster-4DB291.06552321 022006@news.eas t.earthlink.net >,
> "Daniel T." <postmaster@ear thlink.net> wrote:
>[color=green]
> > I'm think rather than a multimap, one could use "map<int, set<string> >"
> > That way, the strings will stay alphabetized.[/color]
>
> Thanks, I'll try that, see if it's quicker for my lookup needs.[/color]

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]

Re: STL Map: Sorting options?

In article <postmaster-CA11DC.07123421 022006@news.eas t.earthlink.net >,
"Daniel T." <postmaster@ear thlink.net> wrote:
[color=blue][color=green]
> >
> > myConcordance[theWord] = myConcordance [theWord]+1;[/color][/color]
[color=blue]
> ++myConcordance[theWord];[/color]

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

[color=blue][color=green]
>> "map<int, set<string> >"[/color]
>If nothing else, it will make it faster to determine how many words
>have
>the same occurrence count.[/color]

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

[Neil Cerutti]

Re: STL Map: Sorting options?

On 2006-02-21, Steve Edwards <gfx@lineone.ne t> wrote:[color=blue]
> 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.[/color]

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]

Re: STL Map: Sorting options?

In article <slrndvmgp2.ro. leadvoice@FIAD0 6.norwich.edu>,
Neil Cerutti <leadvoice@emai l.com> wrote:
[color=blue]
> 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.[/color]


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!)

[Neil Cerutti]

Re: STL Map: Sorting options?

On 2006-02-22, Steve Edwards <gfx@lineone.ne t> wrote:[color=blue]
> In article <slrndvmgp2.ro. leadvoice@FIAD0 6.norwich.edu>,
> Neil Cerutti <leadvoice@emai l.com> wrote:[color=green]
>>
>> 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.[/color]
>
>
> 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.)[/color]

It basically copies the map of string->int into a vector, sorted by
int, of int->string.

I recall now that I used something like this in a small project a few
years ago, but I used a vector of *pointers* to map iterators. In
practice, the above solution is a lot more robust.
[color=blue]
> 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!)[/color]

The way you're doing it now is clearer and easier. The vector mirror
could be considered a lower-level optimisation, which it probably
turns out you do not need.

--
Neil Cerutti
If you throw at someone's head, it's very dangerous, because in
the head is the brain. --Pudge Rodriguez