代码之家 › 专栏 › 技术社区 › WilliamKF

如何将一个向量的后半部分移动到另一个向量中?

erase stdvector insert c++

WilliamKF · 技术社区 · 12 年前

我有一个向量,我想使用STL算法有效地将向量的后半部分分解为另一个向量。我认为有一种方法可以做到这一点,但希望有更高效、更简洁的答案,或者至少有一种使用stl算法的答案:

std::vector<Entry> &entries = someFunction();
int numEntries = entries.size();

// Assume numEntries is greater than or equal to 2.

std::vector<Entry> secondEntries;
std::vector<Entry>::iterator halfway = entries.begin() + numEntries / 2;
std::vector<Entry>::iterator endItr  = entries.end() 

// Copy the second half of the first vector in the second vector:
secondEntries.insert(secondEntries.end(), halfway, endItr);

// Remove the copied entries from the first vector:
entries.erase(halfway, endItr);

3 回复 | 直到 12 年前

GManNickG 12 年前

退一步来说,请记住,您使用的迭代器使用的是自己的算法,而不是容器。所以,如果你有这个:

void foo(const std::vector<Entry>& v) { /* ... */ }

现在你陷入了这种境地:

std::vector<Entry> entries = someFunction();

// have to split entries! make more containers? :(
foo(first_half(entries));
foo(second_half(entries));

请考虑使用迭代器:

// or a template, if it doesn't hurt
void foo(std::vector<Entry>::const_iterator first, 
         std::vector<Entry>::const_iterator second) { /* ... */ }

所以现在你指的是范围而不是容器:

std::vector<Entry> entries = someFunction();

// easy to split entries! :)
auto middle = entries.begin() + entries.size() / 2;
foo(entries.begin(), middle);
foo(middle + 1, entries.end());

这限制了不必要的容器和分配的数量。

有了这些,在C++11中您可以做到这一点(其余部分相同):

// *Move* the second half of the first vector in the second vector:           
secondEntries.insert(secondEntries.end(),
                        std::make_move_iterator(halfway),
                        std::make_move_iterator(endItr));

如果 Entry 有一个move构造函数 move_iterator 适配器将确保在插入过程中使用它(如果不进行正常复制)。在C++03中,您所拥有的可能是最好的。

villintehaspam 12 年前

std::move 如果您可以访问c++11编译器和可移动对象,则可以做得更好。

请注意,您仍然需要从第一个向量中删除它们。

Kirill Kobelev 12 年前

还有其他几种方法可以执行此任务,例如使用复制算法和插入迭代器。

但是在算法上,由于向量容器的性质,这些动作的复杂性将始终为O(n)。Vector不是一个允许在O(1)(恒定)时间内将大块数据从一个容器移动到另一个容器的列表。根据特定的STL实现,一种方式可能比另一种方式好10-20%,但不太可能超过这个。

若容器的数据类型允许移动语义,并且您有这些可用的语言功能,这肯定会有所帮助。但这更多的是关于处理容器中的数据对象,而不是容器本身。