Я использовал карту с ключом std::string, и пока все работало нормально, я не получал ожидаемого результата. Я искал места для оптимизации и улучшения всего лишь немного, и когда коллега сказал: "Этот строковый ключ будет медленным".
Я читал десятки вопросов, и они последовательно говорят:
"не использовать
char *как ключ"
"std::stringключи никогда не являются вашим узким местом"
"разница в производительности между achar *иstd::string- это миф."
Я неохотно попробовал ключ char *, и была разница, большая разница.
Я сварил проблему до простого примера:
#include <stdio.h>
#include <stdlib.h>
#include <map>
#ifdef USE_STRING
#include <string>
typedef std::map<std::string, int> Map;
#else
#include <string.h>
struct char_cmp {
bool operator () (const char *a,const char *b) const
{
return strcmp(a,b)<0;
}
};
typedef std::map<const char *, int, char_cmp> Map;
#endif
Map m;
bool test(const char *s)
{
Map::iterator it = m.find(s);
return it != m.end();
}
int main(int argc, char *argv[])
{
m.insert( Map::value_type("hello", 42) );
const int lcount = atoi(argv[1]);
for (int i=0 ; i<lcount ; i++) test("hello");
}
Сначала версия std::string:
$ g++ -O3 -o test test.cpp -DUSE_STRING
$ time ./test 20000000
real 0m1.893s
Далее версия 'char *':
g++ -O3 -o test test.cpp
$ time ./test 20000000
real 0m0.465s
Это довольно большая разница в производительности и примерно та же разница, что и в моей более крупной программе.
Использование клавиши char * - это боль, чтобы справиться с освобождением ключа и просто не чувствует себя хорошо. Эксперты С++, что мне не хватает? Любые мысли или предложения?
Вы используете const char * в качестве ключевого слова для find(). Для карты, содержащей const char*, это правильный тип, который ожидает find, и поиск может быть выполнен напрямую.
Карта, содержащая std::string, ожидает, что параметр find() будет std::string, поэтому в этом случае const char* сначала должен быть преобразован в std::string. Вероятно, это разница, которую вы видите.
Как отмечалось, проблема является одной из спецификаций ассоциативных контейнеров (наборов и карт), поскольку их методы поиска членов всегда приводят к преобразованию в key_type, даже если существует operator<, который будет принимать сравните свой ключ с ключами на карте, несмотря на их разные типы.
С другой стороны, функции из <algorithm> не страдают от этого, например lower_bound определяется как:
template< class ForwardIt, class T >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );
template< class ForwardIt, class T, class Compare >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );
Таким образом, альтернативой может быть:
std::vector< std::pair< std::string, int > >
И тогда вы могли бы сделать:
std::lower_bound(vec.begin(), vec.end(), std::make_pair("hello", 0), CompareFirst{})
Где CompareFirst определяется как:
struct CompareFirst {
template <typename T, typename U>
bool operator()(T const& t, U const& u) const { return t.first < u.first; }
};
Или даже создать полностью настраиваемый компаратор (но это немного сложнее).
A vector пары, как правило, более эффективна при нагрузках с высокой нагрузкой, поэтому действительно хранить конфигурацию, например.
Я рекомендую предоставить методы для переноса доступа. lower_bound довольно низкоуровневый.
Если ваш в С++ 11, конструктор копирования не называется если строка не изменена. Поскольку std::string является конструкцией С++, для получения строковых данных требуется не менее 1 разыменования.
Я предполагаю, что время будет занято дополнительным разыменованием (что если сделано 10000 раз дорогостоящим), а std::string, скорее всего, проведет соответствующие проверки нулевого указателя, который снова ест циклы.
После компиляции 2 "Hello" строковые литералы будут иметь одинаковый адрес памяти. В случае char * вы используете эти адреса памяти в качестве ключей.
В случае string каждый "Hello" будет преобразован в другой объект. Это небольшая часть (действительно очень маленькая) вашей разницы в производительности.
Большая часть может заключаться в том, что, поскольку все используемые вами "Hello" имеют одинаковый адрес памяти, strcmp всегда будет иметь 2 эквивалентных указателя char, и я уверен, что он проверяет этот случай на раннем этапе: ) Таким образом, он никогда не будет переименовывать все символы, но сравнение std::string будет.
Сохраните std::string как указатель, а затем вы потеряете служебные данные конструктора копии.
Но после того, как вы должны помнить о том, чтобы обрабатывать удаления.
Причина std::string медленная - это то, что она сама создает. Вызывает конструктор копирования, а затем в конце вызывает удаление. Если вы создаете строку в куче, вы теряете конструкцию копии.