Проблема обеспечения работоспособности с этой векторной реализацией

Question

У меня есть вопрос о правильном/неправильном (проектном) подходе к решению проблемы. Сначала я уточняю ситуацию, затем мое решение и, наконец, проблему с моим решением. Я реализую его в C++.

Ситуация:

• Класс типа у необходимо провести и обработать сбор информации определенного типа х.
• Каждый экземпляр этого типа относится только к конкретному объекту.
• Объект должен иметь возможность сделать 3 вещи: найти информацию о соответствующем экземпляре, удалить экземпляр и добавить новый экземпляр.

Я осуществил следующее:

• Вся информация хранится в векторе 1.
• Другие объекты имеют индекс элемента в векторе, чтобы найти правильный экземпляр.
  Однако что, если я удалю элемент? индексы должны быть действительны, поэтому я сделал это:
• Другой вектор 2 хранится параллельно, который содержит логические значения, true, если индекс доступен для нового экземпляра, а false - если он принят. Вместо удаления экземпляра в векторе 1 я установил вектор 2 в значение true. Теперь, если новый экземпляр добавлен, он будет добавлен в первую доступную позицию (или сзади). Таким образом, ни один элемент не удаляется, но вектор не увеличивается при добавлении экземпляра.

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

Например: объект A выпускает экземпляр экземпляра (уведомляет класс y), но не удаляет индекс, и продолжает применять операции над элементом, пока этот индекс теперь назначен другому объекту и содержит другой экземпляр!

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

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

это векторы.

std::vector<bool> availability;  
std::vector<X> data;  

и вот методы

Y::Y() : data(1, X), availability(1, false) { 

} 

int Y::createNewInstance() { 
    if(data.size() > 1) { 
     bool indexFound = false; 
     std::vector<X>::size_type chosenIndex; 
     for(std::vector<X>::size_type i = 1; i < availability.size(); ++i) { 
      //if true, the index is not taken, so use it! 
      if (availability.at(i) == true) { 
       chosenIndex = i; 
       availability.at(chosenIndex) = false; 
       indexFound = true; 
       break; 
      } 
     } 
     if (indexFound) { 
      data.at(chosenIndex) = X; 
      return chosenIndex; 
     } else { 
      data.push_back(X); 
      availability.push_back(false); 
      return availability.size() - 1; 
     } 
    } else { 
      startTimes.push_back(X); 
      availability.push_back(false); 
      return availability.size() - 1; 
    } 
} 

X Y::getDataElement(int index, bool finish) { 
    if (data.size() > index && index != 0) {  
     //if finish is true, make element available for other users 
     if(finish) { 
      availability.at(index) = true; 
     } 
     return data.at(index); 
    } 
} 

Answer 1

Что об использовании зОго :: Карты в качестве контейнера, где ключи будут ваши индексами. У вас не будет проблем с изменением индексов при удалении элементов. Вам нужно будет написать одну функцию, например findFreeIndex, для управления свободными индексами. Если вам не нужно добавлять элементы в «свободное» пространство, вам это даже не нужно. Вы можете просто добавлять новые элементы в максимальный индекс плюс один.

Это решение имеет незначительное ограничение производительности, поскольку доступ к карте немного медленнее, чем доступ к вектору, но обычно это не проблема.