Iteracja nad std :: vector: bez znaku vs podpisana zmienna indeksu

469

Jaki jest prawidłowy sposób iteracji po wektorze w C ++?

Rozważ te dwa fragmenty kodu, ten działa dobrze:

for (unsigned i=0; i < polygon.size(); i++) {
    sum += polygon[i];
}

i ten:

for (int i=0; i < polygon.size(); i++) {
    sum += polygon[i];
}

który generuje warning: comparison between signed and unsigned integer expressions.

Jestem nowy w świecie C ++, więc unsignedzmienna wygląda dla mnie trochę przerażająco i wiem, że unsignedzmienne mogą być niebezpieczne, jeśli nie zostaną właściwie użyte, więc - czy to prawda?

Yuval Adam
źródło
9
Ten bez znaku jest poprawny, ponieważ polygon.size () jest typu unsigned. Bez znaku oznacza zawsze wartość dodatnią lub 0. To wszystko, co oznacza. Więc jeśli użycie zmiennej jest zawsze tylko dla zliczeń, to niepodpisany jest właściwym wyborem.
Adam Bruss,
2
@AdamBruss .size()nie jest typu unsignedaka unsigned int. To rodzaj std::size_t.
underscore_d
1
@underscore_d size_t to alias dla niepodpisanego.
Adam Bruss
1
@AdamBruss No. std::size_tto typedef zdefiniowany przez wdrożenie. Zobacz standard. std::size_tmoże być równoważne z unsignedbieżącą implementacją, ale to nie jest istotne. Udawanie, że tak jest, może skutkować nieprzenośnym kodem i niezdefiniowanym zachowaniem.
underscore_d
2
@LF ... pewnie, co prawdopodobnie jest std::size_tw praktyce. Czy uważasz, że omawialiśmy już wszystko w tym szalonym strumieniu komentarzy przez 6 lat?
underscore_d

Odpowiedzi:

816

W celu powtórzenia wstecz zobacz tę odpowiedź .

Iteracja do przodu jest prawie identyczna. Wystarczy zmienić przyrost iteratorów / swapów przyrostowych. Powinieneś preferować iteratory. Niektóre osoby mówią, aby użyć std::size_tjako typu zmiennej indeksu. Nie jest to jednak przenośne. Zawsze używaj size_typetypedef kontenera (chociaż możesz uciec tylko z konwersją w przypadku iteracji do przodu, może tak naprawdę pójść nie tak w przypadku przypadku iteracji do tyłu std::size_t, jeśli std::size_tjest szerszy niż typef size_type) :


Używanie std :: vector

Korzystanie z iteratorów

for(std::vector<T>::iterator it = v.begin(); it != v.end(); ++it) {
    /* std::cout << *it; ... */
}

Ważne jest, aby zawsze używać iteratorów, których definicji nie znasz. To zapewni, że Twój kod będzie działał jak najbardziej ogólny.

Korzystanie z zakresu C ++ 11

for(auto const& value: a) {
     /* std::cout << value; ... */

Korzystanie z indeksów

for(std::vector<int>::size_type i = 0; i != v.size(); i++) {
    /* std::cout << v[i]; ... */
}

Korzystanie z tablic

Korzystanie z iteratorów

for(element_type* it = a; it != (a + (sizeof a / sizeof *a)); it++) {
    /* std::cout << *it; ... */
}

Korzystanie z zakresu C ++ 11

for(auto const& value: a) {
     /* std::cout << value; ... */

Korzystanie z indeksów

for(std::size_t i = 0; i != (sizeof a / sizeof *a); i++) {
    /* std::cout << a[i]; ... */
}

Przeczytaj w odpowiedzi na iterację wsteczną, jaki problem sizeofmoże przynieść to podejście.

Johannes Schaub - litb
źródło
rozmiar typu wskaźników: użycie parametru różnicowego może być bardziej przenośne. spróbuj iterator_traits <typ_elementu>> :: typ_wielkości. to jedna kęsa deklaracji, ale jest bardziej przenośna ...
wilhelmtell
wilhelmtell, do czego powinienem używać różnic_typu? sizeof jest zdefiniowany, aby zwrócić size_t :) Nie rozumiem cię. gdybym odejmował od siebie wskaźniki, właściwym wyborem byłby typ różnicowy.
Johannes Schaub - litb
iteracja nad tablicami przy użyciu techniki wspomnianej w tym poście nie będzie działać, jeśli iteracja jest wykonywana w funkcji na tablicy przekazanej do tej funkcji. Ponieważ tablica sizeof zwróci tylko wskaźnik sizeof.
systemfault
1
@Nils Zgadzam się, że używanie niepodpisanych liczników pętli jest złym pomysłem. ale ponieważ standardowa biblioteka używa niepodpisanych typów liczb całkowitych dla indeksu i rozmiaru, wolę niepodpisane typy indeksów dla standardowej biblioteki. inne biblioteki w konsekwencji używają tylko podpisanych typów, takich jak biblioteka Qt.
Johannes Schaub - litb
32
Aktualizacja dla C ++ 11: zakres oparty na pętli. for (auto p : polygon){sum += p;}
Siyuan Ren,
170

Minęły cztery lata, Google dał mi tę odpowiedź. W przypadku standardowego C ++ 11 (znanego również jako C ++ 0x ) istnieje nowy przyjemny sposób (za cenę zerwania wstecznej kompatybilności): nowe autosłowo kluczowe. To oszczędza ci bólu związanego z jawnym określaniem typu iteratora, który ma być używany (powtarzanie typu wektora ponownie), gdy jest oczywiste (dla kompilatora), jakiego typu użyć. Z vbycia swojej vector, można zrobić coś takiego:

for ( auto i = v.begin(); i != v.end(); i++ ) {
    std::cout << *i << std::endl;
}

C ++ 11 idzie jeszcze dalej i daje specjalną składnię do iteracji po kolekcjach takich jak wektory. Eliminuje to konieczność pisania rzeczy, które zawsze są takie same:

for ( auto &i : v ) {
    std::cout << i << std::endl;
}

Aby zobaczyć to w działającym programie, skompiluj plik auto.cpp:

#include <vector>
#include <iostream>

int main(void) {
    std::vector<int> v = std::vector<int>();
    v.push_back(17);
    v.push_back(12);
    v.push_back(23);
    v.push_back(42);
    for ( auto &i : v ) {
        std::cout << i << std::endl;
    }
    return 0;
}

Pisząc to, kompilując to z g ++ , zwykle musisz ustawić go do pracy z nowym standardem, podając dodatkową flagę:

g++ -std=c++0x -o auto auto.cpp

Teraz możesz uruchomić przykład:

$ ./auto
17
12
23
42

Należy pamiętać, że instrukcje dotyczące kompilowania i uruchamiania są specyficzne dla kompilatora gnu c ++ w systemie Linux , program powinien być niezależny od platformy (i kompilatora).

kratenko
źródło
7
C ++ 11 dajefor (auto& val: vec)
Flexo
@flexo Dzięki, nie wiem jak mogłem o tym zapomnieć. Chyba nie robię wystarczająco dużo C ++. Nie mogłem uwierzyć, że istnieje coś tak praktycznego (tak naprawdę była to składnia JavaScript). Zmieniłem odpowiedź, aby to uwzględnić.
kratenko
Twoja odpowiedź jest bardzo miła. Nieprzyjemne jest to, że domyślna wersja g ++ w różnych programach dla systemów operacyjnych ma poniżej 4.3, co powoduje, że nie działa.
Ratata Tata
Czy potrzebujesz zainicjować wektor std::vector<int> v = std::vector<int>();, czy mógłbyś po prostu użyć std::vector<int> v;zamiast tego?
Bill Cheatham
@BillCheatham Cóż - właśnie wypróbowałem to bez inicjalizacji i zadziałało, więc wygląda na to, że działa bez.
kratenko
44

W konkretnym przypadku w twoim przykładzie użyłbym algorytmów STL, aby to osiągnąć.

#include <numeric> 

sum = std::accumulate( polygon.begin(), polygon.end(), 0 );

W przypadku bardziej ogólnego, ale wciąż dość prostego przypadku, wybrałbym:

#include <boost/lambda/lambda.hpp>
#include <boost/lambda/bind.hpp>

using namespace boost::lambda;
std::for_each( polygon.begin(), polygon.end(), sum += _1 );
paxos1977
źródło
38

Odnośnie odpowiedzi Johannesa Schauba:

for(std::vector<T*>::iterator it = v.begin(); it != v.end(); ++it) { 
...
}

Może to działać z niektórymi kompilatorami, ale nie z gcc. Problem polega na tym, czy std :: vector :: iterator jest typem, zmienną (członkiem) lub funkcją (metodą). W przypadku gcc pojawia się następujący błąd:

In member function void MyClass<T>::myMethod()’:
error: expected `;' before ‘it’
error: ‘it’ was not declared in this scope
In member function ‘void MyClass<T>::sort() [with T = MyClass]’:
instantiated from ‘void MyClass<T>::run() [with T = MyClass]’
instantiated from here
dependent-name ‘std::vector<T*,std::allocator<T*> >::iterator’ is parsed as a non-type, but instantiation yields a type
note: say ‘typename std::vector<T*,std::allocator<T*> >::iterator’ if a type is meant

Rozwiązaniem jest użycie słowa kluczowego „typename”, jak powiedziano:

typename std::vector<T*>::iterator it = v.begin();
for( ; it != v.end(); ++it) {
...
Polat Tuzla
źródło
2
Należy wyjaśnić, że dotyczy Tto tylko argumentu szablonu, a zatem wyrażenie std::vector<T*>::iteratorjest nazwą zależną. Aby nazwa zależna była analizowana jako typ, musi być poprzedzona typenamesłowem kluczowym, jak wskazuje diagnostyka.
Przywróć Monikę
17

Wywołanie w celu vector<T>::size()zwrócenia wartości typustd::vector<T>::size_type , a nie int, unsigned int lub w inny sposób.

Również ogólnie iteracja nad kontenerem w C ++ odbywa się za pomocą iteratorów , takich jak ten.

std::vector<T>::iterator i = polygon.begin();
std::vector<T>::iterator end = polygon.end();

for(; i != end; i++){
    sum += *i;
}

Gdzie T to typ danych przechowywanych w wektorze.

Lub przy użyciu różnych algorytmów iteracji ( std::transform, std::copy, std::fill, std::for_eachi tak dalej).

Jasper Bekkers
źródło
Iteratory są ogólnie dobrym pomysłem, choć wątpię, aby zachodziło potrzeba przechowywania „końca” w osobnej zmiennej i wszystko to można zrobić w instrukcji for (;;).
Saulius Žemaitaitis
1
Wiem, że begin () i end () są zamortyzowanym stałym czasem, ale generalnie uważam, że jest to bardziej czytelne niż wrzucanie wszystkiego do jednej linii.
Jasper Bekkers
3
Możesz podzielić for na osobne linie, aby poprawić czytelność. Zadeklarowanie iteratorów poza pętlą oznacza, że ​​potrzebujesz innej nazwy iteratora dla każdej pętli nad kontenerami różnych typów.
Jay Conrod
Jestem świadomy wszystkich różnic i sprowadza się to do osobistych preferencji; na ogół tak robię.
Jasper Bekkers
2
@pihentagy Myślę, że byłoby to ustawienie w pierwszej sekcji pętli for. na przykład. for (auto i = polygon.begin (), end = polygon.end (); i! = end; i ++)
Jasper Bekkers
11

Użyj size_t:

for (size_t i=0; i < polygon.size(); i++)

Cytując Wikipedię :

Pliki nagłówkowe stdlib.h i stddef.h definiują wywoływany typ danych, size_tktóry jest używany do reprezentowania wielkości obiektu. Funkcje biblioteczne, które przyjmują rozmiary, oczekują, że będą typu size_t, a operator sizeof ocenia size_t.

Rzeczywisty rodzaj size_tzależy od platformy; częstym błędem jest zakładanie, że size_tjest to samo, co bez znaku int, co może prowadzić do błędów programistycznych, szczególnie gdy architektura 64-bitowa staje się bardziej rozpowszechniona.

Igor Oks
źródło
size_t OK dla wektora, ponieważ musi przechowywać wszystkie obiekty w tablicy (sam również obiekt), ale lista std :: może zawierać więcej niż elementy size_t!
MSalters
1
size_t zwykle wystarcza do wyliczenia wszystkich bajtów w przestrzeni adresowej procesu. Chociaż widzę, że może nie być tak w przypadku niektórych egzotycznych architektur, wolałbym się tym nie martwić.
AFAIK zaleca się #include <cstddef>raczej, zamiast, <stddef.h>lub, co gorsza, całość [c]stdlibi używać std::size_tzamiast wersji niekwalifikowanej - i to samo dla każdej innej sytuacji, w której masz wybór pomiędzy <cheader>i <header.h>.
underscore_d
7

Trochę historii:

Aby pokazać, czy liczba jest ujemna, czy nie, użyj bitu „znakowego”. intjest podpisanym typem danych, co oznacza, że ​​może przechowywać wartości dodatnie i ujemne (około -2 miliardy do 2 miliardów). Unsignedmoże przechowywać tylko liczby dodatnie (a ponieważ nie marnuje trochę na metadane, może przechowywać więcej: 0 do około 4 miliardów).

std::vector::size()zwraca an unsigned, bo jak wektor może mieć długość ujemną?

Ostrzeżenie mówi ci, że prawy operand twojej deklaracji nierówności może pomieścić więcej danych niż lewy.

Zasadniczo, jeśli masz wektor z ponad 2 miliardami pozycji i używasz liczby całkowitej do indeksowania, natrafisz na problemy z przepełnieniem (int zawróci do ujemnych 2 miliardów).

ecoffey
źródło
6

Zwykle używam BOOST_FOREACH:

#include <boost/foreach.hpp>

BOOST_FOREACH( vector_type::value_type& value, v ) {
    // do something with 'value'
}

Działa na kontenerach STL, tablicach, ciągach w stylu C itp.

Martin Cote
źródło
2
Dobra odpowiedź na jakieś inne pytanie (jak mam iterować wektor?), Ale zupełnie nie to, o co pytał OP (jakie jest znaczenie ostrzeżenia o zmiennej bez znaku?)
abelenky
3
Zapytał, jaki jest właściwy sposób iteracji po wektorze. Wydaje się to wystarczająco istotne. Ostrzeżenie to tylko dlatego, że nie jest zadowolony ze swojego obecnego rozwiązania.
czerwiec
5

Aby być kompletnym, składnia C ++ 11 umożliwia tylko jedną kolejną wersję iteratorów ( ref ):

for(auto it=std::begin(polygon); it!=std::end(polygon); ++it) {
  // do something with *it
}

Co jest również wygodne w przypadku iteracji odwrotnej

for(auto it=std::end(polygon)-1; it!=std::begin(polygon)-1; --it) {
  // do something with *it
}
Jan Turoň
źródło
5

W C ++ 11

Użyłbym ogólnych algorytmów, takich jak for_eachunikanie wyszukiwania odpowiedniego typu iteratora i wyrażenia lambda, aby uniknąć dodatkowych nazwanych funkcji / obiektów.

Krótki „ładny” przykład dla konkretnego przypadku (zakładając, że wielokąt jest wektorem liczb całkowitych):

for_each(polygon.begin(), polygon.end(), [&sum](int i){ sum += i; });

testowane na: http://ideone.com/i6Ethd

Nie zapomnij podać: algorytmu i, oczywiście, wektora :)

Microsoft ma też ładny przykład:
źródło: http://msdn.microsoft.com/en-us/library/dd293608.aspx

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() 
{
   // Create a vector object that contains 10 elements.
   vector<int> v;
   for (int i = 1; i < 10; ++i) {
      v.push_back(i);
   }

   // Count the number of even numbers in the vector by 
   // using the for_each function and a lambda.
   int evenCount = 0;
   for_each(v.begin(), v.end(), [&evenCount] (int n) {
      cout << n;
      if (n % 2 == 0) {
         cout << " is even " << endl;
         ++evenCount;
      } else {
         cout << " is odd " << endl;
      }
   });

   // Print the count of even numbers to the console.
   cout << "There are " << evenCount 
        << " even numbers in the vector." << endl;
}
jave.web
źródło
4
for (vector<int>::iterator it = polygon.begin(); it != polygon.end(); it++)
    sum += *it; 
Mehrdad Afshari
źródło
2
W przypadku wektora jest to w porządku, ale generalnie lepiej jest używać ++ it zamiast ++, w przypadku gdy sam iterator nie jest trywialny.
Steve Jessop
Osobiście jestem przyzwyczajony do używania ++ i, ale myślę, że większość ludzi woli styl i ++ (domyślny fragment kodu VS dla „for” to i ++). Tylko myśl
Mehrdad Afshari
@MehrdadAfshari Kogo obchodzi, co robią „większość ludzi”? „większość ludzi” myli się co do wielu rzeczy. Post-inc / decrement, w którym wartość wstępna nigdy nie jest używana, jest niepoprawna i nieefektywna, przynajmniej w teorii - niezależnie od tego, jak często jest używana na ślepo w podrzędnym przykładowym kodzie wszędzie. Nie należy zachęcać do złych praktyk, aby rzeczy wyglądały bardziej znajomo dla osób, które jeszcze nie wiedzą lepiej.
underscore_d
2

Pierwszy to poprawny typ i poprawny w pewnym ścisłym znaczeniu. (Jeśli myślisz o tym, rozmiar nigdy nie może być mniejszy niż zero.) To ostrzeżenie uderza mnie jako jednego z dobrych kandydatów do bycia ignorowanym.

Charlie Martin
źródło
2
Myślę, że to straszny kandydat do zignorowania - łatwo to naprawić, a od czasu do czasu pojawiają się prawdziwe błędy z powodu błędów przy niewłaściwym porównywaniu podpisanych / niepodpisanych wartości. Na przykład w tym przypadku, jeśli rozmiar jest większy niż INT_MAX, pętla nigdy się nie kończy.
Steve Jessop
... a może kończy się natychmiast. Jeden z dwóch. Zależy, czy podpisana wartość jest konwertowana na niepodpisaną do porównania, czy niepodpisana jest konwertowana na podpisaną. Jednak na platformie 64-bitowej z 32-bitową int, podobnie jak win64, int zostałby awansowany do size_t, a pętla nigdy się nie kończy.
Steve Jessop
@ SteveJessop: Nie można z całą pewnością powiedzieć, że pętla nigdy się nie kończy. Podczas iteracji kiedy i == INT_MAX, wówczas i++powoduje niezdefiniowane zachowanie. W tym momencie wszystko może się zdarzyć.
Ben Voigt
@BenVoigt: prawda i nadal nie zapewnia podstaw do zignorowania ostrzeżenia :-)
Steve Jessop,
2

Zastanów się, czy w ogóle potrzebujesz iteracji

<algorithm>Standardowy nagłówek dostarcza nam urządzeń do tego:

using std::begin;  // allows argument-dependent lookup even
using std::end;    // if the container type is unknown here
auto sum = std::accumulate(begin(polygon), end(polygon), 0);

Inne funkcje w bibliotece algorytmów wykonują typowe zadania - upewnij się, że wiesz, co jest dostępne, jeśli chcesz zaoszczędzić wysiłku.

Toby Speight
źródło
1

Niewyraźny, ale ważny szczegół: jeśli powiesz „for (auto it)” w następujący sposób, otrzymasz kopię obiektu, a nie rzeczywisty element:

struct Xs{int i} x;
x.i = 0;
vector <Xs> v;
v.push_back(x);
for(auto it : v)
    it.i = 1;         // doesn't change the element v[0]

Aby zmodyfikować elementy wektora, musisz zdefiniować iterator jako odniesienie:

for(auto &it : v)
Pierre
źródło
1

Jeśli Twój kompilator to obsługuje, możesz użyć zakresu opartego na dostęp do elementów wektorowych:

vector<float> vertices{ 1.0, 2.0, 3.0 };

for(float vertex: vertices){
    std::cout << vertex << " ";
}

Wydruki: 1 2 3. Uwaga: nie można użyć tej techniki do zmiany elementów wektora.

Brett L.
źródło
0

Dwa segmenty kodu działają tak samo. Jednak niepodpisana int int jest poprawna. Użycie typów int bez znaku będzie działało lepiej z wektorem w użytej instancji. Wywołanie funkcji elementu size () w wektorze zwraca wartość całkowitą bez znaku, więc chcesz porównać zmienną „i” do wartości własnego typu.

Ponadto, jeśli nadal jesteś trochę zaniepokojony tym, jak w kodzie wygląda „unsigned int”, spróbuj „uint”. Jest to w zasadzie skrócona wersja „unsigned int” i działa dokładnie tak samo. Nie musisz także dołączać innych nagłówków, aby z niego korzystać.


źródło
Niepisana liczba całkowita dla size () niekoniecznie oznacza „bez znaku int” w kategoriach C ++, często „bez znaku liczba całkowita” w tym przypadku jest 64-bitową liczbą całkowitą bez znaku, podczas gdy „bez znaku int” to zwykle 32 bity.
Medran
0

Dodając to, ponieważ nie znalazłem tego w żadnej odpowiedzi: w przypadku iteracji opartej na indeksie możemy użyć parametru, decltype(vec_name.size())który oceniastd::vector<T>::size_type

Przykład

for(decltype(v.size()) i{ 0 }; i < v.size(); i++) {
    /* std::cout << v[i]; ... */
}
Bharat S.
źródło