Is it possible to construct an "infinite" string?

Question

Is there any real sequence of characters that always compares greater than any other string?

My first thought was that a string constructed like so:

std::basic_string<T>(std::string::max_size(), std::numeric_limits<T>::max())

Would do the trick, provided that the fact that it would almost definitely fail to work isn't such a big issue. So I presume this kind of hackery could only be accomplished in Unicode, if it can be accomplished at all. I've never heard of anything that would indicate that it really is possible, but neither have I heard tell that it isn't, and I'm curious.

Any thoughts on how to achieve this without a possibly_infinite<basic_string<T>>?

Answer 1

You probably need a custom comparator, for which you define a magic "infinite string" value and which will always treat that value as greater than any other.

Answer 2

if you need an artificial bound within a space of objects that isn't bounded, the standard trick is to add an extra element and define a new comparison operator that enforces your property.

Or implement lazy strings.

Answer 3

Well if you were to dynamically construct a string of equal length as the one that you are comparing to and fill it with the highest ASCII code available (7F for normal ASCII or FF for extended) you would be guaranteed that this string would compare equal to or greater than the one you compare it to.

Answer 4

What's your comparator?

Based on that, you can construct something that is the 'top' of your lattice.

Answer 5

Unicode solves a lot of problems, but not that one. Unicode is just a different encoding for a character, 1, 2 or 4 bytes, they are still stored in a plain array. You can use infinite strings when you find a machine with infinite memory.

Answer 6

I assume that you compare strings using their character value. I.e. one character acts like a digit, a longer string is greater than shorter string, etc.

s there any real sequence of characters that always compares greater than any other string?

No, because:

1. Let's assume there is a string s that is always greater than any other string.
2. If you make a copy of s, the copy will be equal to s. Equal means "not greater". Therefore there can be a string that is not greater than s.
3. If you make a copy of s and append one character at the end, it will be greater than original s. Therefore there can be a string that is greater than s.
4. Which means, it is not possible to make s.

I.e.

A string s that is always greater than any other string cannot exist. A copy of s (copy == other string) will be equal to s, and "equal" means "not greater".
A string s that is always greater or equal to any other string, can exist if a maximum string size has a reasonable limit. Without a size limit, it will be possible to take a copy of s, append one character at the end, and get a string that is greater than s.

In my opinion, the proper solution would be to introduce some kind of special string object that represents infinitely "large" string, and write a comparison operator for that object and standard string. Also, in this case you may need custom string class.

It is possible to make string that is always less or equal to any other string. Zero length string will be exactly that - always smaller than anything else, and equal to other zero-length strings.

Or you could write counter-intuitive comparison routine where shorter string is greater than longer string, but in this case next code maintainer will hate you, so it is not a good idea.

Not sure why would you ever need something like that, though.

Answer 7

Yes. How you do it, I have no idea :)

Answer 8

You should try to state what you intend to achieve and what your requirements are. In particular, does it have to be a string? is there any limitation on the domain? do they need to be compared with <?

You can use a non-string type:

struct infinite_string {};
bool operator<( std::string const & , infinite_string const & ) {
   return true;
}
bool operator<( infinite_string const &, std::string const & ) {
   return false;
}

If you can use std::lexicographical_compare and you don't need to store it as a string, then you can write an infinite iterator:

template <typename CharT>
struct infinite_iterator
{
   CharT operator*() { return std::numeric_limits<CharT>::max(); }
   infinite_iterator& operator++() { return *this; }
   bool operator<( const infinite_iterator& ) { return true; }
   // all other stuff to make it proper
};
assert( std::lexicographical_compare( str.begin(), str.end(), 
                              infinite_iterator, infinite_iterator ) );

If you can use any other comparisson functor and your domain has some invalid you can use that to your advantage:

namespace detail {
   // assume that "\0\0\0\0\0" is not valid in your domain
   std::string const infinite( 5, 0 ); 
}
bool compare( std::string const & lhs, std::string const & rhs ) {
   if ( lhs == detail::infinite ) return false;
   if ( rhs == detail::infinite ) return true;
   return lhs < rhs;
}