C ++: очередь с эффективным get / put нескольких элементов? - PullRequest
Новая
       20

C ++: очередь с эффективным get / put нескольких элементов?

5 голосов
/ 29 марта 2011

Итак, я чувствую, что должно быть хорошее встроенное решение для этого в C ++, но я не уверен, что это такое.

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

так, интерфейс выглядит, например, 

//removes the first bytesToRead elements from the front of the queue and places them in array; returns the actual number of bytes dequeued
int dequeue(unsigned char *array, int bytesToRead) 
//Adds bytesToWrite elements from array to the end of the queue; does nothing and returns 0 if this would exceed the queue's max size
int enqueue(unsigned char *array, int bytesToWrite)

Я могу написать сам без особых затруднений, но, похоже, это должно быть что-то, что легко сделать с полки.

Лучшая вещь в STL выглядит так, как будто это может быть stringbuf - мне нужно было бы вручную связать вызовы sgetc / pubseekoff, но, похоже, это будет работать.

Я собираюсь сделать это как замену текущей реализации очереди, которая является проблемой производительности; чтение в этой реализации O (N) на количество данных в очереди. (Это очень наивная реализация - каждая очередь приводит к копии массива оставшихся данных в очереди.)

Дополнительные требования (при необходимости я могу реализовать их в оболочке): -У меня должна быть возможность указать максимальный размер буфера -Читать операции должны восстановить все доступные данные, если доступно меньше данных, чем было запрошено Операции записи не должны делать ничего, если запрашиваемая запись превысит максимальный размер и вернет индикатор ошибки

Итак, мои вопросы: 1) достаточно ли stringbuf? Относятся ли операции чтения / записи O (1) к объему данных в буфере, предполагая, что изменение размера не требуется? (очевидно, они потенциально будут O (n) на количество запрошенных предметов.)

2) Есть ли какой-то другой класс, которого я не вижу, которого будет достаточно?

Заранее спасибо!

Ответы [ 4 ]

8 голосов
/ 29 марта 2011

Хммм ... Вы пробовали очевидное: 

class queue { 
      std::deque<unsigned char> data;
public:
    int enqueue(unsigned char *array, int bytesToWrite) { 
        data.insert(data.end(), array, array+bytesToWrite);
    }

    int dequeue(unsigned char *array, int bytesToRead) { 
        std::copy(data.begin(), data.begin()+bytesToRead, array);
        // or, for C++11: std::copy_n(data.begin(), bytesToRead, array);

        data.erase(data.begin(), data.begin()+bytesToRead);
    }
};

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

Это гарантированно будет линейным по количеству вставленных / удаленных элементов.

1 голос
/ 29 марта 2011

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

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

0 голосов
/ 29 марта 2011

Как и предполагалось, std::stringstream, вероятно, самое простое и лучшее решение.

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

std::deque<unsigned char> buf;

int dequeue(unsigned char *array, int bytesToRead) {
  int result = std::min(bytesToRead, buf.size());
  std::copy(buf.begin(), buf.begin() + result, array);
  buf.erase(buf.begin(), buf.begin() + result);
  return result;
}; 

int enqueue(unsigned char *array, int bytesToWrite) {
  buf.insert(buf.end(), array, array + bytesToWrite);
  return bytesToWrite;
};

Вероятно, вам следует проверить, была ли последняя реализация достигнута максимальная емкость, и скорректировать полученное значение.

0 голосов
/ 29 марта 2011

Не могли бы вы использовать std::stringstream, когда вы вставляете в очередь с помощью write и выталкиваете из очереди с помощью read?

...