Форум программистов, компьютерный форум CyberForum.ru

Std::set( vector ) и расход памяти - C++

Восстановить пароль Регистрация
 
sim1246
0 / 0 / 0
Регистрация: 14.05.2014
Сообщений: 8
14.05.2014, 10:40     Std::set( vector ) и расход памяти #1
Здравствуйте!
Пытаюсь разобраться сколько памяти съедают контейнеры и никак не могу понять следующее. Вот есть код( ниже)
В конце стоит бесконечный цикл(знаю что так делать нельзя) только для того чтобы в таск менеджере посмотреть сколько памяти мы съели.
На экран выводится:
size1= 0.4666; size2 = 1,430;
size3 = 4,1008
При этом в таск менеджере расход показывает 6,11
Если set заменить на вектор ( выделив ему память ровно столько сколько элементов )
то вывод останется таким же а в таск менеджере мы увидим число 3,45.
Почему в случае set памяти больше чем size3?
и меньше в случае вектора?
Спасибо
Upd в строке 3 vtos() преобразует число в строку
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
    
set<string> res;
    for(uint x = 0; x<100000;++x) res.insert( vtos(x,0) );
    uint result = 0;
    cout << "Res.size() == " << res.size() << endl;
    uint size1=0;uint size2=0;uint size3=0;
    set<string>::const_iterator it=res.begin();
    for(;it!=res.end();++it){
        string str = *it;
        size1+=str.size();
        size2+=str.capacity();
        size3+=str.capacity() + sizeof(string);
}
    cout << "size1 == " << ((float)size1)/1024/1024 << endl;
    cout << "size2 == " << ((float)size2)/1024/1024 << endl;
    cout << "size3 == " << ((float)size3)/1024/1024 << endl;
while(true){}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.05.2014, 10:40     Std::set( vector ) и расход памяти
Посмотрите здесь:

std::map, std::vector и порядок обхода коллекции C++
Инициализация std::set C++
std::vector Перераспределение памяти C++
C++ vector<vector<double>> + std::sort()
reallocation памяти контейнера std::vector C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
aLarman
636 / 557 / 89
Регистрация: 13.12.2012
Сообщений: 2,109
14.05.2014, 11:42     Std::set( vector ) и расход памяти #2
Цитата Сообщение от sim1246 Посмотреть сообщение
Почему в случае set памяти больше чем size3?
м.б накладные расходы на контейнер ?)
Ilot
Модератор
Эксперт С++
1765 / 1140 / 221
Регистрация: 16.05.2013
Сообщений: 3,017
Записей в блоге: 5
Завершенные тесты: 1
14.05.2014, 11:43     Std::set( vector ) и расход памяти #3
Давайте рассуждать логически. Множество в большинстве случаев имеет структуру в виде дерева, а значит ему необходим дополнительный объем памяти для хранения указателей правого и левого поддерева для каждого элемента. В случае вектора такие указатели не нужны так как выделяется непрерывный объем памяти.
Цитата Сообщение от sim1246 Посмотреть сообщение
Почему в случае set памяти больше чем size3?
Наверное имелось ввиду это:
C++
1
size3+=str.capacity() + sizeof(set<string>);
Так не проверяли? Потому как у вас явно указатели не входят в sizeof.
aLarman
636 / 557 / 89
Регистрация: 13.12.2012
Сообщений: 2,109
14.05.2014, 11:45     Std::set( vector ) и расход памяти #4
set в данном случае наверняка RB-tree, каждый элемент содержит еще 2 указателя (минимум 4*2*100000 байт доп.расхода памяти)
Ilot
Модератор
Эксперт С++
1765 / 1140 / 221
Регистрация: 16.05.2013
Сообщений: 3,017
Записей в блоге: 5
Завершенные тесты: 1
14.05.2014, 11:46     Std::set( vector ) и расход памяти #5
aLarman, ну вот и я об этом
sim1246
0 / 0 / 0
Регистрация: 14.05.2014
Сообщений: 8
14.05.2014, 11:48  [ТС]     Std::set( vector ) и расход памяти #6
sizeof(set<string> ) как и sizeof(vector<string> ) равен 16. В строке которую вы привели я попытался посчитать сколько памяти съедает сам string который лежит в set( его значение 28 ) и его содержимое.

Добавлено через 58 секунд
Спасибо, но не понятно с вектором почему вектор меньше чем 4,1
aLarman
636 / 557 / 89
Регистрация: 13.12.2012
Сообщений: 2,109
14.05.2014, 12:12     Std::set( vector ) и расход памяти #7
потому что вектор расходует меньше памяти чем set написано ж выше

Добавлено через 4 минуты
Цитата Сообщение от sim1246 Посмотреть сообщение
сам string который лежит в set( его значение 28 ) и его содержимое.
тогда Вам скорее всего надо сделать так
C++
1
2
3
4
5
6
7
8
for(;it!=res.end();++it){
        string str = *it;
        size1+=str.size();
        size2+=str.capacity();
        //size3+=str.capacity() + sizeof(string);
}
size3 = size2+res.capacity()*sizeof(vector<string>);//вектор
//size3 = size2+res.size()*sizeof(set<string>); для set
sim1246
0 / 0 / 0
Регистрация: 14.05.2014
Сообщений: 8
14.05.2014, 12:16  [ТС]     Std::set( vector ) и расход памяти #8
Так по моему не совсем правильно все таки в векторе( сете ) у нас хранится string а не вектор( сет).
По сравнению с set вектор занимает меньше памяти понятно почему, а вот почему он занимает меньше по сравнению с size3 не понятно.
aLarman
636 / 557 / 89
Регистрация: 13.12.2012
Сообщений: 2,109
14.05.2014, 12:22     Std::set( vector ) и расход памяти #9
даж так
C++
1
size3 = size2+sizeof(res);+res.capacity()*sizeof(string)//в случае сета res.size();
size2 это память выделенная на все строки, эти строки хранятся в векторе, т.е каждый элемент это есть string, и элементы в векторе хранятся в виде массива, размер массива capacity() т.е capacity()*sizeof(string) получаем размер массива(хранящегося в векторе) + размер массивов каждой из строк + размер самого контейнера sizeof(res)

Добавлено через 47 секунд
так Вы же в size3 добавляете еще capacity() каждой из строк

Добавлено через 2 минуты
Цитата Сообщение от aLarman Посмотреть сообщение
string str = *it;
неправильно делаете, Вы тут копируете строку, а в ней capacity может отличаться от той что в *it
sim1246
0 / 0 / 0
Регистрация: 14.05.2014
Сообщений: 8
14.05.2014, 12:27  [ТС]     Std::set( vector ) и расход памяти #10
так Вы же в size3 добавляете еще capacity() каждой из строк
C++
1
size3 = size2+sizeof(res) +res.capacity()*sizeof(string)
Эта строка отличается от моей только наличием sizeof( res). Повторюсь что в моем случае для вектора size=capacity специально проверяю.
неправильно делаете, Вы тут копируете строку, а в ней capacity может отличаться от той что в *it
С этим согласен переделал на (*it).size && (*it).capacity(). Результат тот же.
Все равно не понятно почему вектор почти на пол мегабайта меньше чем size3.
Avazart
 Аватар для Avazart
6897 / 5137 / 252
Регистрация: 10.12.2010
Сообщений: 22,570
Записей в блоге: 17
14.05.2014, 12:37     Std::set( vector ) и расход памяти #11
Цитата Сообщение от aLarman Посмотреть сообщение
et в данном случае наверняка RB-tree, каждый элемент содержит еще 2 указателя
Три указателя, еще указатель для родителя.
aLarman
636 / 557 / 89
Регистрация: 13.12.2012
Сообщений: 2,109
14.05.2014, 12:38     Std::set( vector ) и расход памяти #12
Цитата Сообщение от sim1246 Посмотреть сообщение
меньше чем size3.
а что в size3 я уже запутался

Добавлено через 18 секунд
Avazart, а да root еще
sim1246
0 / 0 / 0
Регистрация: 14.05.2014
Сообщений: 8
14.05.2014, 12:40  [ТС]     Std::set( vector ) и расход памяти #13
а что в size3 я уже запутался
C++
1
size3=size2 + sizeof(string)*res.capacity() + sizeof(vector<string>())
Avazart
 Аватар для Avazart
6897 / 5137 / 252
Регистрация: 10.12.2010
Сообщений: 22,570
Записей в блоге: 17
14.05.2014, 12:42     Std::set( vector ) и расход памяти #14
Да при чем для вектора нужен один указатель независимо от кол-во элементов, а для множества нужно три указателя на каждый элемент- то есть линейно зависит от кол-ва элементов.
sim1246
0 / 0 / 0
Регистрация: 14.05.2014
Сообщений: 8
14.05.2014, 12:44  [ТС]     Std::set( vector ) и расход памяти #15
вот ответ с stackoverflow ( там тоже спрашивал ) http://stackoverflow.com/questions/2...19176_23647756.
Перевод насколько я понял : Говорят что маленькие string в MS VS хранятся в непосредственно в самом string-e и capacity + sizeof(string) некорректно использовать.
Avazart
 Аватар для Avazart
6897 / 5137 / 252
Регистрация: 10.12.2010
Сообщений: 22,570
Записей в блоге: 17
14.05.2014, 12:49     Std::set( vector ) и расход памяти #16
Заглянуть посмотреть в исходнки реализации ?
sim1246
0 / 0 / 0
Регистрация: 14.05.2014
Сообщений: 8
14.05.2014, 12:57  [ТС]     Std::set( vector ) и расход памяти #17
Сейчас посмотрю, но тогда получается что и для set вычисления не верны, тогда вообще не понятно куда память девается
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.05.2014, 14:19     Std::set( vector ) и расход памяти
Еще ссылки по теме:

Вывести значения std::vector<std::vector<int*> > C++
Vector<set<string>> C++
Как изменять размер std::vector<std::vector>? C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
sim1246
0 / 0 / 0
Регистрация: 14.05.2014
Сообщений: 8
15.05.2014, 14:19  [ТС]     Std::set( vector ) и расход памяти #18
Вообщем всем спасибо кто принял участие в обсуждении. Сам string занимает 28 байт + примерно 14 байт для каждого элемента сета. Итого на один элемент получатся 32 байта. Ну примерно та же цифра в 4 мб получается, остальное на stackoverflow списали на всякие загруженные либы и так далее.

Добавлено через 33 секунды
Указанные цифры верны только для MSVC реализации string и set
Yandex
Объявления
15.05.2014, 14:19     Std::set( vector ) и расход памяти
Ответ Создать тему
Опции темы

Текущее время: 10:48. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru