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

Question

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

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

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

}

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

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

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

Answer 1

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

Answer 2

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

Например

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 3

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

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

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

Answer 4

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

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

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

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

Answer 5

Собственный цикл for (особенно на основе индекса) - это C-way, а не C ++ - way.

Используйте 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 );

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

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

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

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

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

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

Answer 8

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

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

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

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

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