После этих операции итератор end() становиться невалидным. Лучше использовать while для таких операций

http://www.cppreference.com/wiki/stl/iterators#invalidating_iterators

А это как интересно?

>end() становиться невалидным

не верю (Ц)

> не верю

по ссылкам кликать не умеешь или может быть английский не осилил?

for(std::list<int>::iterator i = list.begin(); i != list.end(); i++ ) {...}

по ссылкам кликать не умеешь или может быть английский не осилил?

«list/map: erase only invalidates iterators to the erased element(s) & no others.»

;)

all hail lists!

Типичный разработчик на C++. Что, прямо метод становится не валидным, да? Раньше он возращала итератор на конец контейнера, а теперь что?

end() тут ваще-то каждый раз берется по новой, так что за это можно не боятся. Хреново будет, если erase сделать на текущий элемент, тогда i++ даст хрень.

for(std::list<int>::iterator i = list.begin(); i != list.end(); i++ ) {...} 

толстые дядьки не рекомендуют называть переменную итератора i и рекомендуют пользоваться префиксным инкрементом

for(std::list<int>::iterator it = list.begin(); it != list.end(); ++it ) {...} 

как то так

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

и вообще, стоит задуматься, может таки стоит юзать вещи типа std::remove_if и иже с ними? они для этого кошернее подходят

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

Итераторы дают возможность абстрагироваться от деталей реализации. Читай SICP.

для единообразия, а т.к. в C++ появился новый оператор for - надобность в прямом использовании итераторов будет гораздо меньше

> Итераторы дают возможность абстрагироваться от деталей реализации

чем перегруженный оператор [] хуже такой абстракции?

чем перегруженный оператор [] хуже такой абстракции?

Для списков он имеет сложность O(N).

>Вопрос: на сколько безопасно и переносимо применять внутри данного цикла операции insert, erase, splice к объекту list? Как обстоят дела с другими контейнерами - последовательностями?

Оно и не может быть безопасно, поскольку в процессе итерации может выскочить экзепшен и оставить все в позе зю. Поэтому при итерировании через контейнер надо формировать отдельную модифицированную коллекцию, а потом делать swap(). Читай Саттера про транзакционную семантику работы с данными.

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

бугага :)

цитируем

template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class vector : protected _Vector_base<_Tp, _Alloc> 
{

[..]

public:
  typedef _Tp value_type;

[..]

  typedef value_type* iterator;
  typedef const value_type* const_iterator;
  typedef value_type& reference;
  typedef const value_type& const_reference;

это, если Вы поняли, кусок реализации std::vector

то есть когда Вы пишете std::vector<int>::iterator - это всего лишь int*, то бишь указатель на базовый элемент, заметьте не какой то там мистический хрен-в-супе с разноцветным силиконовым наполнителем

а вот так определён operator[]

  reference operator[](size_type __n) { return *(begin() + __n); }
  const_reference operator[](size_type __n) const { return *(begin() + __n); }

ну и чё? при переборе всех элементов накукуй каждый раз высчитывать абсолютное смещение если можно просто взять соседний элемент, заметьте без вызовов функций, без арифметических операций

а т.к. в C++ появился новый оператор for

а???

> Для списков он имеет сложность O(N).

ну это уже вопрос оптимизации для частного случая, причем наверняка не составило бы большого труда написать реализацию, для которой последовательные обращения [n][n+1], компилятор смог бы оптимизировать

а???

vector<int> data;
for( int& it : data ) ++it;

> Итераторы дают возможность абстрагироваться от деталей реализации

чем перегруженный оператор [] хуже такой абстракции?

вместо операции ++type_ptr мы вызываем функции operator[], begin(), копируем int значение, складываем результат begin() и значение и возвращаем ссылку на разыменованный адрес

а так ничем :) для однократного доступа - гораздо лучше operator[], для последовательного перебора - итератор

а! range-based for-loop :) это из нового стандарта? оно принято уже?

чёт пока как то ссыкотно его пока использовать, а ну как непереносимый будет :) типа в gcc написал, стал переносить под оффтопик а там всё переписывать

> вместо операции ++type_ptr мы вызываем функции operator[], begin(), копируем int значение, складываем результат begin() и значение и возвращаем ссылку на разыменованный адрес

а так ничем :) для однократного доступа - гораздо лучше operator[], для последовательного перебора - итератор

вы лучше сначала попробуйте сравнить скорость работы со стандартными контейнерами через [] и через итераторы ;)

вы лучше сначала попробуйте сравнить скорость работы со стандартными контейнерами через [] и через итераторы ;)

эм, а що там таки сравнивать - всё прозрачно (в случае вектора точно прозрачно :))

для вектора при вызове [] выполняется минимум 2 вызова функций и операция +, и это это вместо обычного инкремента указателя, будет тупо медленнее в 99,9999% случаев :)

хотите ещё какой контейнер обсудить?

> будет тупо медленнее в 99,9999% случаев :)

я вас шокирую - но будет тупо одинаково

> будет тупо медленнее в 99,9999% случаев :)

я вас шокирую - но будет тупо одинаково

на векторе содержащем 3 элемента - конечно разника будет не различима (!), но то именно неразличима, если же мы будем работать с 1,000,000 элементов, то ситуация уже может быть не столь однозначной

вспомните одну из причин отказа от рекурсивного обхода дерева, не ту которая «я чёт не врубаюсь к чему это»

ха - все еще смешнее:

#include <time.h>
#include <vector>

int main( void )
{
	std::vector<int> data( 10000000 );

	clock_t start = clock();

	std::vector<int>::iterator it = data.begin();
	for( ; it < data.end() ; ++it )
		*it += rand();

	clock_t end1 = clock();
	float interval1 = 1.0f * ( end1 - start ) / CLOCKS_PER_SEC;

	size_t count = data.size();
	for( size_t i = 0 ; i < count ; ++i )
		data[ i ] += rand();

	clock_t end2 = clock();
	float interval2 = 1.0f * ( end2 - end1 ) / CLOCKS_PER_SEC;

	printf( "time1: %f\ntime2: %f\n", interval1, interval2 );
	fgetc( stdin );

	for( size_t i = 0 ; i < count ; ++i )
		printf( "%d", data[ i ] );

	return 0;
}

собирал в VC2010

Debug: 7.141, 0.656 Release: 0.125, 0.125

итого итераторы слили по полной в неоптимизированном варианте, а с оптисмизацией, как я и говорил, никакой разницы

это просто праздник знаний с++ какойто.

при вызове [] выполняется минимум 2 вызова функций

может осмелитесь подтвердить это утверждение листингом ? с O2+ разумеется.

> для вектора при вызове [] выполняется минимум 2 вызова функций и операция +

зачем функции? inline тут отлично подходит - что и показывает результат без оптимизации, ну и как раз для итераторов надо вызывать метод - end()

это просто праздник знаний с++ какойто

+1

дэмс, чёт как то неласковая картина получается, видимо всё дело в волшебных «пизурьках» (видимо лоханулся с inline) :) Вы были правы

модифицировал немного код, добавил тест для for_each, на 1 ляме результат не очень стабильный потому взял 10 лямов, чтобы отсечь флуктуации берём среднее из 10 прогонов

#include <iostream>

#include <algorithm>
#include <time.h> 
#include <vector> 

void functor(int& i) {
	i = rand();
}

int main(void)
{

	unsigned int data_items_count = 10000000;
	float interval1 = 0, interval2 = 0, interval3 = 0;
	clock_t checkpoint1, checkpoint2, checkpoint3, checkpoint4;

	std::vector<int> data( data_items_count ); 

	float avg_time1 = 0.0, avg_time2 = 0.0, avg_time3 = 0.0;
	unsigned int try_count = 10;

	for(int index = 0; index < try_count; ++index ) {

	// --- begin cycle 1 ---
 
	std::vector<int>::iterator it = data.begin(); 
 
	checkpoint1 = clock(); 

	for( ; it < data.end(); ++it ) {
		*it += rand(); 
	}

	// --- begin cycle 2 ---
 
	checkpoint2 = clock(); 
    	
	for( size_t i = 0 ; i < data_items_count; ++i ) {
		data[ i ] += rand(); 
	}
 
	// --- begin cycle 3 --- 

	checkpoint3 = clock(); 	

	std::for_each( data.begin(), data.end(), functor);

	// --- end cycles ---

	checkpoint4 = clock();

	interval1 = 1.0f * ( checkpoint2 - checkpoint1 ) / CLOCKS_PER_SEC; 
	interval2 = 1.0f * ( checkpoint3 - checkpoint2 ) / CLOCKS_PER_SEC; 
	interval3 = 1.0f * ( checkpoint4 - checkpoint3 ) / CLOCKS_PER_SEC; 

	std::cout << "intermediate times" << std::endl;
	std::cout << "iterator  : " << interval1 << std::endl;
	std::cout << "operator[]: " << interval2 << std::endl;
	std::cout << "for_each  : " << interval3 << std::endl;
	std::cout << "------------------" << std::endl;

	avg_time1 += interval1;
	avg_time2 += interval2;
	avg_time3 += interval3;
	}

	avg_time1 /= try_count;
	avg_time2 /= try_count;
	avg_time3 /= try_count;

	std::cout << "fill times" << std::endl;
	std::cout << "iterator  : " << avg_time1 << std::endl;
	std::cout << "operator[]: " << avg_time2 << std::endl;
	std::cout << "for_each  : " << avg_time3 << std::endl;

	return 0;
}

итак, результаты такие

1) без оптимизации /Od

fill times
iterator  : 1.6434
operator[]: 0.607
for_each  : 0.5454

2) с оптимизацией /O2

fill times
iterator  : 0.5457
operator[]: 0.4828
for_each  : 0.4696

вывод какой? вывод простой

1) юзаем std::for_each

2) ???

3) profit

sleepy, jtootf

спасибо Вам мужики за умные и содержательные комментарии по делу :)

я лучше подожду коммунC++0x и буду пользоваться for( int& it : data ) :)

кстати он уже не за горами - VC2010 вот-вот зарелизится, gcc 4.5 тоже на подходе

кстати он уже не за горами - VC2010 вот-вот зарелизится, gcc 4.5 тоже на подходе

ждём, ждём :)

спасибо Вам мужики за умные и содержательные комментарии по делу :)

да не за что, обращайся

Стандарт окончательно примут в 2011.

operator[] для связного списка? Хм.

кстати, мне стало интересно и я раскопал for_each, долго угорал

вот он

// for_each.  Apply a function to every element of a range.
template <class _InputIter, class _Function>
_Function for_each(_InputIter __first, _InputIter __last, _Function __f) {
  __STL_REQUIRES(_InputIter, _InputIterator);
  for ( ; __first != __last; ++__first)
    __f(*__first);
  return __f;
}

разница только в в одном - у for_each есть шаблон :) интересно как это влияет на результат

1) В шаблоне каждый раз не вызывается на проверку функция возвращающая последний итератор (сливается при оптимизации так как функция встраивается)

2) rand() генерирует цисла равномерно но не «равновременно», на разные числа в поседовательности тратиться разное время. Так что проверять господа нужно не подряд друг за другом в одной программе а в разных программах на ОДИНАКОВЫХ последовательностях случайных чисел. Так что приведенные результаты с оптимизацией это не быстрота перебера а быстрота генерации случайных чисел,

у меня для 100000000 получилось с -O2

fill times
iterator  : 1.345
operator[]: 1.471
for_each  : 1.528

заменяя rand() на константу и убирая сложения в 1 и 2 для достижения одинаковых условий, получаются одинаковые результаты

fill times
iterator  : 1.73
operator[]: 1.676
for_each  : 1.7

> operator[] для связного списка? Хм.

точно так же «дико», как и для вектора использовать только абстракцию итератор, что в принципе я и хотел сказать

> rand() генерирует цисла равномерно но не «равновременно», на разные числа в поседовательности тратиться разное время. Так что проверять господа нужно не подряд друг за другом в одной программе а в разных программах на ОДИНАКОВЫХ последовательностях случайных чисел

я его добавил, т.к. шибко умный VC2010 с включенной оптимизацией судя по всему тупо объединял два цикла в один, в итоге первый всегда выполнялся за 0.015с, а второй - за 0с, без различия какой поставить первым

даже такая конструкция как transform (data3.begin(), data3.end(), data3.begin(), bind2nd(plus<int>(), 1)); ничего не меняет. Результаты по времени абсолютно одинаковые во всех трёх случаях.

#include <iostream>

#include <algorithm>
#include <ctime>
#include <vector>
#include <functional>

using namespace std;

int main(void)
{

	const unsigned int data_items_count = 100000000;
	const double cps = 1.0 / CLOCKS_PER_SEC;
	const unsigned int try_count = 10;

	vector<int> data1( data_items_count );
	vector<int> data2( data_items_count );
	vector<int> data3( data_items_count );

	srand(time(0));
	generate(data1.begin(), data1.end(), rand);
	generate(data2.begin(), data2.end(), rand);
	generate(data3.begin(), data3.end(), rand);
	
	clock_t checkpoint1, checkpoint2;

	checkpoint1 = clock();
	for(int index = 0; index < try_count; ++index )
	{
		for(std::vector<int>::iterator it = data1.begin(); it != data1.end(); ++it )
		{
			*it += 1;
		}
	}
	checkpoint2 = clock();
	cout << "iterator  : " << cps * (checkpoint2 - checkpoint1) << std::endl;
	
	checkpoint1 = clock();
	for(int index = 0; index < try_count; ++index )
	{
		for( size_t i = 0 ; i < data_items_count; ++i )
		{
			data2[ i ] += 1;
		}
	}
	checkpoint2 = clock();
	cout << "operator[]: " << cps * (checkpoint2 - checkpoint1) << std::endl;

	checkpoint1 = clock();
	for(int index = 0; index < try_count; ++index )
	{
		transform (data3.begin(), data3.end(), data3.begin(), bind2nd(plus<int>(), 1));
	}
	checkpoint2 = clock();
	cout << "for_each  : " << cps * (checkpoint2 - checkpoint1) << std::endl;

	return 0;
}

rand() генерирует цисла равномерно но не «равновременно», на разные числа в поседовательности тратиться разное время. Так что проверять господа нужно не подряд друг за другом в одной программе а в разных программах на ОДИНАКОВЫХ последовательностях случайных чисел. Так что приведенные результаты с оптимизацией это не быстрота перебера а быстрота генерации случайных чисел,

думал об этом, придумал как обойти, пока нет времени попробовать - вечером затестю

странно, а машина какая и компилятор?

заменяя rand() на константу

представляешь что при включенном /O2 там остаётся? :)

> operator[] для связного списка? Хм.

точно так же «дико», как и для вектора использовать только абстракцию итератор, что в принципе я и хотел сказать

а вот тут есть нюанс, о котором ЕМНИП Вы сами и упоминали, что итератора есть и для вектора и для связанного списка, а вот [] только для вектора, с учётом того что мы выяснили что при /O2 никакой разницы нет, то использовать итераторы кошернее :)