#include <iostream>
#include <vector>
#include <algorithm>
class SquarePushBackIterator
{
std::vector<int>& dst;
public:
SquarePushBackIterator(std::vector<int>& dst) : dst(dst) {}
// These just return references to the iterator.
// The only operation that matters is assignment.
SquarePushBackIterator& operator*() { return *this; }
SquarePushBackIterator& operator++() { return *this; }
SquarePushBackIterator& operator++(int) { return *this; }
// The assignment squares and inserts into the destination.
void operator=(int val)
{
dst.push_back(val * val);
}
};
void mergeSortedArray(std::vector<int>& data)
{
// Find the iterator range for the positive values.
using iter = std::vector<int>::const_iterator;
iter endPositive = std::end(data);
iter loopPositive = std::find_if(std::begin(data), std::end(data),
[](int val) {return val >= 0; });
// Find the iterator range for the negative values.
using reve = std::reverse_iterator<iter>;
reve endNegative = reve(std::begin(data));
reve loopNegative = reve(loopPositive);
// Create an array to put the results into.
std::vector<int> result;
result.reserve(data.size());
// Perform a standard merge
std::merge(loopPositive, endPositive, loopNegative, endNegative,
SquarePushBackIterator(result),
[](int val1, int val2){return std::abs(val1) < std::abs(val2); });
// Use move assignment to put the result in the output vector.
// Alternatively we could return an array by value.
data = std::move(result);
}
int main()
{
std::vector<int> arr={ -3, -2, 0, 4, 5, 8 };
mergeSortedArray(arr);
for (const auto& i : arr)
{
std::cout << i << ' ';
}
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgoKY2xhc3MgU3F1YXJlUHVzaEJhY2tJdGVyYXRvcgp7CglzdGQ6OnZlY3RvcjxpbnQ+JiBkc3Q7CnB1YmxpYzoKCVNxdWFyZVB1c2hCYWNrSXRlcmF0b3Ioc3RkOjp2ZWN0b3I8aW50PiYgZHN0KSA6IGRzdChkc3QpIHt9CgkvLyBUaGVzZSBqdXN0IHJldHVybiByZWZlcmVuY2VzIHRvIHRoZSBpdGVyYXRvci4KCS8vIFRoZSBvbmx5IG9wZXJhdGlvbiB0aGF0IG1hdHRlcnMgaXMgYXNzaWdubWVudC4KCVNxdWFyZVB1c2hCYWNrSXRlcmF0b3ImIG9wZXJhdG9yKigpICAgICB7IHJldHVybiAqdGhpczsgfQoJU3F1YXJlUHVzaEJhY2tJdGVyYXRvciYgb3BlcmF0b3IrKygpICAgIHsgcmV0dXJuICp0aGlzOyB9CglTcXVhcmVQdXNoQmFja0l0ZXJhdG9yJiBvcGVyYXRvcisrKGludCkgeyByZXR1cm4gKnRoaXM7IH0KCgkvLyBUaGUgYXNzaWdubWVudCBzcXVhcmVzIGFuZCBpbnNlcnRzIGludG8gdGhlIGRlc3RpbmF0aW9uLgoJdm9pZCBvcGVyYXRvcj0oaW50IHZhbCkKCXsKCQlkc3QucHVzaF9iYWNrKHZhbCAqIHZhbCk7Cgl9Cn07Cgp2b2lkIG1lcmdlU29ydGVkQXJyYXkoc3RkOjp2ZWN0b3I8aW50PiYgZGF0YSkKewoKCS8vIEZpbmQgdGhlIGl0ZXJhdG9yIHJhbmdlIGZvciB0aGUgcG9zaXRpdmUgdmFsdWVzLgoJdXNpbmcgaXRlciA9IHN0ZDo6dmVjdG9yPGludD46OmNvbnN0X2l0ZXJhdG9yOwoJaXRlciAgZW5kUG9zaXRpdmUgPSBzdGQ6OmVuZChkYXRhKTsKCWl0ZXIgIGxvb3BQb3NpdGl2ZSA9IHN0ZDo6ZmluZF9pZihzdGQ6OmJlZ2luKGRhdGEpLCBzdGQ6OmVuZChkYXRhKSwKCQlbXShpbnQgdmFsKSB7cmV0dXJuIHZhbCA+PSAwOyB9KTsKCgkvLyBGaW5kIHRoZSBpdGVyYXRvciByYW5nZSBmb3IgdGhlIG5lZ2F0aXZlIHZhbHVlcy4KCXVzaW5nIHJldmUgPSBzdGQ6OnJldmVyc2VfaXRlcmF0b3I8aXRlcj47CglyZXZlICBlbmROZWdhdGl2ZSA9IHJldmUoc3RkOjpiZWdpbihkYXRhKSk7CglyZXZlICBsb29wTmVnYXRpdmUgPSByZXZlKGxvb3BQb3NpdGl2ZSk7CgoJLy8gQ3JlYXRlIGFuIGFycmF5IHRvIHB1dCB0aGUgcmVzdWx0cyBpbnRvLgoJc3RkOjp2ZWN0b3I8aW50PiAgcmVzdWx0OwoJcmVzdWx0LnJlc2VydmUoZGF0YS5zaXplKCkpOwoKCS8vIFBlcmZvcm0gYSBzdGFuZGFyZCBtZXJnZQoJc3RkOjptZXJnZShsb29wUG9zaXRpdmUsIGVuZFBvc2l0aXZlLCBsb29wTmVnYXRpdmUsIGVuZE5lZ2F0aXZlLAoJCVNxdWFyZVB1c2hCYWNrSXRlcmF0b3IocmVzdWx0KSwKCQlbXShpbnQgdmFsMSwgaW50IHZhbDIpe3JldHVybiBzdGQ6OmFicyh2YWwxKSA8IHN0ZDo6YWJzKHZhbDIpOyB9KTsKCgkvLyBVc2UgbW92ZSBhc3NpZ25tZW50IHRvIHB1dCB0aGUgcmVzdWx0IGluIHRoZSBvdXRwdXQgdmVjdG9yLgoJLy8gQWx0ZXJuYXRpdmVseSB3ZSBjb3VsZCByZXR1cm4gYW4gYXJyYXkgYnkgdmFsdWUuCglkYXRhID0gc3RkOjptb3ZlKHJlc3VsdCk7Cn0KCmludCBtYWluKCkKewoJc3RkOjp2ZWN0b3I8aW50PiBhcnI9eyAtMywgLTIsIDAsIDQsIDUsIDggfTsKCgltZXJnZVNvcnRlZEFycmF5KGFycik7CgoJZm9yIChjb25zdCBhdXRvJiBpIDogYXJyKQoJewoJCXN0ZDo6Y291dCA8PCBpIDw8ICcgJzsKCX0KfQ==
In file included from /usr/include/c++/4.8/bits/char_traits.h:39:0,
from /usr/include/c++/4.8/ios:40,
from /usr/include/c++/4.8/ostream:38,
from /usr/include/c++/4.8/iostream:39,
from prog.cpp:1:
/usr/include/c++/4.8/bits/stl_algobase.h: In instantiation of ‘_OI std::__copy_move_a(_II, _II, _OI) [with bool _IsMove = false; _II = const int*; _OI = SquarePushBackIterator]’:
/usr/include/c++/4.8/bits/stl_algobase.h:428:38: required from ‘_OI std::__copy_move_a2(_II, _II, _OI) [with bool _IsMove = false; _II = __gnu_cxx::__normal_iterator<const int*, std::vector<int> >; _OI = SquarePushBackIterator]’
/usr/include/c++/4.8/bits/stl_algobase.h:460:17: required from ‘_OI std::copy(_II, _II, _OI) [with _II = __gnu_cxx::__normal_iterator<const int*, std::vector<int> >; _OI = SquarePushBackIterator]’
/usr/include/c++/4.8/bits/stl_algo.h:5640:19: required from ‘_OIter std::merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare) [with _IIter1 = __gnu_cxx::__normal_iterator<const int*, std::vector<int> >; _IIter2 = std::reverse_iterator<__gnu_cxx::__normal_iterator<const int*, std::vector<int> > >; _OIter = SquarePushBackIterator; _Compare = mergeSortedArray(std::vector<int>&)::__lambda1]’
prog.cpp:44:67: required from here
/usr/include/c++/4.8/bits/stl_algobase.h:382:57: error: no type named ‘value_type’ in ‘struct std::iterator_traits<SquarePushBackIterator>’
typedef typename iterator_traits<_OI>::value_type _ValueTypeO;
^
/usr/include/c++/4.8/bits/stl_algobase.h:387:9: error: no type named ‘value_type’ in ‘struct std::iterator_traits<SquarePushBackIterator>’
&& __are_same<_ValueTypeI, _ValueTypeO>::__value);
^
/usr/include/c++/4.8/bits/stl_algobase.h: In instantiation of ‘_OI std::__copy_move_a(_II, _II, _OI) [with bool _IsMove = false; _II = std::reverse_iterator<__gnu_cxx::__normal_iterator<const int*, std::vector<int> > >; _OI = SquarePushBackIterator]’:
/usr/include/c++/4.8/bits/stl_algobase.h:428:38: required from ‘_OI std::__copy_move_a2(_II, _II, _OI) [with bool _IsMove = false; _II = std::reverse_iterator<__gnu_cxx::__normal_iterator<const int*, std::vector<int> > >; _OI = SquarePushBackIterator]’
/usr/include/c++/4.8/bits/stl_algobase.h:460:17: required from ‘_OI std::copy(_II, _II, _OI) [with _II = std::reverse_iterator<__gnu_cxx::__normal_iterator<const int*, std::vector<int> > >; _OI = SquarePushBackIterator]’
/usr/include/c++/4.8/bits/stl_algo.h:5640:20: required from ‘_OIter std::merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare) [with _IIter1 = __gnu_cxx::__normal_iterator<const int*, std::vector<int> >; _IIter2 = std::reverse_iterator<__gnu_cxx::__normal_iterator<const int*, std::vector<int> > >; _OIter = SquarePushBackIterator; _Compare = mergeSortedArray(std::vector<int>&)::__lambda1]’
prog.cpp:44:67: required from here
/usr/include/c++/4.8/bits/stl_algobase.h:382:57: error: no type named ‘value_type’ in ‘struct std::iterator_traits<SquarePushBackIterator>’
typedef typename iterator_traits<_OI>::value_type _ValueTypeO;
^
/usr/include/c++/4.8/bits/stl_algobase.h:387:9: error: no type named ‘value_type’ in ‘struct std::iterator_traits<SquarePushBackIterator>’
&& __are_same<_ValueTypeI, _ValueTypeO>::__value);
^