Пытаюсь выучить boost::intrusive Q5

Question

У меня есть следующая программа. Я построил это с gcc-4.9.2 под linux. Мои вопросы:

1) Почему хеш-таблица кажется отсортированной в первый раз, но теряет сортировку после удаления элементов из значения?

2) Как мне пройти хеш-таблицу по ключу и сказать std::cout каждый элемент, который хэширует в корзину, например, код в the #if 0 #endif раздел?

#include <vector>
#include <iostream>
#include <vector>
#include <functional>

#include <boost/intrusive/unordered_set.hpp>

namespace bic = boost::intrusive;

std::hash<std::string> hash_fn;

struct MyClass : bic::unordered_set_base_hook<bic::link_mode<bic::auto_unlink>>
{
    std::string name;
    int anInt1;
    mutable bool bIsMarkedToDelete;

    MyClass(std::string name, int i) : name(name), anInt1(i), bIsMarkedToDelete(false) {}

    bool operator==(MyClass const& o) const
    {
        //return anInt1 == o.anInt1 && name == o.name;
        return name == o.name;
    }

    struct hasher
    {
        size_t operator()(MyClass const& o) const
        {
            return o.anInt1;
            //return hash_fn(o.name);
        }
    };
};

std::ostream& operator << (std::ostream& out, const MyClass& ac)
{
    std::cout << ac.name << " " << ac.anInt1;

    return out;
}

typedef bic::unordered_set<MyClass, bic::hash<MyClass::hasher>, bic::constant_time_size<false> > HashTable;

int main()
{
    std::vector<MyClass> values
    {
        MyClass { "John",     0 },
        MyClass { "Mike",     0 },
        MyClass { "Dagobart", 25 },
        MyClass { "John",     5 },
        MyClass { "Mike",     25 },
        MyClass { "Dagobart", 26 },
        MyClass { "John",     10 },
        MyClass { "Mike",     25 },
        MyClass { "Dagobart", 27 },
        MyClass { "John",     15 },
        MyClass { "Mike",     27 }
    };

    HashTable::bucket_type buckets[100];
    HashTable hashtable(values.begin(), values.end(), HashTable::bucket_traits(buckets, 100));

    std::cout << "\nContents of std::vector<MyClass> values\n";

    for(auto& e: values)
        std::cout << e << " ";

    std::cout << "\nContents of HashTable hashtable\n";

    for(auto& b : hashtable)
        std::cout << b << '\n';

#if 0 // This code won't compile since there is no operator [] for hashtable
    for(int bucket = 0; bucket < 27; bucket++)
    {
        auto hit(hashtable[bucket].rbegin());
        auto hite(hashtable[bucket].rend());

        while (hit != hite)
        {
            MyClass mc = *hit;

            std::cout << mc << " ";

            hit++;
        }

        std::cout << '\n';
    }
#endif // 0

    std::cout << '\n';
    std::cout << "values size first " << values.size() << '\n';
    std::cout << "hash size fist " << hashtable.size() << '\n';

    for(auto& e: values)
        e.bIsMarkedToDelete |= ("Mike" == e.name);

    std::cout << "removing all bIsMarkedToDelete";
    for(auto& e: values)
        if(e.bIsMarkedToDelete)
            std::cout << e << " ";

    std::cout << '\n';

    values.erase(
        std::remove_if(std::begin(values), std::end(values), std::mem_fn(&MyClass::bIsMarkedToDelete)),
                       std::end(values));

    std::cout << "values size now " << values.size() << '\n';
    std::cout << "hash size now " << hashtable.size() << '\n';

    std::cout << "Contents of value after removing elements " << '\n';
    for(auto& e: values)
        std::cout << e << " ";

    std::cout << "\nContents of HashTable hashtable after delete Mike\n";

    for(auto& b : hashtable)
        std::cout << b << '\n';

    std::cout << '\n';

    values.clear();

    std::cout << values.size() << '\n';
    std::cout << hashtable.size() << '\n';

    std::cout << "Done\n";

    int j;
    std::cin >> j;
}

Answer 1

Ваш хеш и равенство несовместимы, и поэтому вы нарушаете инварианты контейнера:

bool operator==(MyClass const& o) const
{
    //return anInt1 == o.anInt1 && name == o.name;
    return name == o.name;
}

struct hasher
{
    size_t operator()(MyClass const& o) const
    {
        return o.anInt1;
        //return hash_fn(o.name);
    }
};

Это было бы хорошо IFF каждого отдельного значения name всегда хэшируется в одно и то же ведро. Увы, это не так: например, "Майк" хэширует до 3 разных значений:

    MyClass { "Mike",     0  },
    MyClass { "Mike",     25 },
    MyClass { "Mike",     25 },
    MyClass { "Mike",     27 }

1) Почему хеш-таблица кажется отсортированной в первый раз, но теряет сортировку после удаления элементов из значения?

Я пытаюсь понять, что вы имеете в виду, но вывод программы:

Contents of std::vector<MyClass> values
John Mike Dagobart John Mike Dagobart John Mike Dagobart John Mike 
Contents of HashTable hashtable
Mike 0
John 0
John 5
John 10
John 15
Mike 25
Dagobart 25
Dagobart 26
Mike 27
Dagobart 27

values size first 11
hash size fist 10
removing all bIsMarkedToDeleteMike Mike Mike Mike 
values size now 7
hash size now 7
Contents of value after removing elements 
John Dagobart John Dagobart John Dagobart John 
Contents of HashTable hashtable after delete Mike
Dagobart 25
John 0
Dagobart 26
John 15
John 10
John 5
Dagobart 27

0
0
Done

Я должен предположить, что "в первый раз" будет часть "Содержимое HashTable hashtable". В самом деле, если вы посмотрите внимательно, это может показаться "отсортированным по ведру". Это может иметь большой смысл, что контейнер повторяется от корзины к корзине.

Тот факт, что после удаления он больше не может быть связан с тем фактом, что ваши реализации хеша / равенства не совпадают (см. Выше).

2) Как мне пройти хеш-таблицу по ключу и сказать std::cout каждый элемент, который хэширует в корзину, например, код в разделе #if 0 #endif?

Там нет прямого (публичного API) пути. Вы можете построить карту для целей отладки, используя hashtable.bucket(key), хотя:

Жить на Колиру

#include <vector>
#include <iostream>
#include <vector>
#include <map>
#include <functional>

#include <boost/intrusive/unordered_set.hpp>

namespace bic = boost::intrusive;

std::hash<std::string> hash_fn;

struct MyClass : bic::unordered_set_base_hook<bic::link_mode<bic::auto_unlink>>
{
    std::string name;
    int anInt1;
    mutable bool bIsMarkedToDelete;

    MyClass(std::string name, int i) : name(name), anInt1(i), bIsMarkedToDelete(false) {}

    bool operator==(MyClass const& o) const
    {
        return anInt1 == o.anInt1 && name == o.name;
    }

    struct hasher
    {
        size_t operator()(MyClass const& o) const
        {
            return hash_fn(o.name);
        }
    };
};

std::ostream& operator << (std::ostream& out, const MyClass& ac) {
    return out << ac.name << " " << ac.anInt1;
}

typedef bic::unordered_set<MyClass, bic::hash<MyClass::hasher>, bic::constant_time_size<false> > HashTable;

int main()
{
    std::vector<MyClass> values {
        MyClass { "Dagobart", 25 },
        MyClass { "Dagobart", 26 },
        MyClass { "Dagobart", 27 },
        MyClass { "John",     0  },
        MyClass { "John",     10 },
        MyClass { "John",     15 },
        MyClass { "John",     5  },
        MyClass { "Mike",     0  },
        MyClass { "Mike",     25 },
        MyClass { "Mike",     25 },
        MyClass { "Mike",     27 }
    };

    HashTable::bucket_type buckets[100];
    HashTable hashtable(values.begin(), values.end(), HashTable::bucket_traits(buckets, 100));

    std::cout << "\nDebugging buckets of hashtable\n";

    std::multimap<size_t, MyClass const*> debug_map;
    std::transform(hashtable.begin(), hashtable.end(), 
            std::inserter(debug_map, debug_map.end()), 
            [&](MyClass const& mc) { return std::make_pair(hashtable.bucket(mc), &mc); }
        );

    for (auto& entry : debug_map)
        std::cout << "Debug bucket: " << entry.first << " -> " << *entry.second << "\n";
}

Печать

Debugging buckets of hashtable
Debug bucket: 16 -> Mike 27
Debug bucket: 16 -> Mike 25
Debug bucket: 16 -> Mike 0
Debug bucket: 21 -> Dagobart 27
Debug bucket: 21 -> Dagobart 26
Debug bucket: 21 -> Dagobart 25
Debug bucket: 59 -> John 5
Debug bucket: 59 -> John 15
Debug bucket: 59 -> John 10
Debug bucket: 59 -> John 0

Конечно, результат зависит от фактической реализации std::hash<std::string> и настройка хеш-таблицы.