How does strings comparison in C++ work?

Question

I am trying to solve this problem.

I am implementing it with strings. Here is my code snippet

string s,ss;
// s and ss both contains integer input.

while(s <= ss )
//while( s<=ss && s.size() <= ss.size())
{
    int i = inc, j = dec;   // inc and dec are middle values. both equal if odd else different

    while((s[j]-'0')==9 && i < len && j>=0){
        // for cases like 999
        s[i] = s[j] = '0';
        i++;
        j--;
    }
    if(j<0){
        s = "1" + s;
        int l = s[len-1] - '0';
        l++;
        //cout<<l<<"\n";
        s[len] = (l + '0');
    }
    else{
        int l = s[j] - '0';
        l++;
        s[i] = s[j] = (l+'0');
    }

    if(s <= ss)
        cout<<"out in wild "<<s<<" and "<<ss<<"\n";
}

cout<<s<<endl;

The problem that I am facing is when input is like 999 or 9999. The outer while loop keeps on looping even when the value of s increases, but if I add while( s<=ss && s.size() <= ss.size()) it works completely fine. Why is while(s<=ss) is not working? I rarely use the string class, so I don't understand it completely. Why don't string s= 101 and ss=99 stop the while loop?

Complete code link is here

It uses a lexicographical comparison, as [any reference](http://en.cppreference.com/w/cpp/string/basic_string/operator_cmp) would tell you. `"101"` is "less" than `"99"`. — chris, Aug 15 '14 at 14:31
string compare is lexicographical, so "101" is less than "99" because "1" precedes "9". — CashCow, Aug 15 '14 at 14:33
One suggestion, you can improve your code by using some meaningful variable names instead of `s`, `l`, `ss`. — Eric Z, Aug 15 '14 at 14:33

score 4 · Answer 1 · edited Jun 20 '20 at 09:12

You are comparing strings with lexicographical order, not numbers , so "101" is less than "99" (because '1' < '9') , e.g.

int main(){
    std::string s = "99";
    std::string ss = "101";
    
    std::cout << std::boolalpha << (s <= ss);  
}

Outputs false.

Notes:

A better design for your program would be to manipulate numbers (int or double ...) and not strings in the first place, so this kind of expressions would naturally work as you expect.

E.g. "101" + "99" is "10199", not "200" ...
But if you really need strings, consider this post to sort strings containing numbers.
As pointed by @Deduplicator, a program that needlessly overuses strings is sometimes called Stringly Typed
Also see std::lexicographical_compare

Since your input explicitly only involves positive integers without leading 0, writing a comparison function is trivial, something like : (untested)

/* Returns 1 if the integer represented by s1 > the integer represented by s2
*  Returns -1 if the integer represented by s1 < the integer represented by s2
*  Return 0 is both are equals
*
*  s1 and s2 must be strings representing positive integers without trailing 0
*/
int compare(const std::string& s1, const std::string& s2)
{
  if(s1.size() > s2.size())
      return 1;
  if(s2.size() > s1.size())
      return -1;
      
  for(std::size_t i = 0 ; i < s1.size() ; ++i)
  {
    if(s1[i] - '0' < s2[i] - '0')
      return 1;
    if(s2[i] - '0' < s1[i] - '0')
      return -1;
  }
          
  return 0;
}

this question can't be implemented with int or double or any other variables because the input limit is 1000000 digits. I need to use array or string. — anonghost, Aug 15 '14 at 14:56
@anonghost See my second note, I added a link to compare strings containing numbers — quantdev, Aug 15 '14 at 15:00

score 0 · Answer 2 · answered Aug 15 '14 at 14:46

0

While s and ss are string variables, they are compared character by character.

In the case that you mentioned being: s = "101" & ss = "99", by first hand it will check the first character in each string, and as '1' < '9' it exit up with s < ss. I would advise you to convert those values to integers before comparison.

answered Aug 15 '14 at 14:46

Odiseo

21
5

thank you for explaining it in such a simple way. I think in string '1' it will be 49 and for '9' is (48+9) but i get the idea. Some link please. – anonghost Aug 15 '14 at 14:51

score 0 · Answer 3 · answered Aug 15 '14 at 15:07

0

As the s is compared with ss in lexicographical order, I would suggest you to compare one char from tail with one char from head (one by one till you reach the middle) to solve that problem.

answered Aug 15 '14 at 15:07

c000p

43
8

How does strings comparison in C++ work?

3 Answers3