Избегайте строительства ключа для std :: map :: find()

Question

Предположим, у меня есть std::map<std::string, int>. std::string можно сравнить со строками C (const char *) без std::string временных рядов. Тем не менее, map::find(), похоже, заставляет меня создать временный std::string, что, вероятно, требует выделения памяти. Как мне избежать этого? Концептуально это легко, но STL, похоже, предотвращает это.

#include <map> 

int main() 
{ 
    std::map<std::string, int> m; 
    m.find("Olaf"); 
} 

Answer 1

Ваша проблема реальна, и нет хорошего способа обхода для C++ 11.

C++ 14 исправляет эту проблему путем добавления шаблонной перегрузки std::map::find - соответствующее предложение - N3657.В C++ 14, ваша программа будет выглядеть следующим образом:.

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <map> 
#include <algorithm> 

class std_string { 
    char *m_s; 
public: 
    std_string() { m_s = nullptr; } 
    std_string(const char* s) { puts("Oops! A new std_string was constructed!"); m_s = strdup(s); } 
    ~std_string() { free(m_s); } 
    std_string(std_string&& ss) = delete; 
    std_string(const std_string& ss) = delete; 
    std_string& operator=(std_string&& ss) = delete; 
    std_string& operator=(const std_string& ss) = delete; 

    bool operator< (const char* s) const { return strcmp(m_s, s) < 0; } 
    bool operator< (const std_string& ss) const { return strcmp(m_s, ss.m_s) < 0; } 
    friend bool operator< (const char* s, const std_string& ss) { return strcmp(s, ss.m_s) < 0; } 
}; 

int main() 
{ 
    { 
     puts("The C++11 way makes a copy..."); 
     std::map<std_string, int> m; 
     auto it = m.find("Olaf"); 
    } 
    { 
     puts("The C++14 way doesn't..."); 
     std::map<std_string, int, std::less<>> m; 
     auto it = m.find("Olaf"); 
    } 
} 

(std::less<> является обобщенным "менее чем" компаратор, что эквивалентно operator< C++ 03 и C++ 11 имеет разбитый по -стандартная версия этого компаратора, которая заставляет оба аргумента быть одного и того же типа. C++ 14, наконец, делает это правильно.)

К сожалению, Комитет, похоже, решил, что люди должны пройти весь свой код C++ 11 и обновить каждый контейнер, чтобы использовать std::less<> в качестве компаратора - по умолчанию это происходит не просто. Нет веских оснований для этого решения; это просто «Путь». (См. Мои комментарии выше о поломке. C++ имеет плохую привычку вводить сломанные версии вещей, прежде чем вводить «настоящие» версии несколько лет спустя.)

Для C++ 11, std::map::find имеет только одну перегрузку (тот, который принимает const Key&), поэтому любое обходное решение обязательно будет включать изменение типа Key, чтобы быть менее дорогостоящим - мы не можем просто возиться с компаратором, потому что к тому времени, когда выполнение достигнет компаратора, мы уже продвинули find аргумент Key.

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <map> 
#include <algorithm> 

class std_string { 
    char *m_s; 
public: 
    std_string() : m_s(nullptr) { } 
    std_string(const char* s) : m_s(strdup(s)) { puts("Oops! A new std_string was constructed!"); } 
    ~std_string() { free(m_s); } 
    std_string(std_string&& ss) : m_s(nullptr) { std::swap(m_s, ss.m_s); } 
    std_string(const std_string& ss) : m_s(strdup(ss.data())) { puts("Oops! A new std_string was constructed!"); } 
    std_string& operator=(std_string&& ss) = delete; 
    std_string& operator=(const std_string& ss) = delete; 

    const char* data() const { return m_s; } 

    bool operator< (const char* s) const { return strcmp(m_s, s) < 0; } 
    bool operator< (const std_string& ss) const { return strcmp(m_s, ss.m_s) < 0; } 
    friend bool operator< (const char* s, const std_string& ss) { return strcmp(s, ss.m_s) < 0; } 
}; 

struct string_or_ptr { 
    union { 
     const char* ptr; 
     alignas(std_string) unsigned char str[sizeof (std_string)]; 
    } m_u; 
    bool m_deep; 

    char const* & ptr() { return m_u.ptr; } 
    std_string& str() { return *reinterpret_cast<std_string*>(m_u.str); } 
    char const* const & ptr() const { return m_u.ptr; } 
    std_string const& str() const { return *reinterpret_cast<const std_string*>(m_u.str); } 

    string_or_ptr() : m_deep(false) { ptr() = ""; } 
    string_or_ptr(const char* s) : m_deep(false) { ptr() = s; } 
    string_or_ptr(std_string&& s) : m_deep(true) { new ((void*)&str()) std_string(std::move(s)); } 
    string_or_ptr(const std_string& s) : m_deep(true) { new ((void*)&str()) std_string(s); } 
    ~string_or_ptr() { if (m_deep) str().~std_string(); } 
    std_string& operator=(std_string&& ss) = delete; 
    std_string& operator=(const std_string& ss) = delete; 


    operator const char*() const { return m_deep ? str().data() : ptr(); } 

    bool operator< (const char* s) const { return strcmp((const char*)*this, s) < 0; } 
    bool operator< (const std_string& ss) const { return (const char*)*this < ss; } 
    bool operator< (const string_or_ptr& sp) const { return strcmp((const char*)*this, (const char*)sp) < 0; } 
    friend bool operator< (const char* s, const string_or_ptr& sp) { return strcmp(s, (const char*)sp) < 0; } 
    friend bool operator< (const std_string& ss, const string_or_ptr& sp) { return ss < (const char*)sp; } 
}; 

int main() 
{ 
    { 
     puts("The C++11 way..."); 
     std::map<std_string, int> m; 
     auto it = m.find("Olaf"); 
    } 
    { 
     puts("The C++11 way with a custom string-or-pointer Key type..."); 
     std::map<string_or_ptr, int> m; 
     auto it = m.find("Olaf"); 
    } 
} 

Answer 2

Существует на самом деле не способ заставить find использовать оператор сравнения, отличный от той, которая используется для создания map. Если бы вы могли передать другой номер в find, как бы он мог гарантировать, что оба сравнения предоставят одинаковый заказ?

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

1) Вы огибают char* в вашей программе. В этом случае просто не делайте этого. Используйте вместо этого std::string, создавая его один раз, если необходимо, как можно ближе к оригиналу. Тогда преобразование не требуется.

2) Вы пытаетесь найти строковые литералы. В этом случае, почему ключ string? Сделайте ключ быть красиво названным перечисленным типа вместо:

enum names { OLAF }; 
map<names, int> m; 
m.find(OLAF); 

3) Вы хотите найти как строки и C-строковые литералы. В этом случае я бы создал глобальную таблицу поиска строк, индексированных перечислением, но построенных один раз в начале main. Затем вы назовете что-то вроде m.find(global_strings[OLAF]);

EDIT: Вы, кажется, очень сфокусированы/обеспокоены последствиями производительности string здесь. Профилировали ли вы свое приложение и обнаружили, что выделение string - значительная часть времени вашего приложения? Я бы, конечно, поверил этому в встроенные системы/устройства.

Кроме того, вы отметили свой вопрос C++, но, похоже, вы отказываетесь использовать встроенную строковую функцию C++, которая дает гораздо больше, чем «стоить вам производительность». Он предоставляет множество полезных функций/методов/операторов, но, самое главное, он управляет памятью для вас, поэтому вы не тратите дни или недели на поиски этих поистине коварных ошибок, которые, несомненно, возникнут.

Если вы читаете данные переменной длины из сети я не могу вполне понять разницу в производительности между char* buffer = new char[needed_size]; и что-то вроде std::string s; s.resize(needed_size);, кроме того, используя string обеспечивает некоторую безопасность и управление памятью для вас.

Answer 3

Если построение строки из литерала действительно является узким местом производительности, вы можете использовать свой собственный класс вместо std::string, который содержит строку или указатель на литерал. Недостатком является некоторое дополнительное усложнение, а также добавление размера указателя на элементы, которые вы вставляете в контейнер. Обратите внимание, что значение неизменно, как требуется, map, поэтому безопасно хранить результаты c_str.

class mystring 
{ 
    std::string str; 
    const char * value; 
public: 
    mystring() : value(NULL) 
    { 
    } 
    void setString(const std::string & s) 
    { 
     assert(value == NULL); 
     str = s; 
     value = str.c_str(); 
    } 
    void setLiteral(const char * s) 
    { 
     assert(value == NULL); 
     value = s; 
    } 
    bool operator<(const mystring & rhs) 
    { 
     return strcmp(literal, rhs.literal) < 0; 
    } 
}; 

std::map<mystring, int> m; 
mystring text; 
text.setString(some_key); 
m.insert(std::make_pair(text, some_data)); 
// ... 
mystring key; 
key.setLiteral("Olaf"); 
m[key] = new_value;