STL-подобный вектор с произвольным диапазоном индекса

Question

Мне нужно что-то похожее на вектор STL, когда речь идет о сложности доступа, перераспределении при изменении размера и т. Д. Я хочу, чтобы он поддерживал произвольный диапазон индекса, например, могут быть элементы, индексированные от -2 до +7 или от + От 5 до +10. Я хочу иметь возможность push_front эффективно. Также я хочу двухстороннее изменение размера ...

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

Answer 1

Deque очень похож на вектор в том, что он поддерживает произвольный доступ и эффективную вставку в конце, а также поддерживает эффективную вставку в начале.

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

Неупорядоченная карта (tr1) аналогична карте, за исключением того, что она поддерживает лучшую итерацию.

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

Answer 2

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

Answer 3

Вот, пожалуйста, двусторонний вектор

http://dl.dropbox.com/u/9496269/devector.h

использование:

• для резервирования памяти до begin(), используйте reserve(new_back_capacity, new_front_capcity);

• , за исключением случаев использования push_front(), pop_front() и squeeze(), передний предел всегда сохраняется.

• squeeze() очищает всю неиспользуемую память

• по умолчанию namespace; stdext

Концепция:

• в большинстве случаев эквивалентно ::std::vector, но с возможностью push_front

• нет различий в производительности по сравнению с ::std::vector (в отличие от ::std::deque)

• четыре байта служебной информации по сравнению с ::std::vector

Answer 4

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

Затем просто реализуйте общие функции и добавьте новые (например, push_begin для добавления к вектору отрицательных индексов) и обновите соответствующие векторы внутри.