两个 [或多个] 具有相同底层数据但数据视图不同的容器
Two [or more] containers with same underlying data, but different views on the data
下面的 MyClass 表示我需要能够以两种方式快速搜索的数据结构。所以说我将MyClass存储在std::vector中，这样可以快速删除和连续插入其中的相似名称。但是，我还需要能够根据 anInt 对 MyClass 的内容进行排序。这就是侵入式容器（或 Multimap）对 [很可能] 未排序 std::vector 的内容进行排序的地方。两个容器对相同的基础项目执行两种截然不同的职责。此外，如果我从 std::vector 中删除项目，它们也会自动从侵入容器中消失。
有点想法
#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;
}
您需要使用不同的索引进行快速查找。这让我想到了 Boost MultiIndex。
下一个：
So say I store the MyClass in and std::vector so that similar names in it can be quickly deleted and inserted continuously
结合
Also, if I deleted the items from the std::vector they would also automatically disappear
明确表示您无论如何都无法逃避保持所有索引最新的成本。在这种情况下，Boost Multi Index 和它得到的一样好。
这是一个示例：
#include <iostream>
#include <vector>
#include <boost/tuple/tuple_comparison.hpp>
#include <boost/range/iterator_range.hpp>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/random_access_index.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/ordered_index.hpp>
namespace bmi = boost::multi_index;
struct MyClass
{
std::string name;
int anInt1;
MyClass(std::string name, int i) : name(name), anInt1(i) {}
//bool operator==(MyClass const& o) const { return boost::tie(name, anInt1) == boost::tie(o.name, o.anInt1); }
//bool operator< (MyClass const& o) const { return boost::tie(name, anInt1) < boost::tie(o.name, o.anInt1); }
friend std::ostream& operator << (std::ostream& out, const MyClass& ac) {
return out << ac.name << " " << ac.anInt1;
}
};
using Table = bmi::multi_index_container<MyClass,
bmi::indexed_by<
bmi::random_access<bmi::tag<struct as_vector> >,
bmi::ordered_non_unique<bmi::tag<struct by_number>,
bmi::member<MyClass, int, &MyClass::anInt1>
>,
bmi::hashed_non_unique<bmi::tag<struct by_name>,
bmi::member<MyClass, std::string, &MyClass::name>
>
>
>;
void alternative_remove_mikes(Table& values);
int main()
{
Table values {
{ "John", 0 },
{ "Mike", 0 },
{ "Dagobart", 25 },
{ "John", 5 },
{ "Mike", 25 },
{ "Dagobart", 26 },
{ "John", 10 },
{ "Mike", 25 },
{ "Dagobart", 27 },
{ "John", 15 },
{ "Mike", 27 },
};
auto& name_idx = values.get<by_name>();
std::cout << "\nBEFORE: Ordered by number:\n";
for(auto& e: values.get<by_number>())
std::cout << e << "\n";
std::cout << "\nBEFORE: O(1) lookup by name:\n";
for(auto& e : boost::make_iterator_range(name_idx.equal_range("Mike")))
std::cout << e << '\n';
std::cout << "removing all Mikes\n";
name_idx.erase("Mike");
// alternative_remove_mikes(values);
std::cout << "\nAFTER: Ordered by number:\n";
for(auto& e: values.get<by_number>())
std::cout << e << "\n";
std::cout << "\nAFTER: O(1) lookup by name:\n";
for(auto& e : boost::make_iterator_range(name_idx.equal_range("Mike")))
std::cout << e << '\n';
values.clear();
std::cout << "Done\n----------------------------\n";
}
如果您希望删除的代码与您拥有的代码相似（这不是最优的，但是嘿，以防万一）：
void alternative_remove_mikes(Table& values) {
// this uses the same `remove_if` approach together with the `rearrange()` feature of `random_access` index
std::vector<boost::reference_wrapper<MyClass const> > refs(values.begin(), values.end());
// remove_if is not good enough since it will leave the removed end unspecified
auto it = std::partition(refs.begin(), refs.end(), [](MyClass const& mc) { return "Mike" != mc.name; });
std::cout << "Removing " << std::distance(it, refs.end()) << " items:\n";
values.rearrange(refs.begin());
auto newend = values.begin() + std::distance(refs.begin(), it);
for (auto& e : boost::make_iterator_range(newend, values.end()))
std::cout << " -- removing " << e << "\n";
values.erase(newend, values.end());
}
输出：
BEFORE: Ordered by number:
John 0
Mike 0
John 5
John 10
John 15
Dagobart 25
Mike 25
Mike 25
Dagobart 26
Dagobart 27
Mike 27
BEFORE: O(1) lookup by name:
Mike 27
Mike 25
Mike 25
Mike 0
removing all Mikes
AFTER: Ordered by number:
John 0
John 5
John 10
John 15
Dagobart 25
Dagobart 26
Dagobart 27
AFTER: O(1) lookup by name:
Done
----------------------------
下面的 MyClass 表示我需要能够以两种方式快速搜索的数据结构。所以说我将MyClass存储在std::vector中，这样可以快速删除和连续插入其中的相似名称。但是，我还需要能够根据 anInt 对 MyClass 的内容进行排序。这就是侵入式容器（或 Multimap）对 [很可能] 未排序 std::vector 的内容进行排序的地方。两个容器对相同的基础项目执行两种截然不同的职责。此外，如果我从 std::vector 中删除项目，它们也会自动从侵入容器中消失。
有点想法
#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;
}
您需要使用不同的索引进行快速查找。这让我想到了 Boost MultiIndex。
下一个：
So say I store the MyClass in and std::vector so that similar names in it can be quickly deleted and inserted continuously
结合
Also, if I deleted the items from the std::vector they would also automatically disappear
明确表示您无论如何都无法逃避保持所有索引最新的成本。在这种情况下，Boost Multi Index 和它得到的一样好。
这是一个示例：
#include <iostream>
#include <vector>
#include <boost/tuple/tuple_comparison.hpp>
#include <boost/range/iterator_range.hpp>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/random_access_index.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/ordered_index.hpp>
namespace bmi = boost::multi_index;
struct MyClass
{
std::string name;
int anInt1;
MyClass(std::string name, int i) : name(name), anInt1(i) {}
//bool operator==(MyClass const& o) const { return boost::tie(name, anInt1) == boost::tie(o.name, o.anInt1); }
//bool operator< (MyClass const& o) const { return boost::tie(name, anInt1) < boost::tie(o.name, o.anInt1); }
friend std::ostream& operator << (std::ostream& out, const MyClass& ac) {
return out << ac.name << " " << ac.anInt1;
}
};
using Table = bmi::multi_index_container<MyClass,
bmi::indexed_by<
bmi::random_access<bmi::tag<struct as_vector> >,
bmi::ordered_non_unique<bmi::tag<struct by_number>,
bmi::member<MyClass, int, &MyClass::anInt1>
>,
bmi::hashed_non_unique<bmi::tag<struct by_name>,
bmi::member<MyClass, std::string, &MyClass::name>
>
>
>;
void alternative_remove_mikes(Table& values);
int main()
{
Table values {
{ "John", 0 },
{ "Mike", 0 },
{ "Dagobart", 25 },
{ "John", 5 },
{ "Mike", 25 },
{ "Dagobart", 26 },
{ "John", 10 },
{ "Mike", 25 },
{ "Dagobart", 27 },
{ "John", 15 },
{ "Mike", 27 },
};
auto& name_idx = values.get<by_name>();
std::cout << "\nBEFORE: Ordered by number:\n";
for(auto& e: values.get<by_number>())
std::cout << e << "\n";
std::cout << "\nBEFORE: O(1) lookup by name:\n";
for(auto& e : boost::make_iterator_range(name_idx.equal_range("Mike")))
std::cout << e << '\n';
std::cout << "removing all Mikes\n";
name_idx.erase("Mike");
// alternative_remove_mikes(values);
std::cout << "\nAFTER: Ordered by number:\n";
for(auto& e: values.get<by_number>())
std::cout << e << "\n";
std::cout << "\nAFTER: O(1) lookup by name:\n";
for(auto& e : boost::make_iterator_range(name_idx.equal_range("Mike")))
std::cout << e << '\n';
values.clear();
std::cout << "Done\n----------------------------\n";
}
如果您希望删除的代码与您拥有的代码相似（这不是最优的，但是嘿，以防万一）：
void alternative_remove_mikes(Table& values) {
// this uses the same `remove_if` approach together with the `rearrange()` feature of `random_access` index
std::vector<boost::reference_wrapper<MyClass const> > refs(values.begin(), values.end());
// remove_if is not good enough since it will leave the removed end unspecified
auto it = std::partition(refs.begin(), refs.end(), [](MyClass const& mc) { return "Mike" != mc.name; });
std::cout << "Removing " << std::distance(it, refs.end()) << " items:\n";
values.rearrange(refs.begin());
auto newend = values.begin() + std::distance(refs.begin(), it);
for (auto& e : boost::make_iterator_range(newend, values.end()))
std::cout << " -- removing " << e << "\n";
values.erase(newend, values.end());
}
输出：
BEFORE: Ordered by number:
John 0
Mike 0
John 5
John 10
John 15
Dagobart 25
Mike 25
Mike 25
Dagobart 26
Dagobart 27
Mike 27
BEFORE: O(1) lookup by name:
Mike 27
Mike 25
Mike 25
Mike 0
removing all Mikes
AFTER: Ordered by number:
John 0
John 5
John 10
John 15
Dagobart 25
Dagobart 26
Dagobart 27
AFTER: O(1) lookup by name:
Done
----------------------------