самый быстрый способ конвертировать std :: vector в другой std :: vector

Question

Какой самый быстрый способ (если есть какой-либо другой) преобразовать std :: vector из одного типа данных в другой (с идеей экономии места)? Например:

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

мы, очевидно, предполагаем, что первый вектор содержит только 0 и 1. Копирование элемента за элементом крайне неэффективно в случае действительно большого вектора.

Условный вопрос: Если вы думаете, что нет способа сделать это быстрее, существует ли сложный тип данных, который на самом деле позволяет быстро преобразовывать один тип данных в другой?

Answer 1

std::vector<bool> 

Стоп.

A std::vector<bool> - это ... нет.std::vector имеет специализацию для использования типа bool, что вызывает определенные изменения в vector.А именно, он перестает действовать как std::vector.

. Есть определенные вещи, которые стандарт гарантирует, что вы можете сделать с std::vector.И vector<bool> нарушает эти гарантии.Так что вы должны быть очень осторожными в их использовании.

В любом случае, я собираюсь притвориться, что вы сказали vector<int> вместо vector<bool>, поскольку последнее действительно усложняет ситуацию.

Копирование элемента за элементом крайне неэффективно в случае действительно большого вектора.

Только в том случае, если вы делаете это неправильно.

Векторная приведение нужного вам типа должно быть выполнено осторожно, чтобы быть эффективным.

Если источник T type может быть преобразован в пункт назначения T, тогда это работает просто отлично:

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

Достойные реализации должны распознавать, когда им были предоставлены итераторы с произвольным доступом, и оптимизировать распределение памяти и выполнять цикл соответствующим образом.

Самая большая проблема для неконвертируемых типов, которую вы будете иметь для простых типов, заключается в том, чтобы не делать это:

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

Это плохо.Это выделит буфер нужного размера, но он будет также заполнять его данными.А именно, построенный по умолчанию int s (int()).

Вместо этого вы должны сделать это:

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

Это резервирует емкость, равную исходному вектору, но также обеспечиваетчто никакая конструкция по умолчанию не происходит.Теперь вы можете push_back к своему сердцу, зная, что вы никогда не вызовете перераспределение в вашем новом векторе.

Оттуда вы можете просто перебрать каждую запись в старом векторе, выполняя преобразование по мере необходимости.

Answer 2

Невозможно избежать копирования, поскольку std::vector<T> отличается от типа std::vector<U>, и у них нет возможности поделиться памятью.Помимо этого, это зависит от того, как данные отображаются.Если сопоставление соответствует неявному преобразованию (например, unsigned short в bool), то просто создайте новый вектор, используя начальный и конечный итераторы из старого, и добьетесь цели:

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;
    }
};

(обратите внимание, что яЯ просто использую эту функцию преобразования в качестве примера. Если единственное, что отличает функцию преобразования от неявного преобразования, - это проверка, то может быть быстрее сначала проверить все значения в oldV, используя std::for_each, изатем используйте конструктор из двух итераторов, описанный выше.)

В зависимости от стоимости создания целевого типа по умолчанию может быть быстрее создать новый вектор с правильным размером, а затем перезаписать его:

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 был реализован, он также может быть самым быстрым.

Answer 3

Вы должны иметь возможность использовать assign так:

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

Answer 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);
}

Answer 5

Самый быстрый способ сделать это - , а не . Например, если вы заранее знаете, что вашим элементам нужен только байт для хранения, для начала используйте вектор размером в байт. Вам будет трудно найти более быстрый путь, чем этот: -)

Если это невозможно, просто возьмите стоимость конвертации. Даже если это немного медленно (и это ни в коем случае не обязательно, см. Отличный ответ Николя ), это все равно необходимо. Если бы это было не так, вы бы просто оставили его в векторе большего типа.

Answer 6

Во-первых, предупреждение: не делайте того, что я собираюсь предложить.Это опасно и никогда не должно быть сделано.Тем не менее, если вам просто нужно выжать чуть-чуть больше производительности No Matter What ...

Во-первых, есть несколько предостережений.Если вы не встречаете их, вы не можете сделать это:

1. Вектор должен содержать обычные старые данные.Если ваш тип имеет указатели, или использует деструктор, или для правильного копирования требуется оператор = ... не делайте этого.

2. sizeof () обоих типов, содержащихся в векторе, должен бытьтак же.То есть вектор может копировать из вектора , только если sizeof (A) == sizeof (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 *) привести один векторный тип к другому и поменять их местами - у меня был пример кода для этого, но он начал сочиться эктоплазмой на моем экране, поэтомуЯ удалил его.

Answer 7

#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

Answer 8

Копирование элемента за элементом не очень неэффективно.std :: vector обеспечивает постоянное время доступа к любому из его элементов, поэтому операция будет в общем случае O (n).Вы этого не заметите.