#cpp
Имеется вектор с целыми числами, необходимо продублировать каждый из его элементов.
Например:
исходный вектор: 12 56 -7 89 4 0 11 -6;
результат: 12 12 56 56 -7 -7 89 89 4 4 0 0 11 11 -6 -6.
Я решил воспользоваться методом insert(), предварительно объявив итератор. Но программа
выдает ошибку. Насколько я знаю, метод insert(p, x) вставляет значение x ПЕРЕД элементом,
на который указывает итератор p и возвращает итератор на вставленный элемент, поэтому
я сделал шаг p + 2 чтобы добраться до следующего элемента, а иначе, при использовании
обычного инкремента, итератор вставал бы на элемент, который уже был продублирован.
Возможно, я неправильно понимаю, как работает метод insert() и как функционируют итераторы.
Вот цикл, который должен дублировать элементы вектора:
for (auto p = ivec.begin(); p != ivec.end();)
{
ivec.insert(p, *p);
p + 2;
}
ivec - вектор,
p - итератор
Вывод программы:
free(): invalid pointer
Aborted (core dumped)
Ответы
Ответ 1
Влезу и я со своими 5 копейками. При таком варианте у вас будет O(N^2) перемещений элементов, что не слишком хорошо. Я бы создал новый вектор удвоенного размера и простым циклом переписал все элементы, т.е. выполнив операцию за O(N). Потом можно просто выполнить перемещение данных. Примерно так void dbl(vector&v) { vector n; n.reserve(v.size()*2); for(auto i: v) { n.push_back(i); n.push_back(i); } v.swap(n); } int main(int argc, const char * argv[]) { vector v { 1,2,3,4,5,6,7,8,9,10 }; for(auto i: v) cout << i << " "; cout << endl; dbl(v); for(auto i: v) cout << i << " "; cout << endl; } Update Как обычно, проведем эксперимент :) Итак, три версии - моя, AR Hovsepyan, со вставкой. Для int и тормознутого класса (тормознутость имитируется небольшой задержкой). Так как задержка тормозит конкретно, для int - 100000 элементов, для тормозов - 1000. Полный код эксперимента приведен ниже. Результаты для 100000 int: Мой код 533 mks Код ARH 419 mks Вставка 640601 mks Для тормозов в 1 нс :) Мой код 6826 mks Код ARH 40797 mks Вставка 1418118 mks В общем, что и требовалось доказать... Полный код: #include #include #include #include #include #include using namespace std; template void dblHW(vector &v) { vector n; n.reserve(v.size()*2); for(auto i: v) { n.push_back(i); n.push_back(i); } v.swap(n); } template void dblAR(vector & v) { vector t(v.size() * 2); int j = 0; for(T i : v) { t[j] = t[j + 1] = i; j += 2; } v.swap(t); } template void dblIns(vector & v) { for(size_t i = 0; i < v.size(); i+=2) v.insert(v.begin()+i,v[i]); } class Tormoz { #define delay this_thread::sleep_for(1ns) public: Tormoz(int i = 0):i(i) { delay; } ~Tormoz() { delay; } Tormoz& operator = (const Tormoz& t) { i = t.i; delay; return *this; } Tormoz(const Tormoz& t) : i(t.i) { delay; } Tormoz(Tormoz&& t) : i(t.i) { delay; } int i; }; bool operator == (const Tormoz& a, const Tormoz& b) { return a.i == b.i; } class muTimer { using Clock = std::chrono::high_resolution_clock; bool active = false; Clock::duration duration_; Clock::time_point start_ = Clock::now(), stop_ = Clock::now(); muTimer(const muTimer&) = delete; muTimer& operator=(const muTimer&) = delete; public: using ns = std::chrono::nanoseconds; using mks = std::chrono::microseconds; using ms = std::chrono::milliseconds; muTimer() { reset(); start(); } ~muTimer() = default; muTimer& reset() { duration_ = std::chrono::nanoseconds(0); active = false; return *this; } muTimer& start() { if (!active) { start_ = Clock::now(); active = true; } return *this; } muTimer& stop() { if (active) { stop_ = Clock::now(); duration_ += stop_ - start_; active = false; } return *this; } template unsigned long long duration() { return static_cast (std::chrono::duration_cast (stop_-start_).count()); } }; int main(int argc, const char * argv[]) { { vector a; for(int i = 0; i < 100000; ++i) a.push_back(rand()); vector b = a, c = a; //for(int i : a) cout << i << " "; cout << endl; { muTimer m; dblHW(a); m.stop(); cout << "HW: " << m.duration() << " mks\n"; } { muTimer m; dblAR(b); m.stop(); cout << "ARH: " << m.duration() << " mks\n"; } { muTimer m; dblIns(c); m.stop(); cout << "Ins: " << m.duration() << " mks\n"; } assert(a == b && b == c); } { vector a; for(int i = 0; i < 1000; ++i) a.push_back(rand()); vector b = a, c = a; //for(int i : a) cout << i << " "; cout << endl; { muTimer m; dblHW(a); m.stop(); cout << "HW: " << m.duration() << " mks\n"; } { muTimer m; dblAR(b); m.stop(); cout << "ARH: " << m.duration() << " mks\n"; } { muTimer m; dblIns(c); m.stop(); cout << "Ins: " << m.duration() << " mks\n"; } assert(a == b && b == c); } } Ответ 2
http://www.cplusplus.com/reference/vector/vector/insert/ - "Iterator validity" p = ivec.insert(p, *p);Ответ 3
Предложу другой вариант(без вызовов функций) ответа Harry void dbl(std::vector& v) { std::vector t(v.size() * 2); int j = 0; for (int i : v) { t[j] = t[j + 1] = i; j += 2; } v.swap(t); } P.S. А если вы часто пользуетесь вставками и удалением, то std::list кандидат получше вектора Ответ 4
https://ideone.com/RCUR7N #include#include using namespace std; template void duplicate(vector &v) { size_t n = v.size(); v.resize(n << 1); for (size_t q=n-1; ~q; --q) { v[(q<<1)|1] = v[q]; v[q<<1] = move(v[q]); // should work for 0 } } int main(int argc, const char * argv[]) { vector v { 1,2,3,4,5,6,7,8,9,10 }; for(auto i: v) cout << i << " "; cout << endl; duplicate(v); for(auto i: v) cout << i << " "; cout << endl; }
Комментариев нет:
Отправить комментарий