Sorting a std::map

Question

I have defined a map like this

typedef   std::vector< int > aVector;
typedef std::map< int, aVector > aMap;
aMap theMap;

Assume that the map finally contains some elements like this

10 [0 3 7] size=3
12 [40 2 30 3 10] size=5
20 [5 10] size=2
25 [6] size=1

I want to sort on the size of the vector (e.g theMap->second.size()). So the result will be

5 3 2 1

What is the fastest way to do that? The basic idea is to push the sizes on another vector and then call sort(), like this

aVector v, sorted;
aMap::iterator it = theMap.begin();
for (; it != theMap.end(); ++it) {
  v.push_back(it->second.size());
}
// using std sort!!

Is there any better option?

What do you want to sort on the size of the vector? In your code example you seem to be just making a vector of the sizes and sorting that. — David Brown, Jun 23 '13 at 19:15
What is the output that you need?The sorted vector of sizes? — Aravind, Jun 23 '13 at 19:15
Well if you want a sorted list of the sizes I can't think of a better way to do it. — David Brown, Jun 23 '13 at 19:19
You example code doesn't sort a `std::map` and it won't compile because `std::vector` doesn't have a `sort()` member function. The question title also doesn't seem to match the actual question. — Blastfurnace, Jun 23 '13 at 19:21
A `std::map` is a sorted associative container that contains key-value pairs with unique keys. Are you asking how to order it by the size of the values? What are you trying to do and is `std::map` the appropriate container? — Blastfurnace, Jun 23 '13 at 19:29
See http://stackoverflow.com/questions/8736997/using-lambdas-in-maps — kfsone, Jun 23 '13 at 20:35

Jerska · Accepted Answer · 2013-06-23T19:21:12.103

1

Why not putting the vector as the key and using your custom key comparison function / functor which would compare the keys sizes ?

You can see examples of this in http://www.cplusplus.com/reference/map/map/map/ ?

I haven't acces to a C++ compiler right now, but it would be something like:

#include <map>

struct aComparisonStruct {
    bool operator() (const aVector& lhs, const aVector& rhs) const {
        return lhs.size > rhs.size;
    }
};

int main () {
    typedef std::vector<int> aVector;
    typedef std::map<aVector, int, aComparisonStruct> aMap;

    // Use your map

    return 0;
}

There is a problem though : You can't use the property of single key presence anymore, and you wouldn't be able to add multiple times the same vector. Maybe another implementation would be more appropriate ?

Also, it would be definitely better to use pointers as keys, but since I can't compile, I don't want to mix up pointers and references and give you something that wouldn't probably work.

edited Jun 23 '13 at 19:21

answered Jun 23 '13 at 19:13

Jerska

11,722
4
35
54

I think `<` is ascending.Right? I have to use `>` to get `5 3 2 1`. Is that right? – mahmood Jun 23 '13 at 19:19
The problem you are talking could be solved with `std::multimap`, it can store multiple elements with unique keys. – Christian Ammer Jun 23 '13 at 19:40
Can you give reasons for _it would be definitely better to use pointers as keys_. Also for what would it be better (performance, memory management, code maintenance, comprehensibility, ...). – Christian Ammer Jun 23 '13 at 19:54
Essentially memory management is the first idea that comes to my mind. Also, a map uses equals comparison to ensure the unicity. Comparing pointers would always be easier than comparing vectors. And it would allow you to have multiple same vectors (same data) as keys, as soon as they're both different instantiations. – Jerska Jun 23 '13 at 21:43

score 1 · Answer 2 · answered Jun 23 '13 at 20:07

There is a very common task when you need to have quick lookup through std::map or std::hash_map and to manage it with some specific order. In this situation you may use kinda "index" collection over your main collection:

aMap theMap;
std::map<size_t, std::list<aMap::iterator> > sizes;

// add item
auto r = theMap.insert(key, std::vector<int>());
if (!r->second)
{
    sizes[r->first->second.size()].remove(r->first);
}
r->first->second->push_back(item);
sizes[r->first->second.size()].push_back(r->first);

score 0 · Answer 3 · answered Jun 23 '13 at 19:26

0

Std sort is declared as this:

void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

So you can pass in a comp:

struct comp {
    bool operator() (const aVector& lhs, const aVector& rhs) {
      return (lhs.size() < rhs.size());
    }
} mycomp;

std::sort(theMap, comp)

Note that it is better to pass the comp as an input rather than fix it when you declare the map. In this case you don't have to declare different maps when you only want to change the comp.

answered Jun 23 '13 at 19:26

WhatABeautifulWorld

3,198
3
22
30

Are you sure about that? I get this `error C2275: 'myClass::comp' : illegal use of this type as an expression` – mahmood Jun 23 '13 at 19:30
sorry, this might not work as map is already an ordered container... in this case I think better to set the order when you create the container. But for other container this should work – WhatABeautifulWorld Jun 23 '13 at 20:15

Sorting a std::map

3 Answers3