1

除了使用以下方法之外，还有其他固定时间的方法来分割向量吗？

 std::vector<int> v_SplitVector(start , end);

这将需要 O(N) 的复杂度。在这种情况下 O（结束 ​​- 开始）。是否有一个恒定的时间操作来做到这一点。

还是我为任务使用了错误的容器？

4

5 回答 5

3

这是副本而不是拆分，因此很复杂。您可能可以编写一个list可能表现更好的拆分。

于 2013-02-08T08:26:09.917 回答
3

“拆分”一个容器的行为，对于像向量这样的容器，其中元素位于连续的内存上，必然需要复制/移动所有需要在另一边的东西。

容器之类list的，每个元素都在自己的内存块上，可以很容易地重新排列（参见std::list::splice）

但是在非连续内存中包含元素可能会由于更频繁的缓存丢失而导致内存访问性能降低。

换句话说，算法的复杂性可能不是影响性能的唯一因素：一个不频繁的线性副本可能比在分散元素上频繁的线性游走对你造成的伤害要小。

权衡主要取决于硬件如何管理缓存以及您使用的 std 实现如何处理（以及编译器最终如何优化）

于 2013-02-08T08:33:26.480 回答
2

std::vector不支持以下内容，但如果有效的“拆分”操作对您非常重要，那么您也许可以编写自己的容器。这将是相当多的工作。

您可以如下定义“拆分”：

  • 删除容器的初始段，并返回包含这些元素的新容器。对这些元素的引用继续引用新容器中的相同元素。旧容器包含剩余的元素。新容器的容量等于它的大小，旧容器的容量减少了删除元素的数量。

然后旧容器和新容器将共享一个底层存储块（可能带有引用计数）。如果您追加到新容器，则必须重新分配它（因为立即在其元素末尾的内存正在使用中），但只要这种情况很少发生或永远不会发生，它可能是一个胜利。

但是，您的示例代码需要一个副本，它不会修改原始容器。如果需要逻辑副本，则无需实际复制您需要 COW 或不可变对象的元素即可。

std::list具有splice()可以将一系列元素从一个列表移动到另一个列表的功能。这避免了复制元素，但从 C++11 开始，它实际上保证不是O(1)，因为它需要计算它移动了多少元素。在 C++03 中，实现可以选择是否希望此操作成为O(1)或list::size()成为O(1)，但在 C++11size()中，要求所有容器的时间都是恒定的。

不过，比较std::vectorwith的性能std::list通常不仅仅是一项操作。您必须考虑list没有随机访问迭代器，等等。

于 2013-02-08T08:55:52.703 回答
2

创建一个新的std::vector必然需要复制，因为向量不允许共享其实现的一部分。您从中获取的容器中的修改，start 不应end影响splitVector.

您可以相当容易地做的是创建一个View容器，它只包含两个迭代器，并通过它们映射所有访问。类似于以下内容：

template <typename Iterator>
class View
{
    Iterator myBegin;
    Iterator myEnd;
public:
    typedef typename std::iterator_traits<Iterator>::value_type value_type;
    //  And the other usual typedefs, including...
    typedef Iterator iterator;

    View( Iterator begin, Iterator end )
        : myBegin( begin )
        , myEnd( end )
    {
    }

    iterator begin() { return myBegin; }
    iterator end()   { return myEnd; }
    value_type operator[]( ptrdiff_t index ) { return *(myBegin + index ); }
    //  ...
};

这需要相当多的样板文件，因为与 vector 之类的接口相当完整，但一切都非常直接和简单。然而，你不能做的一件事是修改底层容器或任何容器的拓扑结构——任何View可能使任何迭代器无效的事情当然会破坏。

于 2013-02-08T09:30:43.693 回答
0

当向/从不同于开始/结束的地方添加或删除元素时，由于需要内部移位，向量必须具有至少 o(n) 的复杂度。当您不仅要删除元素，还要将元素移出时，sme 就会出现：对于向量，它们必须被复制，因此，每个元素至少移动 1 个操作。这意味着将元素移出向量的时间至少为 O(N)，其中 N 是移动的元素数量。

如果您需要近乎恒定的时间添加/删除操作（无论是添加/插入一个或多个元素），您应该查看列表/链表容器，其中所有元素和子列表都很容易“可拆卸”，特别是如果您知道指针/迭代器。或树，或任何其他动态结构。

顺便说一句，我感觉到了什么v_SplitVector，但它是从哪里来的？我不记得 stdlib 或 boost 中的这种函数/方法？

于 2013-02-08T08:27:38.827 回答