Что будет содержать абстрактный класс?

Question

[vipermagi]

Есть казалось бы простое учебное задание для C++: реализовать классы связанного списка, динамического массива и статического массива. Все три класса должны быть наследниками одного абстрактного класса.

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

А вот реализация статического массива вообще как-то не вяжется с остальными. На сколько эта часть задания соответствует здравому смыслу и реальным задачам? На мой не опытный взгляд уже есть обычный встроенный массив и в реализации динамического массива его следует использовать как поле данных. Как реализовать свой статический массив я не представляю.

Comments

[AtomKrieg]

Сравните std::vector и std::array

Answer 1

[Зелимхан Бельтоев]

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

Для реализации статического массива в конструкторе выделяйте память на нужное количество элементов, а при доступе по индексу - просто делайте смещение от указателя на первый элемент - вот вам и реализация стандартного массива

Answer 2

[Сергей Протько]

вы можете организовать одинаковый интерфейс для связанного списка и статического массива? Можете. Вот и весь ответ.

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

Comments

[vipermagi]

Вы намекаете, что реализация пользовательского статического массива это просто обёртка над встроенным статическим массивом?

[Зелимхан Бельтоев]

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

[Сергей Протько]

vipermagi: ну у вас же будет операция вставки в середину списка например? Со статическим массивом вам нужно будет хэндлить ресайзы и т.д. Интерфейс один, реализация разная.

Answer 3

[Mercury13]

Вариант один вы предложили. Всё пишу на C++03, без шаблонов. C++11 и шаблоны, разумеется, дадут больше вариантов.

class Object {
public:
    virtual ~Object() {}
};

class List {    // interface
protected:
    virtual Object& getAt(size_t i) = 0;
public:
    virtual size_t size() const = 0;
    inline Object& at(size_t i) { return getAt(i); }
    inline const Object& at(size_t i) const
        { return const_cast<List*>(this)->getAt(i); }
    virtual ~List() {}
};

Вариант 2. С ним пользователю не так просто, но если к нему ещё добавить лямбда-функции C++11 — вообще бомба будет!

class ListCallback {    // interface
public:
    virtual void act(size_t index, Object& object) = 0;
    virtual ~ListCallback() {}
};

class ListConstCallback {   // interface
public:
    virtual void act(size_t index, const Object& object) = 0;
    virtual ~ListConstCallback() {}
};

class List2 {   // interface
public:
    virtual size_t size() const = 0;
    virtual void enumerate(ListCallback& body) = 0;
    virtual void enumerate(ListConstCallback& body) const = 0;
};

Например, для динамического массива, у которого быстрый доступ по номеру, будет такое тело

void DynArray::enumerate(ListConstCallback& body) const {
   size_t sz = size();
   for (size_t i = 0; i < sz; ++i)
       body(i, operator[](i));
}

Разумеется, если вы нагрузкой сделаете не абстрактный Object, а что-то окончательное, dynamic_cast не нужен будет.

Вариант 3 принят в Java. Один недостаток — мого кода писать для const-корректности, так что с вашего позволения опущу.

class VirtualListIterator { // interface
public:
    virtual bool next() = 0;
    virtual Object& value() = 0;
    virtual ~VirtualListIterator() {}
};

class ListIterator {   // Назван так для красоты, по сути это умный указатель
private:
    VirtualListIterator* ptr;
    // Запретим копирование и op=, но при желании можно реализовать и их
    ListIterator(ListIterator&) {}
    void operator=(const ListIterator&) {}
public:
    ListIterator() : ptr(NULL) {}
    ListIterator(VirtualListIterator* value) : ptr(value) {}
    ~ListIterator() { delete ptr; }
    bool next() { return ptr->next(); }
    Object* operator->() const { return &ptr->value(); }
    Object& operator*() const { return ptr->value(); }
};

class List3 {   // interface
public:
    virtual size_t size() const = 0;
    virtual VirtualListIterator* enumerate() = 0;
};

class Number : public Object {
public:
    int value;
};

// И пользоваться этим так...
void doSmth(List3& aList) {
    ListIterator it(aList.enumerate());
    while (it.next()) {
        std::cout << dynamic_cast<Number&>(*it).value << std::endl;
    }
}

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

Да, и из вас будет хороший инженер, если вы сразу же задумываетесь о производительности.