c++ - *同时从向量中插入和删除元素*
问题描述
目标
考虑一个排序的 std::vector x
。我们想从这个向量中删除向量所指示位置的所有元素positionsToErase
。我们还想valuesToInsert
在位置插入向量的值positionsToInsert
。
这些删除和插入必须同时发生,因为如果我们先擦除,那么它将使我们想要插入值的位置无效(反之亦然)。我认为这将通过以下示例说明
例子
函数定义示例
template<typename T>
void insertEraseAtPositions(
std::vector<T>& x, // vector to modify. Is sorted and must remain sorted
std::vector<T>& valuesToInsert, // is not sorted
std::vector<size_t>& positionsToInsert, // is not sorted. This could be figured out inside the function but I happen to already know the positions at which values must be inserted
std::vector<size_t>& positionsToErase // is not sorted
);
请注意,非是常量,可以就地进行修改。
参数示例
std::vector<int> x = {0, 10, 20, 21, 30, 50, 60, 70, 81, 90}; // vector to modify
std::vector<int> valuesToInsert = {40, 80, 100}; // Values to insert are '40', '80' and '100'
std::vector<size_t> positionsToErase = {3, 8}; // Erase elements '21' and '81'
std::vector<size_t> positionsToInsert = {5, 8, 10}; // Insert where are currently located the elements '50', '81' and past the current last element.
预期产出
x = {0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
重要笔记
性能非常重要,因此不可能一个一个地插入和删除(即使我们相应地逐步修改位置),因为它会涉及太多的副本(或移动)。
通常,x
大小为 1,000 到 100,000。positionsToInsert
( 和valuesToInsert
) 的大小为 1-20,positionsToErase
大小为 1-5。x
通常具有允许插入值而不重新分配的容量。因此,我期望(但可能是错误的)就地修改会更快。
如果您愿意,我还可以提供迭代器而不是索引(std::vector<std::vector<T>::iterator>
而不是std::vector<size_t>
) 。positionsToErase
positionsToInsert
目前的工作
我写了一个代码来插入位置,但我也没有包括擦除的可能性。这是代码以防万一。
// Return indices representing the order of elements
template <typename T>
std::vector<uint32_t> sort_indices(const std::vector<T> &v) {
// initialize original index locations
std::vector<uint32_t> idx(v.size());
std::iota(idx.begin(), idx.end(), 0);
// sort indexes based on comparing values in v
std::sort(idx.begin(), idx.end(),
[&v](uint32_t i1, uint32_t i2) {return v[i1] < v[i2];});
return idx;
}
template <typename T>
void reorder(std::vector<T>& v, std::vector<uint32_t>& order)
{
auto v2 = v;
for (uint32_t i = 0 ; i < v.size() ; i++)
{
v[i] = v2[order[i]];
}
}
//// Insert multiple elements at specified positions into vector
template<typename T>
void insertAtPositions(std::vector<T>& x, std::vector<T>& values, std::vector<size_t>& positions)
{
// assert values and positions are the same size
assert(values.size() == positions.size());
// Special case - values is empty
if (values.size() == 0) return;
// Special case - single value to insert
if (values.size() == 1)
{
x.insert(positions.front(), values.front());
return;
}
// sort the values and the positions where those values should be inserted
auto indices = sort_indices(positions);
reorder(positions, indices);
reorder(values, indices);
// Special case - x is empty
if (x.size() == 0)
{
x.swap(values);
return;
}
// Allocate memory to x
x.resize(x.size() + values.size());
// Move things to make room for insertions and insert
int pos_index = positions.size()-1;
for (size_t i = x.size()-1 ; pos_index >= 0 ; --i)
{
if (i == positions[pos_index] + pos_index)
{
// A new value should go at index i
x[i] = std::move(values[pos_index]);
--pos_index;
} else
{
// The value from index 'i-pos_index-1' must go to index 'i'
x[i] = std::move(x[i-pos_index-1]);
}
}
}
解决方案
就地修改它是不行的。
考虑到您必须在每个位置插入一些东西。您需要将每个项目复制到临时位置,然后将它们复制回来。
你可能会争辩说你可以从头开始,倒着做。但是如果我们有一些删除,我们还需要在那里存储一些元素,可能会重新将每个元素复制到一些临时存储中并返回。
我认为最快的方法是分配一个新数组,并使用原始数组作为临时存储来构建它。这样你就可以保证每个元素都被复制一次。
现在,根据使用的类型(如整数或指针),这可能比您可能编写的任何其他方法都要快得多。如果副本很昂贵,请考虑使用移动或指针。
如果您担心性能,您应该对代码进行基准测试并对其进行调整。没有数据就很难准确地争论性能。
推荐阅读
- ruby-on-rails - 访问液滴轨道内的当前用户 5
- python-3.x - 获取 ABCMeta 的所有已注册子类
- c# - 如何允许用户从列表框中复制项目并粘贴到 Windows 窗体之外
- reactjs - 使用 jest 进行多环境测试
- async-await - 从任务列表中捕获异常
- java - If Else - Else 在 Java Netbeans 中无法正常工作
- sql - 如何在 SQL Server 中选择最近 7 天的日期
- javascript - 如何使用 Javascript 访问另一个带有空括号(内部没有点)的对象中的对象?
- google-app-maker - Google App Maker - SuggestBox - 小部件的数据源未处于“加载”状态
- spring - 在响应标头中检索令牌时出现问题 - Angular 6 - 后端 Spring