Sorting a std::vector> by the string?

Question

How can I sort this vector by comparing the pair.first which is an std::string? (without providing a static compare function, nor use boost).

score 39 · Accepted Answer · answered Jan 05 '11 at 23:19

39

std::vector<std::pair<std::string, bool> > v;
std::sort(v.begin(), v.end());

std::pair overloads operator< to sort first by the first element then by the second element. Thus, if you just sort the vector using the default sort ordering (operator<), you'll get your desired ordering.

answered Jan 05 '11 at 23:19

James McNellis

348,265
75
913
977

1

This is a C++0x only answer. ;) Edit: Now fixed (`>>` token closing two nested template `<>` pairs is C++0x only). – CB Bailey Jan 05 '11 at 23:20
@Charles: Ha! Yeah, I probably do that in a lot of answers. I'm too used to using a compiler that supports `>>`. – James McNellis Jan 05 '11 at 23:26
4

+1: I didn't know that `std::pair::operator<()` was overloaded. I do now! – Oliver Charlesworth Jan 05 '11 at 23:38
1

Just to be picky, this requires that the second item in the pair has `<` defined. If the second type is not sortable then this will fail. – edA-qa mort-ora-y Jan 06 '11 at 08:18
@edA: Yes. The OP's pair has a `bool` as its second element type, which is comparable. – James McNellis Jan 06 '11 at 17:14

score 4 · Answer 2 · answered Jan 05 '11 at 23:36

4

I really like James' answer, but there's one other option you might want to consider - just funnel everything into a std::map:

std::map<std::string, bool> myMap(v.begin(), v.end());

Or, if you have duplicate strings, a std::multimap:

std::multimap<std::string, bool> myMultiMap(v.begin(), v.end());

This does have the added advantage that if you then need to add or remove new key/value pairs, you can do so in O(lg n), as opposed to O(n) for the sorted vector.

If you really must use a vector, then go with James' answer. However, if you have a vector of pairs, there's a good chance that you really want a std::map.

answered Jan 05 '11 at 23:36

templatetypedef

362,284
104
897
1,065

I need to consider the case where the user does not want them sorted and in the order they gave them. – jmasterx Jan 06 '11 at 00:09
1

Also vector + sort may in practice be much faster than inserting lots of stuff into a (multi)map, regardless of what the big-O notation says. – Reunanen Mar 29 '14 at 14:43

score 1 · Answer 3 · answered Nov 15 '18 at 07:01

Answer to "duplicate question" of this: link: Sort a vector of pairs by first element then by second element of the pair in C++?

bool cmp(const pair<int,int>&x,const pair<int,int>y){
if(x.first==y.first){
   return(x.second<y.second);
}
return(x.first<y.first);
}

array of pairs before:
5 2
4 2
8 2
8 3
8 1
array of pairs after:
4 2
5 2
8 1
8 2
8 3

score 0 · Answer 4 · answered Jan 05 '11 at 23:29

0

You can use a custom comparator to order on the pairs' .first only.

sort(begin, end,
     compose2(less<string>(),
              select1st<pair<string, bool> >(),
              select1st<pair<string, bool> >()));

answered Jan 05 '11 at 23:29

ephemient

198,619
38
280
391

2

Note that `select1st` is not part of the C++ Standard Library. – James McNellis Jan 05 '11 at 23:33
Mmm. Luckily, it's trivial to write: `template struct select1st : public unary_function { const typename T::first_type& operator()(const T& x) const {return x.first;} };` – ephemient Jan 05 '11 at 23:48

score 0 · Answer 5 · answered Aug 30 '21 at 11:06

You don't need to provide any compare function since by default since the sort() function will sort vector in ascending order of values. As each element is a pair, so one pair will be smaller than other one if the first value of one pair is smaller than that for other pair.

vector<pair<string,int>>v;
v = {{"xyz",1},{"pq",2}};   // Sample input
sort(v.begin(),v.end());    // Requires #include<algorithm> header

Sorting a std::vector> by the string?

5 Answers5

Linked

Related