0

如果我取消注释这些

//BaseList   baselist; 
//MemberList memberlist;

在循环之外并注释掉循环内它崩溃的那些。我需要能够在任何循环之外拥有基本列表(和成员列表)。这是如何实现的?

编辑

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

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

所以

  • AllThingsBunchedTogether 可能包含(只是anInt1为了紧凑起见的部分)1,2,1,10,2,3,4,4,5,9,10,10:。
  • 1,1AllThingsSpreadOut 可能在 [1] at [2] 2,2at [3] 3at [4] 4,4at [5] 5at [9] 9at [10]包含(零目前未使用)10,10,10

请注意,数字本身并不存储在 中BaseList,而是存储在例如MyClass(1, "John") 中。

在 [1] 它可能是“Mike”、“John”,在 [2] 它可能是“Mike”、“Dagobart” 在 [3] “John” ... 在 [10] “John” “Mike” “ Dagobart”等,因此BaseList在 AllThingsSpreadOut[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";
    }
}
4

2 回答 2

5

我看到它很晚,但无论如何,这里有:

  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_setorunodered_map如上所述

    • 不想使用auto_unlink模式,因为它会削弱性能(通过执行不受控制的删除触发器,通过抑制恒定时间size()和通过创建线程安全问题)

    • 相反,您应该采用上述策略,但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";
      }
      
于 2014-11-11T22:59:03.700 回答
0

这是您省略的错误消息:

Assertion `node_algorithms::inited(to_insert)' failed.

由此我们可以理解一个元素被插入了两次。这通常不适用于侵入式容器。

当您将列表放入循环中时,它们每次都会被销毁并重新创建。但是当它们在外面时,您永远不会清除它们,并且您也永远不会清除它们values,因此会出现以下顺序:

  1. 将 11 个元素添加到values.
  2. 将所有内容添加values到列表中。
  3. 添加 11 个元素到values; 它仍然有之前的 11 个元素,所以现在有 22 个元素。
  4. 将所有内容添加values到列表中。第一个崩溃,因为它已经在列表中。

一种解决方案是在循环values.clear()顶部添加。while(!done)

于 2014-11-11T07:14:05.393 回答