Как правильно переносить(копировать) элемент одного std::vector в другой

#cpp #stl #vector

Интересует как быстрее всего копировать или переносить элементы из одного std::vector
в другой, раньше для возможности быстрого удаления элементов из контейнера использовал
std::list

        for( auto it=l.begin(); it!=l.end();) {
            if ( условие )
                it=l.erase(it);
            else
               ++it;
        }


но как оказалось list не слишком быстрый даже в этом, теперь использую нечто вроде

        for( auto it=v.begin(); it!=v.end(); ++it) {
            if ( !условие )
                tmpv.emplace_back(*it);
        }
        v.swap(tmpv);
        tmpv.clear();


сначало элементы которые не попали под условие переношу в другой vector, а потом
меняю контейнеры местами, но мне кажется что

                tmpv.emplace_back(*it);


это не совсем правильно и возможно есть другие функции в std которые позволят переносить(копировать)
элемент быстрее чем реализовано у меня
    

Ответы

Ответ 1

А самый простой вариант (оставляет элементы соответствующие cond())

  int n = 0;
  for (int i = 0; i < v.size(); i++)
    if (condition(v[i]))
      v[n++] = v[i];
  v.resize(n);


не пробовали?



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

Вот примерчик:

#include 
#include 
#include 
#include 

#include 
#include 
#include 

using namespace std;

void act (string s) {
  cout << s << '\n';
}

int 
main (int ac, char *av[]) 
{
  vector v;
  string s;

  while (cin >> s)
    v.push_back(s);
  cout << "size: " << v.size() << " capacity: " << v.capacity() << '\n';
  int n = 0, cntcmp = 0, cntcpy = 0, cntact = 0;
  if (av[1]) {
    /*
      size: 108 capacity: 256
      cmp: 120 cpy: 64 act: 140 total: 324
     */
    n = v.size();

    int i = 0, j = v.size() - 1;

    while (j >= i) {
      while (i <= j && isalpha(v[i][0])) {
        cntcmp++;
        i++;
      }
      if (i > j)
        break;
      act(v[i]);
      cntact++;
      n--;
      while (j > i && !isalpha(v[j][0])) {
        cntcmp++;
        cntact++;
        act(v[j--]);
        n--;
      }
      if (j == i)
        break;
      v[i++] = v[j--];
      cntcpy++;
    }
  } else {
    /*
      size: 108 capacity: 256
      cmp: 248 cpy: 108 act: 140 total: 496
     */
    for (int i = 0; i < v.size(); i++) {
      cntcmp++;
      if (isalpha(v[i][0])) {
        cntcpy++;
        v[n++] = v[i];
      } else {
        cntact++;
        act(v[i]);
      }
    }
  }

  v.resize(n);

  for (int i = 0; i < n; i++)
    cout << v[i] << '\n';

  cerr << "size: " << v.size() << " capacity: " << v.capacity() << '\n';
  cerr << "cmp: " << cntcmp << " cpy: " << cntcpy << " act: " << cntact 
       << " total: " << cntcmp + cntact + cntcpy << '\n';
}


Вот результат

avp@avp-ubu1:hashcode$ g++ c.cpp 
avp@avp-ubu1:hashcode$ ./a.out   < c.cpp | sort >2.txt
size: 108 capacity: 256
cmp: 248 cpy: 108 act: 140 total: 496
avp@avp-ubu1:hashcode$ ./a.out 1  < c.cpp | sort >1.txt
size: 108 capacity: 256
cmp: 120 cpy: 64 act: 140 total: 324
avp@avp-ubu1:hashcode$ cmp 1.txt 2.txt
avp@avp-ubu1:hashcode$ 


Ну, все эти sort и cmp для того, чтобы убедиться, что оба варианта дают тот же результат.


Ответ 2

Во-первых, класс std::list имеет специальные функции члены класса remove и remove_if,
которые позволяют выполнить данную операцию для списка за один вызов функции:

void remove(const T& value);
template  void remove_if(Predicate pred);


Что касается вектора, то я думаю, что вместо того, чтобы удалять каждый элемент,
удовлетворяющий заданному условию, по отдельности в цикле, значительно более эффективно
использовать стандартный алгоритм std::remove_if в связке с методом вектора erase.
Например,

v.erase( std::remove_if( v.begin(), v.end(), []( const auto &x ) { return condition(
x ); } ), 
         v.end() );


Если же вы с удаляемыми элементами производите какие-то дополнительные операции,
то вы просто можете реализацию алгоритма std::remove_if использовать в своем коде в
виде цикла и в этот цикл вставить те дополнительные операции, которые вам необходимо
проделать над элементами.

На мой взгляд это более эффективно, чем копировать элементы вектора в другой вектор,
так как это не требует выделение дополнительной памяти и вызова деструкторов для каждого
элемента вектора при обмене векторов. И уж по крайней мере если копировать элементы
вектора в другой вектор, то лучше использовать move итератор. Проблема может состоять
в том, что объекты могут быть не перемещаемы.

Что касается этого вызова

tmpv.emplace_back(*it);


то здесь используется просто конструктор копирования, так как это единственный подходящий
конструктор для аргумента *it. Так что никакой разницы между

tmpv.emplace_back(*it);


и

tmpv.push_back(*it);


в данном случае нет.

Вот демонстрационная программа

#include 
#include 

struct A
{
    A() { std::cout << "A::A()" << std::endl; }
    A( const A & ) { std::cout << "A::A( const A &)" << std::endl; }
    ~A() { std::cout << "A::~A()" << std::endl; }
};   

int main()
{
    std::vector v1( 1, A() );

    std::cout << "-------------------" << std::endl;

    std::vector v2;

    v2.emplace_back( *std::begin( v1 ) );
//    v2.push_back( *std::begin( v1 ) );

    std::cout << "-------------------" << std::endl;
}    


Вывод на консоль:

A::A()
A::A( const A &)
A::~A()
-------------------
A::A( const A &)
-------------------
A::~A()
A::~A()


Ответ 3

Какой-то "размытый" вопрос... Можно например так:

std::vector  src{ 1, 2, 3, 4, 5 };
std::vector  dst;

// ...

std::copy_if( src.begin(), src.end(), std::back_inserter( dst ), []( const int &
i ){ return i > 3; } );


Ответ 4

Насколько я понял, что в вашей задаче происходит копирование по десять элементов.
То наверное и нужно копировать по десять элементов сразу. Точно не уверен в скорости
моего решения просто проверьте быстрее оно или нет. И сильно не ругайте если я не прав
это эксперимент.

#include 
#include 
#include 

using namespace std;

int main(){
    const int size = 50; // размер массива
    vector a; // из которого копируем
    vector b; // основной в который пишем

    srand(time(0)); // рандомизация генератора

    for (int i = 0; i < size; i++){  // заполняем массив значениями
        a.push_back(rand() % 100); // из котрого будем копировать
    }

    vector::iterator start = a.begin(), end = a.begin(); // переменные для начала
и конца копирования

    for (int i = 0; i < size; i += 10){ // копирование по десять элементов
        end += 10; // передвигаем счетчик конца на 10 элементов
        start = end - 10; // находим начало откуда копировать
        b.resize(i + 10); // увеличиваем вместимость вектора
        std::copy(start, end, b.begin() + i); // копируем по десять элементов в другой
массив
        // здесь если вы захотите можете удалять каждый десятый элемент как у вас
в задании
    }

    for (int i = 0; i < size; i++){ // проверка
        cout << b[i] << endl;
    }

    return 0;
}