Пытаюсь выучить boost::intrusive Q2

Question

Пытаюсь выучить boost::intrusive Q2

Если я раскомментирую эти

//BaseList   baselist; 
//MemberList memberlist;

за пределами цикла и закомментируйте те, которые внутри цикла, он выходит из строя. Мне нужно иметь возможность иметь базовый список (и список участников) вне любого цикла. Как это достигается?

редактировать

Фактическая проблема, которую я пытаюсь решить в простейшей форме, заключается в следующем.
Я хочу, чтобы у меня был стандартный вектор MyClassНазовите это AllThingsBunchedTo Вместе. Я также хочу иметь std::vector BaseListНазовите это AllThingsSpreadOut.
Так
AllThingsBunchedTo Вместе может содержать (только anInt1 часть ради компактности): 1,2,1,10,2,3,4,4,5,9,10,10,
AllThingsSpreadOut может содержать (ноль пока не используется) в [1] 1,1 в [2] 2,2 в 3] 3 в [4] 4,4 в 5] 5 в 9] 9 в 10] 10,10,10,
Обратите внимание, что сами числа не хранятся в BaseList, но, например, MyClass(1, "Джон").
В [1] это может быть "Майк", "Джон", в [2] это может быть "Майк", "Дагобарт", в [3] "Джон"... в [10] "Джон", "Майк" " Дагобарт "и т.д., чтобы не было дубликатов ни в одном из BaseList на AllThingsSpreadOut[i], так как каждый MyClass в каждом BaseList хэши к другому значению (anInt1 + Name).
По сути, anInt1 говорит где MyClass живет в AllThingsSpreadOut, но 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";
    }
}

0

c++ c++11 boost intrusive-containers

Источник

user817659 11 ноя '14 в 05:02

2 ответа

Решение

Вот сообщение об ошибке, которое вы пропустили:

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

Из этого мы можем понять, что элемент вставляется дважды. Это не относится к навязчивым контейнерам в целом.

Когда у вас есть списки внутри цикла, они уничтожаются и воссоздаются каждый раз. Но когда они снаружи, вы никогда не очищаете их, и вы также никогда не очищаете valuesИтак, эта последовательность происходит:

Добавить 11 элементов к values,
Добавить все values в списки.
Добавить 11 элементов к values; у него все еще есть предыдущие 11, так что теперь 22 элемента.
Добавить все values в списки. Сбой первого, потому что он уже есть в списке.

Одним из решений является добавление values.clear() на вершине while(!done) петля.

0

Источник

user4323 11 ноя '14 в 07:14

Другие вопросы по тегам c++ c++11 boost intrusive-containers

user85371 11 ноя '14 в 22:59 2014-11-11 22:59 · Accepted Answer · 2014-11-11 22:59

Я видел это поздно, но в любом случае, здесь идет:

То, что вы описываете, точно соответствует реализации навязчивой хеш-таблицы MyClass элементы, где

anInt1 это хеш (идентификатор сегмента) для элемента
списки сегментов реализованы как связанные списки
равенство определяется как равенство (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";

если вы действительно хотели непрерывного хранения, я могу только предположить, что вы хотели это для производительности

Вы не хотите использовать указатели вместо объектов, так как это просто сводит на нет преимущества макета памяти ("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";
}