将std::vector转换为另一个std::vector的最快方法

Question

将std::vector转换为另一个std::vector的最快方法

28

有没有更快的方法（如果有其他方法）可以将std :: vector从一种数据类型转换为另一种数据类型（以节省空间为目的）？例如：

std::vector<unsigned short> ----> std::vector<bool>

我们显然假设第一个向量只包含0和1。如果向量非常大，逐个复制元素的效率非常低。

条件问题：如果您认为没有更快的方法，是否有一种复杂的数据类型实际上允许从一种数据类型快速转换到另一种数据类型？

- scigor

@NikolaiNFetissov：OP想要节省内存。std::vector<bool>被专门设计为内存高效。 - Björn Pollex

@ R. Martinho Fernandes：你说对了！！！我确实想要魔法，不幸的是 std::do_magic() 似乎不存在。 - scigor

@Björn，“vector<bool>”是一场灾难。即使STL的作者也承认这是一个错误。 - Nikolai Fetissov

8个回答

23

无法避免复制，因为std::vector<T>是与std::vector<U>不同的类型，它们无法共享内存。除此之外，这取决于数据映射方式。如果映射对应着隐式转换（例如从unsigned short到bool），那么只需使用旧向量的begin和end迭代器创建一个新向量即可：

std::vector<bool> newV( oldV.begin(), oldV.end() );

如果映射不仅仅是隐式的转换（这包括你想要验证的情况；例如，unsigned short 只包含 0 或 1），那么就会变得更加复杂。显而易见的解决方案是使用 std::transform：

std::vector<TargetType> newV;
newV.reserve( oldV.size() );    //  avoids unnecessary reallocations
std::transform( oldV.begin(), oldV.end(),
                std::back_inserter( newV ),
                TranformationObject() );

这里的TranformationObject是一个函数对象，用于执行转换操作，例如：

struct ToBool : public std::unary_function<unsigned short, bool>
{
    bool operator()( unsigned short original ) const
    {
        if ( original != 0 && original != 1 )
            throw Something();
        return original != 0;
    }
};

注意，我只是以这个转换函数为例子。如果唯一区分转换函数和隐式转换的是验证，那么使用 `std::for_each` 验证所有的值在 `oldV` 中可能会更快，然后再使用上面的两个迭代器构造函数。

根据目标类型的默认构造成本，创建具有正确大小的新向量，然后覆盖它可能更快。

std::vector<TargetType> newV( oldV.size() );
std::transform( oldV.begin(), oldV.end(),
                newV.begin(),
                TranformationObject() );

最后，另一个可能的选择是使用boost::transform_iterator。代码如下：

std::vector<TargetType> newV(
    boost::make_transform_iterator( oldV.begin(), TranformationObject() ),
    boost::make_transform_iterator( oldV.end(), TranformationObject() ) );

在很多方面，这是我偏爱的解决方案；取决于boost::transform_iterator的实现方式，它也可能是最快的。

- James Kanze

非常感谢，这真的很有帮助。我希望我也能将这个答案标记为正确答案。 - scigor

9

您应该可以像这样使用 assign ：

vector<unsigned short> v;
//...
vector<bool> u;
//...
u.assign(v.begin(), v.end());

- Vlad

10

您可以直接在构造函数中这样做：std::vector<bool> u(b.begin(), v.end());。 - Björn Pollex

@BjörnPollex：我认为应该是 u(v.begin(), v.end());，对吗？ - Chap

@Chap：是的，那里有一个错别字。不过评论已经太旧无法编辑了。感谢你发现了这个问题。 - Björn Pollex

4

class A{... }
class B{....}
B convert_A_to_B(const A& a){.......}

void convertVector_A_to_B(const vector<A>& va, vector<B>& vb)
{
    vb.clear();
    vb.reserve(va.size());
    std::transform(va.begin(), va.end(), std::back_inserter(vb), convert_A_to_B);
}

- Vikas

3

最快的方法是不要去做。例如，如果您事先知道您的项目只需要一个字节的存储空间，请使用一个字节大小的向量开始。你会发现没有比这更快的方法了 :-)

如果不可能的话，那就吸收转换成本。即使它有一点慢（这并不确定，详情请参见Nicol的精彩回答），它仍然是必要的。如果不是必须的，你就把它留在较大类型的向量中。

- paxdiablo

当然最好从一开始就使用正确的数据类型。 - scigor

1

首先，警告：不要做我即将提出的建议。这很危险，绝不能这样做。话虽如此，如果你必须尽一切可能挤出更多性能...

首先，有一些注意事项。如果您不满足以下条件，则无法执行此操作：

向量必须包含纯旧数据（plain-old-data）。如果您的类型具有指针，或使用析构函数，或需要运算符=正确复制...不要这样做。
sizeof()两个向量包含的类型必须相同。也就是说，只有当sizeof(A) == sizeof(B)时，vector<A>可以从vector<B>复制。

这里是一个相当稳定的方法：

vector< A > a;
vector< B > b;
a.resize( b.size() );
assert( sizeof(vector< A >::value_type) == sizeof(vector< B >::value_type) );
if( b.size() == 0 )
   a.clear();
else
   memcpy( &(*a.begin()), &(*b.begin()), b.size() * sizeof(B) );

这个函数可以非常快速地从向量b中拷贝内存块，直接覆盖向量a中的任何数据。它不会调用构造函数，也不会进行任何安全检查，而且比这里给出的任何其他方法都要快得多。理论上，优化编译器应该能够匹配这个函数的速度，但除非你使用一个异常好的编译器，否则不会（我几年前使用Visual C++进行了测试，并且它的表现并不出色）。

此外，在这些限制条件下，你可以通过 void* 强制将一个向量类型转换为另一个，然后交换它们 -- 我曾经有一个代码示例，但是它在我的屏幕上开始渗出外胚层物质，所以我删除了它。

- AHelps

0

#ifdef VECTOR_H_TYPE1
#ifdef VECTOR_H_TYPE2
#ifdef VECTOR_H_CLASS
/* Other methods can be added as needed, provided they likewise carry out the same operations on both */

#include <vector>

using namespace std;

class VECTOR_H_CLASS {
public:
        vector<VECTOR_H_TYPE1> *firstVec;
        vector<VECTOR_H_TYPE2> *secondVec;

        VECTOR_H_CLASS(vector<VECTOR_H_TYPE1> &v1, vector<VECTOR_H_TYPE2> &v2) { firstVec = &v1; secondVec = &v2; }
        ~VECTOR_H_CLASS() {}

        void init() { // Use this to copy a full vector into an empty (or garbage) vector to equalize them
                secondVec->clear();
                for(vector<VECTOR_H_TYPE1>::iterator it = firstVec->begin(); it != firstVec->end(); it++) secondVec->push_back((VECTOR_H_TYPE2)*it);
        }

        void push_back(void *value) {
                firstVec->push_back((VECTOR_H_TYPE1)value);
                secondVec->push_back((VECTOR_H_TYPE2)value);
        }

        void pop_back() {
                firstVec->pop_back();
                secondVec->pop_back();
        }

        void clear() {
                firstVec->clear();
                secondVec->clear();
        }
};
#undef VECTOR_H_CLASS
#endif
#undef VECTOR_H_TYPE2
#endif
#undef VECTOR_H_TYPE1
#endif

- Jerry Miller

现在我想起来，我写这个是为了类和派生类指针，所以如果用作通用调整可能会有限制。抱歉！ - Jerry Miller

0

逐个复制元素并不是非常低效的。std::vector提供对其任何元素的常数访问时间，因此操作的总体时间复杂度为O(n)。你几乎察觉不到它。

- Daniel Daranas

仅仅因为一个操作的时间复杂度是O(n)，并不意味着它的影响不可感知。或者你正在使用线性列表来存储数据以进行随机访问吗？ - FrankH.

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Nicol Bolas · Accepted Answer

std::vector<bool>

停一下。 std::vector<bool>不是一个标准的向量。 std::vector 有一个专门用于类型 bool 的特化，这会导致 vector 中发生某些变化。换句话说，它停止像 std::vector 一样工作。

标准保证您可以使用某些方法来操作 std::vector，而 vector<bool> 违反了这些保证。因此，使用它们时应该非常小心。

无论如何，我会假装您说的是 vector<int> 而不是 vector<bool>，因为后者会让事情变得更加复杂。

如果向量很大，则逐个复制元素的效率非常低。

只有在错误的情况下才会出现这种情况。

需要仔细处理所需类型的向量转换以使其高效。

如果源类型 T 可转换为目标类型 T，则可以正常工作：

vector<Tnew> vec_new(vec_old.begin(), vec_old.end());

良好的实现应该识别到它们被给予了随机访问迭代器，并优化内存分配和循环。

对于简单类型而言，最大的问题是没有这样做：

std::vector<int> newVec(oldVec.size());

这很糟糕。它会分配一个正确大小的缓冲区，但它也会填充数据。换句话说，默认构造的int（int()）。

相反，你应该这样做：

std::vector<int> newVec;
newVec.reserve(oldVec.size());

这将保留与原向量相等的容量，但也确保不会进行默认构造。现在，您可以放心地添加 push_back，并确信您不会在新向量中引起重新分配。

从那里，您只需循环遍历旧向量中的每个条目，并根据需要执行转换。