Comparing STL strings that use different allocators

Question

I'd like to compare STL strings that are allocated with different allocators, e.g. an ordinary std::string with a string using a custom STL allocator. Unfortunately, it seems that usual operator==() doesn't work in this case:

// Custom STL allocator to allocate char's for string class
typedef MyAllocator<char> MyCharAllocator;

// Define an instance of this allocator
MyCharAllocator myAlloc;

// An STL string with custom allocator
typedef std::basic_string
<
    char, 
    std::char_traits<char>, 
    MyCharAllocator
> 
CustomAllocString;

std::string s1("Hello");
CustomAllocString s2("Hello", myAlloc);

if (s1 == s2)  // <--- ERROR: doesn't compile
   ...

In particular, MSVC10 (VS2010 SP1) emits the following error message:

error C2678: binary '==' : no operator found which takes a left-hand operand of type 'std::string' (or there is no acceptable conversion)

So, a lower-level (less readable) code like this:

if (strcmp(s1.c_str(), s2.c_str()) == 0)
   ...

should be used.

(This is also particularly annoying in cases where e.g. there are std::vector's of differently-allocated strings, where the usual simple v[i] == w[j] syntax can't be used.)

This doesn't seem very good to me, since a custom allocator changes the way string memory is requested, but the interface of a string class (including comparison with operator==()) is independent from the particular way a string allocates its memory.

Is there something I am missing here? Is it possible to keep the C++ high-level interface and operator overloads in this case?

Answer 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.

Answer 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.