problem with sort function <algorithm> lib

[martin619]

Hi everyone! 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 would like to use “sort” function from library <algorithm> but I have problem with that.. 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;
}

[JLBorges]

Write a comparison function (a binary predicate) to compare two integers as per the specification. Then use the three-parameter version of sort and pass the predicate as the third argument.
See: http://en.cppreference.com/w/cpp/algorithm/sort
http://www.cplusplus.com/articles/NhA0RXSz/

Spoiler: http://coliru.stacked-crooked.com/a/b971abf5df878a0c

[mutexe]

why this:
vector<vector<int> > vec;

and not just this:
vector<int> vec;

?

edit:
explain this output please:

Expected output:
12
13
4
123
27
36

why is 4 in between 13 and 123?
and where is 6?? it's in your example input so where's that gone?

[dhayden]

Another approach:
Notice that you don't need the original values as numbers at all. In fact, since you need to use lexigraphical order to break ties (e.g., "13" < "4"), it's more convenient to consider the input as strings.

I'd create a class that stores the input as a string, and the sum of digits as a number. A constructor can compute the sum of digits of the string. Finally, add a less-than operator to compare as per the requirements:

class FunnyNum {
public:
    FunnyNum(const std::string &str); // computes sumOfDigits
    bool operator < (const FunnyNum &rightHandSide) const;
    const std::string &getval() { return val; }
private:
    std::string val;
    unsigned sumOfDigits;
};

The advantage of this method over JLBorges's is that the sort will run faster since the sum of digits is pre-computed. The disadvantage is that it takes more space, again, because the sum of digits is pre-computed.

Once you have the class, you can dump the values into a vector<FunnyNum> and then use the standard sort() algorithm to sort them.

why is 4 in between 13 and 123?

The sum of digits of 4, 13, and 123 are 4, 4, and 6 respectively. Since 4 and 13 tie, they are sorted lexographically (not numerically), so 13 < 4.

and where is 6?? it's in your example input so where's that gone?

Maybe 6 tells how many numbers follow? It's not clear to me. Anyway, if 6 is part of the set of numbers, then I think the correct output is:

12
13
4
123
6
27
36

[JLBorges]

> The advantage of this method over JLBorges's is that the sort will run faster since the sum of digits is pre-computed.
> The disadvantage is that it takes more space, again, because the sum of digits is pre-computed.

The space overhead would come primarily from the extra sizeof(std::string), and the dynamically allocated sequence of characters held by the string.

Validating (portably) that a string holds a valid representation of a number, and reporting and handling errors if it does not, is messy. Essentially, throw from FunnyNum(const std::string &str).

Pre-computing the sum of digits and the key for lexicographic comparisons would be a good idea though, if the cardinality is large and performance (time) is critical. We can do it quite efficiently too, if we have to. (Dynamic memory allocations and string comparisons are not very fast). Something like:

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <iterator>
#include <tuple>
#include <limits>

std::pair<int,int> sum_and_num_digits( int n ) 
{
    if( n < 0 ) return sum_and_num_digits( -n ) ;
    else if( n < 10 ) return { n, 1 } ;
    else 
    {
        const auto p = sum_and_num_digits( n/10 ) ;
        return { p.first + n%10, p.second+1 }; 
    }
}

std::tuple<int,long long,int> make_key_tuple( int n ) // sum of digits, key for lex comparison, number
{
    if( n == 0 ) return std::make_tuple(0,0,0) ;
    
    const auto pair = sum_and_num_digits(n) ;
    long long lex_key = n ;
    static_assert( std::numeric_limits<long long>::digits10 > std::numeric_limits<int>::digits10, "" ) ;
    for( int i = pair.second ; i <= std::numeric_limits<int>::digits10 ; ++i ) lex_key *= 10 ;
    return std::make_tuple( pair.first, lex_key, n ) ;
}

int main()
{
    std::vector< std::tuple<int,long long,int> > seq ;
    for( int n : { 6, 13, 36, 27, 12, 4, 123 } ) seq.push_back( make_key_tuple(n) );
    std::sort( std::begin(seq), std::end(seq) ) ;
    for( const auto& tup : seq ) std::cout << std::get<2>(tup) << ' ' ;
    std::cout << '\n' ;
}

http://coliru.stacked-crooked.com/a/0e405d8ea23744a4