Comparing STL strings that use different allocators

Solution 1:

Use std::lexicographical_compare for less-than comparison:

bool const lt = std::lexicographical_compare(s1.begin(), s1.end(),
                                             s2.begin(), s2.end());

For equality comparison you can use std::equal:

bool const e = s1.length() == s2.length() &&
               std::equal(s1.begin(), s1.end(), s2.begin());

Alternatively, you can just fall back on strcmp (or actually memcmp, since that has the correct seman­tics; remember that the C++ string is more general than a C string), as you suggested, which can poten­tially employ some lower-level magic like comparing an entire machine word at a time (though the above algorithm may also be specialized thus). Measure and compare, I'd say. For short strings, the standard library algorithms are at least nicely self-descriptive.

Based on @Dietmar's idea below, you could wrap those functions into a templated overload:

#include <string>
#include <algorithm>

template <typename TChar,
          typename TTraits1, typename TAlloc1,
          typename TTraits2, typename TAlloc2>
bool operator==(std::basic_string<TChar, TTraits1, TAlloc1> const & s1,
                std::basic_string<TChar, TTraits2, TAlloc2> const & s2)
{
    return s1.length() == s2.length() &&
           std::equal(s1.begin(), s1.end(), s2.begin());
}

Usage example:

#include <ext/malloc_allocator.h>
int main()
{
    std::string a("hello");
    std::basic_string<char, std::char_traits<char>, __gnu_cxx::malloc_allocator<char>> b("hello");
    return a == b;
}

In fact, you could define such an overload for most standard containers. You could even template it on a template, but that would be extreme.

Solution 2:

The standard only define operators using homogenous string types, i.e., all the template arguments need to match. However, you can define a suitable equality operator in the namespace where the allocator is defined: argument dependent look-up will find it there. If you choose to implement your own assignment operator, it would look something like this:

bool operator== (std::string const& s0,
                 std::basic_string<char, std::char_traits<char>, MyCharAllocator> const& s1) {
    return s0.size() == s1.size() && std::equal(s0.begin(), s0.end(), s1.begin()).first;
}

(plus a few other overloads). Taking this to next level, it may even be reasonable to define versions the various relational operators in terms of the container requirements and not restricting the template arguments:

namespace my_alloc {
    template <typename T> class allocator { ... };
    template <typename T0, typename T1>
    bool operator== (T0 const& c0, T1 const& c1) {
        return c0.size() == c1.size() && std::equal(c0.begin(), c0.end(), c1.end);
    }
    ...
}

Obviously, the operators can be restricted to specific container types, differing only in their allocator template parameters.

With respect to why the standard doesn't define mixed type comparisons, the main reason behind not supporting mixed type comparison is probably that you actually don't want to mix allocators in your program in the first place! That is, if you need to use an allocator, you'd use an allocator type which encapsulates a dynamically polymorphic allocation policy and always use the resulting allocator type. The reasoning for this would be that otherwise you'd get either incompatible interface or you would need to make everything a template, i.e., you want to retain some level of vocabulary types being used. Of course, with using even just one additional allocator type, you'd have two vocabulary string types: the default instantiation and the instantiation for your special allocation.

That said, there is another potential reason to not support mixed type comparison: If operator==() really becomes a comparison between two values, as is the case if the allocators differ, it may give raise to a much broader definition of value equality: should std::vector<T>() == std::deque<T> be supported? If not, why would comparison between strings with different allocators be special? Of course, the allocator is a non-salient attribute of std::basic_string<C, T, A> which could be a good reason to ignore it. I'm not sure if mixed type comparison should be supported. It may be reasonable to support operators (this probably extends to other operators than operator==()) for container types differing only in their allocator type.