Mam listę, z której chcę, aby różne wątki pobierały elementy. Aby uniknąć zablokowania muteksu strzegącego listy, gdy jest pusta, sprawdzam empty()przed zablokowaniem.
W porządku, jeśli wezwanie do list::empty()jest nieprawidłowe w 100% przypadków. Chcę tylko uniknąć awarii lub zakłóceń jednoczesnych list::push()i list::pop()połączeń.
Czy mogę bezpiecznie założyć, że VC ++ i Gnu GCC tylko czasami się empty()mylą i nic gorszego?
if(list.empty() == false){ // unprotected by mutex, okay if incorrect sometimes
mutex.lock();
if(list.empty() == false){ // check again while locked to be certain
element = list.back();
list.pop_back();
}
mutex.unlock();
}
1
Nie możesz tego założyć. Można użyć współbieżne pojemnik jak VC concurrent_queue
—
Panagiotis Kanavos
@Fureeish To powinna być odpowiedź. Dodałbym, że
—
Daniel Langr,
std::list::sizegwarantuje stałą złożoność czasu, co w zasadzie oznacza, że rozmiar (liczba węzłów) musi być przechowywany w osobnej zmiennej; nazwijmy to size_. std::list::emptywtedy prawdopodobnie zwróci coś jako size_ == 0, a jednoczesne odczytywanie i zapisywanie size_spowoduje wyścig danych, a zatem UB.
@DanielLangr Jak mierzy się „stały czas”? Czy jest to pojedyncze wywołanie funkcji czy pełny program?
—
ciekawy,
@curiousguy: DanielLangr odpowiedział na twoje pytanie „niezależnie od liczby węzłów listy”, to jest dokładna definicja O (1), co oznacza, że każde wywołanie jest wykonywane w mniej niż pewnym stałym czasie, niezależnie od liczby elementów. en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions Inna opcja (do C ++ 11) będzie liniowa = O (n), co oznacza, że rozmiar musiałby liczyć elementy (lista połączona), co byłoby jeszcze gorsze dla współbieżność (bardziej oczywisty wyścig danych niż nieatomowy odczyt / zapis licznika).
—
firda
@curiousguy: Biorąc swój przykład z dV, złożoność czasu jest taka sama - ograniczenia matematyczne. Wszystkie te rzeczy są albo rekurencyjnie zdefiniowane, albo w formie „Istnieje C takie, że f (N) <C dla każdego N” - to jest definicja O (1) (dla danego / każdego HW istnieje stała C taka że algo kończy się w czasie krótszym niż C na dowolnym wejściu). Amortyzowana oznacza średnio , co oznacza, że przetworzenie niektórych danych wejściowych może potrwać dłużej (np. Konieczne ponowne przekodowanie / ponowna alokacja), ale nadal jest ona średnio stała (przy założeniu wszystkich możliwych danych wejściowych).
—
firda