Структуры данных для приложений реального времени

Question

Мы разрабатываем приложения p2p с использованием C++, который передает голос другому партнеру с использованием UDP.

Мы являемся , фиксируя сигнал микрофона в буфере в потоке, который фиксирует голос в течение одной секунды в цикле while. Для каждый второй записанный голос в буфере разбивает его на пакеты и отправляет другому партнеру. Теперь мне нужна правильная структура данных в пункте назначения, которая справляется с передачей в реальном времени. Та же структура данных, которую я собираюсь использовать для захвата экрана. Вот два подхода с использованием очереди, я думал о

• Реализация очереди с использованием связанного списка, который поддерживает очередь OneSecVoice объектов или Image объекта в случае изображения.

• Реализация очереди с помощью статического массива OneSecVoice или Image объектов

OneSecVoice/Image объекты будут содержать общее количество пакетов, пакетовбуфера для этого конкретного Image/OneSecVoice.

Как его в режиме реального времени один поток будет непрерывно сканировать очереди и вынимают последний полныйImage/OneSecVoice, суя Image/OneSecVoice из очереди.

Так какой выбрать Реализация очереди с использованием связанного списка или Реализация очереди с использованием статического массива.

Я и мой друг борются за это, поэтому мы решили опубликовать здесь.

Answer 1

Я бы использовал boost::circular_buffer. Вы получите преимущества кэша с фиксированной областью памяти и непредвиденными выделениями памяти.

Для достижения максимальной эффективности, circular_buffer магазинов его элементы в смежной области памяти, который затем дает возможность:

1. Использование фиксированной памяти и не неявное или неожиданное выделение памяти ,
2. Быстрая установка и снятие постоянной и постоянной времени элементов спереди и сзади.
3. Быстрый постоянного времени случайного доступа элементов.
4. Пригодность для применения в реальном времени и производительности.

возможные применения circular_buffer включают:

• хранения из недавно полученных образцов, перезапись самых старых в новые образцы прибывают.
• В качестве базового контейнера для ограниченного буфера (см. пример ограниченного буфера).
• Вид кеша, в котором хранится указанное число последних вставленных элементов.
• Эффективная фиксированная пропускная способность FIFO (First In, First Out) или LIFO (Last In, First Out) очередь, которая удаляет самые старые (вставленные как первые) элементы при заполнении.

Answer 2

Не используйте также. Использование уже существующих реализаций в стандартной библиотеке:

std::queue<T, std::list<T> > 
std::queue<T, std::deque<T> > // uses deque by default, by the way 

Вы можете это определение типа во чтобы поменять местами два очень легко:

template <typename T> 
struct queue_list 
{ 
    typedef typename std::queue<T, std::list<T> > value_type; 
} 

template <typename T> 
struct queue_array 
{ 
    typedef typename std::queue<T, std::deque<T> > value_type; 
} 

typedef queue_list<the_type>::value_type container_type; // use one 
typedef queue_array<the_type>::value_type container_type; 

Теперь профиль и найти, что лучше. Вероятно, массив будет иметь лучшую производительность для кеша.

Вы можете использовать boost's pool allocator, чтобы попытаться получить преимущество быстрой вставки и удаления списка, наряду с выполнением кэшировать массив:

typedef typename std::queue<T, std::list<T, boost::pool_allocator<T> > > value_type; 

Другой структуру, чтобы попытаться это boost::circular_buffer как suggested by fnieto:

template <typename T> 
struct queue_buffer 
{ 
    typedef typename std::queue<T, boost::circular_buffer<T> > value_type; 
}  

Answer 3

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

Я не думаю, что вы получите экономию пространства от использования статического массива. Конечно, вы сохраняете указатель на запись, но за счет выделения большого фиксированного блока памяти. И если ваша очередь будет иногда возникать так часто, возможно, вам нужна гибкость, предоставляемая связанным списком, так как она может вырасти до произвольного размера.

Если вы хотите ограничить размер, на который он может вырасти, вы можете сделать это в любой схеме.

Answer 4

Связанный список будет канонический подход, «Реализация очереди с использованием статического массива» на самом деле, как я бы об этом - так, чтобы снова собрать пакеты UDP, то, возможно, передать виртуализированных данные в LL поэтому он получает заказ. Как вы собираетесь танцевать «непрерывное сканирование очереди и вывести последнюю версию», поскольку вы не можете просто набить ее там, так как udp может появиться в непредвиденной последовательности. Последнее завершение не означает, что «Кофе» появляется после «Бобы типа:», чтобы вы могли где-то путать фасоль.