在常数时间内提取子向量

Question

我有一个 std::vector<int> 并且我想丢弃 x first 和 y last 元素。仅复制元素不是一种选择，因为这是 O(n)。是否有类似 vector.begin()+=x 的东西让向量只是更晚开始并更早结束？我也试过了

items = std::vector<int> (&items[x+1],&items[0]+items.size()-y);

其中 items 是我的矢量，但这给了我 bad_alloc

Answer 1

如果您只需要一个值范围，您可以将其表示为从范围的第一个元素到最后一个元素的一对迭代器。这些可以在恒定时间内获得。

编辑：根据评论中的描述，这似乎是最明智的解决方案。如果您的函数需要矢量引用，那么您需要稍微重构一下。

其他解决方案：

如果您不需要原始向量，因此可以对其进行修改，并且元素的顺序无关紧要，您可以将前 x 个元素与 n-x-y...n-y 个元素交换，然后然后删除最后的 x+y 个元素。这可以在 O(x+y) 时间内完成。

如果合适，您可以选择使用 std::list 如果您有指向子列表的第一个和最后一个节点的迭代器，那么您所要求的可以在固定时间内完成。这也要求您可以修改原始列表，但元素的顺序不会改变。

如果这些不是选项，那么您需要复制并卡在 O(n)。

Answer 2

C++ 标准算法适用于范围，而不适用于实际容器，因此您无需提取任何内容：您只需调整您正在使用的迭代器范围.

void foo(const std::vector<T>& vec, const size_t start, const size_t end)
{
    assert(vec.size() >= end-start);
    auto it1 = vec.begin() + start;
    auto it2 = vec.begin() + end;

    std::whatever(it1, it2);
}

我不明白为什么需要比这更复杂。

(trivial live demo)

Answer 3

其他答案是正确的：通常迭代器就可以。

不过，你也可以写一个矢量视图。这是一个草图：

template<typename T>
struct vector_view
{
    vector_view(std::vector<T> const& v, size_t ind_begin, size_t ind_end)
        : _v(v)
        , _size(/* size of range */)
        , _ind_begin(ind_begin) {}

    auto size() const { return _size; }

    auto const& operator[](size_t i) const
    {
        //possibly check for input outside range
        return _v[ i + _ind_begin ];
    }

    //conversion of view to std::vector
    operator std::vector<T>() const
    {
        std::vector<T> ret(_size);
        //fill it
        return ret;
    }

private:
    std::vector<T> const& _v;
    size_t _size;
    size_t _ind_begin;
}

根据需要公开更多方法（当您想将其与标准库算法一起使用时，一些迭代器内容可能是合适的）。

此外，注意 const 引用的有效性 std::vector<T> const& v; —— 如果这可能是个问题，最好使用共享指针。

这里也可以想到更通用的方法，比如使用strides之类的。

在常数时间内提取子向量

Extract subvector in constant time

c++

arrays

stl

vector

time-complexity

(trivial live demo)