std :: vector, std :: map и проблемы с памятью

Question

Я пишу код, который вставляет строки из базы данных в вектор.Затем векторы сохраняются в std :: map.Эта архитектура позволяет мне логически разделять наборы данных (векторы) на основе ключа карты.

В моем коде я буду извлекать набор данных (т.е. вектор) из std :: map, добавляя / удаляя строкиили выполнение какой-то другой логики, а затем вставление вектора обратно в карту (все это происходит в цикле while ()).

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

Мои вопросы:

1. Учитывая потенциально большое количество элементов, которые может хранить строка, в идеале я хотел бы выделить / освободить из пула памяти.Но я не знаю, как использовать std :: vector с пулом памяти, и я не знаю, будет ли это излишне сложно.Если это излишнее (или слишком сложное), то моя другая идея состоит в том, чтобы предварительно выделить фиксированный кусок памяти при первом создании вектора.Но это также, вероятно, будет слишком упрощенно, поскольку число элементов может варьироваться в широких пределах от одного экземпляра вектора к другому - что приводит к фрагментации (памяти) и т. Д., Не говоря уже о неэффективном использовании памяти.

   Какой здесь рекомендуемый подход?

2. Учитывая тот факт, что std :: map (все контейнеры STL IIRC) хранит КОПИЮэлемент value, перспектива создания копий векторов, содержащих несколько десятков тысяч элементов, просто ошибочен.Поэтому я думаю о написании обертки SmartPointerMap arround stl :: map и сохранении указателей на векторы вместо фактических векторов.

   Я на правильном пути ?.Если нет, то какое решение лучше?Если да, есть ли библиотека повышения, которую я могу использовать (вместо написания шаблона класса SmartPointerMap)?

[Редактировать]

Я строю на Linux (Ubuntu 9.10) с gcc 4.4.1

Answer 1

Предполагая, что вы используете vector для карты data_type, а не key_type, вы можете изменить данные на месте, не копируя их. std::map::operator[]() возвращает ссылку на неконстантную data_type, а итератор, возвращенный из неконстантной версии std::map::find(), позволяет изменять данные.

Что делать, если вам нужно изменить ключ при изменении данных? Вы можете использовать std::swap() для перемещения данных из одного вектора в другой без копирования.

Не забывайте, что vector не уменьшает его capacity() при удалении элементов. Кроме того, vector обычно выделяет больше capacity(), чем вам нужно, так что push_back() занимает амортизированное постоянное время. Для очень больших векторов это поведение может значительно увеличить использование памяти вашей программой, если вы не будете осторожны.

Если вы используете vector для key_type карты, а карта имеет очень большие ключи, тогда могут помочь указатели или умные указатели. Однако, если это так, вы должны убедиться, что не изменили содержимое ключа, на который указывает одно из значений карты, потому что std::map не предназначен для обработки этого.

Что касается идеи пользовательского распределителя, сначала приведите код в действие со стандартным распределителем, а затем посмотрите, достаточно ли он быстр. Это может быть хорошо, используя стандартный распределитель. Если ваш код не достаточно быстрый со стандартным распределителем, профиль, чтобы увидеть, где на самом деле тратится время (это может быть где-то еще, как код базы данных). Если вы пишете пользовательский распределитель и никогда не сравниваете его со стандартным распределителем, вы не будете знать, действительно ли ваш настраиваемый распределитель является улучшением; это может быть намного медленнее, чем стандартный распределитель.

Answer 2

Wrt # 1, реализация кучи по умолчанию в GCC / Linux (ptmalloc) будет использовать свободный список (он же пул памяти) для небольших объектов (<= 64 байта по умолчанию в прошлый раз, когда я проверял). Если вы все еще хотите использовать пользовательский распределитель, библиотека Boost.Pool имеет <a href="http://www.boost.org/doc/libs/1_42_0/libs/pool/doc/interfaces/pool_alloc.html" rel="nofollow noreferrer"> allocators , которые удовлетворяют требованиям стандартного распределителя. Как предложил bk1e, проведите тестирование до и после, чтобы увидеть, стоит ли оно того.

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

Надеюсь, это поможет.

Answer 3

Чтобы ответить на вопрос 2:

using namespace std;

map<string, vector<int>* > foo;
vector<int>* pointer= foo["thekey"];

Если требуется использование умных указателей (с подсчетом ссылок):

#include<tr1/shared_ptr.h>
using namespace std::tr1;
using namespace std;

map<string, shared_ptr<vector<int> > > foo;
shared_ptr<vector<int> > pointer= foo["thekey"];

Чтобы ответить на вопрос № 1, вы можете написать новый класс шаблона распределителя и объявить ваши векторы для использования этого распределителя, но я ничего не знаю о написании распределителей:

map<string, vector<int, myallocator<int> >* > foo;

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

Answer 4

Я собираюсь предложить более общий подход к работе с наборами запросов к базе данных на C / C ++.

Выполните запрос базы данных и поместите строки в массив структур. Если у вас недостаточно физической памяти, используйте файл с отображением памяти, который будет возвращать указатель на базу массива структур, которые MMU на плате процессора будет беспокоиться о том, чтобы при необходимости разместить его в памяти.

Теперь вы можете сортировать () этот массив структур по ключу / ключам, который даст вам доступ к ISAM, ересь в реляционной религии, но именно то, что дают вам курсоры. Это метод доступа к данным # 1

Теперь, если вам все еще нужно смотреть на эти данные по-другому, просто создайте 1 или более индексов / карт, где ключи карты являются подходящими (значение столбца / член структуры) из массива структур, и Значением данных карты является указатель на расположение этой структуры в файле отображения памяти. Это обеспечивает точно такую ​​же функциональность, как индекс БД. Подписав карту на значение struct.member для любой заданной строки, вы вернетесь обратно к этой строке.

Вы можете иметь несколько карт для нескольких индексов, указывающих на одни и те же структуры / строки в массиве, используя разные данные struct.member для ключей карты для разных индексов.

Я игнорирую ваше заявленное требование добавить новые строки / структуры, так как кажется, что вы делаете одно чтение строк из БД, и на самом деле не нужно добавлять новые строки / структуры.

Если, однако, я ошибаюсь, и вам нужно добавить новые структуры / строки, то вместо выделения одного большого массива структур просто используйте malloc () и realloc () массива структур соответствующего размера и повесьте их. от указателей, которые являются «данными» карты. Таким образом вы теряете истинный доступ к ISAM, потому что структуры не хранятся физически смежно в памяти, но вы получаете возможность realloc (). Это компромисс. Доступ к ISAM может быть смоделирован путем итерации по карте, но он будет медленнее, чем последовательное чтение массива структур из памяти.