我正在使用合并排序功能。我没有整理-我正在尝试完成我的合并部分。假设我正在学习C++,对指针有粗略的了解,并且不了解std::vector::iterator的所有规则(就此而言,也不是std::vector的)。
假定num是原始std::vector的大小,该值已从大小为“int ar [num]”的数组中复制(std::copy)值。假设farray的值为(0到(num / 2)),sarray的值为((num / 2)到num)。
int num = original.size();
std::vector<int> final(num);
for (std::vector<int>::iterator it = farray.begin(); it != farray.end(); ++it) {
for (std::vector<int>::iterator iter = sarray.begin(); iter != sarray.end(); ++iter) {
if (*it > *iter) final.push_back(*it);
else
final.push_back(*iter);
}
}
这段代码可以编译,而我最新的稳定版Bloodshed Dev-C++不会引发任何警告或错误。我不知道这是否有效,我仍然需要尝试找出final的所有值。我只想知道这是否是普遍现象,容易出错或只是样式不好。如果是的话,你会怎么做
最佳答案
这是有效的...但是for循环可能不是您想要的。当您使用两个for循环时,每次外部循环循环时,您的内部循环都会回到起始位置。因此,如果您的 vector 包含:
farray: 10 9 8 4 3
sarray: 7 6 4 3 1
然后,您的最终数组将包含以下内容:
10 10 10 10 10 9 9 9 9 9 8 8 8 8 8 7 6 4 4 4 7 6 4 3 3
因为您要测试每个组合,然后将较大的组合添加到最终列表中。更好的解决方案可能是记住每个列表的迭代器,并且只使用一个循环。与其遍历列表,不如遍历两个列表-如果sarray的数目更大,则增加sarray迭代器,并将其与旧的farray迭代器进行比较。当sarray和farray为空时,停止循环。
vector<int> fiter = farray.begin();
vector<int> siter = sarray.begin();
vector<int> final;
// Let's traverse both farray and sarray.
// We'll want to stop this loop once we've traversed both lists.
while (fiter != farray.end() && siter != sarray.end())
{
if (fiter == farray.end())
{
// we must have gone right through farray -
// so use the value from sarray, and go to the next one
final.push_back(*siter);
siter++;
}
else if (siter == sarray.end())
{
// we must have gone right through sarray -
// so use the value from farray, and go to the next one
final.push_back(*fiter);
fiter++;
}
else if (*siter > *fiter)
{
// siter is the bigger of the two - add it to the final list, and
// go to the next sarray entry
final.push_back(*siter);
siter++;
}
else // *fiter >= *siter
{
// fiter is the bigger of the two - add it to the final list, and
// go to the next farray entry
final.push_back(*fiter);
fiter++;
}
}
我还没有测试过-如果这是用于作业,那么请尝试了解自己所做的一切,自己去写,而不要复制粘贴。