Итерация по std :: vector: unsigned vs знаковая переменная со знаком

470

Как правильно перебирать вектор в C ++?

Рассмотрим эти два фрагмента кода, этот работает нормально:

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

и этот:

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

который генерирует warning: comparison between signed and unsigned integer expressions.

Я новичок в мире C ++, поэтому unsignedпеременная выглядит немного пугающей для меня, и я знаю, что unsignedпеременные могут быть опасными, если их не использовать правильно, так - это правильно?

Ювал Адам
источник
10
Неподписанный является правильным, потому что polygon.size () имеет тип unsigned. Без знака означает положительный всегда или 0. Это все, что это значит. Таким образом, если использование переменной всегда только для счетчиков, тогда беззнаковый является правильным выбором.
Адам Брусс
3
@AdamBruss .size()не относится к типу unsignedака unsigned int. Это типа std::size_t.
underscore_d
1
@underscore_d size_t - псевдоним неподписанного.
Адам Брусс
2
@AdamBruss No. std::size_t- это определение типа, определяемое _implementation. Смотрите стандарт. std::size_tможет быть эквивалентно unsignedв вашей текущей реализации, но это не имеет значения. Притворство может привести к непереносимому коду и неопределенному поведению.
underscore_d
2
@LF ... конечно, что, вероятно, std::size_tна практике. Как вы думаете, мы уже охватили все это в этом бессвязном потоке комментариев за 6 лет?
underscore_d

Ответы:

817

Для повторения в обратном направлении смотрите этот ответ .

Итерация вперед почти идентична. Просто измените итераторы / своп декремент на приращение. Вы должны предпочесть итераторы. Некоторые люди советуют вам использовать std::size_tв качестве типа переменной индекса. Однако это не переносимо. Всегда используйте size_typetypedef контейнера (хотя в случае прямой итерации вы можете избежать только преобразования в действительности, в действительности std::size_t, в случае обратной итерации он может пойти не так, как надо , если std::size_tон шире, чем typedef size_type) :


Использование std :: vector

Использование итераторов

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

Важно то, что всегда используйте форму приращения префикса для итераторов, определения которых вы не знаете. Это гарантирует, что ваш код работает как можно более универсальным.

Использование диапазона C ++ 11

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

Использование индексов

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

Использование массивов

Использование итераторов

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

Использование диапазона C ++ 11

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

Использование индексов

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

Прочитайте в обратной итерации ответ, к какой проблеме sizeofможет привести подход.

Йоханнес Шауб - Литб
источник
тип указателей размера: использование diff_type может быть более переносимым. попробуйте iterator_traits <element_type *> :: diff_type. это один глоток декларации, но он более переносимый ...
wilhelmtell
wilhelmtell, для чего я должен использовать diff_type? sizeof определен для возврата size_t :) я вас не понимаю. если бы я вычитал указатели друг от друга, разность-тип был бы правильным выбором.
Йоханнес Шауб -
итерация по массивам с использованием техники, которую вы упомянули в этом посте, не будет работать, если итерация выполняется в функции над массивом, переданным этой функции. Потому что размер массива будет возвращать только указатель размера.
системная ошибка
1
@ Nils Я согласен, что использование счетчиков циклов без знака - плохая идея. но поскольку стандартная библиотека использует целочисленные типы без знака для индекса и размера, я предпочитаю типы индекса без знака для стандартной библиотеки. следовательно, другие библиотеки используют только подписанные типы, такие как Qt lib.
Йоханнес Шауб - Lit
32
Обновление для C ++ 11: диапазон основан на цикле. for (auto p : polygon){sum += p;}
Сиюань Рен
170

Прошло четыре года, Google дал мне этот ответ. Со стандартом C ++ 11 (он же C ++ 0x ) на самом деле есть новый приятный способ сделать это (ценой нарушения обратной совместимости): новое autoключевое слово. Это избавляет вас от необходимости явно указывать тип используемого итератора (повторяя векторный тип), когда очевидно (для компилятора), какой тип использовать. С vбыть вашим vector, вы можете сделать что - то вроде этого:

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

C ++ 11 идет еще дальше и дает вам специальный синтаксис для перебора коллекций, таких как векторы. Это устраняет необходимость писать вещи, которые всегда одинаковы:

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

Чтобы увидеть это в работающей программе, создайте файл 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;
}

На момент написания этой статьи, когда вы компилируете это с помощью g ++ , вам обычно нужно настроить его на работу с новым стандартом, задав дополнительный флаг:

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

Теперь вы можете запустить пример:

$ ./auto
17
12
23
42

Обратите внимание, что инструкции по компиляции и запуску относятся к компилятору gnu c ++ в Linux , программа должна быть независимой от платформы (и компилятора).

кратенько
источник
7
C ++ 11 дает вамfor (auto& val: vec)
Флексо
@flexo Спасибо, я не знаю, как я мог забыть это. Не достаточно C ++, я думаю. Не могу поверить, что есть что-то практичное (на самом деле это был синтаксис JavaScript). Я изменил ответ, чтобы включить это.
Кратенко
Ваш ответ очень приятный. Неудобно, что версия g ++ по умолчанию в различных девкитах ОС находится под 4.3, что делает его неработоспособным.
Ратата Тата
Вам нужно инициализировать вектор с помощью std::vector<int> v = std::vector<int>();, или вы могли бы просто использовать std::vector<int> v;вместо этого?
Билл Читам,
@BillCheatham Хорошо - я только что попробовал это без инициализации, и это работало, таким образом, кажется, это работает без.
Кратенко
44

В конкретном случае в вашем примере я бы использовал алгоритмы STL для достижения этой цели.

#include <numeric> 

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

Для более общего, но все же довольно простого случая, я бы пошел с:

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

using namespace boost::lambda;
std::for_each( polygon.begin(), polygon.end(), sum += _1 );
paxos1977
источник
38

Относительно ответа Йоханнеса Шауба:

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

Это может работать с некоторыми компиляторами, но не с gcc. Проблема здесь заключается в том, является ли std :: vector :: iterator типом, переменной (членом) или функцией (методом). Мы получаем следующую ошибку с gcc:

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

Решение использует ключевое слово typename, как сказано:

typename std::vector<T*>::iterator it = v.begin();
for( ; it != v.end(); ++it) {
...
Полат Тузла
источник
2
Вы должны пояснить, что это применимо только тогда, когда Tэто аргумент шаблона, и, следовательно, выражение std::vector<T*>::iteratorявляется зависимым именем. Для того чтобы зависимое имя было проанализировано как тип, ему должно предшествовать typenameключевое слово, как указывает диагностика.
Восстановить Монику
17

Вызов vector<T>::size()возвращает значение типа std::vector<T>::size_type, а не int, unsigned int или иным образом.

Также обычно итерация над контейнером в C ++ выполняется с использованием итераторов , как это.

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

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

Где T - это тип данных, которые вы храните в векторе.

Или , используя различные алгоритмы итерации ( std::transform, std::copy, std::fill, std::for_eachи т.д.).

Джаспер Беккерс
источник
Итераторы, как правило, хорошая идея, хотя я сомневаюсь, что необходимо хранить «конец» в отдельной переменной, и все это можно сделать внутри оператора for (;;).
Саулюс Жемайтайтис
1
Я знаю, что begin () и end () амортизируются постоянным временем, но обычно я нахожу это более читабельным, чем втиснуть все в одну строку.
Джаспер Беккерс
3
Вы можете разбить for на отдельные строки, чтобы улучшить читаемость. Объявление итераторов вне цикла означает, что вам нужно другое имя итератора для каждого цикла в контейнерах разных типов.
Джей Конрод
Я осознаю все различия, и в основном это сводится к личным предпочтениям; это обычно, как я в конечном итоге делать вещи.
Джаспер Беккерс
2
@pihentagy Я думаю, это будет в первом разделе цикла for. например. for (auto i = polygon.begin (), end = polygon.end (); i! = end; i ++)
Джаспер Беккерс
11

Используйте size_t:

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

Цитируя Википедию :

Заголовочные файлы stdlib.h и stddef.h определяют вызываемый тип данных, size_tкоторый используется для представления размера объекта. Библиотечные функции, принимающие размеры, ожидают, что они имеют тип size_t, и оператор sizeof оценивает их size_t.

Фактический тип size_tзависит от платформы; Распространенная ошибка состоит в том, что предполагается, что size_tэто то же самое, что и unsigned int, что может привести к ошибкам программирования, особенно когда 64-битные архитектуры становятся более распространенными.

Игорь Окс
источник
size_t ОК для вектора, так как он должен хранить все объекты в массиве (тоже сам объект), но std :: list может содержать больше, чем элементы size_t!
MSalters
1
size_t обычно достаточно для перечисления всех байтов в адресном пространстве процесса. Хотя я понимаю, что на некоторых экзотических архитектурах это может быть не так, я бы предпочел не беспокоиться об этом.
AFAIK, рекомендуется, #include <cstddef>а не <stddef.h>или, что еще хуже, полностью [c]stdlibиспользовать и использовать, std::size_tа не неквалифицированную версию - и то же самое для любой другой ситуации, когда у вас есть выбор между <cheader>и <header.h>.
underscore_d
7

Немного истории:

Чтобы определить, является ли число отрицательным или нет, используйте бит знака. intтип данных со знаком, означающий, что он может содержать положительные и отрицательные значения (от -2 млрд до 2 млрд). Unsignedможет хранить только положительные числа (и поскольку он не тратит немного времени на метаданные, он может хранить больше: от 0 до около 4 миллиардов).

std::vector::size()возвращает unsigned, а как вектор может иметь отрицательную длину?

Предупреждение говорит вам, что правый операнд вашего оператора неравенства может содержать больше данных, чем левый.

По сути, если у вас есть вектор с более чем 2 миллиардами записей и вы используете целое число для индексации, вы столкнетесь с проблемами переполнения (int вернется к отрицательным 2 миллиардам).

ecoffey
источник
6

Я обычно использую BOOST_FOREACH:

#include <boost/foreach.hpp>

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

Работает с контейнерами STL, массивами, строками в стиле C и т. Д.

Мартин Кот
источник
2
Хороший ответ на какой-то другой вопрос (как я должен перебирать вектор?), Но совсем не то, о чем спрашивал OP (в чем смысл предупреждения о переменной без знака?)
abelenky
3
Ну, он спросил, каков правильный способ итерации по вектору. Так что кажется достаточно актуальным. Предупреждение состоит лишь в том, почему он не доволен своим текущим решением.
jalf
5

Чтобы быть полным, синтаксис C ++ 11 включает только одну версию для итераторов ( ссылка ):

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

Что также удобно для обратной итерации

for(auto it=std::end(polygon)-1; it!=std::begin(polygon)-1; --it) {
  // do something with *it
}
Ян Турош
источник
5

В С ++ 11

Я бы использовал общие алгоритмы, например, for_eachчтобы избежать поиска правильного типа итератора и лямбда-выражения, чтобы избежать дополнительных именованных функций / объектов.

Короткий «симпатичный» пример для вашего конкретного случая (предполагается, что многоугольник - это вектор целых чисел):

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

проверено на: http://ideone.com/i6Ethd

Не забудьте включить: алгоритм и, конечно же, вектор :)

На самом деле у Microsoft есть хороший пример этого:
источник: 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
источник
4
for (vector<int>::iterator it = polygon.begin(); it != polygon.end(); it++)
    sum += *it; 
Мехрдад Афшари
источник
2
Для вектора это хорошо, но обычно лучше использовать ++ это, а не ++, если сам итератор нетривиален.
Стив Джессоп
Лично я привык к использованию ++ i, но я думаю, что большинство людей предпочитают стиль i ++ (фрагмент кода VS по умолчанию для «for» - это i ++). Просто мысль
Mehrdad Afshari
@MehrdadAfshari Кого волнует, что делают "большинство людей"? «большинство людей» ошибаются во многих вещах. Пост-инк / декремент, где предварительное значение никогда не используется, является неправильным и неэффективным, по крайней мере, в теории - независимо от того, как часто оно используется вслепую в кодовом примере ниже везде. Вы не должны поощрять плохие практики, просто чтобы вещи выглядели более знакомыми для людей, которые еще не знают лучше.
underscore_d
2

Первый тип правильный и правильный в некотором смысле. (Если вы думаете о том, что размер никогда не может быть меньше нуля.) Однако это предупреждение кажется мне одним из хороших кандидатов на игнорирование.

Чарли Мартин
источник
2
Я думаю, что это ужасный кандидат, который следует игнорировать - его легко исправить, и время от времени возникают подлинные ошибки из-за ошибок, сравнивающих значения со знаком и без знака ненадлежащим образом. Например, в этом случае, если размер больше, чем INT_MAX, цикл никогда не завершается.
Стив Джессоп
... или, может быть, это немедленно прекращается. Один из двух Зависит от того, преобразуется ли подписанное значение в неподписанное для сравнения или без знака преобразуется в подписанное. На 64-битной платформе с 32-битным int, хотя, как и в win64, int будет повышен до size_t, и цикл никогда не закончится.
Стив Джессоп
@SteveJessop: Вы не можете с уверенностью сказать, что цикл никогда не заканчивается. На итерации когда i == INT_MAX, то i++вызывает неопределенное поведение. В этот момент все может случиться.
Бен Фойгт
@BenVoigt: правда, и до сих пор не дает оснований игнорировать предупреждение :-)
Стив Джессоп
2

Подумайте, нужно ли вообще повторять

<algorithm>Стандартный заголовок дает нам средства для этого:

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);

Другие функции в библиотеке алгоритмов выполняют общие задачи - убедитесь, что вы знаете, что доступно, если хотите сэкономить силы.

Тоби Спейт
источник
1

Непонятная, но важная деталь: если вы скажете «for (auto it)» следующим образом, вы получите копию объекта, а не фактический элемент:

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]

Чтобы изменить элементы вектора, вам нужно определить итератор как ссылку:

for(auto &it : v)
пьер
источник
1

Если ваш компилятор поддерживает это, вы можете использовать диапазон для доступа к элементам вектора:

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

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

Отпечатки: 1 2 3. Обратите внимание, что вы не можете использовать эту технику для изменения элементов вектора.

Бретт Л
источник
0

Два сегмента кода работают одинаково. Тем не менее, unsigned int "маршрут верен. Использование типов unsigned int будет лучше работать с вектором в экземпляре, в котором вы его использовали. Вызов функции-члена size () для вектора возвращает целочисленное значение без знака, поэтому вы хотите сравнить переменную «я» к значению своего собственного типа.

Кроме того, если вы все еще немного обеспокоены тем, как «unsigned int» выглядит в вашем коде, попробуйте «uint». Это в основном сокращенная версия «unsigned int», и она работает точно так же. Вам также не нужно включать другие заголовки, чтобы использовать его.


источник
Целое число без знака для size () не обязательно равнозначно «unsigned int» в терминах C ++, часто «целое число без знака» в этом случае представляет собой 64-битное целое число без знака, тогда как «unsigned int» обычно составляет 32 бита.
Medran
0

Добавляя это, поскольку я не мог найти это упомянутое в любом ответе: для основанной на индексе итерации мы можем использовать, decltype(vec_name.size())который оценил бы кstd::vector<T>::size_type

пример

for(decltype(v.size()) i{ 0 }; i < v.size(); i++) {
    /* std::cout << v[i]; ... */
}
Бхарат С
источник