0

我有一个相当简单/明显的迭代器解决方案，但我想我会点击 SO 看看是否有人想出了一个偶尔出现在答案中的惊人食谱:)

情况如下：

  • 多个已知和可用大小的 int 向量，当前隐藏在 a 中vector<vector<int>>，由于 API 请求和仅在运行时才知道的 vect 数量的混合，无法解决此问题
  • 这些可以有任意数量，但实际上总是在少数到十几个之间（矢量）
  • 顺序并不重要，因此排序和排序技巧和优化是公平的游戏（不是在这个阶段我发现有任何需要它，但考虑到下面的额外问题，它们可能会突然出现）
  • 那时的向量是一次性的，所以移动技巧也是公平的游戏
  • 大小通常很小，但在罕见但并非非法的边缘情况下，可能有超过几百万个整数，其中一些甚至全部
  • 内存问题不大，通常在任何给定时间都会有几 GB 的连续内存可用，这不是关键系统
  • 性能并不重要，它是飞行前的检查，但由于它仍然面向用户，它看起来不像应用程序挂起。少数几秒钟的边缘案例类型的场景。

由于我目前在两个具有严格二进制要求的 API 之间绑定，这是 GCC 4.1.x 的限制，因此绝对和令人抓狂地缺乏任何可用的 C++0x 和 Boost 1.44。

目前这些vects都包含唯一的索引，但将来产生一个删除重复项的单个过滤数组（未来的使用可能涉及具有重叠索引的提要）也可能成为一项要求，因此如果处理好，则可以加分。

仍然欢迎 C++11 解决方案或任何相关内容。我不是在找人来做我的作业，反正我有一个笨重但工作的东西，我比什么都更追求启蒙和食谱灵感。

提前致谢

4

1 回答 1

1

不是 100% 清楚你想要什么，但充分利用你所说的，我会做这样的事情：

std::vector<std::vector<int>> v; // input, assume it's already filled
std::size_t size = 0;
for (std::vector<std::vector<int>>::const_iterator i = v.begin(); i != v.end(); ++i)
{
    size += i->size();
}

boost::scoped_array<int> array;
if (size != 0)
{
    array.reset(new int[size]);
    std::size_t offset = 0;
    for (std::vector<std::vector<int>>::const_iterator i = v.begin(); i != v.end(); ++i)
    {
        std::copy_n(&(*i)[0], i->size(), array + offset);
        offset += i->size();
    }
}

// ...use array...

如果你想变得array独一无二，你可以这样做：

std::sort(array.get(), array.get() + size);
std::size_t newSize = std::unique(array.get(), array.get() + size) - array.get();
// Now array is unique, assuming you only use elements [0, newSize)

可能有更有效的方法来排序和使其唯一（也许对每个子向量进行排序，然后在将它们复制到新数组时执行合并排序样式操作（并且根本不复制现有项目）），但我的目标是在我的回答中简单+正确。一旦你有一个已知的正确解决方案，优化可以稍后进行。

于 2013-09-07T00:09:42.227 回答