试图学习boost :: intrusive Q2

Question

如果我取消注释这些

//BaseList   baselist; 
//MemberList memberlist;

在循环之外并注释掉循环中的那些它崩溃了.我需要能够在任何循环之外使用baselist(和memberlist).这是如何实现的？

编辑

我试图以最简单的形式解决的实际问题是这个.

我想要一个std :: vector MyClass,称之为AllThingsBunchedTogether.我也想要一个std :: vector BaseList,称之为AllThingsSpreadOut.

所以

• AllThingsBunchedTogether可能含有(只anInt1用于紧凑的缘故部分)1,2,1,10,2,3,4,4,5,9,10,10.
• AllThingsSpreadOut可能包含([1] 1,1中的[1] 2,2,[3] 3,[ 3] ,[4] 4,4,[5] 5,[9] 9,[ 9] ,[10] 10,10,10.

注意,数字本身不存储在BaseList例如MyClass(1,"John")中.

在[1]它可能是"迈克","约翰",在[2]它可能是"迈克","达戈巴特"在[3]"约翰"......在[10]"约翰""迈克"" Dagobart"等因此BaseListAllThingsSpreadOut [i] 中的任何一个都没有重复,因为MyClass每个 BaseList散列到不同的值(anInt1 + Name).

从本质上讲,它anInt1告诉MyClassAllThingsSpreadOut生活在哪里,但anInt1 + name保证每个人的独特性BaseList.

因此,我们的想法是AllThingsSpreadOut是一个向量,BaseList其中每个BaseList向量位置都是类似事物的列表.

然后,当我从AllThingsBunchedTogether中删除内容时(不是通过清除,而是通过搜索删除IsMarkedToDelete下面的代码中的某些项目),它们将自动从相应的AllThingsSpreadOut中消失.

AllThingsSpreadOut充当AllThingsBunchedTogether的排序,具有侵入性语义.AllThingsBunchedTogether允许通过[]进行超高速访问.

结束编辑

#include <vector>
#include <iostream>

#include <boost/intrusive/list.hpp>

using namespace boost::intrusive;

class MyClass : public list_base_hook<link_mode<auto_unlink>> // This is a derivation hook
{
public:
    std::string name;
    bool bIsMarkedToDelete;
    int anInt1;
public:
    list_member_hook<link_mode<auto_unlink>> member_hook_; // This is a member hook

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

bool IsMarkedToDelete(const MyClass &o)
{
    return o.bIsMarkedToDelete;
}

//Define a list that will store MyClass using the public base hook
typedef list<MyClass, constant_time_size<false>> BaseList;

// Define a list that will store MyClass using the public member hook
typedef list<MyClass,
        member_hook<MyClass, list_member_hook<link_mode<auto_unlink>>, &MyClass::member_hook_>,
        constant_time_size<false> > MemberList;

int main()
{
    bool done = false;
    std::vector<MyClass> values;

    std::string names[] = {"John", "Mike", "Dagobart"};

    //BaseList   baselist; 
    //MemberList memberlist;

    int i = 0;
    while(!done)
    {
        // Create several MyClass objects, each one with a different value

        for (int j = 0; j < 11; ++j)
            values.emplace_back(names[j % 3], j);

        BaseList   baselist;
        MemberList memberlist;

        // Now insert them in t-he reverse order in the base hook list
        for (auto& e : values)
        {
            baselist.push_front(e);
            memberlist.push_back(e);
        }

        // Now test lists
        auto rbit(baselist.rbegin());
        auto mit(memberlist.begin());
        auto it(values.begin()), itend(values.end());

        // Test the objects inserted in the base hook list
        for (; it != itend; ++it, ++rbit)
        {
            if (&*rbit != &*it)
                return 1;
        }
        // Test the objects inserted in the member hook list
        for (it = values.begin(); it != itend; ++it, ++mit)
        {
            if (&*mit != &*it)
                return 1;
        }
# if 0
        for(auto& e : values)
            std::cout << e.anInt1 << "\n";

        for(auto& e : baselist)
            std::cout << e.anInt1 << "\n";

        for(auto& e : memberlist)
            std::cout << e.anInt1 << "\n";

#endif // 0

        if(2 == i)
        {
            for(auto& e: values)
                std::cout << e.name << "\n";

            for(auto& e: values)
            {
                if("Mike" == e.name)
                    e.bIsMarkedToDelete = true;
            }

            values.erase(
                std::remove_if(values.begin(), values.end(), IsMarkedToDelete), values.end());
        }


        if(i++ > 3)
        {
            values.clear();
            done = true;
        }

        std::cout << "\n";
        std::cout << values.size()     << "\n";
        std::cout << baselist.size()   << "\n";
        std::cout << memberlist.size() << "\n";
    }
}

Answer 1

我已经看到了很晚,但无论如何,这里有:

1. 您描述的内容完全匹配MyClass元素的侵入式哈希表的实现,其中

   • anInt1是元素的哈希(桶标识符)
   • 存储桶列表实现为链接列表

   • 平等被定义为平等 (anInt1, Name)

     

   
   所以,你的程序可能只是:

   Live On Coliru

   std::unordered_set<MyClass> values {
       { "John",      0 }, { "Mike",      1 }, { "Dagobart",  2 },
       { "John",      3 }, { "Mike",      4 }, { "Dagobart",  5 },
       { "John",      6 }, { "Mike",      7 }, { "Dagobart",  8 },
       { "John",      9 }, { "Mike",     10 },
   };
   
   for(int i = 0; i<=3; ++i) {
       if(2 == i) {
           for(auto& e: values) std::cout << e.name << " "; std::cout << "\n";
           for(auto& e: values) e.bIsMarkedToDelete |= ("Mike" == e.name);
   
           for(auto it=begin(values); it!=end(values);) {
               if (it->bIsMarkedToDelete) it = values.erase(it);
               else ++it;
           }
       }
   
       std::cout << "i=" << i << ", values.size(): " << values.size() << "\n";
   }
   values.clear();
   std::cout << "Done\n";
   

2. 如果你真的想要连续存储,我只能假设你想要这个性能

   • 你不希望使用指针,而不是对象,因为简单地否定了内存布局("AllThingsBunchedTogether")利益,你会更好用unordered_set或unodered_map如上

   • 你不希望使用auto_unlink模式,因为它削弱性能(通过做不受控制删除触发器,通过抑制恒定时间size(),并通过创建线程安全问题)

   • 相反,你应该使用上面的stratagy,但boost::intrusive::unordered_set请参阅http://www.boost.org/doc/libs/1_57_0/doc/html/intrusive/unordered_set_unordered_multiset.html

     在这里,再一次,是一个概念验证:

     Live On Coliru

     #include <vector>
     #include <iostream>
     #include <boost/intrusive/unordered_set.hpp>
     #include <vector>
     //#include <functional>
     //#include <algorithm>
     
     namespace bic = boost::intrusive;
     
     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 o.anInt1; } };
     };
     
     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",  1 }, MyClass { "Dagobart", 2 },
             MyClass { "John", 3 }, MyClass { "Mike",  4 }, MyClass { "Dagobart", 5 },
             MyClass { "John", 6 }, MyClass { "Mike",  7 }, MyClass { "Dagobart", 8 },
             MyClass { "John", 9 }, MyClass { "Mike", 10 },
         }; 
     
         HashTable::bucket_type buckets[100];
         HashTable hashtable(values.begin(), values.end(), HashTable::bucket_traits(buckets, 100)); 
     
         for(int i = 0; i<=3; ++i) {
             if(2 == i) {
                 for(auto& e: values) std::cout << e.name << " "; std::cout << "\n";
                 for(auto& e: values) e.bIsMarkedToDelete |= ("Mike" == e.name);
     
                 values.erase(std::remove_if(begin(values), end(values), std::mem_fn(&MyClass::bIsMarkedToDelete)));
             }
     
             std::cout << "i=" << i << ", values.size():    " << values.size()    << "\n";
             std::cout << "i=" << i << ", hashtable.size(): " << hashtable.size() << "\n";
         }
         values.clear();
         std::cout << "Done\n";
     }