Расширяемое/эффективное решение для поиска конкретных подтипов

Question

Существует класс номера. Он содержит список мебели; стулья, стол & и т. д. Требуется только перечислить список стульев. Сохранение отдельного списка для каждого типа мебели не является расширяемым решением. (Например, для добавления нового типа мебели требуется создание нового типа списка & и т. Д.). Но наличие единого списка и его обновление требуют итерации всей мебели и поискать стулья только с помощью оператора или любого другого пути.

Как эффективно реализовать такую ​​реализацию с помощью шаблона проектирования или структуры данных?

Answer 1

Если вы хотите, чтобы эффективно искать стулы через какую-то единую совокупность, то либо вы используете:

1. нерастяжимое решения, которое вы цитируетесь
2. Расширяемые один с типом мебель будучи ключ к Multimap (тот, который допускает различные значения под тем же ключом)
3. Гибридный вид решения.

Вы уже знаете об нерациональном, поэтому давайте пропустим это.

Для №2 вы можете использовать тип мебели в качестве ключа к ассоциативной структуре данных, которая допускает записи с дублирующими ключами, но с разными значениями. Пример из C++ будет multimap. Вы можете полагаться на информацию о типе, полученной во время выполнения в качестве ключа, если язык поддерживает его, или решения, как это:

class Furniture 
{ 
public: 
    virtual ~Furniture() {} 
    virtual SomeKeyType key() const = 0; 
}; 

class Chair: public Furniture 
{ 
public: 
    virtual SomeKeyType key() const override 
    { 
     return "chair"; // note: doesn't have to be a string. 
    } 
}; 

Теперь, когда вы вставляете мебель в комнате, вставить его в эту ассоциативную структуру с помощью этого key, как ключ поиска. Теперь, когда вы хотите найти стулья, найдите предметы с ключом chair. Это можно легко сделать в логарифмическом времени или лучше.

Решение №3 в гибридном стиле в основном представляет собой собственный дизайн multimap. Вы можете создать агрегат, который берет ключ и использует соответствующий список на основе ключа, предоставленного при поиске, вставке, удалении, итерации. Этот дополнительный контроль может принести определенную пользу, если вы знаете, что у вас, например, не слишком много типов мебели, и вам не нужна полномасштабная древовидная структура или хеш-таблица, и вы можете просто иметь кучу списков, созданных во время выполнения по предоставленному ключу.

Это, как правило, ваш основной выбор. Если вы используете РСУБД, у него уже есть такие функции, встроенные в базовые структуры данных, которые он использует. Если вы откажетесь от своего собственного, как правило, это один из трех выше с точки зрения фундаментальной механики.