Вопрос по c++11, c++ – Как избежать построения ключа для std :: map :: find ()

21

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

<code>#include <map>

int main()
{
    std::map<std::string, int> m;
    m.find("Olaf");
}
</code>
@SteveTownsend Большинство / все эти распределения будут происходить при вставке, хотя, если у вас был высокопроизводительный метод запроса карты, который не выполнял выделений, это могло бы быть аккуратно ... Benj
Если строка действительно настолько мала, то оптимизация с малой строкой позволит избежать любого выделения при построении строки. Например, libc ++ std :: string в x86_64 допускает строки длиной до 22 символов без динамического выделения. VS11 позволяет до 15. bames53
@Benj -map::find в любом случае не приведет к очевидному распределению, если толькоstring конструкция (как здесь, через неявное преобразование) Steve Townsend
Ну, если вы действительно хотите приложить усилия, вы можете написать обертку вокруг std :: map только для строки и предоставить два метода для поиска. Один для std :: string и один для const char *, но для такого небольшого влияния на производительность очень много работы. Alessandro Teruzzi
Если вы используете картуstring ключи то под чехлами и при построении карты много невидимогоstring ассигнования уже происходят. Это действительно стоит беспокоиться? У большинства приложений есть и другие проблемы, которые стоят выше. Этого можно избежать, изолировав магические значения в статическом & quot; MyConstants & quot; класс может быть. Steve Townsend

Ваш Ответ

4   ответа
10

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

C ++ 14 исправляет эту проблему, добавляя шаблонную перегрузкуstd::map::find & # X2014; соответствующее предложение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<> в качестве компаратора & # x2014; это не происходит по умолчанию. Для этого решения нет веской причины; это просто так, как оно есть. (См. Мои комментарии выше о разбивке по замыслу. В C ++ есть плохая привычка представлять испорченные версии вещей, прежде чем вводить «настоящие» версии через несколько лет.)

Для C ++ 11,std::map::find имеет только одну перегрузку (ту, которая принимаетconst Key&), поэтому любой обходной путь обязательно будет включать изменениеKey тип будет дешевле & # x2014; мы не можем просто возиться с компаратором, потому что к тому времени, когда выполнение достигает компаратора, мы уже продвинулись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");
    }
}
Идея состоит в том, что старый код остается таким же быстрым (и не становится медленнее), и новый код может использовать новые типы объектов функций. Это также проблема правильности - в проблеме, с которой я столкнулся, это привело к UB.
@dyp Кажется, это хорошая причина не писатьstupid_string, но это не кажется хорошей причиной для компилятора генерировать медленный код дляstd::map<smart_string, int>, ("Делайте глупый код медленным, а умный - быстрым", мне кажется,strictly better философия, которая заключается в том, что «сделать глупый код не удается скомпилировать и сделать умный код медленным». Другими словами, я не согласен с тем, составляет ли приведенный выше бит пустяков как & quot;good Причина & Quot; для Комитета пессимизации реализации по умолчаниюstd::map а такжеstd::set.
"There's no good reason for this decision; it's just The Way It Is." Неправильно. Рассмотрим, существует ли для некоторого типаstupid_string только конвертирующий конструктор изchar const* но не оператор сравненияoperator<(stupid_string const&, char const*), толькоoperator<(stupid_string const&, stupid_string const&), посколькуstd::less<> перешлем оператору сравнения,each comparison will create a new stupid_string, Я видел эту проблему в реальном коде несколько лет назад, поскольку STLPort (IIRC) делает это по умолчанию как несоответствующее расширение.
2

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

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

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

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

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

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

РЕДАКТИРОВАТЬ: Вы, кажется, очень сосредоточены / обеспокоены последствиями производительностиstring Вот. Вы профилировали свою заявку и обнаружили, чтоstringРаспределение ресурсов составляет значительную часть времени вашего приложения? Я бы, конечно, поверил в это на встроенных системах / устройствах.

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

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

@Benj: Опять же, сетевой пакет был просто примером. Я на самом деле использую массив для буфера, и строка, конечно, не будет весь буфер. С являетсяbad идея. Нет необходимости отказываться от C ++, если целью является производительность.
@XTF Как вы выглядите из ваших комментариев: вы говорите, что хотите использовать C ++ определенным образом, но, к сожалению, это не поддерживается; Я предлагаю альтернативные варианты, вы говорите, что они не будут работать. На данный момент это действительно выглядит так, как будто вы хотите C здесь.
@ XTF Я полагаю, что если ваши опасения настолько низки, то, возможно, C не такая уж плохая идея ;-)
@XTF Ничто не мешает вам создать карту & lt; char *, int & gt; с компаратором, который выполняет strcmp (). Просто не забудьте удалить все ваши указатели, когда вы очистите карту.
Мне не нужен другой оператор сравнения, оператор & lt; Это хорошо. 1. Это конкретный пример, но проблема носит общий характер. Использование std :: string не дает мне ничего, кроме снижения производительности. 2. Может быть, а может и нет. Строка может прийти из сетевого пакета. Зачем мне копировать его в std :: string, чтобы иметь возможность использовать его? XTF
0

Там нет никакого способа специально определить компаратор дляmap::find() функция. Вместо этого я бы посоветовал вам создать свой компаратор (myOwnCmp) и delcare astd::map<char*, int, myOwnCmp> для вашей программы. Для очень больших программ или когда количество тестов очень велико, это будет сравнительно быстрее, чемstd::map<string, int> потому что время, затрачиваемое на создание строки путем вызова конструктора строки и последующего вызова ее деструктора, занимает значительное количество времени. Использование const char * в качестве ключа будет включать только сравнение указателей.

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

Код будет выглядеть примерно так:

 struct myOwnComp {
        bool operator()(const char* a, const char* b) const {
            return (strcmp(a, b) < 0);
        }
    };

std::map<char*, int, myOwnComp> mymap;

void addToMap(char*& ref, int value)
{
    char *key = new char[strlen(ref) + 1]{};
    std::copy(ref, ref + strlen(ref), key);
    mymap[key] = value;
}
1

Если построение строки из литерала действительно является для вас узким местом измеряемой производительности, вы можете использовать свой собственный класс вместо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;

Похожие вопросы