Использование отображений при реализации композиции

 

Когда родительский объект начинает содержать большое количество дочерних объектов, начинает хромать производительность алгоритмов поиска. Пусть имеется название главы, требуется найти ее в составе книги. Использование простого контейнера, такого как std::vector, для хранения глав означает, что реализация поиска будет основана на линейном переборе элементов. Как только число сканируемых элементов превысит 10, недостатки этого подхода могут стать заметными.

 

Задачу поиска главы по известному названию можно решить с применением дополнительного контейнера-отображения, не отменяющего хранение глав в векторе. Ключом в таком отображении будет строка, а значением - указатель на главу. Поскольку итерировать главы в алфавитном порядке не требуется, логично выбрать контейнер std::unordered_map. Внесение таких изменений также позволяет добавить полезную проверку - в книге не должно быть двух глав с одинаковым названием. Ниже представлен набросок кода предлагаемых изменений:

 

book.hpp

 

#include <unordered_map>

 

class Book

{

public:

 

// Метод для поиска главы по названию

Chapter const * findChapterByTitle (std::string const & _title) const;

 

//...

 

private:

 

//...

// Отображение для ускорение поиска: ключ - название главы, значение - глава

std::unordered_map< std::string, Chapter const * > m_chaptersByTitle;

};

 

book.cpp

 

/*****************************************************************************/

 

// Реализация метода для поиска главы по названию

Chapter const *

Book::findChapterByTitle (std::string const & _title) const

{

// Ищем главу во вспомогательном отображении

auto it = m_chaptersByTitle.find(_title);

return (it!= m_chaptersByTitle.end())? it->second: nullptr;

}

 

/*****************************************************************************/

 

// Реализация метода добавления главы

void Book::addChapter (std::unique_ptr< Chapter > _chapter)

{

// Проверка на уникальность названия главы

if (findChapterByTitle(_chapter->getTitle()))

throw std::logic_error("Chapter with duplicate title");

 

// Регистрация главы во вспомогательном отображении

m_chaptersByTitle[ _chapter->getTitle() ] = _chapter.get();

 

// Регистрация главы в основном контейнере

m_chapters.push_back(std::move(_chapter));

}

 

/*****************************************************************************/

 

// Реализация метода удаления главы

void Book::removeChapter (Chapter const & _chapter)

{

// Проверять наличие главы в книге теперь проще по названию

auto itByTitle = m_chaptersByTitle.find(_chapter.getTitle());

if (itByTitle == m_chaptersByTitle.end())

// Ошибка: глава не найдена в книге

throw std::logic_error("Chapter does not exists in book");

 

// Удаляем главу из вспомогательного отображения

m_chaptersByTitle.erase(itByTitle);

 

// Удаляем главу из основного контейнера

int nChapters = getChaptersCount();

for (int i = 0; i < nChapters; i++)

if (m_chapters[ i ].get() == &_chapter)

{

m_chaptersByTitle.erase(_chapter.getTitle()); // удалит и уничтожит главу

return;

}

}

 

/*****************************************************************************/

 

// Реализация метода очистки книги от глав

void Book::clearChapters ()

{

// Сбрасываем оба контейнера

m_chaptersByTitle.clear();

m_chapters.clear();

}

 

/*****************************************************************************/

 

Использование множеств

 

Множества применяются для реализации композиции объектов в тех случаях, когда набор дочерних объектов должен содержать только уникальные элементы. В принципе, такое ограничение можно поддержать и на обычном контейнере, таком как std::vector, но, также как и в задачах поиска, подтверждение уникальности будет основано на линейном переборе.

 

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

 

author.hpp

 

#ifndef _AUTHOR_HPP_

#define _AUTHOR_HPP_

 

/*****************************************************************************/

 

#include <string>

 

/*****************************************************************************/

 

class Author

{

 

/*-----------------------------------------------------------------*/

 

public:

 

/*-----------------------------------------------------------------*/

 

// Конструктор: принимает имя автора и год его рождения

Author (std::string const & _name, int _birthYear);

: m_name(_name), m_birthYear(_birthYear)

{}

 

// Метод доступа к имени

std::string const & getName () const { return m_name; }

 

// Метод доступа к году рождения

int getBirthYear () const { return m_birthYear; }

 

/*-----------------------------------------------------------------*/

 

private:

 

/*-----------------------------------------------------------------*/

 

// Имя автора

const std::string m_name;

 

// Год рождения автора

const int m_birthYear;

 

/*-----------------------------------------------------------------*/

 

};

 

/*****************************************************************************/

 

#endif // _AUTHOR_HPP_

 

 

Реализация книги дополняется множеством авторов (хэш-таблица указателей на объекты Author), а также типовым набором операций для формирования и просмотра множества. При этом, в отличие от глав, книга не отвечает за уничтожение авторов, поскольку они могут быть авторами и других книг. Ниже показаны расширения класса Book для обработки набора авторов:

 

book.hpp

 

/*****************************************************************************/

 

//...

 

#include <unordered_set>

 

class Author;

 

/*****************************************************************************/

 

class Book

{

 

/*-----------------------------------------------------------------*/

 

public:

 

/*-----------------------------------------------------------------*/

 

//...

 

// Метод, возвращающий количество авторов

int getAuthorsCount () const;

 

// Метод, выясняющий является ли указанная персона автором данной книги

bool hasAuthor (Author const & _author) const;

 

// Метод, регистрирующий очередного автора книги

void addAuthor (Author const & _author);

 

// Метод, отменяющий регистрацию одного из авторов книги

void removeAuthor (Author const & _author);

 

// Метод очистки набора авторов

void clearAuthors ();

 

// Метод обхода набора авторов с применением указанного пользовательского действия

void forEachAuthor (std::function< void (Author const &) > _action) const;

 

/*-----------------------------------------------------------------*/

 

private:

 

/*-----------------------------------------------------------------*/

 

//...

 

// Множество авторов книги

std::unordered_set< Author const * > m_authors;

 

/*-----------------------------------------------------------------*/

 

};

 

/*****************************************************************************/

 

//...

 

// Реализация метода, возвращающего количество авторов

Inline int

Book::getAuthorsCount () const

{

return m_authors.size();

}

 

//...

 

/*****************************************************************************/

 

 

book.cpp

 

//...

 

/*****************************************************************************/

 

// Реализация метода, выясняющего является ли указанная персона автором данной книги

bool Book::hasAuthor (Author const & _author) const

{

// Поиск на множестве: если автор есть в составе, результат отличен от end()

return m_authors.find(& _author)!= m_authors.end();

}

 

/*****************************************************************************/

 

// Реализация метода, добавляющего очередного автора к книге

void Book::addAuthor (Author const & _author)

{

// Авторы не должны повторяться

if (hasAuthor(_author))

throw std::logic_error("Duplicate author");

 

// Добавляем автора во множество авторов данной книги

m_authors.insert(& _author);

}

 

/*****************************************************************************/

 

// Реализация метода удаления автора из книги

void Book::removeAuthor (Author const & _author)

{

// Ищем позицию автора во множестве

auto it = m_authors.find(& _author);

if (it == m_authors.end())

// Ошибка: такой автор не был зарегистрирован

throw std::logic_error("No such author");

 

// Удаляем автора из множества

m_authors.erase(it);

}

 

/*****************************************************************************/

 

// Реализация метода очистки набора авторов

void Book::clearAuthors ()

{

m_authors.clear();

}

 

/*****************************************************************************/

 

// Реализация метода обхода всех авторов с вызовом указанного пользовательскоо действия

void Book::forEachAuthor (std::function< void (Author const &) > _action) const

{

for (Author const * pAuthor: m_authors)

_action(* pAuthor);

// ^

// Клиентский код получит ссылку на автора

}

 

/*****************************************************************************/