Thread: Longest and Shortest String

Originally Posted by phantomotap

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;
}

Originally Posted by esbo

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;
}

Originally Posted by laserlight

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;
}

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

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