获取随机元素并将其删除 [英] Get random element and remove it

问题描述

问题：我需要为容器获取一个随机元素，并将其从该容器中删除。容器不需要排序。 我不关心订单。

• 向量可以让我在 O中的随机元素（1），但只能在中删除​​O（N）


• 列出删除元素 O（1）但只能在 O（N）

中获取随机元素

所以我想出了一个想法，制作一个自定义向量，允许你通过其索引删除任何元素 O（1）+ 复杂性。
想法是交换最后一个元素和要删除的元素，然后交换 pop_back（）。
如果您需要删除最后一个元素 - 只需 pop_back（）。
向量的顺序将不一样，但您可以获得快速的删除方法。

由于我可以理解deque具有较慢的索引访问权限和更好的删除复杂度，所以我的解决方案，但不是100％肯定。

$ b $我很好奇，在 O（1）或 O（logN）中有随机访问和元素删除的数据结构code>按索引或mb按值？

解决方案

你有解决方案，似乎完全正常。用C ++编写它的惯用方式不是创建另一个类（而请 不要从 std :: vector 继承，而只是写一个函数：

 模板< typename T> 
 void remove_at（std :: vector< T>& v，typename std :: vector< T> :: size_type n）
 {
 std :: swap（v [n] v.back（））; 
 v.pop_back（）; 
} 
  

用法：

  remove_at（v，42）; 
  

这提供了与 std :: swap< T> / code>。

现在，如果要返回对象，并且您可以访问C ++ 11编译器，可以按照以下方式进行操作。困难的部分是在所有情况下提供基本的异常保证：

 模板< typename T> 
 T remove_at（std :: vector& T& v，typename std :: vector< T> :: size_type n）
 {
 T ans = std :: move_if_noexcept（v [ n]）; 
 v [n] = std :: move_if_noexcept（v.back（））; 
 v.pop_back（）; 
 return ans; 
} 
  

的确，您不希望向量保持在无效状态如果在移动操作期间抛出异常。

Problem: I need to get a random element for a container and also delete it from that container. Container does not need to be sorted. I dont care about the order.

• Vector can get me random element in O(1) but delete it only in O(N)
• List deletes element in O(1) but can only get random element in O(N)

So I came up with an idea of making a custom vector that allow you to remove any element by its index with O(1)+ complexity. The idea is to swap the last element and an element you want to remove and then pop_back(). If you need to remove the last elemtent - just pop_back(). The order of the vector will not be the same but you get a fast remove method.

As i can understand deque have slower access by index and worse removal complexity then my solution but im not 100% sure.

I'm curious are there data structures that have random access and element removal in O(1) or O(logN) by index or mb by value ?

解决方案

You have the solution, and it seems perfectly fine. The idiomatic way to write it in C++ is not to create another class (and please don't inherit from std::vector), but just to write a function:

template <typename T>
void remove_at(std::vector<T>& v, typename std::vector<T>::size_type n)
{
    std::swap(v[n], v.back());
    v.pop_back();
}

Usage:

remove_at(v, 42);

This offers the same exception guarantee as std::swap<T>.

Now if you want to return the object, and you have access to a C++11 compiler, you can do it the following way. The difficult part is to provide the basic exception guarantee in all cases:

template <typename T>
T remove_at(std::vector<T>&v, typename std::vector<T>::size_type n)
{
    T ans = std::move_if_noexcept(v[n]);
    v[n] = std::move_if_noexcept(v.back());
    v.pop_back();
    return ans;
}

Indeed, you don't want the vector to be left in an invalid state if an exception is thrown during a move operation.

这篇关于获取随机元素并将其删除的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！