CODEWITHSUNDEEP
c++stringsortingint
Gundown64
Gundown64

Reputation: 103

Sorting a vector of ints that have been converted into strings

So I am needing to sort a vector of strings in numerical order. I am using the sort function and it almost works. Say I have the numbers 10, 20, 5, 200, 50, 75 that have been converted to strings. The sort function sorts them like so: 10, 200, 25, 5, 50, 75. So it is only sorting the first character I suppose? Is there an easy way to get it to sort more than the first character? And yes, they must be converted to strings for my particular use.

Thanks!

Upvotes: 0

Views: 107

Answers (3)

shawn1874
shawn1874

Reputation: 1451

Can you use a standard map instead?

// now since map is already sorted by keys, you look up on the integer to get the equivalent string.
std::map<int, string> integersAndStrings;
integersAndStrings[1] = "one";
integersAndStrings[2] = "two";
integersAndStrings[3] = "three";

You could also write a variant of 40two's example. Instead of stoi, you can just make your own predicate to compare the characters. If lhs has fewer digits than rhs, lhs must be a smaller number (assuming no floating point); if same number of digits than compare the strings (i.e., what David Rodriguez showed you in his answer). I didn't notice that he had already suggested that when I wrote my answer. The only additional thing that I am adding is really the suggestion of using another container (i.e., std::map).

Upvotes: 0

David Rodr&#237;guez - dribeas
David Rodr&#237;guez - dribeas

Reputation: 208353

The question is really why you want to sort this after it became a vector of strings and not before that.

The simplest way to sort a vector of strings holding ints might be to convert it to ints, sort that and then convert back to strings into the first vector... which in your case could be more efficient if you did not convert to strings in the first place.

Regarding the suggestion to convert to int on the fly inside the comparator, that is going to be expensive. Comparing int is trivial compared with the process of conversion from string to int. Sorting is O(N log N) (expected) number of comparisons, if you convert on the fly you will be doing O(N log N) conversions, if you convert once you will do O(N) conversions and O(N log N) trivial int compares.

You can also handcraft an algorithm to do the comparison. If you can assume that all values are positive and there are no leading zeros, a number, represented as a string, is larger than any other number represented as a string with a shorter length. You could use that to build a comparisson function:

struct Compare {
    bool operator()(std::string const & lhs, std::string const & rhs) const {
        return lhs.size() < rhs.size()
            || (lhs.size() == rhs.size() && lhs < rhs);
    }
};

If there can be leading zeros, it is simple to find how many leading zeroes and adjust the size accordingly inside the comparator. If the numbers can be negative you can further extend the comparator to detect the sign and then apply something similar to the comparisson above.

Upvotes: 2

Dimitrios Bouzas
Dimitrios Bouzas

Reputation: 42909

Look the following piece of code:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

int main()
{
  std::vector<std::string> v {"123", "453", "78", "333"};
  std::sort(std::begin(v), std::end(v), [] (std::string const &A, std::string const &B) { return std::stoi(A) < std::stoi(B);});

  for(auto i : v) std::cout << i << std::endl;
}

Upvotes: 3

Related Questions