Simplest, safest way of holding a bunch of const char* in a set?

Question

I want to hold a bunch of const char pointers into an std::set container [1]. std::set template requires a comparator functor, and the standard C++ library offers std::less, but its implementation is based on comparing the two keys directly, which is not standard for pointers.

I know I can define my own functor and implement the operator() by casting the pointers to integers and comparing them, but is there a cleaner, 'standard' way of doing it?

Please do not suggest creating std::strings - it is a waste of time and space. The strings are static, so they can be compared for (in)equality based on their address.

1: The pointers are to static strings, so there is no problem with their lifetimes - they won't go away.

Answer 1

Depending on how big a "bunch" is, I would be inclined to store a corresponding bunch of std::strings in the set. That way you won't have to write any extra glue code.

Answer 2

The "optimized way"

If we ignore the "premature optimization is the root of all evil", the standard way is to add a comparator, which is easy to write:

struct MyCharComparator
{
   bool operator()(const char * A, const char * B) const
   {
      return (strcmp(A, B) < 0) ;
   }
} ;

To use with a:

std::set<const char *, MyCharComparator>

The standard way

Use a:

std::set<std::string>

It will work even if you put a static const char * inside (because std::string, unlike const char *, is comparable by its contents).

Of course, if you need to extract the data, you'll have to extract the data through std::string.c_str(). In the other hand, , but as it is a set, I guess you only want to know if "AAA" is in the set, not extract the value "AAA" of "AAA".

Note: I did read about "Please do not suggest creating std::strings", but then, you asked the "standard" way...

The "never do it" way

I noted the following comment after my answer:

Please do not suggest creating std::strings - it is a waste of time and space. The strings are static, so they can be compared for (in)equality based on their address.

This smells of C (use of the deprecated "static" keyword, probable premature optimization used for std::string bashing, and string comparison through their addresses).

Anyway, you don't want to to compare your strings through their address. Because I guess the last thing you want is to have a set containing:

{ "AAA", "AAA", "AAA" }

Of course, if you only use the same global variables to contain the string, this is another story.

In this case, I suggest:

std::set<const char *>

Of course, it won't work if you compare strings with the same contents but different variables/addresses.

And, of course, it won't work with static const char * strings if those strings are defined in a header.

But this is another story.

Answer 3

Must the set contain const char*?

What immediately springs to mind is storing the strings in a std::string instead, and putting those into the std::set. This will allow comparisons without a problem, and you can always get the raw const char* with a simple function call:

const char* data = theString.c_str();

Answer 4

The standard way of doing it, if you don't want to wrap them in std::strings, is to define a functor class:

struct ConstCharStarComparator
{
  bool operator()(const char *s1, const char *s2) const
  {
    return strcmp(s1, s2) < 0;
  }
}

typedef std::set<onst char *, ConstCharStarComparator> stringset_t;
stringset_t myStringSet;

Answer 5

Presumably you don't want to use std::string because of performance reasons.

I'm running MSVC and gcc, and they both seem to not mind this:

bool foo = "blah" < "grar";

EDIT: However, the behaviour in this case is unspecified. See comments...

They also don't complain about std::set<const char*>.

If you're using a compiler that does complain, I would probably go ahead with your suggested functor that casts the pointers to ints.

Edit: Hey, I got voted down... Despite being one of the few people here that most directly answered his question. I'm new to Stack Overflow, is there any way to defend yourself if this happens? That being said, I'll try to right here:

The question is not looking for std::string solutions. Every time you enter an std::string in to the set, it will need to copy the entire string (until C++0x is standard, anyway). Also, every time you do a set look-up, it will need to do multiple string compares.

Storing the pointers in the set, however, incurs NO string copy (you're just copying the pointer around) and every comparison is a simple integer comparison on the addresses, not a string compare.

The question stated that storing the pointers to the strings was fine, I see no reason why we should all immediately assume that this statement was an error. If you know what you're doing, then there are considerable performance gains to using a const char* over either std::string or a custom comparison that calls strcmp. Yes, it's less safe, and more prone to error, but these are common trade-offs for performance, and since the question never stated the application, I think we should assume that he's already considered the pros and cons and decided in favor of performance.

Answer 6

Either use a comparator, or use a wrapper type to be contained in the set. (Note: std::string is a wrapper, too....)

const char* a("a");
const char* b("b");

struct CWrap {
 const char* p;
 bool operator<(const CWrap& other) const{
  return strcmp( p, other.p ) < 0;
 }
 CWrap( const char* p ): p(p){}
};

std::set<CWrap> myset;
myset.insert(a);
myset.insert(b);

Answer 7

Others have already posted plenty of solutions showing how to do lexical comparisons with const char*, so I won't bother.

Please do not suggest creating std::strings - it is a waste of time and space.

If std::string is a waste of time and space, then std::set might be a waste of time and space as well. Each element in a std::set is allocated separately from the free store. Depending on how your program uses sets, this may hurt performance more than std::set's O(log n) lookups help performance. You may get better results using another data structure, such as a sorted std::vector, or a statically allocated array that is sorted at compile time, depending on the intended lifetime of the set.

the standard C++ library offers std::less, but its implementation is based on comparing the two keys directly, which is not standard for pointers.

The strings are static, so they can be compared for (in)equality based on their address.

That depends on what the pointers point to. If all of the keys are allocated from the same array, then using operator< to compare pointers is not undefined behavior.

Example of an array containing separate static strings:

static const char keys[] = "apple\0banana\0cantaloupe";

If you create a std::set<const char*> and fill it with pointers that point into that array, their ordering will be well-defined.

If, however, the strings are all separate string literals, comparing their addresses will most likely involve undefined behavior. Whether or not it works depends on your compiler/linker implementation, how you use it, and your expectations.

If your compiler/linker supports string pooling and has it enabled, duplicate string literals should have the same address, but are they guaranteed to in all cases? Is it safe to rely on linker optimizations for correct functionality?

If you only use the string literals in one translation unit, the set ordering may be based on the order that the strings are first used, but if you change another translation unit to use one of the same string literals, the set ordering may change.

I know I can define my own functor and implement the operator() by casting the pointers to integers and comparing them

Casting the pointers to uintptr_t would seem to have no benefit over using pointer comparisons. The result is the same either way: implementation-specific.

Answer 8

Just go ahead and use the default ordering which is less<>. The Standard guarantees that less will work even for pointers to different objects:

"For templates greater, less, greater_equal, and less_equal, the specializations for any pointer type yield a total order, even if the built-in operators <, >, <=, >= do not."

The guarantee is there exactly for things like your set<const char*>.