stl: вопрос

0000

Примерный код (точно есть косяки - пишу по памяти)


#include <vector> 

...

std::vector <int> v;

std::vector::iterator i;

...

for (i = v.begin ; i<= v.end; ++i)

{

    if (bla-bla) v.push_back (100);

}|

Вопрос: будет ли элемент 100 в цикле обработан и что вообще с итератором произойдет?

Maurog

думаю, что будет обработан
хотя итератор может сломаться после push_back
так что лучше так не делать

Dasar

для вектора не гарантируется валидность итератора после вставки.
если, например, память под вектор будет перевыделяться, то итератор будет указывать на "левую" область памяти

Maurog

для вектора не гарантируется валидность итератора после вставки
я тоже имею такое мнение, однако задокументировано ли это?
тут не увидел:
http://www.sgi.com/tech/stl/Vector.html

0000

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

Maurog

можно так:


 std::vector<int> v;

 unsigned len = v.size;

 for (unsigned i = 0; i < len; i++)

   {

     ....//обращаемся к элементам вектора так: v[i]

     if (...) v.push_back(100);

   }

evgen5555

Операция "<=" для итератора не определена

Dasar

в лоб так


std::vector <int> v;

std::vector::iterator i;

std::list<int> addedItems;

...

for (i = v.begin ; i<= v.end; ++i)

{

    if (bla-bla) addedItems.push_back (100);

}|



//не помню как точно записывается

v.push_back_all(addedItems);

Maurog

//не помню как точно записывается
v.push_back_all(addedItems);
что за ахтунг?
я бы сделал так


 v.insert(v.end addedItems.begin addedItems.end;

Dasar

это оно и есть

0000

Всем спасибо, буду пробовать

0000

Все заработало, тока вот возник вопрос:
STL и скорость перебора элементов.
Пишу под КПК (WinCE) и перебор элементов этого вектора выполняется каждую перерисовку. После добавления в вектор еще одного отображаемого объекта тормозов прибавлялось так, что видно было заметно на глаз.
Решил проверить свои подозрения и забацал тестик.
Результаты: копец - обычный массив быстрее в 20
Я конечно, упростил ситуацию - в векторе у меня собраны указатели, а в массиве сами объекты (это попроще наверно).
Это действительно такая разница и от частого перебора вектора лучше отказаться? 


#include <windows.h>

#include "auxLib.h"

#include <vector>



class CObject

{

public:

	CObject;

	int         m_SizeX ;

	int         m_SizeY ;

	float       m_PositionX ;

	float       m_PositionY;

};



CObject::CObject

{

	m_SizeX = 0;

	m_SizeY = 0;

	m_PositionX = 0;

	m_PositionY = 0;

};



const int OBJECT_MAX = 50000;



int WINAPI WinMain(HINSTANCE hInstance,

                   HINSTANCE hPrevInstance,

                   LPTSTR    lpCmdLine,

                   int       nCmdShow)

{

	int j;

	DWORD StartTime, EndTime, Result1, Result2; 



	// Тест как вектор

	CObject* pObj;

	std::vector <CObject*> g_Objects;    

	for (j = 0; j<= OBJECT_MAX - 1; j ++)

	{

		pObj = new CObject ;

		g_Objects.push_back (pObj);

	}



	std::vector <CObject*>::iterator i;

	StartTime = GetTickCount ;

	for (i = g_Objects.begin ; i != g_Objects.end ; ++i)

	{

		(*i)->m_SizeX = j + 1;

		(*i)->m_SizeY = j + 2;

		(*i)->m_PositionX = j + 3;

		(*i)->m_PositionY = j + 4;

	}

	EndTime = GetTickCount ;

    Result1 = EndTime - StartTime;



	// Тест массивом

	CObject *pArr= new CObject[OBJECT_MAX];

	CObject *pIt;

	pIt = pArr;

	StartTime = GetTickCount ;

	for (j = 0; j<= OBJECT_MAX - 1; j++)

	{

		pIt->m_SizeX = j + 1;

		pIt->m_SizeY = j + 2;

		pIt->m_PositionX = j + 3;

		pIt->m_PositionY = j + 4;

		pIt++;

	}

	EndTime = GetTickCount ;

	Result2 = EndTime - StartTime;



	Log(L"\nRes1: %i, Res2: %i\n", Result1, Result2);

}

kokoc88

Результаты: копец - обычный массив быстрее в 20
Собери проект в релизе.
И с вектором в твоём случае лучше работать не через итераторы. Есть такая штука T* pT = &v[0] - как указатель на массив.

Marinavo_0507

> T* pT = &v[0]
а говорят, что это на перле код нечитаемый

0000

Разница сократилась - разница в два раза (55 vs 23 в среднем +-3).
Убрал итератор и разница исчезла - крута
(если я конечно не перемудрил).Это нормально так делать? (про запихивание объектов в вектор, они ведь раскопируются и это будет ни один объект?)


	CObject Obj;

	std::vector <CObject> Objects;    

	for (j = 0; j<= OBJECT_MAX - 1; j ++)

		Objects.push_back (Obj);



	CObject *pi;

	pi = &g_Objects[0];

	for (j = 0; j <= OBJECT_MAX; j++)

	{

		...

	}

	EndTime = GetTickCount ;

kokoc88

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

0000

Не, добавление единичны и их скорость совсем не критична.
Спасиб, а то я уж напугался, что с указателями придется работать, а так - всего то надо от итераторов отказаться

iljaden

Спасиб, а то я уж напугался, что с указателями придется работать
а че страшного ? Оо

0000

Ниче, когда с ними постоянно работаешь.

margadon

Операция "<=" для итератора не определена
какое отчаянное гонево

Maurog

в чем гонево?:)
вот гонево:
Есть такая штука T* pT = &v[0] - как указатель на массив

которе является хаком и не гарантируется, что будет работать в каком-либо стл

smit1

>которе является хаком и не гарантируется, что будет работать в каком-либо стл
Это такое же отчаянное гонево, ботай 23.2.4.1

smit1

>в чем гонево?:)
Ботать 23.2.4.1, 24.1.5 до просветления

Maurog

готов почитать
только не очень понял о каком стандарте идет речь
напиши плз

Maurog

это?
Programming-Languages-C++-International-Standart-ISO-IEC-148821998-09-01-Ansi-Standart

smit1

>только не очень понял о каком стандарте идет речь
ANSI-ISO-IEC-14882 2003
Programming languages — C++
как это ни странно

Maurog

сравнение итераторов нашел и понял
а вот в 23.2.4.1 ничего полезного не нашел.
можно цитату, в которой рассказывается про &v[0] ?

Maurog

не могу скачать 2003 =( есть только 1998

Maurog

нашел список изменений 2003 относительно 1998:
A vector is a kind of sequence that supports random access iterators. In addition, it supports (amortized)
constant time insert and erase operations at the end; insert and erase in the middle take linear time. Storage
management is handled automatically, though hints can be given to improve efficiency. The elements of a
vector are stored contiguously, meaning that if v is a vector<T, Allocator> where T is some type
other than bool, then it obeys the identity &v[n] == &v[0] + n for all 0 <= n < v.size.

теперь буду в курсе =)

Maurog

замучался искать я этот стандарт 2003.
ни в гз локалке, ни на торрентсру =\
кое-как скачал в емуле =\

Marinavo_0507

а чё, нормальной бесплатной документации по плюсам не бывает?

poi1981

держи - с++ для чайников
Оставить комментарий
Имя или ник:
Комментарий: