Why can't `boost::multi_index replace` be used for pointer types?

Question

Short answer: User modify instead, details in the accepted answer and also this answer

I'm attempting to use a boost::multi_index_container holding a pointer type. It appears to me the replace function is broken, and am wondering what I am doing wrong.

The following code demonstrates two cases: first a container holding a copy of the data (which works correctly) and secondly a container holding a pointer to the data (which fails).

using namespace boost::multi_index;
using boost::multi_index_container;

struct Data
{
    int key1;
    int key2;
};

using DataContainer =
    multi_index_container<
        Data,
        indexed_by<
            hashed_unique<member<Data, int, &Data::key1>>,
            hashed_unique<member<Data, int, &Data::key2>>>>;

using DataPtrContainer = 
    multi_index_container<
        Data*,
        indexed_by<
            hashed_unique<member<Data, int, &Data::key1>>,
            hashed_unique<member<Data, int, &Data::key2>>>>;

TEST(DummyTest, Test1)
{
    Data data{1,2};
    DataContainer dataContainer;
    dataContainer.insert(data);

    EXPECT_EQ(1, dataContainer.get<0>().find(1)->key1);
    EXPECT_EQ(2, dataContainer.get<0>().find(1)->key2);

    auto iter = dataContainer.get<0>().find(1);
    Data d = *iter;
    d.key2 = 5;
    dataContainer.replace(iter, d);

    EXPECT_EQ(1, dataContainer.get<1>().find(5)->key1);
    EXPECT_EQ(5, dataContainer.get<1>().find(5)->key2);

}

TEST(DummyTest, Test2)
{
    Data* data = new Data{1,2};
    DataPtrContainer dataContainer;
    dataContainer.insert(data);

    EXPECT_EQ(1, (*dataContainer.get<0>().find(1))->key1);
    EXPECT_EQ(2, (*dataContainer.get<0>().find(1))->key2);

    auto iter = dataContainer.get<0>().find(1);
    Data* d = *iter;
    d->key2 = 5;
    dataContainer.replace(iter, d);

    EXPECT_EQ(1, (*dataContainer.get<1>().find(5))->key1);  // fail as the iterator not dereferencable
    EXPECT_EQ(5, (*dataContainer.get<1>().find(5))->key2); // fail as the iterator not dereferencable

}

Answer 1

OK, this is not a bug in Boost.MultiIndex, but a subtle contract violation in your code. The pointerless version:

auto iter = dataContainer.get<0>().find(1);
Data d = *iter;
d.key2 = 5;
dataContainer.replace(iter, d);

is taking a copy of the contained value into d, modifying it and then using it for replacement: so far so good. But the pointer version is breaking invariants along the way:

auto iter = dataContainer.get<0>().find(1);
Data* d = *iter;
d->key2 = 5;  // #1: invariant breach here
dataContainer.replace(iter, d); // #2: unexpected behavior ensues

In #1, you're modifying an internal key of dataContainer without its consent or knowledge: once you've done that, the touched element is incorrectly indexed. This is analogous to casting constness away in the pointerless version:

auto iter = dataContainer.get<0>().find(1);
const Data& d = *iter;
const_cast<Data&>(d).key2 = 5;

So, when #2 is executed, datacontainer, which does not suspect you've changed its keys, simply verifies that your proposed replacement d is equivalent to what it already has, and does nothing (no reindexing then).

Answer 2

It appears that the same effect can by achieved using the modify function (shown below). This is a work-around rather than an answer, and I'll accept any answer that can achieve the same result using replace.

TEST(DummyTest, Test2)
{
    Data* data = new Data{1,2};
    DataPtrContainer dataContainer;
    dataContainer.insert(data);

    EXPECT_EQ(1, (*dataContainer.get<0>().find(1))->key1);
    EXPECT_EQ(2, (*dataContainer.get<0>().find(1))->key2);

    auto iter = dataContainer.get<0>().find(1);
    //Data* d = *iter;
    //d->key2 = 5;
    //dataContainer.replace(iter, d);
    dataContainer.modify(iter, [](Data* data){ data->key2 = 5; });

    EXPECT_EQ(1, (*dataContainer.get<1>().find(5))->key1);
    EXPECT_EQ(5, (*dataContainer.get<1>().find(5))->key2);

}

Answer 3

replace () will work with ordered_unique.

class FooBar final
{
  public:
    FooBar (uint64_t id, std::string_view name)
      : id_ {id},
        name_ {name}
    {
    }

    uint64_t id () const noexcept { return id_; }

    const std::string & name () const noexcept { return name_; }

    void setName (std::string_view name) { name_ = name; }

  private:
    uint64_t id_;
    std::string name_;
};

    struct FooBarId {};
    struct FooBarName {};

    using FooBars = boost::multi_index::multi_index_container <
        std::shared_ptr <FooBar>,
        boost::multi_index::indexed_by <
            boost::multi_index::hashed_unique <
                boost::multi_index::tag <FooBarId>,
                boost::multi_index::const_mem_fun <
                    FooBar,
                    uint64_t,
                    & FooBar::id
                >
            >,
            boost::multi_index::ordered_unique <
                boost::multi_index::tag <FooBarName>,
                boost::multi_index::const_mem_fun <
                    FooBar,
                    const std::string &,
                    & FooBar::name
                >
            >
        >
    >;

    FooBars fooBars;

    auto fooBar1 = std::make_shared <FooBar> (1, "Test1");
    auto fooBar2 = std::make_shared <FooBar> (2, "Test2");
    auto fooBar3 = std::make_shared <FooBar> (3, "Test3");

    fooBars.emplace (fooBar1);
    fooBars.emplace (fooBar2);
    fooBars.emplace (fooBar3);

    auto it1 = fooBars.get <FooBarName> ().find ("Test2");
    assert (it1 != fooBars.get <FooBarName> ().end ());
    assert ((* it1)->id () == fooBar2->id ());

    fooBar2->setName ("Test4");
    fooBars.get <FooBarName> ().replace (it1, fooBar2);

    assert (fooBars.get <FooBarName> ().find ("Test2") == fooBars.get <FooBarName> ().end ());
    assert (fooBars.get <FooBarName> ().find ("Test4") != fooBars.get <FooBarName> ().end ());