Наиболее эффективный способ присвоить значения карты карты

Question

Учитывая карту карт, как:

std::map<unsigned int, std::map<std::string, MyBase*>> m_allMyObjects; 

Что бы наиболее эффективным способ, чтобы вставить/добавить/«устанавливать» элемент в m_allMyObjects Дан unsigned int и std::string с учетом оптимизации (на современных компиляторах)?

Что было бы самым эффективным способом получить элемент?

m_allMyObjects потенциально может содержать до 100 000 элементов в будущем.

Answer 1

Общие знания и фольклор о том, как эффективно вставить в карты (как правило, говорят вам, чтобы избежать operator[] и желаемый блестящие новый emplace) рассматривают расходы на строительство и копирования значения от на карте. В вашем случае эти значения являются простыми указателями, которые можно скопировать практически без затрат, а указатели копирования могут быть агрессивно оптимизированы компилятором.

С другой стороны, у вас действительно есть объект, который стоит дорого обрабатывать, а именно: ключ типа std::string. Вам нужно следить за копиями (перемещенными или скопированными) ключа для определения производительности. Очевидно, что для поиска по дереву вам уже нужен объект string, даже если у вас есть его как char *, так как нет функции вставки, которая настроена по типу ключа. Это означает, что для поиска места для вставки вы используете один определенный объект std :: string, но как только узел карты создается, новый объект std :: string внутри карты инициализируется с его копией (возможно, перемещается). Избегайте всех, превышающих эту единственную копию/перемещение, должна быть вашей целью.

Примерное время!

#include <map> 
#include <cstdio> 

struct noisy { 
    noisy(int v) : val(v) {} 
    noisy(const noisy& src) : val(src.val) { std::puts("copy ctor"); } 
    noisy(noisy&& src) : val(src.val)  { std::puts("move ctor"); } 
    noisy& operator=(const noisy& src) 
    { val = src.val; std::puts("copy assign"); return *this; } 
    noisy& operator=(noisy&& src) 
    { val = src.val; std::puts("move assign"); return *this; } 
    int val; 
}; 

bool operator<(const noisy& a, const noisy& b) 
{ 
    return a.val < b.val; 
} 

int main(void) 
{ 
    std::map<noisy,int> m; 
    std::puts("Operator[]"); 
    m[noisy(1)] = 3; 
    std::puts("insert/make_pair"); 
    m.insert(std::make_pair(noisy(2), 3)); 
    std::puts("insert/make_pair/ref"); 
    m.insert(std::make_pair<noisy&&,int>(noisy(3), 3)); 
    std::puts("insert/pair/ref"); 
    m.insert(std::pair<noisy&&,int>(noisy(4), 3)); 
    std::puts("emplace"); 
    m.emplace(noisy(5), 3); 
} 

скомпилирован с г ++ 4.9.1, -std = C++ 11, -O2, результат

Operator[] 
move ctor 
insert/make_pair 
move ctor 
move ctor 
insert/make_pair/ref 
move ctor 
move ctor 
insert/pair/ref 
move ctor 
emplace 
move ctor 

Который показывает: избегать всего, что создает промежуточную пару, содержащую копию ключ! Имейте в виду, что std :: make_pair никогда не создает пару, что содержит ссылок, даже если они могут принимать параметры по ссылке! Всякий раз, когда вы передаете пару, содержащую копию ключа, ключ копируется в пару, а затем на карту.

Выражение, предлагаемое MarkMB, а именно m[int_k][str_k] = ptr, неплохо и, вероятно, создает оптимальный код. Нет оснований для того, чтобы первый индекс (int_k) не использовал [], так как вы хотите, чтобы построил по умолчанию построенный подмаркет, если индекс еще не используется, поэтому лишних накладных расходов нет. Как мы видели, индексирование со строкой уходит с одной копией, так что вы в порядке. Если вы можете позволить себе потерять свою строку, то m[int_k][std::move(str_k)] = ptr может быть победой. Как обсуждалось в начале, использование emplace вместо [] - это только значения, которые фактически могут обрабатываться в вашем случае.