jeudi 21 janvier 2021

Find element in boost multi_index_container

In my code I need to have a functionality to iterate over all elements and check if there some element already exists possibly as soon as possible, so my choice fell on boost multi index container where I can use vector and unordered_set interface for my class Animal at the same time. The problem is that I am not able to find some element through unordered_set interface since I replaced key from std::string to std::array<char, 50> and adjusted the code, and I don't know what I am doing wrong ?

code: https://wandbox.org/permlink/dnCaEzYVdXkTFBGo

#include <array>
#include <algorithm>
#include <iostream>
#include <chrono>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <memory>

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/composite_key.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/sequenced_index.hpp>
#include <boost/multi_index/random_access_index.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/identity.hpp>

int constexpr elements_size{ 1'000'000 };

struct Animal
{
Animal(std::string name, std::string description, int leg, int age, double maxSpeed) noexcept :
    description_{std::move(description)}, leg_{leg}, age_{age}, maxSpeed_{maxSpeed}
{
    std::copy(name.begin(), name.end(), name_.data());
}

Animal(std::string const& name, std::string const& description) noexcept :
    description_{description}
{
    std::copy(name.begin(), name.end(), name_.data());
}

Animal(Animal&& animal) noexcept
{
    name_ = name_;
    description_ = std::move(animal).description_;
    leg_ = animal.leg_;
    age_ = animal.age_;
    maxSpeed_ = animal.maxSpeed_;
}

Animal(Animal const& animal) noexcept
{
    name_ = animal.name_;
    description_ = animal.description_;
    leg_ = animal.leg_;
    age_ = animal.age_;
    maxSpeed_ = animal.maxSpeed_;
}

Animal& operator=(Animal&& animal) noexcept
{
    name_ = name_;
    description_ = std::move(animal).description_;
    leg_ = animal.leg_;
    age_ = animal.age_;
    maxSpeed_ = animal.maxSpeed_;
    return *this;
}

Animal& operator=(Animal const& animal) noexcept
{
    name_ = animal.name_;
    description_ = animal.description_;
    leg_ = animal.leg_;
    age_ = animal.age_;
    maxSpeed_ = animal.maxSpeed_;
    return *this;
}

std::array<char, 50> name_;
std::string description_;
int leg_{0};
int age_{0};
double maxSpeed_{0.0};
};

struct Hasher
{
bool print_;
Hasher(bool print = false): print_{print} {}
std::size_t operator()(std::array<char, 50> const& name) const
{
    if (print_)
        std::cout << "array hash" << std::hash<std::string_view>{}(name.data()) << std::endl;
    return std::hash<std::string_view>{}(name.data());
}
std::size_t operator()(std::string const& name) const
{
    if (print_)
        std::cout << "string hash" << std::hash<std::string_view>{}(name.c_str()) << std::endl;
    return std::hash<std::string_view>{}(name.c_str());
}
std::size_t operator()(const char* name) const
{
    if (print_)
        std::cout << "char hash" << std::hash<std::string_view>{}(name) << std::endl;
    return std::hash<std::string_view>{}(name);
}
};

struct KeysComparator
{
bool operator()(std::array<char, 50> const& a1, std::array<char, 50> const& a2) const {return a1 == a2; }
template <typename T>
bool operator()(std::string const& n1, T const& t) const
{
    std::cout << "### value.name_" << t.value.name_.data() << ", n1: " << n1 << std::endl;
    return n1 == t.value.name_.data();
}
};

template<typename TimePoint>
std::string getElapsedTime(TimePoint const& start, TimePoint const& end)
{
auto micro = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
auto milli = std::chrono::duration_cast<std::chrono::milliseconds>(micro);
auto sec = std::chrono::duration_cast<std::chrono::seconds>(milli);

return {std::to_string(micro.count()) + " µs, " + std::to_string(milli.count()) + " ms, " + std::to_string(sec.count()) + " s"};
}

template<typename TimePoint>
void printStatistics(TimePoint const& emplace_start, TimePoint const& emplace_end, TimePoint const& iterate_start, TimePoint const& iterate_end,
TimePoint const& find_start, TimePoint const& find_end, intmax_t const sum, std::string target)
{
std::cout << "Elapsed time emplace: "  << getElapsedTime(emplace_start, emplace_end)
    << "  |  iterate: " << getElapsedTime(iterate_start, iterate_end)
    << "  |  find: " << getElapsedTime(find_start, find_end)
    << ", sum:" << sum << " , calculation for " << target << std::endl;
}

void test()
{
using namespace boost::multi_index;
using Animal_multi = multi_index_container<Animal, indexed_by<
    random_access<>,
    hashed_unique<
        composite_key<Animal, member<Animal, std::array<char, 50>, &Animal::name_>>,
        composite_key_hash<Hasher>,
        composite_key_equal_to<KeysComparator>>
>>;

Animal_multi container;
auto emplace_start = std::chrono::steady_clock::now();
for (auto i = 0; i < elements_size; ++i)
    container.emplace_back("the really long name of some animal 12345678910_" + std::to_string(i),
                           "bla bla bla bla bla bla bla bla bla bla bla bla bla", 4, i, i + 2);
auto emplace_end = std::chrono::steady_clock::now();

intmax_t sum{0};
auto iterate_start = std::chrono::steady_clock::now();
for (auto const& e : container)
    sum += e.age_;
auto iterate_end = std::chrono::steady_clock::now();

KeysComparator key_comparator;
Hasher hasher{true};
auto find_start = std::chrono::steady_clock::now();
auto &container_interface = container.get<1>();
auto isSucceeded = container_interface.count("the really long name of some animal 12345678910_" + std::to_string(elements_size-1),
                                             hasher, key_comparator);
if (not isSucceeded)
    std::cout << "WARN: Element has not been found." << std::endl;
auto find_end = std::chrono::steady_clock::now();

printStatistics(emplace_start, emplace_end, iterate_start, iterate_end, find_start, find_end, sum, "Animal_multi (boost multi_index)");
}

int main()
{
    test();
    return 0;
}

Aucun commentaire:

Enregistrer un commentaire