logo标签列表

将对象移动到C++向量的前面

c++vector
7

我有一个包含string词和一些int num的vector<Suggestions> finalSuggestions。

如果这个词满足某个条件，我想将该对象移动到向量的前面，并从原来的位置中删除它。

我可以使用vector::insert将其插入到列表的开头。

for (auto &x: finalSuggestions) {
    if ( double((x.num)/(topword.num)) < 50)
    {
        finalSuggestions.insert(finalSuggestions.begin(),x);
        break;
    }
}

但是我不知道如何将其从列表中移除。

例如，对于任意向量{1,2,3,4,50,6,7,8,9}，如果50符合条件，则将其移到列表前面并从原位置删除，返回{50,1,2,3,4,6,7,8,9}。上面的代码返回{50,1,2,3,4,50,6,7,8,9}

我正在研究vector::erase，但遇到了问题，耗时比预期长。

我想象一个简单的解决方案（但这显然行不通）

for (auto &x: finalSuggestions) {
    if ( double((x.num)/(topword.num)) < 50)
    {
        finalSuggestions.insert(finalSuggestions.begin(),x);
        finalSuggestions.erase(x);
        break;
    }
}

我研究了删除-移除惯用法（这是我的实现）：

 finalSuggestions.erase( remove( begin(finalSuggestions), end(finalSuggestions), x ), end(finalSuggestions) );

但是我遇到了一个错误，我不理解：
In instantiation of '_FIter std::remove(_FIter, _FIter, const _Tp&) [with _FIter = __gnu_cxx::__normal_iterator<Suggestion*, std::vector<Suggestion> >; _Tp = Suggestion]':|
如果 erase 操作所需的时间比预期的长，你可能需要使用另一种数据结构，例如 list。 - Anton Savin
1
“比它应该花费的时间更长”是指我似乎找不到解决方案，而不是运行时变慢。对于歧义造成的困扰，我感到抱歉。 - SSOPLIF
6个回答
29

使用std::rotate。它比删除和重新插入要快得多。

例如：

for (auto it = finalSuggestions.begin(), lim = finalSuggestions.end();
     it != lim;
     ++it) {
  if (it->num < 50 * topword.num) {
    std::rotate(finalSuggestions.begin(), it, it + 1);
    break;
  }
}

更好的方法是，正如@JerryCoffin在评论中建议的那样，使用std::find_if来查找枢轴点：
auto pivot = std::find_if(finalSuggestions.begin(),
                          finalSuggestions.end(),
                          [&topword](const Suggestions& s) -> bool {
                            return s.num < 50 * topword.num;
                          });
if (pivot != finalSuggestions.end()) {
  std::rotate(finalSuggestions.begin(), pivot, pivot + 1);
}
我宁愿使用std::find_if来查找正确的位置，但我绝对同意建议使用std::rotate而不是插入/删除。 - Jerry Coffin
对我来说，这更像是：http://en.cppreference.com/w/cpp/algorithm/stable_partition - yachoor
@yachoor：partition将向量分成两部分。OP只想移动单个元素。如果意图是移动满足该谓词的所有元素，那么std::partition当然是正确的选择。 - rici
1
@j00hi：不，目标是将一个元素移动到开头，而不是向量的其余部分。 - rici
@rici 嗯，没错。这很有道理。谢谢！ - j00hi
显示剩余2条评论
11

vector::erase需要一个迭代器，因此无法使用基于范围的for循环。请改用简单的for循环。先删除一个元素，然后再插入它，因为insert会使迭代器失效:

for (auto it = finalSuggestions.begin(); it != finalSuggestions.end(); ++it) {
    if (some_condition(*it)) {
        auto x = *it; // or std::move(*it)
        finalSuggestions.erase(it);
        finalSuggestions.insert(finalSuggestions.begin(), x /* or std::move(x) */);
        break;
    }
}

使用std::move可以移动元素而不是复制它，这可能会节省一些循环时间。

如果( double( *(it.num)/(topword.num))<50) 抛出错误 "没有成员'num'". 对不起，我不太擅长迭代器。 - SSOPLIF
@fliposs if ( double((it->num)/(topword.num)) < 50) 如果（double((it->num)/(topword.num)) < 50）则 - Anton Savin
2
你的迭代器使得很难知道所讨论的元素的位置。你可能想尝试使用标准的 for 迭代器，它允许访问位置（被 std::vector::erase 使用）。
int len=finalSuggestions.size();
for (int i=0, ; i<len; ++i) {
    // Save a copy of the item
    auto item = finalSuggestions.at(i);
    if (double((item.num)/(topword.num)) < 50) {
        // Erase the item in the list
        finalSuggestions.erase(i);
        // Add the copy of the item back in at the front
        finalSuggestions.insert(finalSuggestions.begin(), item);
        break;
    }
}

... 或者使用一个 std::iterator ...
for (auto it = finalSuggestions.begin(); it != finalSuggestions.end(); ++it) {
    if (double((*it->num)/(topword.num)) < 50) {
        // Save a copy of the item
        auto item = *it;  
        // Erase the item in the list
        finalSuggestions.erase(it); 
        // Add the copy of the item back in at the front
        finalSuggestions.insert(finalSuggestions.begin(), item); 
        break;
    }
}

std::vector 对象使用连续的内存来存储元素，这意味着在修改容器时需要实际移动内存。如果您要移动元素，您可能需要考虑使用 std::list 或 std:deque。这些容器的定义几乎相同（即：可以互换使用），因此替换它们相当简单。

建议：

std::deque 旨在实现在容器的开头和结尾进行优化插入。从 cplusplus.com 网站中获取以下引用：

它们提供了类似于向量的功能，但是除了在序列的末尾之外，还可以高效地插入和删除元素。但是，与向量不同，双端队列不能保证将其所有元素存储在连续的存储位置中：...

1

它在功能上等同于Anton的答案，但我会使用std::find_if来获取指向所需元素的迭代器，而不是使用循环。

//add #include <algorithm> to your source file

auto result = std::find_if(finalSuggestions.begin(), finalSuggestions.end(), condition_func);
if(result != finalSuggestions.end())
{
    auto resultValue = *result;
    finalSuggestions.erase(result);
    finalSuggestions.insert(finalSuggestions.begin(), resultValue);
}

condition_func 应该是一个返回布尔值的函数，它需要带有一个与你的向量元素类型相匹配的参数（在本例中为 Suggestion）：

bool condition_func(Suggestion elementValue) { /*condition here*/ }

有关find_if的更多信息可在此处获取。

1

Anton的回答是正确的。但是如果您经常这样做，应考虑使用不同的数据结构。删除和插入都是O（N）操作，其中N是向量的大小。如果这是常见操作，则使用列表会更好。

是的，我同意。不过我只会在相对较小的向量长度（<100）上执行一次。 - SSOPLIF
在得出列表更好的结论之前，我会进行一些测试 - 大多数测试表明即使在看似最有利于它的情况下，列表也不是更好的选择。问题在于，尽管删除和插入的时间复杂度为O(1)，但查找的时间复杂度仍为O(N)，而且常数通常要高得多，因为它通常具有较差的引用局部性（导致缓存使用不佳）。 - Jerry Coffin
1
也许使用std::iter_swap可以解决您的问题。
#include <iostream> 
#include <algorithm>
#include <vector>
using namespace std;
int main () {
vector<int> myvector{};
for(int io{}; io<7; ++io) myvector.push_back(io+1);
for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
cout << ' ' << *it;
cout << '\n';
iter_swap(myvector.begin(),myvector.begin()+2);//exchange the third element with the first.
cout << "myvector contains:";
for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
std::cout << ' ' << *it;
 std::cout << '\n';
return 0;
}
如果您不需要算法稳定，那么这确实是最有效的方法。 - Trass3r
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接