时间戳

首页 > 解决方案 > 在特定位置将多个值插入向量中

c++ - 在特定位置将多个值插入向量中

问题描述

假设我有一个这样的整数向量，std::vector<int> _data; 我知道如果我想从中删除多个项目_data，那么我可以简单地调用

_data.erase( std::remove_if( _data.begin(), _data.end(), [condition] ), _data.end() );

erase这比ing 多个元素要快得多，因为在vector. 我想知道插入是否有类似的东西。

例如，如果我有以下对

auto pair1 = { _data.begin() + 5, 5 };
auto pair2 = { _data.begin() + 12, 12 };

我可以使用一些现有std函数在一次迭代中插入这两个吗？我知道我可以做类似的事情：

_data.insert( pair2.first, pair2.second );
_data.insert( pair1.first, pair1.second );

但这对于大型向量（涉及 100,000 多个元素）来说（非常）慢。

编辑：基本上，我有一个自定义集（和地图），它使用 avector作为底层容器。我知道我可以只使用std::setor std::map，但是我做的遍历次数远远超过了插入/删除。从一个set和切换map到这个自定义集/映射已经减少了 20% 的运行时间。但目前，插入占用了大约 10% 的剩余运行时间，因此减少这一点很重要。

不幸的是，订单也是必需的。我尽可能使用这些unordered_版本，但在某些地方，顺序确实很重要。

标签： c++vector

解决方案

一种方法是创建另一个容量等于原始大小加上要插入的元素数量的向量，然后执行不重新分配的插入循环，O(N) 复杂度：

template<class T>
std::vector<T> insert_elements(std::vector<T> const& v, std::initializer_list<std::pair<std::size_t, T>> new_elements) {
    std::vector<T> u;
    u.reserve(v.size() + new_elements.size());
    auto src = v.begin();
    size_t copied = 0;
    for(auto const& element : new_elements) {
        auto to_copy = element.first - copied;
        auto src_end = src + to_copy;
        u.insert(u.end(), src, src_end);
        src = src_end;
        copied += to_copy;
        u.push_back(element.second);
    }
    u.insert(u.end(), src, v.end());
    return u;
}

int main() {
    std::vector<int> v{1, 3, 5};
    for(auto e : insert_elements(v, {{1,2}, {2,4}}))
        std::cout << e << ' ';
    std::cout << '\n';
}

输出：

1 2 3 4 5

推荐阅读