Как работает вектор?

[ilia.sk8]

Вопрос в том, массив это или список? То есть, если это массив, то как работает push_back за О(1)? А если это список, то получается, что у вектора нету произвольного доступа, то есть v[100] должен работать за 100*С(с=const) операций(а v[10000] за 10000*С). Так что же такое вектор?

[pproger]

массив это. т.е все элементы располагаются в одном непрерывном блоке памяти. если блока не хватает, память перераспределяется. работает он не за O(1), а точнее за амортизированное O(1). при вставке N элементов на самом деле выделяется память для 2*N элементов, чтобы постоянно не вызывать realloc при добавлении новых элементов. иначе время было бы O(n).

[ilia.sk8]

то есть вектор занимает в 2 раза больше памяти, чем массив "такого же размер"?

[coinkrsk]

#include <iostream>
#include <vector>

#define MAX 15
using std::vector;
using std::cout;
using std::endl;

int _tmain(int argc, _TCHAR* argv[])
{

	vector<int> v;

	for ( int i = 0; i < MAX; ++i )
	{
		v.push_back(i);
		cout << i << ": " << v.capacity( ) << endl;
	}
	
	return 0;
}

помедитируй сам

[Obey-Kun]

Реализация может быть разной. Но всегда память непрерывна.

[pproger]

ну вообще я читал в офф стл доке, что увеличение вектора при нехватке памяти всегда квадратичное. в студийном компиляторе оно по всей видимости логарифмичное

[Obey-Kun]

У меня в системе тоже квадратичное. Но стандартом не установлено.