È std :: map :: end-thread-safe ed è garantito che sia sempre lo stesso per lo stesso contenitore?

Question

Io uso std::map e per ottenere un singolo elemento che posso usare: http://www.cplusplus.com/reference/map/map/

• iterator find (const key_type& k);
• mapped_type& at (const key_type& k);
• mapped_type& operator[] (const key_type& k);

anche: lower_bound() o equal_range() - sono le stesse find() in questo caso .

non posso usare:

• at() - perché un'eccezione, e ho misurato 10 volte la degradazione delle prestazioni
• operator[] - perché inserire un elemento, se non esiste, tale comportamento è inaccettabile

find() - è quello che voglio. Ma io uso std::map nel programma multi-thread e proteggerlo dal blocco std::mutex.

Ci sono anche l'inserimento e la rimozione a std::map dagli altri thread.

Devo proteggere std::map::end o è garantito che sia sempre lo stesso per un contenitore allocato?

Posso usare qualcosa come questo static auto const map_it_end = map1.end(); che non è protetto da std::mutex?

http://ideone.com/tATn0H

#include <iostream> 
#include <string> 
#include <mutex> 
#include <thread> 
#include <map> 

std::map<std::string, std::string> map1 ({{"apple","red"},{"lemon","yellow"}}); 
static auto const map_it_end = map1.end(); 
std::mutex mtx1; 

void func() { 
    std::lock_guard<std::mutex> lock1(mtx1); 

    auto it1 = map1.find("apple"); 
    if(it1 != map_it_end) // instead of: if(it1 != map1.end()) 
     std::cout << it1->second << ", "; 
} 

int main() 
{ 
    std::thread t1(func); 
    std::thread t2(func); 
    t1.join(); 
    t2.join(); 

    return 0; 
} 

http://www.cplusplus.com/reference/map/map/end/

gare dati Il contenitore si accede (né il const né le versioni non-const modificano il contenitore). Nessun elemento contenuto è accessibile dalla chiamata, ma l'iteratore restituito può essere utilizzato per accedere a o modificare elementi. L'accesso o la modifica contemporanea di diversi elementi è sicuro.

Answer 1

Devo proteggere std::map::end o è garantito che sia sempre lo stesso per un contenitore allocato?

Tecnicamente qualsiasi chiamata a una funzione membro deve essere protetta da un mutex se può accadere in concomitanza con qualsiasi funzione membro non const. Quindi, se qualsiasi thread potrebbe inserire o cancellare elementi, non è sicuro chiamare end() senza bloccare il mutex.

Posso usare qualcosa come questo static auto const map_it_end = map1.end(); che non è protetto da std::mutex?

È possibile memorizzare nella cache l'iteratore past-the-end, in alcuni casi, perché l'iteratore past-the-end per un std::map non è inficiata dal inserimenti e cancellature, solo potenzialmente scambiando o spostando la mappa.

Ma perché vorresti? L'operazione lenta è find() non end(), quindi se si chiama end() mentre si mantiene ancora il mutex, allora funziona sicuramente.

Se altri thread possono cancellare elementi, è necessario tenere il blocco mutex mentre si denigra l'iteratore restituito da find() per assicurarsi che non venga invalidato da un altro thread che cancella l'elemento a cui fa riferimento. Quindi, di nuovo, effettuare una chiamata a end() non sarà un problema mentre il mutex è già bloccato.

Answer 2

trovo nulla in 23.2 Container requirements che specifica che end() restituisce sempre lo stesso valore, né che è thread-safe. end() è definito come segue.

begin() restituisce un iteratore che fa riferimento al primo elemento nel contenitore . end() restituisce un iteratore che rappresenta il valore passato- per il contenitore. Se il contenitore è vuoto, quindi begin() == end();

Questa specifica sembra coprire end() per tutti i contenitori. Non trovo nulla in 23.4.4 Class template map che sostituisca questo requisito generale del contenitore.In realtà, il valore "Past-the-end" è formulato in modo tale da poter ragionevolmente essere interpretato nel senso che il valore di end() potrebbe cambiare a seconda di cosa/dove è l'ultimo elemento nel contenitore.

E quello sarebbe il caso tipico di un std::vector. Un tipico valore di di cambia a seconda del numero di elementi nel vettore, per ovvi motivi. Nulla specifica che debba farlo, ma di solito è così. Tornando a un std::map, ci si potrebbe aspettare che lo end() di una determinata mappa sia sempre lo stesso valore, ma nessuno dichiara che debba farlo.

Direi che tutti gli accessi a std::map devono essere protetti da un mutex. Una volta rilasciato un mutex, nulla sulla mappa è più valido. Non si può supporre che end() rimanga un iteratore valido, dopo che il mutex viene rilasciato.