LINUX.ORG.RU

[C++] Особенности реализации std::vector


0

0

Поведение std::vector при добавлении нового элемента с помошью push_back оказалось для меня неожиданным. Ниже приведён исходный текст программы и результат её работы:


#include <string>
#include <vector>
#include <iostream>

class Foo
{
	public:
		Foo(const std::string& n):
			name(n)
		{ std::cout << "Foo(const std::string&)(" << name << ")" << std::endl; }

		Foo(const Foo& f):
			name(f.name)
		{ std::cout << "Foo(const Foo&)(" << name << ")" << std::endl; }


		~Foo()
		{ std::cout << "~Foo(" << name << ")" << std::endl; }

	private:
		std::string name;
};

int main(int argc, char* argv[])
{
	std::vector<Foo> v;
	
	v.push_back(Foo("a"));
	v.push_back(Foo("b"));
	v.push_back(Foo("c"));

	return 0;
}


Foo(const std::string&)(a)
Foo(const Foo&)(a)
~Foo(a)
Foo(const std::string&)(b)
Foo(const Foo&)(a)
Foo(const Foo&)(b)
~Foo(a)
~Foo(b)
Foo(const std::string&)(c)
Foo(const Foo&)(a)
Foo(const Foo&)(b)
Foo(const Foo&)(c)
~Foo(a)
~Foo(b)
~Foo(c)
~Foo(a)
~Foo(b)
~Foo(c)

Я ожидал, что конструктор будет вызван 6 раз (из них 3 раза копирующий), а получилось, что при добавлении элемента в конец вектора перебираются все его элементы. При этом ещё и создаются их временные копии. В исходниках std::vector сам чёрт ногу сломит. Не подскажите, где можно почитать про особенности реализации данного контейнера. У Страуструпа ничего толкового не нашёл (или просто искал плохо?).


а с включенной оптимизацией + reserve?

lester ★★★★ ()

Перераспределдяется память ведь. Вектор растёт. Надо предварительно вызывать v.reserv(x).

anonymous ()

> Не подскажите, где можно почитать про особенности реализации данного контейнера. У Страуструпа ничего толкового не нашёл (или просто искал плохо?).

реализаций на самом деле много - и, да, они отличаются

lester ★★★★ ()
#include <string>
#include <vector>
#include <iostream>

using namespace std;

int main(int argc, char* argv[])
{
	vector<int> v;
	for (int i = 0; i < 10000000; ++i)
	{
		size_t capacity = v.capacity();
		v.push_back(0);
		if (v.capacity() != capacity)
		{
			cout << "capacity " << v.capacity() << endl;
		}
	}
   return 0;
}
capacity 1
capacity 2
capacity 4
capacity 8
capacity 16
capacity 32
capacity 64
capacity 128
capacity 256
capacity 512
capacity 1024
capacity 2048
capacity 4096
capacity 8192
capacity 16384
capacity 32768
capacity 65536
capacity 131072
capacity 262144
capacity 524288
capacity 1048576
capacity 2097152
capacity 4194304
capacity 8388608
capacity 16777216
anonymous ()
Ответ на: комментарий от anonymous

> Перераспределдяется память ведь. Вектор растёт. Надо предварительно вызывать v.reserv(x).

Да. Вызов reserve помог. Но мне казалось, что память и так должна выделяеться блоками сразу на несколько элементов с запасом. А так, получается, при v.size() == v.capacity() придётся снова явно вызывать reserve. Ну или писать свой аллокатор. Иначе при большом количестве элементов код будет неэффективен за счёт лишнего копирования объектов.

gcc version 4.3.2 (Debian 4.3.2-1.1)

SSN ()
Ответ на: комментарий от SSN

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

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

lester ★★★★ ()
Ответ на: комментарий от SSN

Показано же в примере, что у меня в GCC 4.4.3 размер щедро увеличивается сразу в 2 раза. Если заранее известен размер, то или reserve-push_back или resize-operator[].

anonymous ()
Ответ на: комментарий от anonymous

спасибо. Действительно надо было посмотреть на большем количестве элементов. Вопросов более не имею.

SSN ()
Ответ на: комментарий от SSN

> Иначе при большом количестве элементов код будет неэффективен за счёт лишнего копирования объектов.

за счет того что std::vector увеличивает свой размер экспоненциально, получится что эта неэффективность не так уж велика, неэффективность будет всего лишь линейной от количества push_back(), так что это не страшно.

Но конечно, никто не мешает тебе сделать reserve если размер известен.

dilmah ★★★★★ ()
Ответ на: комментарий от dilmah

> неэффективность будет всего лишь линейной от количества push_back(), так что это не страшно.

тут все зависит от задачи - если будет много «мелких» объектов, которые содержат в себе вектор, в который набивается 10-20 элементов, то неэффективность будет достаточно большой

lester ★★★★ ()

Я может конечно криворукий, но как-то тестировал std::vector, QList, QVector и свой самописный вариант. Результат - std::vector столь тормозной, что хоть вешайся.

shutty ()
Ответ на: комментарий от shutty

> Результат - std::vector столь тормозной, что хоть вешайся.

а reserve, опять же, делал?

lester ★★★★ ()
Ответ на: комментарий от SSN

>Иначе при большом количестве элементов код будет неэффективен за счёт лишнего копирования объектов.

Именно это и происходит во всех других языках. Ну, с поправкой на то, что массивы могут реализовываться как списки/деревья, и/или хранить ссылки.

legolegs ★★★★★ ()
Ответ на: комментарий от lester

а reserve, опять же, делал?


делал. сравнивал по следующим параметрам:
1. Создание+удаление
2. добавление элемента (да, с резервом)
3. доступ к элементу

сливало. щас уже подробностей не помню.

shutty ()
Ответ на: комментарий от shutty

> 1. Создание+удаление

Полагаю делался v.erase(iterator). Это медленно.
А вот если так:
std::swap(*iterator, v.back());
v.resize(v.size() - 1);
будет уже существенно быстрее. Правда порядок элементов в контейнере нарушится. Но не всегда порядок критичен.

andreyu ★★★★★ ()
Ответ на: комментарий от andreyu

> Правда порядок элементов в контейнере нарушится. Но не всегда порядок критичен.

так может проще std::set тогда взять?

lester ★★★★ ()
Ответ на: комментарий от lester

>> Правда порядок элементов в контейнере нарушится. Но не всегда порядок критичен.

так может проще std::set тогда взять?

Так в set свой порядок, ради которого оно балансироваться любит. А если порядок совсем не важен, то выше описанный фокус с вектором хорошо пойдёт.

const86 ★★★★★ ()
Ответ на: комментарий от const86

> Так в set свой порядок, ради которого оно балансироваться любит

да, зато поиск очень быстрый

А если порядок совсем не важен, то выше описанный фокус с вектором хорошо пойдёт


в принципе да - надо смотреть по задаче

lester ★★★★ ()

Помнится, у меня такая же проблема была, причём всё осложнялось тем, что объекты, лежащие в vector'е, ссылались на объекты, лежащие в других vector'ах. Соответственно, при беспорядочном добавлении, всё нафиг путалось.

Никак не мог понять, что за фигня, пока не догадался посмотреть адреса объектов.

Obey-Kun ★★★★★ ()
Ответ на: комментарий от Obey-Kun

> лежащие в vector'е, ссылались на объекты, лежащие в других vector'ах.

а я тебе писал, что нельзя делать указатели на элементы вектора :)

lester ★★★★ ()
Ответ на: комментарий от lester

а если сначала все вектора заполнить, а потом сделать ссылки? у меня сейчас так и реализовано. или все равно list? то, как сейчас, работает.

Obey-Kun ★★★★★ ()
Ответ на: комментарий от Obey-Kun

> а если сначала все вектора заполнить, а потом сделать ссылки?

нет и еще раз нет :) это ты сейчас думаешь, что заполнил - и все, а потом человек другой( или ты сам ) добавит копирование/добавление и т.п. - и все, жопа

lester ★★★★ ()
Ответ на: комментарий от lester

лады, то есть тут точно использовать list / QLinkedList?

Obey-Kun ★★★★★ ()
Ответ на: комментарий от Obey-Kun

Если ты ссылаешься на объект - то будь добр храни в листе ссылки

namezys ★★★★ ()
Ответ на: комментарий от namezys

> ссылки

имеешь в виду не ссылки, а то, на что ссылаюсь?

ну я так себе и представлял это... так и поступлю, в общем.

Obey-Kun ★★★★★ ()
Ответ на: комментарий от Obey-Kun

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

Obey-Kun ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.