CODEWITHSUNDEEP
c++c++11stlc++14
Lukas Barth
Lukas Barth

Reputation: 3048

C++: Replace an element in a std::unordered_set to which we have an iterator

I have a std::unordered_set of pointers to some objects. The set has custom hash and equivalence functions, s.t. objects can be equal regarding the set even if the objects are not equal in the sense of "all members are equal".

Now I want to insert a new object. If an equivalent object already exists in the set, I want the old object to be replaced if and only if some condition on the "other" members (i.e., which are not part of the hash / equality check) of the objects is true.

If I decide to replace the object, I wonder how to do this most efficiently. I feel like the whole process should be doable with a single hashmap lookup. My best approach currently is this:

Below is a complete example demonstrating what I'm trying to do. It's a bit lengthy because of the custom hash / equality structs, sorry.

#include <unordered_set>

struct Foo {
    int set_value;
    int other_value;
};

struct SetEqual {
    bool operator()(Foo * lhs, Foo * rhs) const noexcept
    {
        return lhs->set_value == rhs->set_value;
    }
};
struct SetHasher {
    size_t operator()(Foo * foo) const noexcept
    {
        std::hash<int> hasher;
        return hasher(foo->set_value);
    }
};

std::unordered_set<Foo *, SetHasher, SetEqual> my_set;

void 
replace_if_lower(Foo * foo) 
{
    auto insertion_result = my_set.insert(foo);
    bool was_inserted = insertion_result.second;
    auto insertion_it = insertion_result.first;

    if (!was_inserted) {
        // Replace iff the other value is lower
        if (foo->other_value < (*insertion_it)->other_value) {
            // This is what I would like to do:
            // *insertion_it = foo;

            // This is the best I could figure out:
            my_set.erase(insertion_it);
            my_set.insert(foo); 
        }
    }
}

Does anybody see how to do this with just one set lookup? I would be fine with useing C++ 11 or 14 features. Thanks!

Upvotes: 5

Views: 2143

Answers (2)

cantordust
cantordust

Reputation: 1612

Would something like this work for you? Might not be the best design, you can optimise it (maybe have a wrapper class MySet) with a member replace_if_lower. The idea is to use a shared_ptr to add a bit of safety to an otherwise potentially unsafe operation.

#include <iostream>
#include <unordered_set>
#include <memory>

struct Foo
{
    int set_value;
    int other_value;
    Foo(int _s, int _o)
        :
          set_value(_s),
          other_value(_o)
    {}

    friend std::ostream& operator << (std::ostream& _s, const Foo& _f)
    {
        return _s << _f.set_value << ", "  << _f.other_value;
    }
};

using FooPtr = std::shared_ptr<Foo>;

struct SetEqual {
    bool operator()(const FooPtr& lhs, const FooPtr& rhs) const noexcept
    {
        return lhs->set_value == rhs->set_value;
    }
};
struct SetHasher {
    size_t operator()(const FooPtr& foo) const noexcept
    {
        std::hash<int> hasher;
        return hasher(foo->set_value);
    }
};

std::unordered_set<FooPtr, SetHasher, SetEqual> my_set;

void replace_if_lower(FooPtr& foo)
{
    auto insertion_result = my_set.insert(foo);
    bool was_inserted = insertion_result.second;
    auto insertion_it = insertion_result.first;

    if (!was_inserted)
    {
        // Replace iff the other value is lower
        if (foo->other_value < (*insertion_it)->other_value)
        {
            // This is what I would like to do:
            // *insertion_it = foo;

            // Swap the pointer contents:
            const_cast<FooPtr&>(*insertion_it).swap(foo);
        }
    }
}

int main()
{
    my_set.emplace(std::make_shared<Foo>(1,1));
    my_set.emplace(std::make_shared<Foo>(2,1));
    my_set.emplace(std::make_shared<Foo>(3,1));

    std::cout << "Foo set:\n";
    for (const auto& f : my_set)
    {
        std::cout << f << ": " << *f << "\n";
    }
    std::cout << "\n";

    FooPtr f30(std::make_shared<Foo>(3,0));

    replace_if_lower(f30);

    std::cout << "Foo set:\n";
    for (const auto& f : my_set)
    {
        std::cout << f << ": " << *f << "\n";
    }
    std::cout << "\n";

    FooPtr f32(std::make_shared<Foo>(3,2));

    replace_if_lower(f32);

    std::cout << "Foo set:\n";
    for (const auto& f : my_set)
    {
        std::cout << f << ": " << *f << "\n";
    }
    std::cout << "\n";

    return 0;
}

This prints

Foo set:
0x563e834eec70: 3, 1
0x563e834eec90: 2, 1
0x563e834eec30: 1, 1

Foo set:
0x563e834efd30: 3, 0
0x563e834eec90: 2, 1
0x563e834eec30: 1, 1

Foo set:
0x563e834efd30: 3, 0
0x563e834eec90: 2, 1
0x563e834eec30: 1, 1

Upvotes: 1

Caleth
Caleth

Reputation: 62626

No, this is not possible, by design.

All access to the elements contained within the set are const qualified, so that the set can maintain the necessary structure to be able to search in O(1) time. If you could modify the elements, they could be in the wrong place.

You can insert the contents of my_set (or in C++17 merge the set directly) into a new (single element) set then swap them, however this is an O(N) operation.

decltype(my_set) temp{ { foo } }; 
temp.insert(my_set.begin(), my_set.end());
std::swap(my_set, temp);
// my_set now has foo, temp has replaced element or is empty

Alternatively, if you only care about the value of foo->other_value being placed into the set, note that you can modify an object through a const pointer.

auto ptr = *my_set.insert(foo).first;
ptr->other_value = foo->other_value;
assert(ptr->set_value == foo->set_value);
// ptr is "Foo * const", not "Foo const *"

Upvotes: 4

Related Questions