C++: set of C-strings

Question

I want to create one so that I could check whether a certain word is in the set using set::find

However, C-strings are pointers, so the set would compare them by the pointer values by default. To function correctly, it would have to dereference them and compare the strings.

I could just pass the constructor a pointer to the strcmp() function as a comparator, but this is not exactly how I want it to work. The word I might want to check could be part of a longer string, and I don't want to create a new string due to performance concerns. If there weren't for the set, I would use strncmp(a1, a2, 3) to check the first 3 letters. In fact, 3 is probably the longest it could go, so I'm fine with having the third argument constant.

Is there a way to construct a set that would compare its elements by calling strncmp()? Code samples would be greatly appreciated.

Here's pseudocode for what I want to do:

bool WordInSet (string, set, length)
{
   for (each word in set)
    {
       if strncmp(string, word, length) == 0
            return true;
    }
    return false;
}

But I'd prefer to implement it using the standard library functions.

Answer 1

Assuming a constant value as a word length looks like asking for trouble to me. I recommend against this solution.

Look: The strcmp solution doesn't work for you because it treats the const char* arguments as nul-terminated strings. You want a function which does exactly the same, but treats the arguments as words - which translates to "anything-not-a-letter"-terminated string.

One could define strcmp in a generic way as:

template<typename EndPredicate>
int generic_strcmp(const char* s1, const char* s2) {
    char c1;
    char c2;
    do { 
        c1 = *s1++; 
        c2 = *s2++; 
        if (EndPredicate(c1)) {
            return c1 - c2; 
        }
    } while (c1 == c2);

    return c1 - c2; 
}

If EndPredicate is a function which returns true iff its argument is equal to \0, then we obtain a regular strcmp which compares 0-terminated strings.

But in order to have a function which compares words, the only required change is the predicate. It's sufficient to use the inverted isalpha function from <cctype> header file to indicate that the string ends when a non-alphabetic character is encountered.

So in your case, your comparator for the set would look like this:

#include <cctype>

int wordcmp(const char* s1, const char* s2) {
    char c1;
    char c2;
    do { 
        c1 = *s1++; 
        c2 = *s2++; 
        if (!isalpha(c1)) {
            return c1 - c2; 
        }
    } while (c1 == c2);

    return c1 - c2; 
}

Answer 2

You could create a comparator function object.

struct set_object {
    bool operator()(const char* first, const char* second) {
        return strncmp(first, second, 3);
    }
};

std::set<const char*, set_object> c_string_set;

However it would be far easier and more reliable to make a set of std::strings.

Answer 3

Make a wrapper function:

bool myCompare(const char * lhs, const char * rhs)
{
    return strncmp(lhs, rhs, 3) < 0;
}