Longest and Shortest String

This is a discussion on Longest and Shortest String within the C++ Programming forums, part of the General Programming Boards category; Originally Posted by phantomotap Code: copy(issi(cin), issi(), bi(data)); sort(data.begin(), data.end(), [](const string & l, const string & r) {l.length() < ...

  1. #31
    Registered User
    Join Date
    Jan 2009
    Posts
    10
    Quote Originally Posted by phantomotap View Post
    Code:
    copy(issi(cin), issi(), bi(data));
    sort(data.begin(), data.end(), [](const string & l, const string & r) {l.length() < r.length()});
    copy(data.begin(), data.end(), ossi(cout, "\n"));
    Ctrl + Z in new line?

    Ok. Let me show this code.

    Code:
    #include <iostream>
    #include <iterator>
    #include <algorithm>
    #include <string>
    #include <vector>
    
    using namespace std;
    
    struct CompareString
    {
        bool operator()(const string &l, const string &r)
        {return (l.length() < r.length());}
    };
    
    int main()
    {
        vector<string> data;
    
        copy(istream_iterator<string>(cin), istream_iterator<string>(), back_inserter(data));
        sort(data.begin(), data.end(), CompareString());
        copy(data.begin(), data.end(), ostream_iterator<string>(cout, "\n"));
        return 0;
    }

  2. #32
    Registered User
    Join Date
    Jan 2009
    Posts
    10
    Quote Originally Posted by esbo View Post
    True, but it is not necessary to remember them all, just the longest and shortest
    Ok. Without vector.
    Code:
    int main()
    {
        string shortest, str, longest;
        cin >> shortest;
        while(cin >> str)
        {
            if(str < shortest) shortest = str;
            if(str > longest) longest = str;
        }
        cout << shortest << endl << longest << endl;
        return 0;
    }

  3. #33
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,632
    Eh, Viewer, your second example compares strings, not the lengths of the strings, though it will still result in a correct answer, but possibly with unnecessary copying.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #34
    Registered User
    Join Date
    Jan 2009
    Posts
    10
    Quote Originally Posted by laserlight View Post
    Eh, Viewer, your second example compares strings, not the lengths of the strings, though it will still result in a correct answer, but possibly with unnecessary copying.
    I see my error.
    Code:
    int main()
    {
        string shortest, str, longest;
        cin >> shortest;
        while(cin >> str)
        {
            if(str.length() < shortest.length()) shortest = str;
            if(str.length() > longest.length()) longest = str;
        }
        cout << shortest << endl << longest << endl;
        return 0;
    }

  5. #35
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,230
    Eh, Viewer, your second example compares strings, not the lengths of the strings, though it will still result in a correct answer, but possibly with unnecessary copying.
    ^_^

    I may be wrong. It has been a very long time since I looked at any 'std::string' implementations.

    This should be efficient enough...

    Soma

    Code:
    int main()
    {
        string shortest, str;
        cin >> shortest;
        string longest(shortest);
        while(cin >> str)
        {
            if(str.length() < shortest.length()) swap(shortest, str);
            if(str.length() > longest.length()) swap(longest, str);
        }
        cout << shortest << endl << longest << endl;
        return 0;
    }
    Last edited by phantomotap; 01-31-2009 at 01:29 PM.

  6. #36
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,632
    Quote Originally Posted by phantomotap
    I may be wrong. It has been a very long time since I looked at any 'std::string' implementations.
    No need to look though, since swap is guaranteed constant time complexity.

    EDIT:
    Quote Originally Posted by phantomotap
    This should be efficient enough...
    But then the string comparison would still take linear time, as opposed to the constant time comparison of string lengths.
    Last edited by laserlight; 01-31-2009 at 01:34 PM.

  7. #37
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,484

    Cool

    Quote Originally Posted by phantomotap View Post
    ^_^

    I may be wrong. It has been a very long time since I looked at any 'std::string' implementations.

    This should be efficient enough...

    Soma

    Code:
    int main()
    {
        string shortest, str;
        cin >> shortest;
        string longest(shortest);
        while(cin >> str)
        {
            if(str.length() < shortest.length()) swap(shortest, str);
            iif(str.length() > longest.length()) swap(longest, str);
        }
        cout << shortest << endl << longest << endl;
        return 0;
    }
    This sample once again compares strings instead of lengths
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  8. #38
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,230
    But then the string comparison would still take linear time, as opposed to the constant time comparison of string lengths.
    ^_^

    Uh, LL, mate, if that is the only off bit you noticed before my second edit, you really need to practice more.

    This sample once again compares strings instead of lengths
    ^_~

    I'm pretty sure that it doesn't. (For everyone else, before my second edit this was true.)

    Soma

  9. #39
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,632
    Quote Originally Posted by phantomotap
    Uh, LL, mate, if that is the only off bit you noticed before my second edit, you really need to practice more.
    Considering that you were the one making the mistakes... you really need to practice more
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #40
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,230
    Considering that you were the one making the mistakes... you really need to practice more
    ^_^

    Nah.

    The bug isn't that I was wasting time using a linear comparison when a constant comparison was available. (I was, but that's not the bug; it was only stupid.)

    I foolishly took you at your word.

    though it will still result in a correct answer
    Comparison of the 'std::string' objects should result in lexicographic ordering and not length ordering.

    No need to look though, since swap is guaranteed constant time complexity.
    About this, I know that 'std::swap' is of constant complexity. That doesn't impose any requirement on the underlying assignment operation.

    Basically, I didn't "just know" that 'std::swap' was specialized to swap the internal state of 'std::string' or if it would result in three assignments.

    That's just what you get when you avoid the STL for your own work.

    I'm assuming that 'std::swap' is then required to forward to 'std::string::swap'? (I don't have the standard. I don't actually care. I just thought having the answer would be nice for others reading the thread.)

    Soma

  11. #41
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,632
    Quote Originally Posted by phantomotap
    I foolishly took you at your word.
    That's true. On the other hand, if I were working on the code myself, a little routine testing would have discovered the bug, assuming that I did not fix it even before testing.

    EDIT:
    Quote Originally Posted by phantomotap
    I'm assuming that 'std::swap' is then required to forward to 'std::string::swap'?
    Yes, though I say this from what I remember, not from what I checked.
    Last edited by laserlight; 01-31-2009 at 08:15 PM.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Page 3 of 3 FirstFirst 123
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. text processing assignment
    By nellosmomishot in forum C Programming
    Replies: 28
    Last Post: 11-25-2008, 02:56 PM
  2. working on a string tough string prog, need help
    By Brokn in forum C Programming
    Replies: 1
    Last Post: 11-13-2005, 03:14 PM
  3. using strlen and finding shortest and longest words
    By Unregistered in forum C Programming
    Replies: 7
    Last Post: 09-30-2001, 06:09 PM
  4. length of string etc.
    By Peachy in forum C Programming
    Replies: 5
    Last Post: 09-27-2001, 12:04 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21