C++: Правильный способ перебора контейнеров STL

Question

В моем проекте движка я широко использую STL, в основном классы std::string и std::vector.

Во многих случаях мне приходится проходить через них. Сейчас, как я делаю это:

for(unsigned int i = 0; i < theContainer.size(); i ++) 
{ 

} 

• я делаю это правильно?

• Если нет, то почему, и что мне делать вместо этого?

• Действительно ли размер() выполняется каждый цикл цикла с этой реализацией? Потеря производительности будет незначительной?

Answer 1

Обычно правильный способ «перебора» по контейнеру использует «итераторы». Что-то вроде

string myStr = "hello"; 
for(string::iterator i = myStr.begin(); i != myStr.end(); ++i){ 
    cout << "Current character: " << *i << endl; 
} 

Конечно, если вы не собираетесь изменять каждый элемент, то лучше использовать string::const_iterator.

И да, size() вызывается каждый раз, и это O (п), поэтому во многих случаях потеря производительности будет заметно и это O (1), но это хорошая практика для расчета размера до цикл, чем вызов размера каждый раз.

Answer 2

STL контейнеры поддерживают итераторы

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

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

Answer 3

• Для контейнеров с произвольным доступом это не так.

• Но вместо этого вы можете использовать итераторы.

  for (string::const_iterator it = theContainer.begin(); 
      it != theContainer.end(); ++it) { 
      // do something with *it 
  } 
  

• Есть некоторые обстоятельства, при которых компилятор может оптимизировать прочь .size() (или .end() в случае итератора) вызывает (например, только const доступа, функция pure). Но не зависеть от этого.

Answer 4

Возможно, вы захотите ознакомиться с стандартными алгоритмами.

Например

vector<mylass> myvec; 

// some code where you add elements to your vector 

for_each(myvec.begin(), myvec.end(), do_something_with_a_vector_element); 

где do_something_with_a_vector_element это функция, которая делает то, что происходит в цикле

, например

void 
do_something_with_a_vector_element(const myclass& element) 
{ 
// I use my element here 
} 

много стандартных алгоритмов - см http://www.cplusplus.com/reference/algorithm/ - поэтому большинство вещи поддерживаются

Answer 5

Вы делаете это нормально для векторов, хотя это не соответствует правильному пути для других контейнеров.

Более общий способ

for(std::vector<foo>::const_iterator i = theContainer.begin(); i != theContainer.end; ++i) 

который больше типирование, чем мне очень нравится, но будет гораздо более разумным с переопределением auto в предстоящем стандарте. Это будет работать на всех стандартных контейнерах. Обратите внимание, что вы ссылаетесь на человека foo на номер *i и используете &*i, если хотите его адрес.

В вашей петле .size() выполняется каждый раз. Тем не менее, это постоянное время (стандартное, 23.1/5) для всех стандартных контейнеров, поэтому оно не замедлит вас, если вообще. Дополнение: Стандарт говорит, что «должен» иметь постоянную сложность, поэтому особенно плохая реализация может сделать его не постоянным. Если вы используете такую ​​плохую реализацию, вам придется беспокоиться о других проблемах с производительностью.

Answer 6

Нет, это неправильный способ сделать это. Для ::std::vector или ::std::string он отлично работает, но проблема в том, что если вы когда-либо используете что-либо еще, это не будет работать так хорошо. Кроме того, это не идиоматично.

И, чтобы ответить на ваш другой вопрос ... Функция size, вероятно, встроена. Это означает, что он скорее всего извлекает значение из внутренних элементов ::std::string или ::std::vector. Компилятор будет оптимизировать это и просто извлечь его один раз в большинстве случаев.

Но вот идиоматический способ:

for (::std::vector<Foo>::iterator i = theContainer.begin(); 
    i != theContainer.end(); 
    ++i) 
{ 
    Foo &cur_element = *i; 
    // Do stuff 
} 

++i очень важен. Опять же, для ::std:vector или ::std::string, где итератор в основном является указателем, это не так важно. Но для более сложных структур данных это так. i++ должен сделать копию и создать временную, потому что старое значение нужно придерживаться. ++i не имеет такой проблемы. Входите в привычку всегда использовать ++i, если у вас нет веской причины не делать этого.

Наконец, theContainer.end() также будет в целом оптимизирован из существования. Но вы можете заставить вещи, чтобы быть немного лучше, делая это:

const ::std::vector<Foo>::iterator theEnd = theContainer.end(); 

for (::std::vector<Foo>::iterator i = theContainer.begin(); i != theEnd; ++i) 
{ 
    Foo &cur_element = *i; 
    // Do stuff 
} 

Конечно, C++ 0x упрощает все это существенно с новым синтаксисом for петель:

for (Foo &i: theContainer) 
{ 
    // Do stuff with i 
} 

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

Answer 7

Родной для цикла (особенно на основе индексов) - это C-образный, а не C++-путь.

Используйте BOOST_FOREACH для петель.

Сравните, для контейнера целых чисел:

typedef theContainer::const_iterator It; 
for(It it = theContainer.begin(); it != theContainer.end(); ++it) { 
    std::cout << *it << std::endl; 
} 

и

BOOST_FOREACH (int i, theContainer) { 
    std::cout << i << std::endl; 
} 

Но это не идеальный способ. Если вы можете выполнять свою работу без цикла - вы ДОЛЖНЫ делать это без цикла. Например, с алгоритмами и Boost.Phoenix:

boost::range::for_each(theContainer, std::cout << arg1 << std::endl); 

Я понимаю, что эти решения обеспечивают дополнительные зависимости в вашем коде, но повышающий «должен иметь» для современного C++.

Answer 8

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

#include <iostream> 
#include <vector> 
#include <string> 

using namespace std; 

int main() 
{ 
    vector<string> vs; 
    vs.push_back("One"); 
    vs.push_back("Two"); 
    vs.push_back("Three"); 

    for (const auto &s : vs) 
    { 
     cout << s << endl; 
    } 

    return 0; 
}