c++ - 两个 [或多个] 具有相同底层数据但数据 View 不同的容器

Question

下面的 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;
}

Answer 1

您需要使用不同的索引进行快速查找。这让我想到了 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 尽善尽美。

这是一个示例:

Live On Coliru

#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
----------------------------