代码之家  ›  专栏  ›  技术社区  ›  Jon Purdy

是否可以构造一个“无限”字符串?

  •  3
  • Jon Purdy  · 技术社区  · 14 年前

    是否有任何实际的字符序列总是比任何其他字符串都大?

    我的第一个想法是一根这样的绳子:

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

    如果它几乎肯定会失效的事实不是那么大的问题。所以我假设这种黑客只有在Unicode中才能完成,如果完全可以完成的话。我从来没有听说过任何能表明这是真的 可能,但我也没听说过 不是 我很好奇。

    关于如何在没有 possibly_infinite<basic_string<T>> ?

    8 回复  |  直到 14 年前
        1
  •  3
  •   SigTerm    14 年前

    我假设您使用字符串的字符值比较字符串。也就是说,一个字符就像一个数字,一个较长的字符串比较短的字符串大,等等。

    是否有任何真正的字符序列总是比任何其他字符串都大?

    不,因为:

    1. 假设有一个字符串 S 它总是大于任何其他字符串。
    2. 如果你复制了 S ,副本将等于 S . 等于表示“不大于”。因此,可以有一个不大于 S .
    3. 如果你复制了 S 并在结尾附加一个字符,它将大于原始字符 S . 因此,可以有一个大于 S .
    4. 也就是说,不可能 S .

    即。

    一串 S 总是大于任何其他字符串都不存在。一份 S (copy==其他字符串)将等于 S ,和“相等”是指“不大于”。
    一串 S 如果最大字符串大小有合理限制,则可以存在大于或等于任何其他字符串的值。如果没有大小限制,则可以复制 S ,在结尾附加一个字符,并获取一个大于 S .

    在我看来,正确的解决方案应该是引入某种特殊的字符串对象来表示无限大的字符串,并为该对象和标准字符串编写一个比较运算符。此外,在这种情况下,您可能需要自定义字符串类。

    可以使字符串始终小于或等于任何其他字符串。长度为零的字符串将完全相同-总是小于任何其他字符串,并且等于其他长度为零的字符串。

    或者您可以编写一个反直觉的比较例程,其中较短的字符串大于较长的字符串,但在这种情况下,下一个代码维护人员会讨厌您,所以这不是一个好主意。

    但不知道为什么你会需要这样的东西。

        2
  •  2
  •   JSBÕ±Õ¸Õ£Õ¹    14 年前

    您可能需要一个定制的比较器,为此您定义了一个神奇的“无限字符串”值,并始终将该值视为大于任何其他值。

        3
  •  2
  •   Hans Passant    14 年前

    Unicode解决了很多问题,但不是那个问题。Unicode只是一个字符(1、2或4字节)的不同编码,它们仍然存储在一个普通数组中。当您找到具有无限内存的机器时,可以使用无限字符串。

        4
  •  2
  •   Xodarap    14 年前

    Yes . 你怎么做的,我不知道:)

        5
  •  1
  •   David Rodríguez - dribeas    14 年前

    你应该试着陈述你打算达到什么,你的要求是什么。特别是,是吗 成为一根绳子?有 任何 对域名的限制?它们需要与 < ?

    可以使用非字符串类型:

    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;
    }
    
        6
  •  0
  •   vlabrecque    14 年前

    如果你需要在一个物体空间内进行人工绑定, 不是 有界的,标准的技巧是添加一个额外的元素并定义一个新的比较运算符来强制您的属性。

    或者实现惰性字符串。

        7
  •  0
  •   Josiah    14 年前

    好吧,如果你要动态地构造一个长度与你要比较的字符串相同的字符串,并用可用的最高的ASCII码填充它(对于普通的ASCII码为7F,对于扩展码为FF),你就可以保证这个字符串与你要比较的字符串相等或更大。

        8
  •  0
  •   Paul Nathan    14 年前

    你的比较器是什么?

    基于这一点,你可以构建一个格子的“顶部”。