Интересует как быстрее всего копировать или переносить элементы из одного 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 которые позволят переносить(копировать) элемент быстрее чем реализовано у меня
Ответ
А самый простой вариант (оставляет элементы соответствующие 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
using namespace std;
void act (string s) {
cout << s << '
';
}
int
main (int ac, char *av[])
{
vector
while (cin >> s)
v.push_back(s);
cout << "size: " << v.size() << " capacity: " << v.capacity() << '
';
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] << '
';
cerr << "size: " << v.size() << " capacity: " << v.capacity() << '
';
cerr << "cmp: " << cntcmp << " cpy: " << cntcpy << " act: " << cntact
<< " total: " << cntcmp + cntact + cntcpy << '
';
}
Вот результат
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 для того, чтобы убедиться, что оба варианта дают тот же результат.
Комментариев нет:
Отправить комментарий