Russian Qt Forum

Программирование => С/C++ => Тема начата: Igors от Февраля 03, 2013, 10:13



Название: std::map (поиск + вставка)
Отправлено: Igors от Февраля 03, 2013, 10:13
Добрый день

Код
C++ (Qt)
typedef std::pair <int, int> TPair;
typedef std::map<int, int> TMap;
TMap theMap;
TPair elem(1, 2);
 
TMap::iterator it = theMap.find(elem.first);
if (it == theMap.end())
theMap.insert(elem);
else
it->second += elem.second;
 
 
Если элемента нет в мапе - вставляем, иначе наращиваем value. Однако поиск выполняется дважды: один раз для проверки, второй для вставки. Как избежать этих затрат?

Спасибо


Название: Re: std::map (поиск + вставка)
Отправлено: Old от Февраля 03, 2013, 10:23
Однако поиск выполняется дважды: один раз для проверки, второй для вставки.
Почему не просто так:
Код
C++ (Qt)
theMap[ elem.first ] += elem.second;
 


Название: Re: std::map (поиск + вставка)
Отправлено: vregess от Февраля 03, 2013, 10:32
Код
C++ (Qt)
TMap::iterator it = theMap.lower_bound(elem.first);
 
if (it != theMap.end() && !theMap.key_comp()(elem.first, it->first))
 // do update
else
 theMap.insert(it, elem);
 

подробности: совет 24. Эффективное использование STL, Мейерс.


Название: Re: std::map (поиск + вставка)
Отправлено: Old от Февраля 03, 2013, 10:47
Код
C++ (Qt)
TMap::iterator it = theMap.lower_bound(elem.first);
 
if (it != theMap.end() && !theMap.key_comp()(elem.first, it->first))
 // do update
else
 theMap.insert(it, elem);
 
Вы процитировали практически дословно operator[] из map. ;)


Название: Re: std::map (поиск + вставка)
Отправлено: Igors от Февраля 03, 2013, 11:33
Почему не просто так:
Код
C++ (Qt)
theMap[ elem.first ] += elem.second;
 
В общем случае конструктор по умолчанию может и не устроить. Может так
Код
C++ (Qt)
size_t old = theMap.size();
int & value = theMap[elem.first];
if (theMap.size() > old)
value = elem.second;
else
valie += elem.second;
 

Код
C++ (Qt)
TMap::iterator it = theMap.lower_bound(elem.first);
 
if (it != theMap.end() && !theMap.key_comp()(elem.first, it->first))
 // do update
else
 theMap.insert(it, elem);
 
Да, вставка с хинтом (читал но не сообразил). Спасибо

Вы процитировали практически дословно operator[] из map. ;)
А можно подробнее (а то все намеками  :))


Название: Re: std::map (поиск + вставка)
Отправлено: Old от Февраля 03, 2013, 11:37
Может так
;D
А чем отличается:
Код
C++ (Qt)
val = defaultVal;
от
Код
C++ (Qt)
val = 0; //Создается конструктором
val += defaultVal;
 


Название: Re: std::map (поиск + вставка)
Отправлено: Old от Февраля 03, 2013, 11:38
А можно подробнее (а то все намеками  :))
В смысле подробней?
Это код оператора [] из map.


Название: Re: std::map (поиск + вставка)
Отправлено: vregess от Февраля 03, 2013, 12:31
Это код оператора [] из map.

С той лишь разницей, что не создается лишний объект конструктором по умолчанию.