Vector vs Lista

Question

Witam piszę ponieważ natknołem na małą zagwozdkę. Otóż chce stworzyć jakiś kontener, z którego będe mógł wylosować jakiś dowolny element a następnie go usunąć. Zastanawiałem się na początku nad użyciem std::vector<> ponieważ posiada on iterator swobodnego dostępu i można łatwo odwoływać się do elementów.

np. losuje sobie liczbe n=6 , następnie odwołuje się do vectora MyVector[n] i moge sobie działać na wylosowanym obiekcie. Następnie trzeba go usunąć więc używam funkcji vector.erease(n). Problem tkwi tutaj w bardzo słabej efektywności ponieważ za każdym razem kiedy dodaje element do wektora lub usuwam tak naprawdę kopiuję całą tablicę. (raczej kiepsko przy większej ilości danych)

rozwiązanie z listą wydaje się bardziej efektywne ponieważ lista nie ma układu takiego jak tablica i można swobodnie dodawać i usuwać z niej elementy bez utraty na jakości. Ale znowu jak wylosować losowy element?

Bardzo prosiłbym o jakieś sugestie:)

Answer 1

no cóż taka jest specyfika kontenerów :D każdy ma jakieś wady i zalety jeżeli chodzi o liste musiałbyś po prostu przechodzić za każdym razem przez całość (od początku lub od końca) do danego elementu jest to oczywiscie wolniejsze od dostępu bezpośredniego jak w vectorze jednak myśle że lepsze od kopiowania za każdym razem dużej ilości danych, słyszałeś o kontenerach nieuporządkowanych ? przyjrzyj się może unordered_set może to jakoś pomoże :)

Comments

też się nad tym zastanowiłem i postanowiłem skorzystać z listy i z funkcji std::advance(), która pozwoli łatwo przesuwać iterator:). Z chęcią się przyjrzę tym kontenerką dzięki za response!