1

我有一个 STL 对象，例如

std::vector <long> vec1;

我想把它转换成一个向量

std::vector <int> vec2;

使用

std::map<long,int>map;

是否有一种有效的方法可以动态删除映射到 vec2 的 vec1 元素以减小 vec1 的大小？这个算法应该消耗最少的内存并且应该很快。是否可以就地执行此操作？std::remove_if 会做好吗？与分块处理相比，性能如何，即 vec1 被分成块；然后将每个块映射并存储在 vec2 中；在此之后从内存中删除块。

vec1（和 vec2）也可以是向量（向量的向量）。

4

3 回答 3

1

如果您已经有地图，可以试试这个 (C++11) 解决方案：

std::vector<long> vec1;  // Original vector
std::map<long, int> map; // How to map the `long` value to an `int`

std::vector<int> vec2;  // The destination vector

for (const auto l : vec1)
    vec2.push_back(map[l]);

如果第一个向量是向量的向量，只需使用嵌套循环：

for (const auto& v : vec1)
{
    for (const auto l : v)
        vec2.push_back(map[l]);
}
于 2013-03-13T05:27:12.143 回答
1

是否有一种有效的方法可以动态删除映射到 vec2 的 vec1 元素以减小 vec1 的大小？

从 a 的开头删除东西vector是低效的，因为它会导致剩余的元素向前移动以填充开头的空白空间。并且在向量末尾释放的内存无论如何都不会返回到堆中，因为它都是一个大内存块的一部分，一次全部释放。

这里更合适的是默认std::queue使用std::deque数据结构。这包括一系列小内存块。您可以在开始时使用pop.

#include <queue>

std::queue <long> vec1;
std::queue <int> vec2;

while ( ! vec1.empty() ) {
    vec2.push( value_map[ vec1.front() ] );
    vec1.pop();
}

您也可以std::deque直接使用对象。然后你会使用push_frontand pop_back。这是一堂很酷的课；它保持了对象“扁平”序列的错觉，即使它们不在一个单一的、扁平的阵列中vector使用。

于 2013-03-13T06:22:20.990 回答
0

您可以在将元素复制到目标向量时从源向量中删除它们。

while (!source.empty()) {
  destination.push_back(map[source.back()]);
  source.pop_back();
}

这需要 O( n log m ) 时间和 O(1) 空间，其中n是source.size()，m是map.size()。

于 2013-03-13T05:34:15.753 回答