The function
template <typename Container, typename Comparator, typename Predicate>
void sortButKeepSomeFixed (Container& c, const Comparator& comp, const Predicate& pred)
is to sort the container c
according to the ordering criterion comp
, but those elements that satisfy pred
shall remain fixed in their original positions after the sort (i.e. unaffected by the sort).
I tried to adapt quick sort to fit this, but could not think of it. In the end, I decided to adapt the crude selection sort to get the job done:
#include <iostream>
#include <vector>
std::vector<int> numbers = {5,7,1,8,9,3,20,2,11};
template <typename Container, typename Comparator, typename Predicate>
void sortButKeepSomeFixed (Container& c, const Comparator& comp, const Predicate& pred) { // O(n^2), but want O(nlogn) on average (like quick sort or merge sort)
const std::size_t N = c.size();
std::size_t i, j, minIndex;
for (i = 0; i < N-1; i++) {
if (pred(c[i]))
continue; // c[i] shall not swap with any element.
minIndex = i;
for (j = i + 1; j < N; j++) {
if (pred(c[j]))
continue; // c[j] shall not swap with any element.
if (comp(c[j], c[minIndex]))
minIndex = j;
}
if (minIndex != i)
std::swap(c[i], c[minIndex]);
}
}
int main() {
sortButKeepSomeFixed (numbers,
std::greater<int>(), // Ordering condition.
[](int x) {return x % 2 == 0;}); // Those that shall remain fixed.
for (int x : numbers) std::cout << x << ' '; // 11 9 7 8 5 3 20 2 1
}
But the time complexity is O(N^2) (I think). Can someone improve on the time complexity here, to perhaps O(NlogN) on average? In other words, find an overall better algorithm, using recursion or something like that?
Or perhaps a better idea is to take out the elements that satisfy pred
, sort what left with std::sort
and then put the extracted elements back in their original positions? Would that be any more efficient, or would that just make it worse?
Update:
This is based on Beta's suggestion (sorting the iterators that don't pass pred
). But though the elements that pass pred
do indeed remain fixed, the sorting at the end is not correct.
template <typename Container, typename Comparator, typename Predicate>
void sortButKeepSomeFixed (Container& c, const Comparator& comp, const Predicate& pred) {
std::vector<typename Container::iterator> iterators;
for (typename Container::iterator it = c.begin(); it != c.end(); ++it) {
if (!pred(*it))
iterators.emplace_back(it);
}
std::vector<typename Container::iterator> originalIterators = iterators;
std::sort(iterators.begin(), iterators.end(),
[comp](const typename Container::iterator& x, const typename Container::iterator& y)
{return comp(*x, *y);});
for (int i = 0; i < originalIterators.size(); i++)
*originalIterators[i] = *iterators[i];
}
The incorrect output is 11 9 9 8 11 3 20 2 9
when it should be 11 9 7 8 5 3 20 2 1
.
Use the Python List sort() method to sort a list in place. The sort() method sorts the string elements in alphabetical order and sorts the numeric elements from smallest to largest. Use the sort(reverse=True) to reverse the default sort order.
What is Set in C++? As mentioned above, sets in C++ are the type of STL containers that are used for storing elements in a sorted way. The operations allowed to be performed on sets are insertion and deletion. The elements are internally sorted according to a strict weak ordering in a set type container.
Given an array of positive integers. Sort the given array in decreasing order of number of factors of each element, i.e., element having the highest number of factors should be the first to be displayed and the number having least number of factors should be the last one.
That's a fun one. I first tried to code the IMO correct approach, using a custom iterator that just skips elements that satisfy the predicate. This turned out to be quite challenging, at least writing that on a mobile phone as I'm doing it.
Basically, this should lead to code similar to what you can find in Eric Niebler's ranges v3.
But there's also the simpler, direct approach that you're trying to use above. The problem of your non working solution is, that it's changing the values the (rest of the sorted) iterators point to when assigning in that last for
loop. This issue can be avoided by having a copy, like in my code:
int main(int, char **) {
vector<int> input {1,2,3,4,5,6,7,8,9};
vector<reference_wrapper<int>> filtered{begin(input), end(input)};
filtered.erase(remove_if(begin(filtered), end(filtered),
[](auto e) {return e%2==0;}), end(filtered));
vector<int> sorted{begin(filtered), end(filtered)};
// change that to contain reference wrappers to see the issue
sort(begin(sorted), end(sorted),
greater<int>{});
transform(begin(filtered), end(filtered),
begin(sorted),
begin(filtered),
[](auto to, auto from) {
to.get() = from; return to;});
copy(begin(input), end(input),
ostream_iterator<int>{cout, ", "});
return 0;
}
Live example here. Forgot to fork before modifying, sorry.
(Instead of using copies at last for types that are using heap allocated data move
should probably be used. Though I'm not sure whether you can assign to a moved from object.)
Using a ... rather weird ... wrapper class instead of the std::reference_wrapper
makes it possible to achieve the filtered sorting without having to use a vector with (copied or moved) elements of the value type:
template <class T>
class copyable_ref {
public:
copyable_ref(T& ref) noexcept
: _ptr(std::addressof(ref)), _copied(false) {}
copyable_ref(T&&) = delete;
copyable_ref(const copyable_ref& x) noexcept
: _ptr (new int(*x._ptr)), _copied (true) {
}
~copyable_ref() {
if (_copied) {
delete _ptr;
}
}
copyable_ref& operator=(const copyable_ref& x) noexcept {
*_ptr = *x._ptr;
}
operator T& () const noexcept { return *_ptr; }
T& get() const noexcept { return *_ptr; }
private:
T* _ptr;
bool _copied;
};
Upon construction this class stores a pointer to it's argument, which is also modified when the copy assignment operator is used. But when an instance is copy constructed, then a heap allocated copy of the referenced (by the other) value is made. This way, it's possible to swap two referenced values with code similar to
Value a, b;
copyable_ref<Value> ref_a{a}, ref_b{b};
copyable_ref<Value> temp{ref_a};
ref_a = ref_b;
ref_b = temp;
// a and b are swapped
This was necessary because std::sort
doesn't seem to use swap
(found through ADL or std::swap
) but code equivalent to the one above.
Now it's possible to sort a filtered "view" by filling a vector with (not copy constructed) instances of the weird wrapper class and sorting that vector. As the output in the example is showing, there's at most one heap allocated copy of a value type. Not counting the needed size for the pointers inside of the wrapper, this class enables filtered sorting with constant space overhead:
vector<int> input {1,2,3,4,5,6,7,8,9};
vector<copyable_ref<int>> sorted;
sorted.reserve(input.size());
for (auto & e : input) {
if (e % 2 != 0) {
sorted.emplace_back(e);
}
}
sort(begin(sorted), end(sorted),
greater<int>{});
copy(begin(input), end(input),
ostream_iterator<int>{cout, ", "});
cout << endl;
// 9 2 7 4 5 6 3 8 1
Finally, while this works quite well, I probably wouldn't use this in production code. I was especially surprised that std::sort
wasn't using my own swap
implementation, which led to this adventurous copy constructor.
You cannot generalise your code to work for sets and maps: Those are sorted by design, and they need that fixed order to function properly. And the unordered variants are, well, unordered and thus cannot maintain an order. But you can always (as long as you don't modify the container) use std::reference_wrapper
s inside of a vector to provide a sorted "view" of your data.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With