Самый простой, самый безопасный способ держать кучу const char * в наборе?

Question

Я хочу хранить несколько указателей на константные символы в контейнере std :: set [1]. Шаблон std :: set требует функтора компаратора, а стандартная библиотека C ++ предлагает std :: less, но его реализация основана на непосредственном сравнении двух ключей, что не является стандартным для указателей.

Я знаю, что могу определить свой собственный функтор и реализовать оператор (), приведя указатели к целым числам и сравнив их, но есть ли более чистый, "стандартный" способ сделать это?

Пожалуйста, не предлагайте создавать std :: strings - это пустая трата времени и пространства. Строки являются статическими, поэтому их можно сравнивать на (в) равенство по их адресу.

1: указатели на статические строки, поэтому с их временем жизни проблем нет - они не исчезнут.

Answer 1

Если вы не хотите заключать их в std::string s, вы можете определить класс функторов:

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

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

Answer 2

Просто продолжайте и используйте порядок по умолчанию, который меньше <>. Стандарт гарантирует, что меньше будет работать даже для указателей на разные объекты:

"Для шаблонов" больше, меньше, больше, больше и меньше ", специализации для любого Тип указателя дает общий порядок, даже если встроенные операторы <,>, <=,> = не делают.

Гарантия там точно на такие вещи, как ваш set<const char*>.

Answer 3

«Оптимизированный путь»

Если мы игнорируем «преждевременная оптимизация - корень зла», стандартным способом является добавление компаратора, который легко написать:

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

Для использования с:

std::set<const char *, MyCharComparator>

Стандартный способ

Используйте:

std::set<std::string>

Это будет работать, даже если вы поместите статический const char * внутрь (потому что std :: string, в отличие от const char *, сравним по своему содержанию).

Конечно, если вам нужно извлечь данные, вам придется извлечь данные с помощью std :: string.c_str (). С другой стороны, но, поскольку это набор, я думаю, вы хотите знать только, есть ли в наборе «AAA», а не извлекать значение «AAA» из «AAA».

Примечание: я читал о "Пожалуйста, не предлагайте создавать std :: strings", но затем вы спросили "стандартный" способ ...

Способ "никогда не делай"

Я заметил следующий комментарий после моего ответа:

Пожалуйста, не предлагайте создавать std :: strings - это пустая трата времени и пространства. Строки являются статическими , поэтому их можно сравнить на (in) равенство на основе их адреса .

Это пахнет C (использование устаревшего ключевого слова static, вероятная преждевременная оптимизация, используемая для std :: string bashing и сравнения строк по их адресам).

В любом случае, вы не хотите сравнивать свои строки по их адресу. Потому что, я думаю, последнее, что вам нужно, это иметь набор, содержащий:

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

Конечно, если вы используете одни и те же глобальные переменные для хранения строки, это уже другая история.

В этом случае я предлагаю:

std::set<const char *>

Конечно, это не сработает, если вы сравните строки с одинаковым содержимым, но разными переменными / адресами.

И, конечно, он не будет работать с static const char * строками, если эти строки определены в заголовке.

Но это другая история.

Answer 4

Другие уже опубликовали множество решений, показывающих, как проводить лексические сравнения с const char*, поэтому я не буду беспокоиться.

Пожалуйста, не предлагайте создавать std :: strings - это пустая трата времени и пространства.

Если std::string является пустой тратой времени и пространства, то std::set может быть пустой тратой времени и пространства. Каждый элемент в std::set размещается отдельно от бесплатного магазина. В зависимости от того, как ваша программа использует наборы, это может ухудшить производительность, чем производительность поиска в std::set O (log n). Вы можете получить лучшие результаты, используя другую структуру данных, такую ​​как отсортированный std::vector, или статически распределенный массив, который сортируется во время компиляции, в зависимости от предполагаемого времени жизни набора.

стандартная библиотека C ++ предлагает std :: less, но ее реализация основана на непосредственном сравнении двух ключей, что не является стандартным для указателей.

Строки являются статическими, поэтому их можно сравнивать на (in) равенство по их адресу.

Это зависит от того, на что указывают указатели. Если все ключи выделены из одного и того же массива, то использование operator< для сравнения указателей не является неопределенным поведением.

Пример массива, содержащего отдельные статические строки:

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

Если вы создадите std::set<const char*> и заполните его указателями, которые указывают на этот массив, их порядок будет четко определен.

Если, однако, все строки являются отдельными строковыми литералами, сравнение их адресов, скорее всего, приведет к неопределенному поведению. Работает ли он или нет, зависит от реализации компилятора / компоновщика, от того, как вы его используете, и от ваших ожиданий.

Если ваш компилятор / компоновщик поддерживает объединение строк и он включен, дублирующиеся строковые литералы должны иметь один и тот же адрес, но гарантированно ли они есть во всех случаях? Безопасно ли полагаться на оптимизацию компоновщика для корректной работы?

Если вы используете строковые литералы только в одной единице перевода, установленный порядок может основываться на порядке, в котором строки используются впервые, но если вы измените другую единицу перевода, чтобы использовать одну из тех же строковые литералы, установленный порядок может измениться.

Я знаю, что могу определить свой собственный функтор и реализовать оператор (), приведя указатели к целым числам и сравнив их

Преобразование указателей в uintptr_t, по-видимому, не принесет пользы по сравнению с использованием сравнения указателей. Результат одинаков в любом случае: зависит от реализации.

Answer 5

Либо используйте компаратор, либо используйте тип оболочки, который содержится в наборе. (Примечание: std::string также является оболочкой ....)

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 6

Предположительно, вы не хотите использовать std :: string из-за соображений производительности.

Я использую MSVC и gcc, и они оба, похоже, не против:

bool foo = "blah" < "grar";

РЕДАКТИРОВАТЬ: Однако поведение в этом случае не определено. Смотрите комментарии ...

Они также не жалуются на std::set<const char*>.

Если вы используете компилятор, который жалуется, я, вероятно, продолжу с вашим предложенным функтором, который приводит указатели к int s.

Edit: Эй, за меня проголосовали ... Несмотря на то, что я был одним из немногих людей, которые прямо ответили на его вопрос. Я новичок в Stack Overflow, есть ли способ защитить себя, если это произойдет? При этом я попытаюсь прямо здесь:

Вопрос не ищет std::string решения. Каждый раз, когда вы вводите std::string в набор, ему нужно будет копировать всю строку (во всяком случае, до тех пор, пока C ++ 0x не станет стандартом). Кроме того, каждый раз, когда вы выполняете поиск по множеству, ему нужно будет выполнять несколько сравнений строк.

Хранение указателей в наборе, однако, не приводит к копированию строки (вы просто копируете указатель), и каждое сравнение представляет собой простое целочисленное сравнение по адресам, а не сравнение строк.

В вопросе говорилось, что хранить указатели на строки было нормально, я не вижу причин, по которым мы все должны немедленно предположить, что это утверждение было ошибкой. Если вы знаете, что делаете, то при использовании const char* по сравнению с std::string или при специальном сравнении, которое вызывает strcmp, вы получаете значительный прирост производительности. Да, это менее безопасно и более подвержено ошибкам, но это общие компромиссы для производительности, и, поскольку в вопросе никогда не указывалось применение, я думаю, мы должны предположить, что он уже рассмотрел все за и против и принял решение в пользу производительности. .

Answer 7

Должен ли набор содержать const char*?

То, что сразу приходит на ум, - это хранить строки в std::string и помещать их в std::set. Это позволит проводить сравнения без проблем, и вы всегда можете получить необработанный const char* простым вызовом функции:

const char* data = theString.c_str();

Answer 8

В зависимости от того, насколько велика «связка», я склонен хранить в наборе соответствующую связку std::string с. Таким образом, вам не придется писать дополнительный код для клея.