努力学习的boost ::侵入Q2 [英] Trying to learn boost::intrusive Q2

查看：164
本文介绍了努力学习的boost ::侵入Q2的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

如果我去掉这些

  // BaseList baselist;
//会员会员;

外循环并注释掉崩溃的循环内的人。我需要能够有任何循环外的baselist（和会员）。这是如何实现的？

修改


  

我想在它来解决实际问题的最简单的形式是这样的。


  
  

我想有 MyClass的的一个std ::向量，称之为AllThingsBunchedTogether。
  我也希望有 BaseList 的一个std ::向量，称之为AllThingsS preadOut。


  
  

所以


  
  

      
  • AllThingsBunchedTogether可能包含（对于紧凑的缘故只是 anInt1 部分）： 1,2,1,10,2,3,4 ，4,5,9,10,10 。

    •   
  • AllThingsS preadOut可能包含在[1] 1,1 在[2] 2,2（零不用于现在） 在[3] 3 在[4] 4,4 在[5] 5 在[9] 9 在[10] 10,10,10 。

    •   

  
  

请注意，本身并不存储在号码 BaseList ，但如在 MyClass的（1 ， 约翰）。


  
  

目前[1]也可能是迈克，约翰，在[2]也可能是迈克，Dagobart在[3]
  约翰在... [10]约翰麦克Dagobart等，使在那里没有重复
  在每个任何 BaseList 在AllThingsS preadOut [我]，因为每个 MyClass的
   BaseList 散列不同的值（ anInt1 +姓名）。


  
  

在本质上， anInt1 讲述其中 MyClass的住在AllThingsS preadOut，但 anInt1 +名称保证在每个独特 BaseList 。


  
  

这样的想法是，AllThingsS preadOut是一个vector BaseList ，其中每个 BaseList 在矢量位置是类似的事情的清单。


  
  

然后，当我从AllThingsBunchedTogether删除的东西（而不是明确的，而是由一个搜索除去像下面IsMarkedToDelete的code部分项目），它们将自动从相应的AllThingsS preadOut消失。


  
  

AllThingsS preadOut作为一种用于AllThingsBunchedTogether，具有侵入性语义。 AllThingsBunchedTogether允许通过[]超快的访问。


结束修改 

 的#include＆LT;矢量＆GT;
＃包括LT＆;＆iostream的GT;＃包括LT＆;升压/侵入/ list.hpp＆GT;使用空间boost ::侵入;MyClass类：公共list_base_hook＆LT; link_mode＆LT; auto_unlink＆GT;＆GT; //这是一个推导挂钩
{
上市：
    性病::字符串名称;
    布尔bIsMarkedToDelete;
    INT anInt1;
上市：
    list_member_hook＆LT; link_mode＆LT; auto_unlink＆GT;＆GT; member_hook_; //这是一个成员挂钩    MyClass的（性病::字符串n，int i）以：名（n），anInt1（I），bIsMarkedToDelete（假）{}
};布尔IsMarkedToDelete（常量MyClass的＆放大器; O）
{
    返回o.bIsMarkedToDelete;
}//定义将使用公共基类钩子保存MyClass的名单
的typedef列表＆LT; MyClass的，constant_time_size＆LT;假＆gt;＆GT; BaseList;//定义将使用公有成员钩子保存MyClass的名单
的typedef列表＆LT; MyClass的，
        member_hook＆所述; MyClass的，list_member_hook＆所述; link_mode＆下; auto_unlink＆GT;＆gt;中＆放大器; MyClass的:: member_hook_＆gt;中
        constant_time_size＆LT;假＆gt; ＆GT;会员;诠释的main（）
{
    布尔做= FALSE;
    的std ::矢量＆lt;＆MyClass的GT;值;    性病::字符串名称[] = {约翰，迈克，Dagobart};    // BaseList baselist;
    //会员会员;    INT I = 0;
    而（！完成）
    {
        //创建几个MyClass的对象，每一个不同的值        为（中间体J = 0; J＆下; 11; ++ j）条
            values​​.emplace_back（地名[J％3]，J）;        BaseList baselist;
        会员会员;        //现在将其插入T-他在基地挂钩列表反序
        为（自动急症：值）
        {
            baselist.push_front（E）;
            memberlist.push_back（E）;
        }        //现在测试列表
        自动RBIT（baselist.rbegin（））;
        自动MIT（memberlist.begin（））;
        自动它（values​​.begin（）），itend（values​​.end（））;        //测试插入在基座钩列表中的对象
        为（;！它= itend ++吧，++ RBIT）
        {
            如果（安培;！* RBIT =放大器; *它）
                返回1;
        }
        //测试插入构件钩列表中的对象
        对于（IT = values​​.begin（）;它= itend;！++中，++ MIT）
        {
            如果（安培;！* MIT =放大器; *它）
                返回1;
        }
＃如果0
        为（自动急症：值）
            性病::法院LT＆;＆LT; e.anInt1＆LT;＆LT; \\ n;        为（自动急症：baselist）
            性病::法院LT＆;＆LT; e.anInt1＆LT;＆LT; \\ n;        为（自动急症：会员）
            性病::法院LT＆;＆LT; e.anInt1＆LT;＆LT; \\ n;#ENDIF // 0        如果（2 == I）
        {
            为（自动急症：值）
                性病::法院LT＆;＆LT; e.name＆LT;＆LT; \\ n;            为（自动急症：值）
            {
                如果（迈克== e.name）
                    e.bIsMarkedToDelete = TRUE;
            }            values​​.erase（
                性病::的remove_if（values​​.begin（），values​​.end（），IsMarkedToDelete），values​​.end（））;
        }
        如果（ⅰ++→3）
        {
            values​​.clear（）;
            做= TRUE;
        }        性病::法院LT＆;＆LT; \\ n;
        性病::法院LT＆;＆LT; values​​.size（）＆所述;＆下; \\ n;
        性病::法院LT＆;＆LT; baselist.size（）＆所述;＆下; \\ n;
        性病::法院LT＆;＆LT; memberlist.size（）＆所述;＆下; \\ n;
    }
}


解决方案

我已经看到了它晚了，但不管怎么说，这里有云：


  1. 您描述一下比赛的究竟的 MyClass的元素的侵入哈希表的实现，其中


    • anInt1 是哈希（中的斗的标识符）的元素

    • 桶列表被实现为链表

    • 平等是指平等（anInt1，名称）


        





    所以真的，你的程序可能的只是的是：

    <大骨节病> 住在Coliru 

     的std :: unordered_set＆LT; MyClass的＆GT;值{
        {约翰，0}，{迈克，1}，{Dagobart，2}，
        {约翰，3}，{迈克，4}，{Dagobart，5}，
        {约翰，6}，{迈克，7}，{Dagobart，8}，
        {约翰，9}，{迈克，10}，
    };的for（int i = 0; I＆LT; = 3; ++ I）{
        如果（2 == I）{
            为（自动急症：值）的std ::法院LT＆;＆LT; e.name＆LT;＆LT; ;性病::法院LT＆;＆LT; \\ n;
            为（自动急症：值）e.bIsMarkedToDelete | =（迈克== e.name）;        为（自动它=开始（值）！=它结束（值））{
                如果（IT-＆GT; bIsMarkedToDelete）IT = values​​.erase（它）;
                其他++中;
            }
        }    性病::法院LT＆;＆LT; 我=＆LT;＆LT; I＆LT;＆LT; values​​.size（）：＆所述;＆下; values​​.size（）＆所述;＆下; \\ n;
    }
    values​​.clear（）;
    性病::法院LT＆;＆LT; 做的\\ n;


  2. 如果你真的想连续的存储，我只能假设你想这对性能


    • 在不要想用指针而不是对象，因为这只是否定了内存布局（AllThingsBunchedTogether）利益，你会与<$ C $更好C> unordered_set 或 unodered_map 如上


    • 在不要要使用 auto_unlink 模式，因为它削弱性能（通过做不受控制删除触发器，通过抑制恒时间尺寸（），并通过创建线程安全问题）


    • 相反，你应该使用上述战略思考，而是用的boost ::侵入:: unordered_set ，而不是看的http://www.boost.org/doc/libs/1_57_0/doc/html/intrusive/unordered_set_unordered_multiset.html

      下面，又是一个证明的概念：

      <大骨节病> 住在Coliru 

       的#include＆LT;矢量＆GT;
      ＃包括LT＆;＆iostream的GT;
      ＃包括LT＆;升压/侵入/ unordered_set.hpp＆GT;
      ＃包括LT＆;矢量＆GT;
      //＃包括＆lt;功能＆GT;
      //＃包括LT＆;＆算法GT;命名空间BIC =的boost ::侵入;结构MyClass的：BIC :: unordered_set_base_hook＆LT; BIC :: link_mode＆LT; BIC :: auto_unlink＆GT;＆GT;
      {
          性病::字符串名称;
          INT anInt1;
          可变布尔bIsMarkedToDelete;    MyClass的（标准::字符串名称，int i）以：姓名（名称），anInt1（I），bIsMarkedToDelete（假）{}    布尔运算符==（const的MyClass的放大器和O）const的{返回anInt1 == o.anInt1＆放大器;＆安培;命名== o.name; }    结构散列器{为size_t运算符（）（MyClass的常量和放大器; O）const的{返回o.anInt1; }};
      };BIC的typedef :: unordered_set＆LT; MyClass的，BIC ::散列＆LT; MyClass的::散列器＆gt;中BIC :: constant_time_size＆LT;假＆gt; ＆GT;哈希表;诠释主（）{    的std ::矢量＆lt;＆MyClass的GT;值{
              MyClass的{约翰，0}，{MyClass的迈克，1}，{MyClass的Dagobart，2}，
              MyClass的{约翰，3}，{MyClass的迈克，4}，{MyClass的Dagobart，5}，
              MyClass的{约翰，6}，{MyClass的迈克，7}，{MyClass的Dagobart，8}，
              MyClass的{约翰，9}，{MyClass的迈克，10}，
          };    哈希表:: bucket_type桶[100];
          哈希表哈希表（values​​.begin（），values​​.end（），哈希表:: bucket_traits（桶，100））;    的for（int i = 0; I＆LT; = 3; ++ I）{
              如果（2 == I）{
                  为（自动急症：值）的std ::法院LT＆;＆LT; e.name＆LT;＆LT; ;性病::法院LT＆;＆LT; \\ n;
                  为（自动急症：值）e.bIsMarkedToDelete | =（迈克== e.name）;            values​​.erase（性病::的remove_if（开始（值），端（值）的std ::的mem_fn（放大器; MyClass的:: bIsMarkedToDelete）））;
              }        性病::法院LT＆;＆LT; 我=＆LT;＆LT; I＆LT;＆LT; values​​.size（）：＆所述;＆下; values​​.size（）＆所述;＆下; \\ n;
              性病::法院LT＆;＆LT; 我=＆LT;＆LT; I＆LT;＆LT; hashtable.size（）：＆所述;＆下; hashtable.size（）＆所述;＆下; \\ n;
          }
          values​​.clear（）;
          性病::法院LT＆;＆LT; 做的\\ n;
      }



if I uncomment these 

//BaseList   baselist; 
//MemberList memberlist;

outside the loop and comment out the ones inside the loop it crashes. I need to be able to have the baselist (and memberlist) outside any loop. How is this achieved?

Edit

The actual problem I am trying to solve in it's simplest form is this.

I want to have a std::vector of MyClass, call it AllThingsBunchedTogether. I also want to have a std::vector of BaseList, call it AllThingsSpreadOut.

So

  • AllThingsBunchedTogether might contain (just the anInt1 part for the sake of compactness): 1,2,1,10,2,3,4,4,5,9,10,10.
  • AllThingsSpreadOut might contain (zero not used for now) at [1] 1,1 at [2] 2,2 at [3] 3 at [4] 4,4 at [5] 5 at [9] 9 at [10] 10,10,10.

Note that the numbers themselves aren't be stored in the BaseList, but e.g., the MyClass(1, "John").

At [1] it could be "Mike", "John", at [2] it could be "Mike", "Dagobart" at [3] "John" ... at [10] "John" "Mike" "Dagobart" etc so that there no duplicates in any of the BaseList at AllThingsSpreadOut[i] since each MyClass in each BaseList hashes to a different value (anInt1 + Name).

In essence, anInt1 tells where the MyClass lives in AllThingsSpreadOut, but anInt1 + name guarantees uniqueness within each BaseList.

So the idea is that AllThingsSpreadOut is a vector of BaseList where at each BaseList at vector location is a list of similar things.

Then, when I remove things from AllThingsBunchedTogether (not by a clear, but by a search to remove some items like in the code below IsMarkedToDelete), they will automatically disappear from the corresponding AllThingsSpreadOut.

AllThingsSpreadOut acts as a sort for AllThingsBunchedTogether, with intrusive semantics. AllThingsBunchedTogether allows superfast access through [].

End Edit

#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";
    }
}

解决方案

I've seen it late, but anyways, here goes:

  1. What you describe matches exactly the implementation of an intrusive hash table of MyClass elements, where

    • anInt1 is the hash (the bucket identifier) for an element
    • the bucket lists are implemented as linked lists

    • equality is defined as equality of (anInt1, Name)


    So really, your program could just be:

    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. if you really wanted contiguous storage, I can only assume you wanted this for performance

    • you do not want to use pointers instead of objects, since that simply negates the memory layout ("AllThingsBunchedTogether") benefits and you'd be better of with the unordered_set or unodered_map as above

    • you do not want to use auto_unlink mode, since it cripples performance (by doing uncontrolled deletion triggers, by inhibiting constant-time size() and by creating thread safety issues)

    • instead, you should employ the above stratagy, but with boost::intrusive::unordered_set instead see http://www.boost.org/doc/libs/1_57_0/doc/html/intrusive/unordered_set_unordered_multiset.html

      Here, again, is a proof-of-concept:

      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";
}

这篇关于努力学习的boost ::侵入Q2的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文
相关文章
C/C++开发最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆