C++ - Sorting strings in a vector in a specific way

Question

I'm currently attempting to sort strings in a vector, but I'm unsure on how to go about doing it a specific manner. The game engine I am working with requires strings to be sorted case-insensitively (which I have been able to accomplish). It also sorts these file names with underscores coming before letters.

For example, these strings are currently sorted as follows:

ChallengeBattleships.bsf
ChallengeBattleships.zip
ChallengeBattleshipsPause.bsf
ChallengeBattleshipsSummary.bsf
ChallengeBattleshipsSurface.bsf
ChallengeBattleships_arena.bsf
ChallengeBattleships_day.zip

But I need them to be sorted like this (as well as case-insensitively):

ChallengeBattleships.bsf
ChallengeBattleships.zip
ChallengeBattleships_arena.bsf
ChallengeBattleships_day.zip
ChallengeBattleshipsPause.bsf
ChallengeBattleshipsSummary.bsf
ChallengeBattleshipsSurface.bsf

Would anyone happen to know how to sort strings in a vector in this manner?

[`std::sort`](https://en.cppreference.com/w/cpp/algorithm/sort). Always `std::sort`. Then use a suitable [lambda](https://en.cppreference.com/w/cpp/language/lambda) for the comparisons. — Some programmer dude, Dec 07 '20 at 08:44
Besides that, why do you need to sort this list of file-names? Why is the order you want them in special, what problem is that ordering supposed to solve? — Some programmer dude, Dec 07 '20 at 08:46
One possibility is to create pairs of strings, the first part correspondind to the name before the underscore, and the second part after. Then to sort the original strings with the help of these pairs and the help of a dedicated lambda function — Damien, Dec 07 '20 at 08:48
[`std::sort`](https://en.cppreference.com/w/cpp/algorithm/sort) does the thing you want. If it doesn't meet your requirements, you should give the rules of sorting or you need to create your own. — Akib Azmain Turja, Dec 07 '20 at 09:33
@Someprogrammerdude The game I'm modding is oddly picky about the order in which these strings are listed in the file archive I'm creating. I realized this when I had generated an archive from files I had on an external drive. For some reason these files ended up being sorted correctly (perhaps by date of creation? These files were dumped sequentially from one of the game's original file archives). When I tried to add new files to the archive, these files were put at the end of the list regardless of their names. The game wouldn't load the new files so I figured that string order was important — MasterMinya, Dec 08 '20 at 00:22

Cedric · Answer 1 · 2020-12-07T10:04:58.253

What you are asking for is a custom lexicographical ordering. One possibility would be to use the lexicographical comparison helper in #include <algorithm> which accepts custom comparators. E.g. something that loves underscores above all else :

#include <algorithm>
#include <iostream>

namespace {
std::vector<std::string> names = {
  "ChallengeBattleships_day.zip",
  "ChallengeBattleships.bsf",
  "ChallengeBattleshipsSummary.bsf",
  "ChallengeBattleshipsPause.bsf",
  "ChallengeBattleships_arena.bsf",
  "ChallengeBattleships.zip",
  "ChallengeBattleships_day.zip",
  "ChallengeBattleshipsSurface.bsf"
};

// custom char ordering
bool UnderscoreSupporter(char lhs, char rhs) {
  if (lhs == rhs) return false;
  if (lhs == '_') return true;  // '_' is smaller than everything !
  if (rhs == '_') return false; // nothing is smaller than '_' !
  
  return (lhs < rhs); // default lexicographical ordering
}
}

int main()
{

  std::cout << "Original order: " << std::endl;
  for (const auto& str : names) std::cout << str << std::endl;
  std::cout << std::endl;

  // lambda to compare strings using our custom ordering
  auto sorting_fct = [](const std::string& s1, const std::string& s2) {
    return std::lexicographical_compare(s1.cbegin(), s1.cend(), s2.cbegin(), s2.cend(), UnderscoreSupporter);
  };

  // sort names based on that lambda
  std::sort(names.begin(), names.end(), sorting_fct);

  std::cout << "New order: " << std::endl;
  for (const auto& str : names) std::cout << str << std::endl;
  std::cout << std::endl;

  return 0;
}

I'll let you add the "ignore case" part, but that should be straight forward using e.g. tolower from <cctype>.

TKA · Accepted Answer · 2020-12-07T13:17:11.497

2

Use std::sort with lambda. If original strings are not to be modified then:

std::sort(vec.begin(), vec.end(), 
         [](std::string s1, std::string s2){
             std::transform(s1.begin(), s1.end(), s1.begin(),
                   [](char c){ return std::tolower(c); });
             std::transform(s2.begin(), s2.end(), s2.begin(),
                   [](char c){ return std::tolower(c); });
             return s1 < s2;
         });

To change case: How to convert std::string to lower case?

edited Dec 07 '20 at 13:17

answered Dec 07 '20 at 13:07

TKA

183
2
4

What about the '_'? – Surt Dec 07 '20 at 13:41
- tolower method will leave underscore as it is. And since underscore ASCII value is lower than all alphabets it will be sorted first w.r.t. anything at that position in the strings. – TKA Dec 07 '20 at 14:07
Ah, underscore is a lower ASCII than the small letters, but not the Capital letters therefor it works for the `tolower` case. – Surt Dec 07 '20 at 15:25

C++ - Sorting strings in a vector in a specific way

2 Answers2