Reallocation памяти контейнера std::vector

@voipp · Регистрация: 30.04.2011

расширение памяти в этом контейнере происходит по логарифмическому закону. Объясните , пожалуйста, знатоки, зачем это нужно?

@nexen · 25.06.2013, 15:52

@voipp, все просто, если ты пытаешься вставить элемент, но размер вектора уже исчерпан, он увеличивается в 2 раза. Нужно это для того, чтобы при каждом добавлении новой переменной не выделять заново память. Сравни, у тебя в массиве 1024 элемента, ты решил поштучно добавить по 1 элементу столько же. Размер самого массива, скажем, тоже 1024. Добавив ещё 1, массив расширился до 2048 и ты легко добавил свои элементы в уже выделенный массив, в отличие от того, когда ты 1024 раза добавляешь элементы и выделяешь, и освобождаешь память вновь и вновь, и вновь, и вновь, и вно..

@voipp · 25.06.2013, 16:55 **[ТС]**

Сообщение от nexen

@voipp, все просто, если ты пытаешься вставить элемент, но размер вектора уже исчерпан, он увеличивается в 2 раза. Нужно это для того, чтобы при каждом добавлении новой переменной не выделять заново память. Сравни, у тебя в массиве 1024 элемента, ты решил поштучно добавить по 1 элементу столько же. Размер самого массива, скажем, тоже 1024. Добавив ещё 1, массив расширился до 2048 и ты легко добавил свои элементы в уже выделенный массив, в отличие от того, когда ты 1024 раза добавляешь элементы и выделяешь, и освобождаешь память вновь и вновь, и вновь, и вновь, и вно..

Это понятно, но не понятно, почему выбирается логарифмический размер! Я так понимаю, что считается функция log()

@nexen · 25.06.2013, 17:19

@voipp, вы о чем?.. Я же сказал, размер увеличивается в 2 раза каждый раз, т.е в 2, 4, 8, 16, 32, 64. Логарифм тут причем? Или 5-ое увеличение размера дает 5 = log2(Multiplier==32)

Tulosba · 25.06.2013, 18:25

@nexen, кстати рост емкости вектора в 2 раза или в любое другое кол-во раз совсем не стандартизован. VS2010 например увеличивает емкость на 50%, при нехватке размера, а вовсе не в 2 раза.

@nexen · 25.06.2013, 20:21

@Tulosba, тогда я ещё меньше понима вопрос про log автора темы :0

Croessmah · 25.06.2013, 21:40

Сообщение от nexen

Я же сказал, размер увеличивается в 2 раза каждый раз

Сообщение от nexen

@Tulosba, тогда я ещё меньше понима вопрос про log автора темы :0

Все зависит от реализации. Может быть вообще использован какой-нибудь хитроумный алгоритм

Tulosba · 25.06.2013, 22:40

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

@voipp 0 / 0 / 0 Регистрация: 30.04.2011 Сообщений: 68
		1
	Reallocation памяти контейнера std::vector 25.06.2013, 15:47. Просмотров 962. Ответов 7 Метки нет (Все метки) расширение памяти в этом контейнере происходит по логарифмическому закону. Объясните , пожалуйста, знатоки, зачем это нужно? 0

@nexen 187 / 180 / 25 Регистрация: 27.01.2012 Сообщений: 1,335
	25.06.2013, 15:52	2
	@voipp, все просто, если ты пытаешься вставить элемент, но размер вектора уже исчерпан, он увеличивается в 2 раза. Нужно это для того, чтобы при каждом добавлении новой переменной не выделять заново память. Сравни, у тебя в массиве 1024 элемента, ты решил поштучно добавить по 1 элементу столько же. Размер самого массива, скажем, тоже 1024. Добавив ещё 1, массив расширился до 2048 и ты легко добавил свои элементы в уже выделенный массив, в отличие от того, когда ты 1024 раза добавляешь элементы и выделяешь, и освобождаешь память вновь и вновь, и вновь, и вновь, и вно.. 1

@voipp 0 / 0 / 0 Регистрация: 30.04.2011 Сообщений: 68
	25.06.2013, 16:55 [ТС]	3
	Сообщение от nexen @voipp, все просто, если ты пытаешься вставить элемент, но размер вектора уже исчерпан, он увеличивается в 2 раза. Нужно это для того, чтобы при каждом добавлении новой переменной не выделять заново память. Сравни, у тебя в массиве 1024 элемента, ты решил поштучно добавить по 1 элементу столько же. Размер самого массива, скажем, тоже 1024. Добавив ещё 1, массив расширился до 2048 и ты легко добавил свои элементы в уже выделенный массив, в отличие от того, когда ты 1024 раза добавляешь элементы и выделяешь, и освобождаешь память вновь и вновь, и вновь, и вновь, и вно.. Это понятно, но не понятно, почему выбирается логарифмический размер! Я так понимаю, что считается функция log() 0

@nexen 187 / 180 / 25 Регистрация: 27.01.2012 Сообщений: 1,335
	25.06.2013, 17:19	4
	@voipp, вы о чем?.. Я же сказал, размер увеличивается в 2 раза каждый раз, т.е в 2, 4, 8, 16, 32, 64. Логарифм тут причем? Или 5-ое увеличение размера дает 5 = log2(Multiplier==32) 0

Tulosba :) 4764 / 3258 / 497 Регистрация: 19.02.2013 Сообщений: 9,046
	25.06.2013, 18:25	5
	@nexen, кстати рост емкости вектора в 2 раза или в любое другое кол-во раз совсем не стандартизован. VS2010 например увеличивает емкость на 50%, при нехватке размера, а вовсе не в 2 раза. 1

@nexen 187 / 180 / 25 Регистрация: 27.01.2012 Сообщений: 1,335
	25.06.2013, 20:21	6
	@Tulosba, тогда я ещё меньше понима вопрос про log автора темы :0 0

Croessmah Don't worry, be happy 16958 / 9839 / 1895 Регистрация: 27.09.2012 Сообщений: 24,393 Записей в блоге: 2
	25.06.2013, 21:40	7
	Сообщение от nexen Я же сказал, размер увеличивается в 2 раза каждый раз Сообщение от nexen @Tulosba, тогда я ещё меньше понима вопрос про log автора темы :0 Все зависит от реализации. Может быть вообще использован какой-нибудь хитроумный алгоритм 1

Tulosba :) 4764 / 3258 / 497 Регистрация: 19.02.2013 Сообщений: 9,046
	25.06.2013, 22:40	8
	@Croessmah, главное, что следует иметь в виду: везде выделение идет с запасом. С учетом ожидания новых вставок в вектор. 1

Опции темы