Реализация следующих видов поисковых таблиц:
- упорядоченная таблица;
- неупорядоченная таблица;
- хеш-таблица с разрешением коллизий методом цепочек;
- хеш-таблица с разрешением коллизий методом открытой адресации (квадратичное пробирование).
-
Сборка с помощью cmake.
-
На все случаи жизни имеются тесты.
-
Используются контейнеры (
std::vector
,std::list
) и некоторые алгоритмы (бинарный поиск) из STL. -
Широко используются шаблоны. Таблицы шаблонные, однако ключи только типа uint32.
-
Для каждой таблицы реализован итератор. Для, например, неупорядоченных таблиц можно создать итератор на начало/конец следующими способами.
typename UnsortedTable<int>::iterator it1 = table.begin();
auto it2 = table.begin();
typename UnsortedTable<int>::iterator it3 = table.end();
auto it4 = table.end();
Итераторы наследуются от std::iterator (т.е. могут использоваться в стандартных алгоритмах) и поддерживают, как минимум, интерфейс InputIterator.
В коде (см. include/Table.h) используется паттерн CRTP (Curiously recurring template pattern, Странно повторяющийся шаблон) для имитации виртуальных функций (https://ru.wikipedia.org/wiki/Curiously_recurring_template_pattern). Проиллюстрирую на примере.
class Base {
public:
virtual std::string getClassName() = 0;
void printHello() {
std::cout << "Hello from " << getClassName() <<std::endl;
}
};
class Derived : public Base {
public:
std::string getClassName() override {
return "Derived";
}
};
int main() {
Derived a;
a.printHello(); // "Hello from Derived"
}
Чтобы избежать дополнительных затрат на поддержку динамического полиморфизма, можно сделать так.
template <class TDerived>
class Base {
public:
std::string getClassName() {
static_cast<TDerived*>(this)->getClassName();
}
void printHello() {
std::cout << "Hello from " << getClassName() <<std::endl;
}
};
class Derived : public Base<Derived>{
public:
std::string getClassName() {
return "Derived";
}
};
Мы увеличили время компиляции, но избавились от динамического полиморфизма, т.е. уменьшили runtime. Это может играть большую роль, если мы вызываем функцию getClassName()
в цикле очень много раз.
Для того, чтобы избежать инстанцирования шаблона классом, не являющимся наследником Base, можно использовать static_assert
https://en.cppreference.com/w/cpp/language/static_assert.
static_assert(std::is_base_of<Base, TDerived>::value, "Derived class is not of Base type");
Шаблонная структура std::is_base_of
определена в заголовочном файле <type_traits>
(https://ru.cppreference.com/w/cpp/header/type_traits) и используется для определения на этапе компиляции, является ли TDerived наследником Base. Если да, то в структуре будет определена статическая константа value=true
. Также в <type_traits>
определено много других полезных структур подобного рода, например, enable_if
https://ru.cppreference.com/w/cpp/types/enable_if. Это все очень крутые вещи, советую почитать.
Рассмотрим пример:
UnsortedTable<std::vector<int>> table;
table.insert(std::vector<int>(10000, 7));
Здесь мы кладем в таблицу вектор из 10000 семерок. Что при происходит:
- создается временный объект
std::vector<int>(10000, 7)
; - он передается по ссылке в функцию
insert
с сигнатурой, например,void UnsortedTable<T>::insert(const T& elem)
; - и записывается в функции в конец массива storage - поля класса UnsortedTable
storage\[size\] = elem;
.
В пункте 3 по идее должен вызываться operator=
для std::vector
, который копирует вектор целиком, после чего при выходе из insert
временный объект должен уничтожиться. Очевидно, что это лишние затраты, которых можно было бы избежать без каких-либо потерь. Современные компиляторы в таких ситуациях просто перемещают временный объект в контейнер без лишнего копирования. Но что делать, если нужно создать вектор, проинициализировать его некоторым нетривиальным образом, а потом положить его в конейнер? Казалось бы, в следующем коде без копирования не обойтись:
UnsortedTable<std::vector<int>> table;
std::vector<int> v(10000);
for (int i = 0; i < 10000; i++)
v[i] = someFunc(i);
table.insert(v);
Однако начиная с С++11 можно написать так:
UnsortedTable<std::vector<int>> table;
std::vector<int> v(10000);
for (int i = 0; i < 10000; i++)
v[i] = someFunc(i);
table.insert(std::move(v));
И копирования не произойдет, вектор будет перемещен. После выполнения этого кода в таблице будет лежать проинициализированный вектор, а переменная v
будет пустым вектором нулевого размера.
Для того, чтобы такая магия была возможной, нужно правильно реализовать как объект, который кладем в контейнер (нужен конструктор перемещения и оператор присваивания перемещением, std::vector реализован правильно, ура), так и функцию вставки (в коде есть по 2 функции insert
- для копирования и для перемещения). Как именно это сделать, хорошо написано здесь https://habr.com/ru/post/226229/. В статье используются термины rvalue и lvalue, про них подробно можно почитать тут https://habr.com/ru/post/348198/.
Для всех таблиц тесты выглядят примерно одинаково. Google test позволяет запускать один тест для шаблонной фикстуры, проинстанцированной различными типами (макрос TYPED_TEST_P
). Как это делается, продемонстрировано в файле test/test_HashTable.cpp.
Также тест может быть параметризован различными значениями. Например, можно написать один тест с использованием некоторого целого параметра a и запустить его для a=1, 10, 145, ... (макрос TEST_P
).
Подробно про все это можно почитать в документации к google test (https://github.com/google/googletest/blob/master/googletest/docs/advanced.md и другие файлы в папке doc).
Также можно писать свои макросы для тестирования. Например, есть следующие тесты:
TEST(TestUnsortedTable, dont_throw_exception_when_insert) {
UnsortedTable<std::string> table;
ASSERT_NO_THROW(table.insert(1, "a"));
}
TEST(TestSortedTable, dont_throw_exception_when_insert) {
SortedTable<std::string> table;
ASSERT_NO_THROW(table.insert(1, "a"));
}
TEST(TestHashTable, dont_throw_exception_when_insert) {
HashTable<std::string> table;
ASSERT_NO_THROW(table.insert(1, "a"));
}
Тесты с почти одинаковым телом, отличие только в типе таблицы. Хотелось бы избежать повторов. Можно было бы использовать TYPED_TEST_P
, но следующее решение, на мой взгляд, даже красивее (test/test_Table.cpp).
#define TEST_FOR_ALL_TABLES(test_case, test_name) \
template <template<class> class TableType> void func##test_case##test_name(); \
TEST(test_case##UnsortedTable, test_name) { \
func##test_case##test_name<UnsortedTable>(); \
} \
TEST(test_case##SortedTable, test_name) { \
func##test_case##test_name<SortedTable>(); \
} \
TEST(test_case##HashTable, test_name) { \
func##test_case##test_name<HashTableOpenAddressing>(); \
} \ \
template <template<class> class TableType> \
void func##test_case##test_name()
TEST_FOR_ALL_TABLES(Test, dont_throw_exception_when_insert) {
TableType<std::string> table;
ASSERT_NO_THROW(table.insert(1, "a"));
}
Макрос многострочный, поэтому в конце каждой строки, кросе последней, при определении макроса стоит слеш. Конструкция a##b
просто соединяет строки в одну: ab
, при этом выполняя подстановку аргумента макроса, где это необходимо.
Итак, мы определили макрос, который будет для нашего теста развернут препроцессором в следующий код (конечно, макросы TEST
будут тоже развернуты):
template <template<class> class TableType> void funcTestdont_throw_exception_when_insert();
TEST(TestUnsortedTable, dont_throw_exception_when_insert) {
funcTestdont_throw_exception_when_insert<UnsortedTable>();
}
TEST(TestSortedTable, dont_throw_exception_when_insert) {
funcTestdont_throw_exception_when_insert<SortedTable>();
}
TEST(TestHashTable, dont_throw_exception_when_insert) {
funcTestdont_throw_exception_when_insert<HashTableOpenAddressing>();
}
template <template<class> class TableType>
void funcTestdont_throw_exception_when_insert() {
TableType<std::string> table;
ASSERT_NO_THROW(table.insert(1, "a"));
}
Получается, будто мы объявили шаблонную функцию funcTestdont_throw_exception_when_insert
, потом вызвали ее из трех разных тестов, а в конце определили. Красиво! Как-то так на самом деле и написана библиотека google test. Можно определить свои ASSERT при желании. Но злоупотреблять всем этим не стоит, потому что макросы - зло :)