Sorting vector of string pointers

Question

I'm sorry if this has already been asked somewhere, but I haven't been able to find an answer to what I'm looking for.

I have a vector of std::string pointers, that I want to sort in alphabetical order, and I haven't been able to figure out how to do this. I am using std::sort.

I wrote up a quick program to test out what I was trying to do (since in the actual implementation, my code is being run in a child process, so it's kind of hard to debug):

#include <string>
#include <algorithm>
#include <vector>
#include <string.h>

bool cmpStrPtrs(std::string *a, std::string *b) {
  std::string a1 = *a;
  std::string a2 = *b;
  if(a1 == a2) return 0;
  return a1 > a2 ? 1 : -1;
}

int main(int argc, char *argv[]) {
  std::vector<std::string *> vec;
  std::string *str1 = new std::string("AAAAA");
  std::string *str2 = new std::string("aaaaa");
  std::string *str3 = new std::string("xxxxx");
  std::string *str4 = new std::string("bfuen");
  std::string *str5 = new std::string("xylophone");
  vec.push_back(str1);
  vec.push_back(str2);
  vec.push_back(str3);
  vec.push_back(str4);
  vec.push_back(str5);

  std::sort(vec.begin(), vec.end(), cmpStrPtrs);
  for(std::string *str : vec) {
    printf("%s\n", str->c_str());
  }
  return 0;
}

When I run this, I get this output:

$ ./strsort
xylophone
bfuen
xxxxx
aaaaa
AAAAA

This doesn't seem to be in any sort of alphabetical order at all, so I can assume that I'm either using sort() wrong or there's something wrong with my comparator function. I also tried it without a comparator function and I think that's just ordering them based on their memory locations from least to greatest, which doesn't actually change anything. I also tried using

bool cmpStrPtrs(std::string *a, std::string *b) {
  return a->compare(*b);
}

but it gave me the same result.

If it's relevant, I'm compiling with g++ using the c++17 standard.

Using new is non-idiomatic C++. Your comparison function is wrong too (let's start with "you're returning an int from a function that was supposed to return bool") Also see en.cppreference.com/w/cpp/concept/Compare — milleniumbug
– milleniumbug, Commented Mar 7, 2018 at 0:05
I do not recommend returning -1, 0, +1 in a function marked as returning bool — user4581301
– user4581301, Commented Mar 7, 2018 at 0:05
Are you sure you want vector<string*> and not just vector<string>? I don't see what value the extra indirection adds. — Dai
– Dai, Commented Mar 7, 2018 at 0:05

Community · Accepted Answer · 2020-06-20 09:12:55Z

4

std::string::compare returns an int, not a bool. According to cppreference.com the return value is

negative value if *this appears before the character sequence specified by the arguments, in lexicographical order

zero if both character sequences compare equivalent

positive value if *this appears after the character sequence specified by the arguments, in lexicographical order strong text

The returned value is cast to bool which evaluates to true for all non-zero values. That means that your function returns true for every non-identical pair of strings.

The C++ standard actually defines operator< for strings so you can change your function to

bool cmpStrPtrs(std::string *a, std::string *b) {
    return *a < *b;
}

But that still leaves a big issue in your code. You absolutely do not need pointers for this. In fact, you are leaking memory right now because you neglect to delete them. The proper tool for this job is std::vector<std::string>. This has the added benefit that without the extra level of indirection, std::sort can implicitly call operator< without a helper function, leading to the following solution.

std::vector<std::string> vec;
vec.emplace_back("AAAAA");
vec.emplace_back("aaaaa");
vec.emplace_back("xxxxx");
vec.emplace_back("bfuen");
vec.emplace_back("xylophone");

std::sort(vec.begin(), vec.end());

edited Jun 20, 2020 at 9:12

CommunityBot

11 silver badge

answered Mar 7, 2018 at 0:15

patatahooligan

3,3811 gold badge21 silver badges28 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Andrew Graber Over a year ago

Wow, I feel like such an idiot. I can't believe I didn't notice I wasn't returning a bool. Was just kind of on autopilot from writing so many java comparison functions for my algorithms class last year. Thank you!

Andrew Graber Over a year ago

Also, you're right that my code has problems, but the reason I'm using string pointers rather than just strings is that the underlying structure of the application requires them to be pointers. This was just a quick example I whipped up to test out what I was trying to do, not the actual implementation. Don't worry, in the actual code, they're getting deleted.

patatahooligan Over a year ago

@AndrewGraber Why does it have to be pointers? Is it just because they shouldn't be copies or is there a more restricting reason?

Robinson · Accepted Answer · 2018-03-07 00:10:35Z

2

You can do it with a lambda:

std::sort(vec.begin(), vec.end(), [](std::string * a, std::string * b) {
    return *a < *b;    
  });

answered Mar 7, 2018 at 0:10

Robinson

10.2k16 gold badges81 silver badges121 bronze badges

Comments

Stack Exchange Broke The Law · Accepted Answer · 2018-03-07 00:13:04Z

2

Your comparison function is meant to simulate the less-than operator - that means it should return true if a comes before b. Your current implementation returns true if a doesn't equal b.

You have:

if(a1 == a2) return 0;
return a1 > a2 ? 1 : -1;

which should be:

if(a1 == a2) return false;
return a1 > a2 ? false : true;

or just:

return a1 < a2;

answered Mar 7, 2018 at 0:13

Stack Exchange Broke The Law

59.2k7 gold badges57 silver badges103 bronze badges

Comments

user4581301 · Accepted Answer · 2018-03-07 00:22:25Z

std::sort expects Strict Weak Ordering. It doesn't give a crap about equals; it only cares about before and after.

The comparison function should return true if the right hand side goes before left hand side. Unfortunately in

bool cmpStrPtrs(std::string *a, std::string *b) {
  std::string a1 = *a;
  std::string a2 = *b;
  if(a1 == a2) return 0;
  return a1 > a2 ? 1 : -1;
}

bool is true for any value that is not 0. This means that both greater than and less than are true. This makes logical ordering pretty much impossible because greater than and less than go before.

Improvement cut 1: return bool based on lexicographic (alphabetical) ordering. String already implements a less than operator that does exactly what you want. Let's use it.

bool cmpStrPtrs(std::string *a, std::string *b) {
  std::string a1 = *a;
  std::string a2 = *b;
  return a1 < a2;
}

Improvement cut 2: std::string a1 = *a; creates a brand new string that is a copy of the original. Since you have a pointer to the original you can dereference the pointer and use the original. No need for the copy.

bool cmpStrPtrs(std::string *a, std::string *b) {
  return *a < *b;
}

Collectives™ on Stack Overflow

Sorting vector of string pointers

4 Answers 4

3 Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

3 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related