Usuwanie z kontenera - który sposób lepszy?

Chcę wywalić wszystko z deque(początkowo uzywalem vectora ale zdecydowalem sie na deque, czy to dobrze?) jednocześnie wykonując pewną operacje dla każdego z nich.
Wymyśliłem dwa sposoby, i zastanawiam się który jest lepszy.
(pseudokody)
Pierwsza część jest taka sama dla obydwu sposobów:

std::deque<b2Body*> toDelete;
void setToDelete(b2Body* obj)
{
 bool ok(true);
    for(const b2Body* b: toDelete)
    {
        if(b == obj) // sprawdź czy wskaźnik już był dodany. inaczej będzie crash
        {
        ok = false;
        }
    }

    if(ok) {
    toDelete.push_back(obj);
    }
}

Na drugą cześć, gdzie usuwam, mam dwa sposoby:
Sposób 1

 while(toDelete.empty())
    {
        world.DestroyBody(toDelete.back());
        toDelete.pop_back();
    }

• Sposób 2**

for(const b2Body* b : toDelete)
{
world.DestroyBody(b);
}
toDelete.clear();

Który sposób jest lepszy i dlaczego? + czy dobrze zrobiłem używając deque zamiast std::vector?

Dodanie do tej tablicy (czy tam kolejki) jest nieefektywne, bo za każdym razem lecisz po całym kontenerze. Raczej używałbym czegoś w stylu std::set. Samo usuwanie to już pikuś, range for z auto wygląda ładniej (i powinno być szybsze), a clear raczej nie jest potrzebne.

Zabawa gołymi wskaźnikami trochę razi, choć w tym przypadku opakowanie tego w jakiś unique_ptr wygląda trochę jak przerost formy nad treścią.

twonek napisał(a):

Dodanie do tej tablicy (czy tam kolejki) jest nieefektywne, bo za każdym razem lecisz po całym kontenerze. Raczej używałbym czegoś w stylu std::set. Samo usuwanie to już pikuś, range for z auto wygląda ładniej (i powinno być szybsze), a clear raczej nie jest potrzebne.

Zabawa gołymi wskaźnikami trochę razi, choć w tym przypadku opakowanie tego w jakiś unique_ptr wygląda trochę jak przerost formy nad treścią.

poznaj może najpierw std::deque, a potem kłam, że dodawanie jest nieefektywne; wszystko jest efektywne dopóki pracujesz na pierwszym lub ostatnim elemencie,

std::set wymaga zdefiniowanego operator< lub funkcji sortującej + sortuje co insert co czyni go milion razy mniej wydajnym od deque (jeżeli warunki są spełnione), pewnie miałeś na myśli unordered_set

edit:
sposób 2

gośćabc napisał(a):

poznaj może najpierw std::deque, a potem kłam, że dodawanie jest nieefektywne; wszystko jest efektywne dopóki pracujesz na pierwszym lub ostatnim elemencie,

To pokaż mi pierwszy i ostatni element w tym kodzie:

for(const b2Body* b: toDelete)
{
    if(b == obj) // sprawdź czy wskaźnik już był dodany. inaczej będzie crash
    {
        ok = false;
    }
}

twonek napisał(a):

gośćabc napisał(a):

poznaj może najpierw std::deque, a potem kłam, że dodawanie jest nieefektywne; wszystko jest efektywne dopóki pracujesz na pierwszym lub ostatnim elemencie,

To pokaż mi pierwszy i ostatni element w tym kodzie:

for(const b2Body* b: toDelete)
{
    if(b == obj) // sprawdź czy wskaźnik już był dodany. inaczej będzie crash
    {
        ok = false;
    }
}

a gdzie w tym kawałeczku masz modyfikację chlopaku, że tak mi cytujesz kod, który nie modyfikuje kontenera?

on tutaj tylko sprawdza czy już dodał ten wskaźnik, a pod spodem używa push_back, który nie invaliduje nic i działa świetnie z std::deque

Przy każdej operacji push_back leci po całym kontenerze. Może powiesz mi, że to jest efektywne?

twonek napisał(a):

Przy każdej operacji push_back leci po całym kontenerze. Może powiesz mi, że to jest efektywne?

to jest spieprzona logika a nie wina złego kontenera;

gośćabc napisał(a):

twonek napisał(a):

Przy każdej operacji push_back leci po całym kontenerze. Może powiesz mi, że to jest efektywne?

to jest spieprzona logika a nie wina złego kontenera;

No to teraz cytuj, gdzie napisałem, że to jest nieefektywne z winy kontenera?

Dodanie do tej tablicy (czy tam kolejki) jest nieefektywne,

edit:
już nic więcej nie pisz znawco, bo mi ciśnienie skoczyło

gośćabc napisał(a):

Dodanie do tej tablicy (czy tam kolejki) jest nieefektywne,
bo za każdym razem lecisz po całym kontenerze.

Umiesz czytać całe zdanie, czy tylko wybrane przez siebie fragmenty i bić pianę?

tak bo operacja push_back wymaga iterowania po całym kontenerze,

no z matołem gadam

A ja chyba z analfabetą. Piszę do autora lecisz po całym kontenerze, a nie operacja push_back leci po całym kontenerze. Widzisz różnicę?

ok to jeżeli poszedłem z rozumowaniem za daleko i powinienem odczytać to dosłownie, to co podmiana na set da?

g**no, tak jak całe Twoje rozumowanie

Ja tylko dodam od siebie, ze zgodnie z dokumentacją, push_back jak i pop_back mają Complexity Constant.
Co znaczy(chyba, nie jestem pewny) że koszt operacji jest niezależny od rozmiaru kontenera.

@gośćabc, Wiem że trudno ci to zrozumieć, więc przyjmij następujące rzeczy na wiarę:

1. Koszt operacji wyszukania elementu wg wartości w deque wynosi O(n)
2. Koszt operacji wyszukania elementu wg wartości w set wynosi O(log(n))
3. n > log(n)

_13th_Dragon napisał(a):

@gośćabc, Wiem że trudno ci to zrozumieć, więc przyjmij następujące rzeczy na wiarę:

1. Koszt operacji wyszukania elementu wg wartości w deque wynosi O(n)
2. Koszt operacji wyszukania elementu wg wartości w set wynosi O(log(n))
3. n > log(n)

zapomiałeś wspomnieć o kosztach insertu do set i deque, ale żeby było Ci łatwiej zrozumieć to daj wiarę temu, że dodanie elementu na końcu czy początku deque jest szybsze o std::set insert czy emplace

edit:

ale Bóg ma Cię w swojej opiece pewnie i Cię ukarze za półprawdy, które lubisz wypisywać

Argument z operatorem< nie jest poprawny, ponieważ std::less ma specjalizację dla wskaźników (których porównanie w innym przypadku mogłoby być UB - jeśli nie są częścią tego samego obiektu lub tablicy).

zapomiałeś wspomnieć o kosztach insertu do set i deque, ale żeby było Ci łatwiej zrozumieć to daj wiarę temu, że dodanie elementu na końcu czy początku deque jest szybsze o std::set insert czy emplace
Ale @abbq tutaj nie robi samego push_back tylko find (ale dla "ułatwienia" pisze sobie pętlę) + push_back, czyli ma O(n) + O(1) = O(n).

Ja bym proponował std::unordered_set.

gośćabc napisał(a):

zapomiałeś wspomnieć o kosztach insertu do set i deque, ale żeby było Ci łatwiej zrozumieć to daj wiarę temu, że dodanie elementu na końcu czy początku deque jest szybsze o std::set insert czy emplace

No to przyjmij również za wiarę, że n + 1 > log(n) dla odpowiednio dużych n.

@abbq musisz poprawić logikę tak, aby dodawać do kolejki raz, i mieć pewność, że nie dodasz tego samego wskaźnika drugi raz,

oni wolą, żebyś zrobił find zamiast poprawił błędy w logice, co już zasugerowałem chyba w 6 poście

@gośćabc, Widzę że kolejny banalny problem jest dla ciebie niezbyt oczywisty, więc cię wytłumaczę "na palcach" w kodzie (od autora postu):

 bool ok(true);
    for(const b2Body* b: toDelete)
    {
        if(b == obj) // sprawdź czy wskaźnik już był dodany. inaczej będzie crash
        {
        ok = false;
        }
    }
 
    if(ok) {
    toDelete.push_back(obj);
    }

wyraźnie widać (dla każdego myślącego i znającego C++ człowieka) że najpierw się sprawdza czy element istnieje w kontenerze po czym jeżeli nie istnieje to się go dodaje, więc

1. Dla deque O(n) - sprawdzenie; O(1) - wstawienie razem O(n)
2. Dla set O(log(n)) - sprawdzenie razem z wstawieniem; razem O(log(n))
3. Mam nadzieje że to "n > log(n)" już sobie zanotowałeś.

@abbq, http://www.cplusplus.com/reference/unordered_set/unordered_set/
Ale podejrzewam że b2Body jest twoją własną klasą więc zastanów się nad:

std::deque<b2Body*> toDelete;
void setToDelete(b2Body* obj)
{
    if(!obj->MarkToDelete)
    {
        obj->MarkToDelete=true;
        toDelete.push_back(obj);
    }
}
// oczywiście razem ze sposobem 2

przy takim podejściu deque jest lepsze, z tym że testy pokazują że przy dużych rozmiarach vector i tak przebija wydajnościowo.

Dobra, ostatecznie przekonało mnie użycie std::unordered_set do rozwiązania tego problemu.
Dwa pytania:

1. jeżeli zrobię kontener.insert(wskaźnik) funkcja nie będzie miała żadnego efektu, jeśli wskaźnik już jest, tak wiec nie muszę się martwić o duplikaty?
2. Ważnym aspektem, o którym nie wspomniałem a powinienem, poza tym i tak za bardzo odeszliście od tematu wiec już wam nie przeszkadzałem, jest to ze kontener zazwyczaj nie będzie zawierał nawet 10 elementów! dlatego też mógłbym przeboleć te stracone nanosekundy.

Jeżeli mam racje co do pierwszego pytania, to moje ostateczne rozwiązanie wyglądałoby mniej wiecej tak:

std::unordered_set<b2Body*> toDelete;
void World::setToDelete(b2Body* obj)
{
 toDelete.insert(obj);
}

  for(const auto o : toDelete)
  {
        world.DestroyBody(o);
    }
    toDelete.clear();

Co o nim sądzicie?

1. Tak.
2. To std::vector lub zostaw ten std::unordered_set dla wygody.

@abbq, jeżeli z jakichś racji bardziej sensownych niż: - "Bo nie" nie możesz zrobić tak jak napisałem tu: http://4programmers.net/Forum/1102286
to z unordered_set jest najlepiej.

Edit:

std::vector<b2Body*> toDelete;
void setToDelete(b2Body* obj)
{
    if(obj->userData!=&toDelete)
    {
        obj->userData=&toDelete;
        toDelete.push_back(obj);
    }
}

@_13th_Dragon
Nieźle. Musisz mieć sporo wolnego czasu, że chciało Ci się zerknąć na tą bibliotekę :) Jednocześnie rozwiązałeś mój przyszły problem! Tak to jest, jak się nie zna wszystkich możliwości biblioteki.
Wielkie dzięki.