Лучший тип контейнера
Я работаю в приложении, которое требует "Скользящее окно", которое является просто контейнером строк,
Window = ["the", "dog", "is", "hungry"]
Приложение обрабатывает большой текстовый файл, и когда определенные условия выполняются, окно добавляет новую строку в конец и удаляет первый элемент,
Т.е. сказать "сейчас" это следующее слово, которое будет добавлено, то
Window <- Window.AddToEnd("now") and Window.DeleteFirst()
так становится, Window = ["dog", "is", "hungry", now"]
Каждый раз, когда окно изменяется, процесс запускается над элементами, где важен порядок (т. Е. Важен индекс).
По сути я пошел с вектором строк и попробовал deque. Мне было любопытно, что люди считают лучшим?
Подводя итог, мне нужен контейнер строк, который индексируется, где ОЧЕНЬ регулярно добавляется новый элемент + удаляется первый элемент. Мне также нужно перебрать контейнер много.
Некоторые другие биты информации:
- Строка никогда не изменяется один раз в контейнере
- Элементы окна никогда не меняются (за пределами pop и push, как обсуждалось)
- Размер окна неизвестен до времени выполнения (что-то, что пользователь передает)
- Окно никогда не изменяет размер, после инициализации в начале оно остается таким же для всего приложения.
Любые предложения будут с благодарностью, ура Дэвид
3 ответа
Ниже приведен пример шаблона класса для круглого контейнера, в котором размер контейнера постоянен во время выполнения, но задается во время создания шаблона класса. Чтобы использовать это, размер должен быть известен или предварительно рассчитан заранее; если вы не знаете, каким будет размер, вы можете рассмотреть возможность использования алгоритма, аналогичного этому, без шаблона или другого контейнера. Это работает очень хорошо, если размер не очень большой. Как вы можете видеть в addString() Функция, когда добавляемые элементы начинают превышать размер содержащегося массива, вызывается цикл for, который должен сдвинуть все в этом массиве. Это хорошо для массивов порядка 100 или 1000 элементов, но когда вы получаете массивы размером 100 000 или 1 000 000 записей; это будет узким местом и будет довольно медленным, однако это обеспечивает механизм смещения всего влево на один пробел и добавления в конце массива, списка или контейнера.
#include <iostream>
#include <memory>
#include <string>
template<unsigned Size>
class CircularContainer {
public:
const static unsigned SIZE = Size;
private:
std::string data_[SIZE];
unsigned counter_;
public:
CircularContainer() : counter_(0) {}
void addString( const std::string& str ) {
// In a real container this would be a member and not static
// If you have a static here, and you have multiple instances
// It will still increment across all instances.
//static unsigned counter = 0;
if ( counter_ < SIZE ) {
data_[counter_++ % SIZE] = str;
} else {
// This function can be expensive on large data sets
// due to this for loop but for small structures this
// is perfectly fine.
for ( unsigned u = 0; u < SIZE-1; u++ ) {
data_[u] = data_[u+1];
}
data_[SIZE - 1] = str;
}
}
std::string& getString( unsigned idx ) {
if ( idx < 0 || idx >= SIZE ) {
return std::string();
} else {
return data_[idx];
}
}
unsigned size() const {
return SIZE;
}
};
int main() {
CircularContainer<4> cc;
cc.addString( "hello" );
cc.addString( "world" );
cc.addString( "how" );
cc.addString( "are" );
for ( unsigned u = 0; u < cc.size(); u++ ) {
std::cout << cc.getString( u ) << "\n";
}
std::cout << std::endl;
cc.addString( "you" );
cc.addString( "today" );
for ( unsigned u = 0; u < cc.size(); u++ ) {
std::cout << cc.getString( u ) << "\n";
}
std::cout << "\nPress any key and enter to quit." << std::endl;
char c;
std::cin >> c;
return 0;
}
Теперь вы можете адаптироваться к этому; и обмениваться необработанным массивом строк в этом классе и использовать кучу с указателем связи, а затем все, что вам нужно сделать, это переназначить ваш beg а также end указатели на соответствующие данные, так как все остальное в середине уже будет связано как кусочки цепочки.
редактировать
Я расширил этот класс, чтобы принять любой тип, и вместо использования необработанного массива этого типа данных, я заменил массив с использованием std::shared_ptr Вот редизайн вышеупомянутого класса. Я также исправил проблему с использованием static counter и сделал это членом.
#include <iostream>
#include <memory>
#include <string>
template<typename T, unsigned Size>
class CircularBuffer {
public:
const static unsigned SIZE = Size;
private:
std::shared_ptr<T> data_[SIZE];
unsigned counter_;
public:
CircularBuffer() : counter_(0) {}
~CircularBuffer() {}
void addItem( const T& t ) {
if ( counter_ < SIZE ) {
data_[counter_++ % SIZE] = std::make_shared<T>( t );
} else {
for ( unsigned u = 0; u < SIZE - 1; u++ ) {
data_[u] = data_[u + 1];
}
data_[SIZE - 1] = std::make_shared<T>( t );
}
}
T getItem( unsigned idx ) {
if ( idx < 0 || idx >= SIZE ) {
throw std::exception( "Array Buffer Out of Bounds!" );
} else {
return *(data_[idx].get());
}
}
unsigned size() const {
return SIZE;
}
};
int main() {
CircularBuffer<std::string, 5> cb;
cb.addItem( "hello" );
cb.addItem( "world" );
cb.addItem( "how" );
cb.addItem( "are" );
cb.addItem( "you" );
for ( unsigned u = 0; u < cb.size(); u++ ) {
std::cout << cb.getItem( u ) << "\n";
}
std::cout << std::endl;
cb.addItem( "today" );
cb.addItem( "my" );
cb.addItem( "friend" );
for ( unsigned u = 0; u < cb.size(); u++ ) {
std::cout << cb.getItem( u ) << "\n";
}
std::cout << std::endl;
std::cout << "\nPress any key and enter to quit." << std::endl;
char c;
std::cin >> c;
return 0;
}
Он по-прежнему использует указанный массив и ту же технику, чтобы обвести вокруг индекса этого массива. Единственная разница здесь в том, что я использую массив std::shared_ptr<T>, Это приведет к тому, что хранимые объекты будут в куче, а не в локальном стеке в области видимости шаблона класса. Очистка памяти должна выполняться автоматически, но это не всегда гарантируется. Нет особой необходимости отслеживать head & tail позиционировать, если только вы явно не нуждаетесь в них, и это не должно быть трудно добавить к этому шаблону класса.
В дополнение к std::deque, который, согласно cplusplus.com,
обеспечить функциональность, аналогичную векторам, но с эффективной вставкой и удалением элементов также в начале последовательности, а не только в ее конце. Но, в отличие от векторов, deques не гарантирует хранение всех своих элементов в смежных местах хранения
Вы также можете использовать вектор фиксированного размера и сохранить начальный индекс.
Так что он действует как круговой массив. например:
Вектор v, который изначально равен [a, b, c, d], с начальным индексом =0; после того, как 'e' входит, это [e, b, c, d], но теперь с начальным индексом =1. I-й элемент v[(beginning_index + i) % v.size()], Эта схема достаточно проста для реализации самостоятельно.
Вы можете использовать std::deque,
#include <deque>
#include <string>
#include <vector>
int main() {
std::deque<std::string> strs;
// .. initialize;
std::string tmp;
while (true) {
strs.pop_front();
std::cin >> tmp;
strs.push_back(tmp);
}
return 0;
}
std::list также разделяет те же функции.
Если вы хотите ограничить, сколько раз вы выделяете / освобождаете память, вы также можете использовать std::vector вот так:
#include <vector>
#include <string>
int main() {
std::vector<std::string> strs;
// ...
std::string tmp;
while (true) {
for (size_t i = 1; i < strs.size(); ++i)
strs[i-1] = std::move(strs[i]);
// strs.erase(strs.begin()); also works.
std::cin >> tmp;
strs.back() = tmp;
}
return 0;
}
Это позволяет вам удерживать сколько угодно мест, а затем только перемещать значения.