Co naprawdę umożliwia włączenie debugowania iteratora STL?

Question

mam włączony iterator debugowania w aplikacji poprzez zdefiniowanie

_HAS_ITERATOR_DEBUGGING = 1 

Spodziewałem się to naprawdę tylko sprawdzić granice wektora, ale mam wrażenie, że robi dużo więcej niż to. Jakie kontrole itp. Są faktycznie wykonywane?

Dinkumware STL, przy okazji.

Answer 1

Istnieje szereg operacji z iteratorów, które prowadzą do nieokreślonego zachowania, celem tego jest wyzwalacz do aktywacji kontrole uruchomieniowe, aby zapobiec jego występujące (używając twierdzi).

Kwestia

Oczywistym operacja jest użycie nieprawidłowej iterator, ale nieważność ta może wynikać z różnych przyczyn:

• Unitialized iterator
• Iterator do elementu, który został skasowany
• Iterator do elementu, którego fizyczna lokalizacja uległa zmianie (realokacja na vector)
• Iterator poza [begin, end)

Standardowe precyzyjna rozdzierający informacji dla każdego pojemnika, który operacja unieważnia która iteracyjnej.

Jest jakoś mniej oczywistym powodem, że ludzie zapominają: mieszanie iteratory do różnych pojemników:

std::vector<Animal> cats, dogs; 

for_each(cats.begin(), dogs.end(), /**/); // obvious bug 

Ten odnoszą się do bardziej ogólnej kwestii: ważność zakresach przekazywane do algorytmów.

• [cats.begin(), dogs.end()) jest nieważny (dopóki nie jest alias dla innych)
• [cats.end(), cats.begin()) jest nieważny (chyba cats pusty ??)

Roztwór

Rozwiązanie polega dodawanie informacji do iteratorów, tak aby ich ważność i ważność zdefiniowanych przez nich zakresów można było uzyskać podczas wykonywania, uniemożliwiając w ten sposób niezdefiniowanie zachowanie do wystąpienia.

Symbol _HAS_ITERATOR_DEBUGGING służy jako czynnik uruchamiający tę funkcję, ponieważ niestety spowalnia program. Teoretycznie jest to bardzo proste: każdy iterator jest wykonany z kontenera, z którego został wydany iw związku z tym jest powiadamiany o modyfikacji.

W Dinkumware osiąga się to przez dwa dodatki:

• Każdy iterator przenosi wskaźnik do powiązanej z pojemnikiem
• Każdy pojemnik posiada połączoną listę iteratorów to stworzone

i to zgrabnie rozwiązuje nasze problemy:

• Unitizowany iterator nie ma Pojemnik dominująca większość operacji (z wyjątkiem przypisania i zniszczenia) spowoduje twierdzenie
• Iterator do usunięte lub przeniesione elementu został powiadomiony (dzięki liście) oraz znać jego nieważności
• Na zwiększania i zmniejszania iterator Może ona sprawdza, pozostaje w granicach
• sprawdzając, 2 iteratory należą do tego samego pojemnika jest tak proste, jak porównanie ich wskaźniki nadrzędne
• sprawdzenie ważności zakresie jest tak proste, jak sprawdzanie, że dotrzemy do końca zakresu zanim dotrzemy do końca kontenera (operacja liniowa dla tych kontenerów, które nie są losowo dostępne, a więc większość z nich)

Koszt

Koszt jest ciężki, ale nie poprawności ma swoją cenę? Możemy rozbić koszt choć:

• alokacji dodatkowej pamięci (dodatkowy wykaz iteratorów utrzymany): O(NbIterators)
• proces powiadamiania o operacjach mutującymi: O(NbIterators) (Zauważ, że push_back lub insert niekoniecznie unieważnia iteratory, ale erase robi) kontrola prawidłowości
• zakres: O(min(last-first, container.end()-first))

Większość algorytmów biblioteki mają oczywiście wdrożono f lub maksymalna efektywność, zazwyczaj kontrola jest wykonywana raz na zawsze na początku algorytmu, następnie uruchamiana jest niezaznaczona wersja.Jednak prędkość może poważnie spowolnić, szczególnie z pętlami odręcznymi:

for (iterator_t it = vec.begin(); 
    it != vec.end();    // Oups 
    ++it) 
// body 

Wiemy, że Oups linia jest zły smak, ale tutaj jest jeszcze gorzej: w każdym przebiegu pętli, tworzymy nowy iterator następnie go zniszczyć, co oznacza przydzielanie i zwalnianie węzła dla listy iteratorów vec ... Czy muszę podkreślić koszt przydzielania/zwalniania pamięci w ciasnej pętli?

Oczywiście, taki problem nie pojawiłby się w przypadku for_each, co stanowi kolejny ważny argument w kierunku wykorzystania algorytmów STL zamiast wersji kodowanych ręcznie.

Answer 2

O ile mi zrozumieć:

_HAS_ITERATOR_DEBUGGING wyświetli okno dialogowe, w czasie wykonywania dochodzić żadnych nieprawidłowe korzystanie iterator tym:

1) iteratory stosowanych w pojemniku po elemencie zostanie skasowana

2) Iterators stosowane w wektorach po .Push() lub .Założyć() jest wywoływana

Answer 3

Według http://msdn.microsoft.com/en-us/library/aa985982%28v=VS.80%29.aspx

Standard C++ opisuje, które funkcje składowe powodują, że iteratory w kontenerze stają się nieważne. Dwa przykłady to:

• Usunięcie elementu z pojemnika powoduje, że iteratory elementu stają się nieważne.
• Zwiększenie rozmiaru wektora (wciśnięcie lub wstawienie) powoduje, że iteratory w pojemniku wektorowym stają się nieważne.