Можно ли построить бесконечную строку?

Question

Есть ли какая-либо реальная последовательность символов, которая всегда сравнивается больше, чем любая другая строка?

Моя первая мысль была о том, что строка построена следующим образом:

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

сделать бы трюк, при условии, что тот факт, что это почти определенно не в состоянии работать не такая большая проблема. Поэтому я предполагаю, что такого рода хакерство может быть достигнуто только в Юникоде, если это может быть достигнуто вообще. Я никогда не слышал ничего, что указывало бы на то, что это действительно возможно, но я тоже не слышал, что это не, и мне любопытно.

Любые мысли о том, как достичь этого без possibly_infinite<basic_string<T>>?

Answer 1

Я предполагаю, что вы сравниваете строки, используя их значение символа. То есть один символ действует как цифра, более длинная строка больше короткой строки и т. д.

Есть ли какая-либо действительная последовательность символов, которая всегда сравнивается больше, чем любая другая строка?

Нет, потому что:

1. Давайте предположим, что есть строка s что всегда больше, чем любая другая строка.
2. Если вы сделаете копию с, копия будет равна s. Равный означает «не больше». Следовательно, может быть строка, которая не превышает с.
3. Если вы делаете копию s и добавляете один символ в конце, он будет больше, чем оригинал s.Следовательно, может быть строка, которая больше s.
4. Это означает, что невозможно сделать s.

I.e.

Строка s, которая всегда больше, чем любая другая строка, не может существовать. Копия s (копия == другая строка) будет равна s, а «equal» означает «не больше».
Строка s, которая всегда больше или равна любой другой строке, может существовать, если максимальный размер строки имеет разумный предел. Без ограничения по размеру можно будет взять копию s, добавить один символ в конце и получить строку, которая больше s.

На мой взгляд, правильным решением было бы ввести какой-то специальный строковый объект, представляющий бесконечно большую строку, и написать оператор сравнения для этого объекта и стандартной строки. Кроме того, в этом случае вам может понадобиться собственный класс строк.

Можно сделать строку, которая всегда меньше или равна любой другой строке. Строка нулевой длины будет точно такой, что всегда меньше, чем что-либо еще, и равна другим строкам нулевой длины.

Или вы могли бы написать контр-интуитивную процедуру сравнения, где более короткая строка больше длинной строки, но в этом случае следующий поддерживающий код будет вас ненавидеть, поэтому это не очень хорошая идея.

Не знаете, зачем вам когда-нибудь понадобилось что-то подобное.

Answer 2

Возможно, вам нужен пользовательский компаратор, для которого вы определяете значение «бесконечной строки» магии и которое всегда будет рассматривать это значение как большее, чем любое другое.

Answer 3

Если вам нужна искусственная привязка в пространстве объектов, то не является ограниченным, стандартный трюк заключается в добавлении дополнительного элемента и определении нового оператора сравнения, который обеспечивает ваше свойство.

Или реализовать ленивые строки.

Answer 4

Хорошо, если бы вы динамически построили строку равной длины, сравнимую с ней и заполнили ее самым высоким доступным кодом ASCII (7F для обычного ASCII или FF для расширенного), вам гарантируется, что эта строка будет сравнивать равную или большую, чем та, с которой вы сравниваете ее.

Answer 5

Какой у вас компаратор?

Исходя из этого, вы можете построить что-то, что является «вершиной» вашей решетки.

Answer 6

Unicode решает много проблем, но не тот. Unicode - это просто другая кодировка для символа, 1, 2 или 4 байта, они все еще хранятся в простом массиве. Вы можете использовать бесконечные строки, когда найдете машину с бесконечной памятью.

Answer 7

Yes. Как вы это делаете, я понятия не имею :)

Answer 8

Вы должны попытаться указать, чего вы намереваетесь достичь и каковы ваши требования. В частности, есть строка? есть any ограничение на домен? их нужно сравнивать с <?

Вы можете использовать тип нестроковой:

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

Если вы можете использовать std::lexicographical_compare и вам не нужно хранить его в виде строки, то вы можете написать бесконечный итератор:

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

Если вы можете использовать любой другой comparisson функтор и ваш домен имеет некоторые недействительны вы можете использовать это в свою пользу:

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