c++ - 尝试学习 boost::intrusive Q5

Question

我有以下程序。我是在linux下用gcc-4.9.2搭建的。我的问题是:

1) 为什么哈希表第一次看起来是排序的，但是在从值中删除项目后排序就丢失了？

2) 我如何自己通过 key 遍历哈希表并说出 std::cout 散列到桶中的每个项目，例如 #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);
    }
};

如果 name 的每个不同值都可以进行 IFF总是哈希到同一个桶。 las，它没有:例如“Mike”散列为 3 个不同的值:

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

1) Why does the hashtable seem to be sorted the first time around, but loses the sort after the items are deleted from value?

我想明白你的意思，但程序的输出是:

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 哈希表的内容”部分。事实上，如果你仔细观察，那似乎是“按桶排序”。容器逐桶迭代可能很有意义。

在删除后它不再存在的事实可能与您的散列/相等性实现不匹配这一事实有很大关系(见上文)。

2) How do I walk the hashtable by key myself and say std::cout each item that hashes to a bucket, e.g., the code in the #if 0 #endif section?

没有直接的(公共(public) API)方式。不过，您可以使用 hashtable.bucket(key) 构建用于调试目的的映射:

Live On Coliru

#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>的实际执行以及哈希表的调整。