4

Using std::set in C++, the only way I can find to remove an item from a set is to use the erase method. This deletes the item in question, which I don't want to happen. The only way I can think of to remove an item from a set without deleting it would be to create a new set and add all the items of the old set to it iteratively, making sure to not add the item that needs to be removed from the set, then deleting the old set.

Is there a cleaner way to do this?

skrooms
  • 143
  • 2
  • 7
  • 6
    Confused because: both method (1) and method (2) delete the item in question. – Richard Critten Apr 10 '19 at 22:18
  • Say you do create a new set. How would you move any existing items into it? If you mean literally using move semantics, that would meanh deleting the old items which is what you said you didn't want to do. If not move semantics, in what sense would it be moving at all? – David Schwartz Apr 10 '19 at 22:22
  • 1
    It would help a lot to understand precisely why you don't want the original object to be deleted. It makes a huge difference if it's because, for example, you have references to it stashed somewhere versus if it's because it's expensive to construct. – David Schwartz Apr 10 '19 at 22:30
  • It is not clear what you mean. You could copy the item to another location (like a vector) then delete it from the set. You are still deleting the original value but you have a copy of that value in another container. Is this what you mean? – Martin York Apr 10 '19 at 22:36
  • Possible duplicate of https://stackoverflow.com/questions/45030932/extracting-move-only-type-from-stdset – Galik Apr 10 '19 at 23:07
  • https://tio.run/##zVLBTsMwDL3vK8yQupZtiPNaeuQHdmQIpalTReqSKklhCPrtw0nL1iIEFw6LqjS2n/OeY/OmWVecH6@l4nVbImRSW2eQ7fPZ2WfRjU3RKu6kVqzOjwRuuYMHreF9BrTcW4MlCrCu3GwMCjSoOD6/GtY0aDIC5nBypyFFGImq7DMGdohAE5w5bSDLIJ7GtF0B18r2vJFIBm6/DLrWKNDW580p/jj3p0gE@2neU3ZhH8TXaO3ohkLr@sQeJxCPqNiEuEgG65w8khAxIN4iPcV60i6d0Td70bIEh5Qcf8kPRdJb@0cavd0Kgu1V5rDtr/P04nys0vMFXLcu1Co@QuWh8MVOLX7CVD2m@g2zXq93ani37a1UFo2LRfLNUQ0O1joNB7inSIGVVPHgF9TJWCoHkmJ3KUGuPIYaTwhYLg8r2uS4kxMVMij8WPjfzWEqt/tTNPXS4kniZaoTF6nuP0aKxv3o1e@ZVGHaw9x76d3xEw – jxh Apr 11 '19 at 00:42

2 Answers2

5

You can't remove an item from a set without deleting it. Sets own their members. If the member is removed from the set, it doesn't exist anymore. If you want to be able to remove something without deleting it, don't add it to a set.

Imagine if you have int x[5]; x[2]=2;. How can you get x[2] out of the array? What would that even mean? You can, of course, construct a new integer with the same value, int j = x[2];. But that's a new object (with the same value) that is not extending the life of the existing object.

Depending on what your outer problem is, there might be a solution. For example, you could add a std::unique_ptr to an object into a set and then you can destroy that std::unique_ptr without destroying the object it points to be constructing a new std::unique_ptr to the same underlying object.

David Schwartz
  • 179,497
  • 17
  • 214
  • 278
  • 1
    Except that you can - you can use extract + std::move to transfer ownership of an element – Alecto Irene Perez Apr 10 '19 at 22:22
  • 1
    @JorgePerez That doesn't transfer ownership of an element. That deletes an existing element while creating a new element with the same value as the existing one. (Unless you want to put the old element into the same type of container.) – David Schwartz Apr 10 '19 at 22:23
  • If the existing element doesn't own any resources, then it doesn't matter that it gets copied. If it does own resources, then this will transfer ownership of the resources. – Alecto Irene Perez Apr 10 '19 at 22:25
  • 1
    @JorgePerez Copying an element that doesn't own any resources and destroying the original invalidates all pointers and references to it. So you can't really say it "doesn't matter". – David Schwartz Apr 10 '19 at 22:26
  • This is answer outlines the only sensible option. – J.R. Apr 10 '19 at 22:48
1

Moving an object out of a set

You can use extract to remove the corresponding node from the set. This gives you a handle to the node. Once you have the handle, you can move the item out of the handle.

template<class T>
T find_and_remove(std::set<T>& s, T const& elem) {
    auto iterator = s.find(elem); 
    if(iterator == s.end() {
        throw std::invalid_argument("elem not in set"); 
    }
    // Remove element, return node handle
    auto node_handle = s.extract(iterator);
    return std::move(node_handle.value());
}

Alternatively, if you already have the iterator to the node, you can write it like this:

template<class T>
T remove_from_set(std::set<T>& s, std::set<T>::iterator it) {
    return std::move(s.extract(it).value());
}

Moving the value transfers ownership of any resources owned by the value. For example, if the set contains a string, the contents of the string won't be deleted, and any iterators to the string won't be invalidated.

The caveat of this is that if you had pointers or references to the object from when it was still in the set, these will be invalidated.

Extracting the object itself without a move and without invalidating any pointers or references to the object

This is the less common case, but if you had a reference or pointer to the object in the set, you may want to do this.

Again, we can use the extract function:

auto node_handle = s.extract(my_object);

Or:

auto node_handle = s.extract(my_iterator);

You can access the stored object with node_handle.value(), which returns a reference to the object. The object won't be deleted until the node_handle is deleted, and if you need to extend it's lifetime further, you can return the node_handle from a function without the object being deleted.

Alecto Irene Perez
  • 10,321
  • 23
  • 46
  • Your `remove_from_set` returns a new object with the same value as the original value and destroys the original -- exactly what the OP said they didn't want to do. – David Schwartz Apr 10 '19 at 22:25
  • If the original value supports move semantics, it doesn't matter that the original value gets destroyed. Any resources will be transferred over without being deleted. – Alecto Irene Perez Apr 10 '19 at 22:27
  • As I said in my response to your comment to my answer, that's just false. It can matter very much, for example if a pointer or reference to it has been stashed somewhere. We don't know why the OP doesn't want the original object to be deleted, but they've said that's what they want to avoid. – David Schwartz Apr 10 '19 at 22:27
  • Your last edit makes your answer dangerously wrong. What if, for example, the string uses a short string optimization and the iterator contains a pointer to a buffer inside the `std::string` object itself. – David Schwartz Apr 10 '19 at 22:29
  • I updated my answer clarifying and differentiating between "move from the set" and "remove without invalidating any existing pointers or references". Are you satisfied with the changes? – Alecto Irene Perez Apr 10 '19 at 22:33
  • The C++ standard containers create "outer objects" that hold the item for the container (has-a relationship). For example, the item belongs to an array managed by the vector, or the item belongs to a rb-tree node managed by the set. When removing the item from the container, you have to allow the "outer object" to become available to hold a different item. So minimally, a copy out to a different memory location is required to preserve the item. I think the OP wants the container to hold `std::reference_wrapper`. – jxh Apr 10 '19 at 22:34