Итераторы в последовательных контейнерах

[__Heaven__]

Всем доброго времени суток!
Последнее время я больше нацелен не только на результат выполнения определённых операций, но и на скорость их выполнения.
В связи с этим, меня стал интересовать вопрос использования итераторов.
Использование итераторов в ассоциативных контейнерах для меня выглядит как способ быстрого прохода по значениям контейнера.

В последовательных же контейнерах у меня непонятки.
Меня интересует проход по значениям. Раньше я без зазрения совести использовал конструкцию

Код:

for (int i = 0; i < vec.size(); i++)   // или для каждого третьего элемента i += 3
{
    ...
    vec.at(i);
    ...
}

Сточки зрения читабельности для меня этот вариант был удобен.
Сейчас же меня заинтересовала работа с итераторами, но я плохо себе представляю для чего они нужны в последовательных контейнерах, если существует указатель на начало массива данных. В интернете я нашёл, что итератор позволяет модифицировать объекты контейнера без влияния на сам итератор. Но, ведь при модифицировании контейнера можно поменять и указатель...
Объясните, пожалуйста, тёмному человеку преимущества итераторов.
Также интересует скорость работы с итераторами и с указателями.

[Old]

Не так давно был уже знатный срач на эту тему: http://www.prog.org.ru/topic_24541_0.html

[__Heaven__]

Не так давно был уже знатный срач на эту тему: http://www.prog.org.ru/topic_24541_0.html

Хохохо!   и как же я это не нашёл!
Спасибо!

[_Bers]

В целом, итераторы - просто паттерн "универсального" обхода любых контейнеров.

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

То есть, они могут перебирать содержимое любых контейнеров, даже самых замороченных точно так же, как если бы это был какой нибудь обычный массив.

http://ideone.com/4wyh7u

Код:

#include <iostream>     // std::cout
#include <iterator>     // std::ostream_iterator
#include <algorithm>    // std::generate, std::remove
#include <vector>       // std::vector
#include <ctime>        // std::time
#include <cstdlib>      // std::rand, std::srand

using namespace std;

int main() 
{
    //--- создаем и заполняем контейнер случайными данными    
    std::vector<int> data(5);
    std::generate(data.begin(), data.end(), [](){ return (std::rand()%100);}  );
    
    //--- выводим в консоль содержимое контейнера
    std::cout<<" ---1---\n";
    std::copy( data.begin(), data.end(), std::ostream_iterator<int>(std::cout, ", ") );
    std::cout<<'\n';
	
	std::cout<<" ---2---\n";
    for (size_t i = 0, end = data.size() ; i!=end; ++i)
        cout << data[i] << ", ";
    std::cout<<'\n';
    
    std::cout<<" ---3---\n";
    for (auto i = data.begin(), end = data.end(); i!=end ; ++i)
        cout<< *i << ", ";
    std::cout<<'\n';

	
	return 0;
}

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

Есть области, где паттерн "итератор" значительно облегчает жизнь.

Вот например: нужно пройтись по файловой системе, перебирая файлы и папки:

Код:

#include <iostream>
using namespace std;

#include <boost/filesystem.hpp>
namespace fs = boost::filesystem;

int main()
{
    cout<<"WELLCOME TO EXAMPLE APPLICATION!\n";
    fs::path p = fs::current_path();

    std::vector< fs::path > files;
    std::copy( fs::directory_iterator(p), fs::directory_iterator(), std::back_inserter(files) );
    std::copy( files.begin(), files.end(), std::ostream_iterator< fs::path > (std::cout, "\n") );

}

Сначала положит в files список всех файлов и каталогов, а затем выведет в консоль.

Без итераторов данная процедура заняла бы значительно большее количество кода.

[__Heaven__]

Мда…
Пойду ка я книжку умную почитаю, ибо ничего я не знаю о лямбда функциях, а пример с фс вообще не понял…
Спасибо за ответ.

[_Bers]

пример с фс вообще не понял…

Перебираем содержимое каталога программы, и выводим его на экран.

Вот рабочий пример в действии:
http://rextester.com/HUV66703

Тоже самое, но без использования алгоритмов stl:

http://rextester.com/PNAGF68674

Код:

#include <iostream>
using namespace std;

#include <boost/filesystem.hpp>

//псевдоним namespace
//используется для сокращения писанины
namespace fs = boost::filesystem;

int main()
{
    cout<<"WELLCOME TO EXAMPLE APPLICATION!\n";

    //каталог, где была запущена программа    
    fs::path p = fs::current_path();
    cout<<"current path: "<< p<<endl;

    //выводим содержимое этого каталога
    //если встречаем каталог - пишим, что каталог
    //если встречаем обычный файл - пишим, что файл
    cout<< "current directory contains:\n";
    for( fs::directory_iterator it(p), end;  it!=end; ++it  )
        cout << (fs::is_directory(*it)? "directory: " : "file: " )<< *it <<endl; 

    //при этом пустой fs::directory_iterator означает конец каталога
    //именно ему равен созданный по дефолту итератор end
    
    //а само содержимое по итератору может быть либо файлом, либо каталогом, либо ссылкой, либо ...
    //в зависимости от ОС и её причуд
    
    //итератор позволяет единообразно итерироваться по элементам файловой системы независимо от того, чем именно являются эти элементы
    //и при необходимости - узнать подробности о природе элемента, на который указывает итератор
}

[__Heaven__]

Я проверил по скорости исполнения оба кода и получил, что второй, без использования stl алгоритмов, работает в 25 раз быстрее, хоть выводит информации больше.

Можно ли основываясь на этом сделать вывод, что использование stl алгоритмов пагубно влияет на скорость исполнения?

[Bepec]

Потому что в первом имеет место копирование Как известно, это самая нехорошая часть в таких вычислениях А во втором варианте успешно без этого обходятся

[Old]

Я проверил по скорости исполнения оба кода и получил, что второй, без использования stl алгоритмов, работает в 25 раз быстрее, хоть выводит информации больше.

Вы не забыли, что первый вариант запихивает пути в vector, который с этим справляется хуже всего.

Можно ли основываясь на этом сделать вывод, что использование stl алгоритмов пагубно влияет на скорость исполнения?

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

[Bepec]

Чтобы сравнить нужно взять и сравнивать перебор. Т.е. циклы обработки, без подготовки данных.

[_Bers]

Я проверил по скорости исполнения оба кода и получил, что второй, без использования stl алгоритмов, работает в 25 раз быстрее, хоть выводит информации больше.

Можно ли основываясь на этом сделать вывод, что использование stl алгоритмов пагубно влияет на скорость исполнения?

Нельзя.

В первом примере в вектор помещаются все повстречавшиеся fs::path, что ко всему прочему приводит к постоянному реалоку вектора.И только потом содержимое вектора выводится в консоль.

Во втором - только перебор файловых объектов в цикле и вывод на экран.

[Igors]

Вот рабочий пример в действии:
http://rextester.com/HUV66703

Тоже самое, но без использования алгоритмов stl:

http://rextester.com/PNAGF68674

Ну второй как-то "не сильно хуже" и, на мой взгляд, гибче. Понадобится напр обновлять индикатор и/или проверить отмену (юзверь нажал cancel) - и как это встроить в std::copy? А при незатейливом цикле этой проблемы нет. Вообще короткий, элегантный текст обоих примеров достигнут за счет использования мощностей буста, силу итераторов он не демонстрирует 

[Old]

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

Даааа, мощности там задействованы серьезные.

силу итераторов он не демонстрирует 

Потому что вы от них очень многого ждете.

[Igors]

Даааа, мощности там задействованы серьезные.

Очень даже серьезные. Я так вижу Вам не приходилось это в нативняке исполнять - выглядит примерно так (начало)

Код

C++ (Qt)
	FSIterator iterator;
	OSStatus error = FSOpenIterator(&ref, kFSIterateFlat, &iterator);
	if (error) return false;
 
	ItemCount maxCount = 10;
	FSSpec FS[10];
 
	while (true) {
	 error = FSGetCatalogInfoBulk(
	 		 iterator,
			 10,		 		// ItemCount maximumObjects,
			 &maxCount, 		// ItemCount * actualObjects,
			 0, 				// Boolean * containerChanged,
			 kFSCatInfoNone, 	// FSCatalogInfoBitmap whichInfo,
			 0,				// FSCatalogInfo * catalogInfos,
			 0, 				// FSRef * refs,
			 FS,				// FSSpec * specs,
			 0	 			// HFSUniStr255 * names
			); 
	 if (error && error != errFSNoMoreItems) break;		
	 Boolean aliasFileFlag, folderFlag;
 
	 for (int i = 0; i < maxCount; ++i) {
	  OSErr err2 = IsAliasFile(FS + i, &aliasFileFlag, &folderFlag);
...

Главное что вот эту всю грязную работу за меня сделали - и на всех платформах, и за это я даже согласен с итераторами  

[Old]

Очень даже серьезные.

Да, вот это серьезность.

Я так вижу Вам не приходилось это в нативняке исполнять - выглядит примерно так (начало)

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

Код

C++ (Qt)
    DIR *dir;
    struct dirent *entry;
 
    dir = opendir("/");
    if (!dir) {
        perror("diropen");
        exit(1);
    };
 
    while ( (entry = readdir(dir)) != NULL) {
        printf("%d - %s [%d] %d\n",
            entry->d_ino, entry->d_name, entry->d_type, entry->d_reclen);
    };
 
    closedir(dir);
 

ну findfirst/findnext в крайнем случае, а это вы хрень какую-то написали.

И да, так я писал на C (года так до 93), как только у меня появился C++, я сразу сделал для него специальный класс и долгое время использовал его. А потом в boost сделали filesystem.