help sort of Container values

[Christian Gruber]

dear NG,

I have a problem sorting the values of a container,
multimap<int, pair<int, double> > map;

where the key element is the first column
and part of the value is the second column.

1 2 1.4
1 0 2.3
2 3 3.2
2 2 0.7
3 1 0.4
3 3 4.2
3 2 2.3
4 0 ...

now, I need to sort the container according to the first + second column:

1 0 2.3
1 2 1.4
2 2 ...
2 3
3 1
3 2
3 3
4 0
..
when using
stable_sort(map.begin(), map.end(), bigger())
whit

class bigger
{
public:
bool bigger()(iter I1, iter I2)
{
return ((*I1).second).first < ((*I2).second).first
}
};

I get numerous errors and can't find my way through.
so my question is, whether the concept is right in principle
and I just made some typo errors or whether I have to handle
the problem completely different... any proposals?

Best Regards,

Christian

 

[David B. Held]

I have a problem sorting the values of a container,
multimap<int, pair<int, double> > map;
[...]
now, I need to sort the container according to the first +
second column:

The map and set containers are always sorted. Therefore,
you cannot call a sort function on them.

[...]
I get numerous errors and can't find my way through.
so my question is, whether the concept is right in
principle and I just made some typo errors or whether
I have to handle the problem completely different... any
proposals?

You have a few options. One is to make your key the
pair instead of the map value. So you would have this
instead:

multimap<pair<int, int>, double> map;

I believe this will give you exactly the ordering you want,
although you are still free to provide a custom comparator
as a template parameter to the map type.

However, you really need to consider the complexity
requirements and performance profile of your application.
If you populate your map once or a few times, and insert
does not need to be particularly fast, then you should
consider using a vector instead, and sorting it only when
need be. If you still want to use the map-like interface,
then you can look for any of a number of associative
vector libraries on the web. Loki also contains an
associative vector.

Dave

 

[Ivan Vecerina]

| I have a problem sorting the values of a container,
| multimap<int, pair<int, double> > map;
|
| where the key element is the first column
| and part of the value is the second column.
....
| now, I need to sort the container according to the first + second column:
....
| stable_sort(map.begin(), map.end(), bigger())
....
| I get numerous errors and can't find my way through.
| so my question is, whether the concept is right in principle
| and I just made some typo errors or whether I have to handle
| the problem completely different... any proposals?

Such a call is illegal for several reasons: std::sort or
std::stable_sort require random access iterators, and these
algos will assign/copy items which is illegal in a map.

One simple change would be to use:
map<int, vector< pair<int, double > > > map;

During construction, this means you need to
replace map.insert(make_pair(key,my_pair));
with map[key].push_back( my_pair );
And you would sort individual vector items when needed.


An alternative would be to use a sequence container that
matches your item access requirements (e.g. vector or list)
and sort it explicitly when needed.


hth,
Ivan

 

[Frank Schmitt]

dear NG,

I have a problem sorting the values of a container,
multimap<int, pair<int, double> > map;

where the key element is the first column
and part of the value is the second column.

1 2 1.4
1 0 2.3
2 3 3.2
2 2 0.7
3 1 0.4
3 3 4.2
3 2 2.3
4 0 ...

now, I need to sort the container according to the first + second column:

1 0 2.3
1 2 1.4
2 2 ...
2 3
3 1
3 2
3 3
4 0
.
when using
stable_sort(map.begin(), map.end(), bigger())

As David already pointed out, you can't call sort on a multimap, since
it's already sorted.
Also, if you want to sort on the first two values, a

whit

class bigger
{
public:
bool bigger()(iter I1, iter I2)
{
return ((*I1).second).first < ((*I2).second).first
}
};

This comparison criterion won't work - use sth like:


#include <iostream>
#include <map>
#include <utility>

typedef<std:air<int,int> > Key;
typedef double Value;

struct bigger{
bool operator()(const Key& lhs, const Key& rhs) {
return lhs.first < rhs.first ||
(lhs.first == rhs.first &&
lhs.second < rhs.second);
}
};

typedef std::multimap<Key,Value,bigger> MyWonderfulMultiMap;

void print(const MyWonderfulMultiMap& m) {
std::cout << "begin:\n";
for (MyWonderfulMultiMap::const_iterator i=m.begin(); i!=m.end(); ++i)
std::cout << i->first.first << " " << i->first.second << " " << i->second << "\n";
std::cout << "end" << std::endl;
}

int main() {
MyWonderfulMultiMap m;
m.insert(std::make_pair(std::make_pair(1,2),2.5));
print(m);
m.insert(std::make_pair(std::make_pair(1,0),3.5));
print(m);
m.insert(std::make_pair(std::make_pair(2,3),1.5));
print(m);
return 0;
}


HTH & kind regards
frank