Вектор С++ не хватает памяти

У меня очень большой вектор (миллионы записей по 1024 байта каждая). Я превышаю максимальный размер вектора (получаю исключение неправильного распределения памяти). Я выполняю рекурсивную операцию над вектором элементов, которая требует доступа к другим элементам в векторе. Операции нужно делать быстро. Я пытаюсь избежать записи на диск из соображений скорости. Есть ли другой способ сохранить эти данные, не требующий записи на диск? Если мне нужно записать данные на диск, как лучше всего это сделать>

отредактируйте для получения дополнительной информации.

Операции, которые я выполняю с набором данных, рекурсивно генерируют строку на основе других точек данных в векторе. Данные сортируются при считывании. Наборы данных от 50 000 до 50 000 000.


c++ memory-leaks memory-management stdvector
person user2174896    schedule 15.03.2013    source источник
comment
Мы не можем ничего сказать, не зная больше о ваших данных.   -  person NPE    schedule 15.03.2013
comment
Сколько памяти требуется? Сколько памяти у вас есть?   -  person    schedule 15.03.2013
comment
Вам нужна непрерывная память для всего, что вы делаете? Если нет, то простым изменением будет использование вместо него std::deque; это должно позволить вам хранить гораздо больше элементов, прежде чем закончится память.   -  person Praetorian    schedule 15.03.2013
comment
В большинстве реализаций std::vector используется стратегия перераспределения с удвоением емкости, что означает, что если вы сильно увеличиваете свой вектор, он, вероятно, использует гораздо больше места для хранения, чем необходимо для хранения фактических адресуемых элементов.   -  person Charles Salvia    schedule 15.03.2013
comment
@CharlesSalvia Он не отключается адаптивно, если возникает ошибка нехватки памяти?   -  person    schedule 15.03.2013
comment
@ Санчо, это точно не обязательно. Я не знаю, действительно ли это делает какая-либо реализация, но я предполагаю, что ответ - нет для всех существующих реализаций.   -  person Charles Salvia    schedule 15.03.2013
comment
Да, данные должны быть непрерывными. Спасибо за вклад, хотя.   -  person user2174896    schedule 15.03.2013
comment
Ваш процесс 32-битный или 64-битный? Какая ОС?   -  person Yakk - Adam Nevraumont    schedule 15.03.2013
comment
Ваши данные должны быть непрерывными, но вы планируете хранить некоторые из них на диске? Не могли бы вы дать немного больше справочной информации? Потому что я не вижу ситуации, когда данные должны быть непрерывными, но хранение на диск рассматривается как вариант.   -  person    schedule 15.03.2013
comment
@Yakk должен работать как на 32, так и на 64. Ubuntu 10 и 12.   -  person user2174896    schedule 15.03.2013
comment
32 бита пространства памяти, по 1024 байта на блок данных, означает теоретическую верхнюю границу 2^22 элементов (и практическую границу намного меньше, потому что не все ваше пространство памяти будет этим одним контейнером). Это всего лишь 4,2 миллиона элементов. Вы запрашиваете непрерывный буфер памяти, содержащий миллионы 1024-байтовых элементов в 32-разрядной ОС — ответ — нет, вы не можете этого сделать. Расслабьте некоторые из них, и вы сможете их решить. Зачем, собственно, вам нужен смежный?   -  person Yakk - Adam Nevraumont    schedule 15.03.2013
comment
контейнеры не могут содержать бесконечное количество элементов: используйте std::vector::max_size(), чтобы определить максимальный размер, который вы можете хранить.   -  person andre    schedule 15.03.2013
comment
@user2174896: user2174896: Должен ли он на самом деле быть непрерывным или достаточно произвольного доступа?   -  person Mooing Duck    schedule 16.03.2013

Ответы (4)


arrow_upward
9
arrow_downward

Самый простой способ решить эту проблему — использовать STXXL. Это повторная реализация STL для больших структур, которая прозрачно записывает на диск, когда данные не помещаются в памяти.

person Dirk Holsopple    schedule 15.03.2013
comment
Если данные должны быть непрерывными, как поможет STXXL? Любая запись на диск (прозрачная или нет) нарушает непрерывность. - person Yakk - Adam Nevraumont; 15.03.2013
comment
@Yakk, на самом деле он не является непрерывным, он просто представляет тот же интерфейс, что и std::vector. Вопрос не требует, чтобы он был непрерывным, или, по крайней мере, этого не было, когда я опубликовал ответ. - person Dirk Holsopple; 15.03.2013
comment
@DirkHolsopple Да, автор вопроса добавил это ограничение глубоко в комментарии к вопросу. - person ; 15.03.2013
comment
@Yakk, возможно, мне нужна бесконечная непрерывная память, это не разумное требование. - person Charles Salvia; 15.03.2013

arrow_upward
3
arrow_downward

Ваша проблема не может быть решена, как указано и разъяснено в комментариях.

Вы запросили способ иметь непрерывный буфер в памяти из 50 000 000 записей размером 1024 в 32-битной системе.

32-битная система имеет только 4294967296 байт адресуемой памяти. Вы запрашиваете 5 120 000 0000 байт адресуемой памяти, или в 11,9 раз больше объема адресного пространства памяти в вашей системе.

Если вы не требуете, чтобы ваши данные были непрерывными и адресуемыми в памяти, если вам не требуется, чтобы все ваши данные находились в памяти одновременно, или если вы ослабляете другие требования, может быть ответ на вашу проблему. То есть, некоторые ОС предоставляют доступ к пространству значений, не относящемуся к памяти, которое соответствует ОЗУ (там, где в 8-гигабайтных системах Windows есть способы использовать более 4 гигабайт общей ОЗУ) через какой-то хакерский интерфейс или другой.

Но, как уже говорилось, ответ «нет, вы не можете этого сделать».

person Yakk - Adam Nevraumont    schedule 15.03.2013
comment
Вот что я понял. Спасибо. - person user2174896; 15.03.2013
comment
@user2174896 user2174896, чтобы было ясно, мой ответ означает, что вы задаете неправильный вопрос, а не не можете решить свою настоящую проблему. Я сильно сомневаюсь, что ваша реальная проблема составляет 51200000000 байт непрерывного пространства памяти в 32-битной ОС. - person Yakk - Adam Nevraumont; 15.03.2013

arrow_upward
0
arrow_downward

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

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

Если это не удается:

  • добавьте больше памяти на свой компьютер (может не помочь, если вы столкнулись с ограничениями адресации или реализации)
  • переключиться на необработанный массив
  • найти способ уменьшить размер ваших элементов
  • попытайтесь найти решение, которое может решить проблему небольшими блоками
person Community    schedule 15.03.2013
comment
Добавление дополнительной памяти на вашу машину ничего не изменит в современной ОС с максимальным размером vector, при условии, что пользователь предоставил достаточно виртуальной памяти. Выделение — это использование адресного пространства, а не памяти. Даже в этом случае ОС может бездумно выделять больше адресного пространства, чем у нее есть виртуальной памяти, и терпит неудачу только тогда, когда память действительно изменяется. - person Yakk - Adam Nevraumont; 15.03.2013
comment
Это именно то, что я понял. Спасибо. - person user2174896; 15.03.2013

arrow_upward
-1
arrow_downward

Это 1 ГБ памяти (1024 КБ * 10 ^ 6 = 1 МБ * 10 ^ 3 = 1 ГБ). В идеале для 32-битной машины можно выполнять операции с памятью до 4 ГБ. Чтобы ответить на ваш вопрос, попробуйте сначала обычный вызов malloc() и выделите 1 ГБ памяти. Это должно быть сделано без ошибок. Кроме того, вставьте точное сообщение об ошибке, которое вы получаете при использовании вектора.

person Shehbaz Jaffer    schedule 15.03.2013
comment
Почти единственная полезная информация, которую OP дает в вопросе, - это то, какую ошибку он видит - исключение неправильного выделения памяти, также известное как std::bad_alloc - person Praetorian; 15.03.2013
comment
использование malloc было ответом :) - person Shehbaz Jaffer; 15.03.2013
comment
Это неправильный ответ. Вопрос говорит о миллионах, а не об 1 миллионе. Даже если предположить, что их всего 2–3 миллиона, нет никакой гарантии, что 32-разрядная машина сможет выделить 2–3 ГБ непрерывного адресного пространства. Некоторое адресное пространство будет использоваться для ядра, общих библиотек, стека и т. д. - person Dirk Holsopple; 15.03.2013
comment
В вопросе также говорится о миллионах 1024 байт. - person ; 15.03.2013