Представьте себе следующие требования:
данные измерений должны быть зарегистрированы, и пользователь должен иметь возможность перебирать данные.
uint32_t timestamp;
uint16_t place;
struct SomeData someData;
имеет метку времени (uint32_t), место (uint16_t) и некоторые данные в структуре
имеют постоянное количество наборов данных. Если приходит новый, самый старый выбрасывается.
число «мест» является динамическим, пользователь может вставлять новые во время выполнения
должна быть возможность перебирать данные до следующего более нового или более старого набора данных, но только если место совпадает
нужно вставить только в конце
память должна быть выделена один раз при запуске программы
вставка не должна быть быстрой, но не должна блокировать другие потоки в течение длительного времени, которое может повторяться в контейнере
требования к памяти должны быть низкими
РЕДАКТИРОВАТЬ: - Контейнер должен всю память, которая не используется в противном случае, поэтому он может быть большим.
Я не уверен, какой контейнер мне следует использовать. Это встроенная система, которая не должна использовать boost и т. Д.
Я вижу следующие возможности:
std :: vector - недостатки: вставка в конце требует, чтобы все объекты были скопированы, и в течение этого времени другой поток не может получить доступ к вектору. Редактировать: Этого можно избежать, если использовать его как кольцевой буфер - см. Комментарии ниже. При переборе по вектору я должен проверить идентификатор места. Может также быть проблемой выделение большого объема памяти как одного блока - потому что память может быть сегментирована?
std::deque - по сравнению с std::vector вставка (и pop_back) быстрее, но требуется память? Итераторы не становятся недействительными, если вставка находится в конце. Но я все еще должен повторить и проверить второй идентификатор («место»). Я думаю, что не нужно выделять всю память в одном большом блоке, как в случае с вектором или массивом. Если элемент добавляется впереди, а другой удаляется в конце (или удаляется первым и добавляется после), я полагаю, не происходит выделение памяти?
std::queue - вместо дек, мне лучше использовать очередь? Правда ли, что во многих реализациях очередь добавляется просто как deque?
std::map - Подобно deque любые итераторы для существующих элементов не станут недействительными. Если я сделаю ключ комбинацией места и метки времени, то итерация по карте может быть быстрее, потому что она уже отсортирована? Требования к памяти карты?
std::multimap - так как количество мест не является постоянным, я не могу сделать мультикарту с "местом" в качестве индекса.
std::list - не имеет здесь никакого преимущества перед deque?
Некоторые предлагали использовать кольцевой буфер. Если я не хочу, чтобы память выделялась как один большой блок, мне все равно придется использовать контейнер, и большинство вопросов выше остаются в силе.
Обновление:
Я буду использовать кольцевой буфер, как предложено здесь, но с использованием deque в качестве основного контейнера. Чтобы иметь возможность быстро прокручивать наборы данных с предварительно выбранным «местом», я в конечном итоге введу два дополнительных индекса в структуру данных, которые будут указывать на предыдущий и следующий индексы с тем же местом.
Сколько памяти будет использовано? В моем особом случае размер структуры составляет 56 байт. Библиотека GNU использует минимальный размер блока 512 байт, компилятор IAR - 16 байт. Следовательно, используемый размер блока будет 512 или 56 байт соответственно. Помимо двух итераторов (по 4 указателя в каждом) и размера, для каждого блока будет храниться указатель. Следовательно, при реализации компилятора iar (размер блока 56 байтов) издержки 7% (в 32-битной системе) будут выше, чем при использовании std :: vector или массива. В реализации gcc в блоке поместятся 9 объектов (504 байта), в то время как для каждого блока требуется 512 + 4 байта, что на 2% больше.
Размер блока невелик, но объем непрерывной памяти, необходимый для массива указателей, уже относительно велик, особенно для реализации, где один блок - это одна структура.
Для std :: list потребуются 2 указателя на структуру, что в моем случае составляет 14% на 32-битных системах.