Гибридный вектор / список контейнеров?

Question

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

После некоторых размышлений я выяснил, как я могусоздайте такой контейнер, используя вектор в качестве базового контейнера, и оберните фактические сохраненные данные в структуру, которая также содержит поля для записи того, был ли элемент допустимым, и указатели на следующий / предыдущий действительный элемент в векторе.В сочетании с некоторой перегрузкой и тому подобным, звучит так, как будто она должна быть достаточно прозрачной и соответствовать моим требованиям.

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

Answer 1

Если порядок не имеет значения, я бы просто использовал хеш-таблицу для отображения целых чисел на указатели.std::tr1::unordered_map<int, T *> (или std::unordered_map<int, unique_ptr<T>>, если C ++ 0x в порядке).

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

В качестве альтернативы, я думаю, вы можете реализовать свою собственную идею в виде очень простой комбинации std::vector и std::list.Просто поддерживайте как list<T> my_list, так и vector<list<T>::iterator> my_vector.Чтобы добавить объект, поместите его в конец my_list, а затем вставьте его итератор в my_vector.(Установите итератор на my_list.end() и уменьшите его, чтобы получить итератор для последнего элемента.) Для поиска посмотрите в векторе и просто разыщите итератор.Чтобы удалить, удалите из списка (что вы можете сделать с помощью итератора) и установите местоположение в векторе на my_list.end().

std::list гарантирует, что элементы внутри не будут перемещаться при их удалении.

[обновление]

Я чувствую себя мотивированным.Первый проход при реализации:

#include <vector>
#include <list>

template <typename T>
class NairouList {
public:
  typedef std::list<T> list_t;
  typedef typename list_t::iterator iterator;
  typedef std::vector<iterator> vector_t;

  NairouList() : my_size(0)
  { }

  void push_back(const T &elt) {
      my_list.push_back(elt);
      iterator i = my_list.end();
      --i;
      my_vector.push_back(i);
      ++my_size;
  }

  T &operator[](typename vector_t::size_type n) {
      if (my_vector[n] == my_list.end())
          throw "Dave's not here, man";
      return *(my_vector[n]);
  }

  void remove(typename vector_t::size_type n) {
      my_list.erase(my_vector[n]);
      my_vector[n] = my_list.end();
      --my_size;
  }

  size_t size() const {
      return my_size;
  }

  iterator begin() {
      return my_list.begin();
  }

  iterator end() {
      return my_list.end();
  }

private:
  list_t my_list;
  vector_t my_vector;
  size_t my_size;
};

В нем отсутствуют некоторые касания качества реализации ... Например, вам, вероятно, нужна дополнительная проверка ошибок (что, если я удалю один и тот же элемент дважды?) И, возможно, немного const версии operator[], begin(), end().Но это только начало.

Тем не менее, для «нескольких тысяч» элементов карта, скорее всего, будет служить как минимум так же.Хорошее практическое правило: «Никогда ничего не оптимизируйте, пока ваш профилировщик не скажет вам».

Answer 2

Похоже, вам может понадобиться std :: deque . Удаление элемента не так эффективно, как std::list, но потому что декы обычно создаются с использованием несмежных «блоков» памяти, которые управляются через дополнительный массив / вектор указателей, внутренний для контейнера (каждый «блок» будет массив из N элементов), удаление элемента внутри deque не приводит к той же операции перестановки, которую вы видели бы с вектором.

Редактировать: Хотя на секунду и после рассмотрения некоторых комментариев, хотя я думаю, что std::deque может работать, я думаю, что std::map или std::unordered_map на самом деле будет лучше для вас, так как он позволит индексировать синтаксис массива, который вам нужен, но также обеспечит быстрое удаление элементов.