How can i sort array/vector by repetition of elements? For example
Input
Leo
Mike
Eric
Leo
Leo
Output _ _ _ Or
Leo Leo
Leo Eric
Leo Mike
Eric
Mike
9
3 Answers
I recommend processing your data in 3 passes:
Use std::sort to get all repeated elements adjacent to each other.
Iterate over your sorted range recording the length and position of each equal_range.
Now you can resort your sequence based on the data you've recovered in step 2. You may consider using stable_search in this phase if you could like a secondary search key to be alphabetical.
Comments
I would have liked to explain this in words and have you write the code, but I'm finding that I'm so familiar with C++ now, that it's a lot easier for me to just write code. Slight variation on what Steve said. Your original vector of strings is v.
std::map<std::string, int> m;
for(auto i=v.begin(); i!=v.end(); ++i)
m[*i]++;
typedef std::pair<std::string, int> P;
auto comp_by_second = [](const P & lhs, const P & rhs) { return lhs.second < rhs.second; };
for(auto i=v.begin(); !m.empty(); )
{
auto j = std::max_element(m.begin(), m.end(), comp_by_second);
while(j->second-- > 0)
*i++ = j->first;
m.erase(j);
}
answered Apr 11, 2011 at 14:45
Benjamin Lindley
104k11 gold badges210 silver badges285 bronze badges
1 Comment
ildjarn
Pedantry Mode On: Your
P typedef is wrong; the value type of a map<K, V> is pair<K const, V>. One technical fix would be to change it to typedef std::pair<std::string const, int> P;, but the preferred route is to use the map's value_type: typedef std::map<std::string, int>::value_type P;, or better yet its const_reference: typedef std::map<std::string, int>::const_reference P; auto comp_by_second = [](P lhs, P rhs) { ... };There's no built-in way to do this. A relatively simple way is to build a map<string, size_t> containing the counts of each element (just iterate over your input vector, incrementing the count for each string you see). Then write all the keys in the map to a vector, and std::sort that vector with a comparator that compares the number from the map.
That involves more map lookups than strictly necessary, so you could instead write a vector of pairs from the map, then sort the pairs, and finally create your vector of strings from the sorted pairs.
Comments
std::sort(data.begin(), data.end());