Is it possible to use std::sort to sort by lexicographic order?

Question

My problem looks like this:

1. At the beginning u have to insert an amount of numbers.
2. Next program counts the sum of digits of the number that u inserted in step one.
3. All scores are inserted in vector called vec

The problem is this: At the end of the program all numbers that You inserted in steps 1, must be sorted depends of theirs sums of digits(Sorting in increasing order).

And ATTENTION please! For example if two of numbers(e.g. 123 and 12300) have the same sum of digits you have to sort them by the lexicographic order.

I don't want to create function build by myself but I would like to use “sort” function from library but I have problem with that..Is it possible to use sort function also to sorting by the lexicographic order? Can someone can help me? Example input:

6 
13
36
27
12
4
123

Expected output:

12
13
4
123
27
36

My code:

#include<iostream>
#include<cmath>
#include<string>
#include<vector>
#include<sstream>
#include<algorithm>
using namespace std;

int main()
{
    vector<vector<int> > vec;
    int num;
    int n;
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        cin >> num;
        vector<int> row;

        row.push_back(num);

        //conversion int to string:
        ostringstream ss;
        ss << num;
        string str = ss.str();

        int sum = 0;
        for (int g = 0; g < str.length(); g++){
            int pom = str[g] - '0';
            sum += pom;
        }

        row.push_back(sum);
        vec.push_back(row);
        row.clear();
    }

    //sort(vec[0][0], vec[vec.size()][0]);

    for (int i = 0; i < vec.size(); i++){
        for (int j = 0; j < 2; j++){
            //cout << vec[i][j] << " ";
        }
        cout << vec[i][0] << endl;
    }



    system("pause");
    return 0;
}

Answer 1

You could store each number as a string, but also pre-compute its digit-sum and keep both in a pair<int,string>, then put them into a vector<pair<int,string> and sort it. No need for a custom comparator, the one for std::pair does exactly what you want.

// note: std::pair<std::string,int> would not work
typedef std::pair<int,std::string> number;
std::vector<number> numbers;

// fill numbers such that number::first holds the digit sum
// and number::second the number as string.
// this is similar to your code

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

// now numbers are ordered as you want them

Answer 2

Since you want to compare on sum of digits first and then lexicographically to break ties, it will be convenient to convert your input numbers to strings.

From there you can define a custom comparator to achieve the desired behavior:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int sumDigits(string s)
{
    int sum = 0;
    for (unsigned int i=0; i<s.length(); ++i)
    {
        sum += s[i] - '0';
    }
    return sum;
}

bool digitSumComparator(int i, int j)
{
    int iSum = sumDigits(to_string(i));
    int jSum = sumDigits(to_string(j));
    if (iSum == jSum)
    {
        return iStr < jStr;
    }
    else
    {
        return iSum < jSum;
    }
}

int main()
{
    vector<int> v {6,13,36,27,12,4,123};
    sort(v.begin(), v.end(), digitSumComparator);
    for (vector<int>::iterator it=v.begin(); it!=v.end(); ++it)
    {
        cout <<  *it << ' ';
    }
    cout << '\n';
    return 0;
}

Output:

$ g++ -std=c++11 digitsumsort.cpp
$ ./a.out
12 13 4 123 6 27 36

Answer 3

Just pass a suitable comparison function (or functor, e.g. a lambda would be natural) to std::sort.