Thursday, October 31, 2019

Полиморфизм в си++.


Что такое полиморфизм? Давайте разбираться вместе. В каком-то смысле это свойство пользовательских типов. В более современных языках, таких как Java, в которых нет ограничений по обратной совместимости, полиморфизм “включен” по умолчанию. В нашем случае это не так, и его нужно включать принудительно. Но погодите, сам по себе полиморфизм не существует, сначала нам понадобится наследование. Вообще пользовательские типы это много всякой "дури", но не будем хвататься за все сразу. Наследовать свойства одних типов другими это удобно, преимущества такого подхода всем известны, это дает нам возможность строить родительские связи между типами и работать с наследниками как потомками одного родительского типа.

Давайте рассмотрим пример. Мы имеем родительский класс животные и его наследников кот и собака.
class Cat : public Animal {}; Cat cat;
Сложим наших наследников в контейнер и обработаем каждый элемент в цикле, например, вызовем унаследованный от родительского типа метод – подать сигнал. Создав контейнер, который содержит "элементы" родительского типа - животные и так как этому условию соответствуют наши наследники – кот и собака, помещаем их туда.
vector<Animal*> army = {&cat, &dog};
for(auto solder : army){ solder->signal(); }
 
Далее мы можем "решать проблему" тремя способами.
 
Первый способ – мы хотим сохранить нашу систему как можно более простой и принимаем как должное, что все животные могут “говорить”, просто издавать звуки, это достаточный для нас уровень абстракции, и мы не будем его дальше детализировать. Потому что на уровне наследников нам не важно, что именно они “говорят”, а более важно к примеру, что кот ловит мышей, а собака нарушителей границы, но при этом они могут подать звуковой сигнал. Создадим в родителе общий для всех наследников метод один раз и можем его использовать в любом наследнике, которых может быть любое количество.
class Animal{ void signal() { todo(); } }; 
 
Второй способ, когда у нас возникла необходимость конкретизировать поведение некоторых наследников. По каким-то причинам это может понадобится - переопределить поведение наследника, чтобы оно отличалось от родительского.
class Cat : public Animal{ void signal() { todo(); } };
Но в отличии от Java, только этого недостаточно. Мы должны указать в родительском типе, что при наличии преопределенного метода в наследнике, нужно использовать именно его, с помощью ключевого слова virtual:
virtual void signal() { todo(); }
В добавок для удобства можно использовать ключевое слово override в наследнике:
void signal() override { todo(); }
 
Третий способ, это частный случай второго способа, когда у нас возникла необходимость конкретизировать поведение всех наследников. В этом случае, с одной стороны нам не нужно определять общий для вех наследников метод - мы это сделаем в самих наследниках, с другой стороны нам нужно как-то указать на необходимость обязательного определения такого поведения в наследниках, т.к. если мы его не определим в родителе или наследнике, то при его вызове получим ошибку. В этом случае нам поможет чисто виртуальный метод, записанный в родительском типе в таком виде:
virtual void signal() = 0;
 
“И где тут полиморфизм?”, спросите вы. И вообще зачем он? Для меня ответ такой – это инструмент, который позволяет решать задачу действуя от общего к частному, что часто очень полезно. При таком подходе мы можем создать скелет сложной системы и потом изменять ее, путем добавления или замены ее элементов, которые будут вести себя по разному, настоящая магия и превращения (morph). В нашем случае мы работаем с животными, которые могут быть и вести себя как кот, собака и т.д. Давайте рассмотрим сам механизм:
Animal* x = &cat;
x->signal();
Слева у нас родительский тип животное, справа наследник кот. И у родителя, и у наследника есть поведение - сигнал, какой его вариант будет использован при вызове, родительский или потомка?
 
Если мы хотим, чтобы использовался родительский, это обычное наследование без полиморфизма, это рассмотренный выше первый способ. Если мы хотим использовать вариант потомка, что в свою очередь дает возможность использовать собственные варианты для разных потомков, то есть вести себя по-разному – полиморфно. То определяем родительское поведение, как виртуальное, это рассмотренный выше второй способ.
 
Код, который можно скомпилировать:
#include <iostream>
#include <vector>

class Animal {
public:
    virtual void signal() {
        std::cout << "Animal!\n";
    }
};

class Cat : public Animal {
public:
    void signal() override {
        std::cout << "Cat!\n";
    }
};

class Dog : public Animal {
public:
    //void signal() override {
    //    std::cout << "Dog!\n";
    //}
};

int main() {
    Cat cat;
    Dog dog;
    std::vector<Animal *> army = {&cat, &dog};
    for (auto solder:army) {
        solder->signal();
    }

    return 0;
}

Output:
>>Cat!
>>Animal!

P.S. Статья писалась с целью навести порядок в голове, буду рад если еще кому-то будет полезно.
Перегуд В.

Friday, October 4, 2019

Priority Queue


#include <string>
#include <map>
#include <iostream>

template <typename T>
class FakePriorityQueue
{
public:
    FakePriorityQueue()
    {
        m_list = new std::map<T, float>();
    }

    ~FakePriorityQueue()
    {
        m_list->clear();
        delete m_list;
    }

    bool Empty()
    {
        return m_list->empty();
    }

    void Enqueue(T element, float priority)
    {
        m_list->insert(std::pair<T, float>{element, priority});
    }

    T Dequeue()
    {
        if (m_list->empty())
        {
            //throw
        }
        T best = (T)m_list->begin()->first;
        float priority = m_list->at(best);

        for (auto &[candidate, val] : *m_list)
        {

            if (m_list->at(candidate) < priority)
            {
                best = candidate;
                priority = m_list->at(candidate);
            }
        }

        m_list->erase(best);
        return best;
    }

private:
    std::map<T, float> *m_list = nullptr;
};

int main()
{
    auto myXXX = FakePriorityQueue<std::string>();

    myXXX.Enqueue("B", 20.0f);
    myXXX.Enqueue("C", 30.0f);
    myXXX.Enqueue("A", 10.0f);

    while (!myXXX.Empty())
    {
        std::cout << myXXX.Dequeue() << std::endl;
    }
    std::cout << "Empty!" << std::endl;
}

////////////////////////
> .\game.exe
A
B
C
Empty!



=================================
            extract keys from a C++ map
=================================
-----------
std::vector<std::string> extract_keys(std::map<std::string, std::string> const& input_map) {
  std::vector<std::string> retval;
  for (auto const& element : input_map) {
    retval.push_back(element.first);
  }
  return retval;
}
----------
std::vector<std::string> extract_values(std::map<std::string, std::string> const& input_map) {
  std::vector<std::string> retval;
  for (auto const& element : input_map) {
    retval.push_back(element.second);
  }
  return retval;
}
----------
template<typename TK, typename TV>
std::vector<TK> extract_keys(std::map<TK, TV> const& input_map) {
  std::vector<TK> retval;
  for (auto const& element : input_map) {
    retval.push_back(element.first);
  }
  return retval;
}
----------
template<typename TK, typename TV>
std::vector<TV> extract_values(std::map<TK, TV> const& input_map) {
  std::vector<TV> retval;
  for (auto const& element : input_map) {
    retval.push_back(element.second);
  }
  return retval;
}

----------
#include <iostream>
#include <unordered_map>

template<typename K, typename V>
void print_map(std::unordered_map<K,V> const &m)
{
    for (auto const& pair: m) {
        std::cout << "{" << pair.first << ": " << pair.second << "}\n";
    }
}

int main()
{
    std::unordered_map<int, char> m =
    {
        {1, 'A'},
        {2, 'B'},
        {3, 'C'}
    };
    print_map(m);
    return 0;
}