MyClass below represents a data structure that I need to be able to search very fast in two ways. So say I store the MyClass in and std::vector so that similar names in it can be quickly deleted and inserted continuously. But, I also need to be able to sort the contents of MyClass based on anInt. That is where an intrusive container (or Multimap) would sort the contents of a [very likely] unsorted std::vector. Two containers performing two very different duties on the same underlying items. Also, if I deleted the items from the std::vector they would also automatically disappear from the intrusive container.
Here is sort of the idea
#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; // need the items in the intrusive container to sort on number
}
struct hasher
{
size_t operator()(MyClass const& o) const
{
//return hash_fn(o.name);
return o.anInt1; // need the items in the intrusive container to sort on number
}
};
};
std::ostream& operator << (std::ostream& out, const MyClass& ac)
{
out << 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';
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';
// Note how easy and performance fast it is to delete items from the std::vector view
// I need the intrsive view to automatically update as well
values.erase(
std::remove_if(std::begin(values), std::end(values), std::mem_fn(&MyClass::bIsMarkedToDelete)),
std::end(values));
#if 0 // This code won't compile since there is no operator [] for hashtable
// If I did this now, it should show the "Mike" itens gone and the
/// rest of the items hanging off the same bucket still there.
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 << "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 << '\n';
values.clear();
std::cout << values.size() << '\n';
std::cout << hashtable.size() << '\n';
std::cout << "Done\n";
int j;
std::cin >> j;
}
