如果我取消注释这些
//BaseList baselist;
//MemberList memberlist;
在循环外并注释掉它崩溃的循环内的那些。我需要能够在任何循环之外拥有基本列表(和成员列表)。这是如何实现的?
编辑
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 ofBaseList
, 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., theMyClass
(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 eachMyClass
in eachBaseList
hashes to a different value (anInt1 + Name
).In essence,
anInt1
tells where theMyClass
lives in AllThingsSpreadOut, butanInt1 + name
guarantees uniqueness within eachBaseList
.So the idea is that AllThingsSpreadOut is a vector of
BaseList
where at eachBaseList
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 [].
结束编辑
#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";
}
}
最佳答案
我很晚才看到它,但无论如何,这里是:
您描述的内容完全
MyClass
元素的侵入式哈希表的实现,其中anInt1
是元素的哈希值(bucket 标识符)- 桶列表以链表的形式实现
相等定义为
(anInt1, Name)
所以说真的,您的程序只是可以是: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";
如果你真的想要连续存储,我只能假设你想要这个是为了 boost 性能
您不想使用指针而不是对象,因为这只会抵消内存布局(“AllThingsBunchedTogether”)的好处,您最好使用
unordered_set
或unodered_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再次,这是一个概念验证:
#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"; }
关于c++ - 尝试学习 boost::intrusive Q2,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26857832/