排序元素，但保持某些固定 [英] Sort elements, but keep certain ones fixed
问题描述
函数
template <typename Container, typename Comparator, typename Predicate>
void sortButKeepSomeFixed (Container& c, const Comparator& comp, const Predicate& pred)
是根据排序标准 comp 对容器 c 进行排序，但满足 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
}
但时间复杂度O（N ^ 2）（我想）。有人能改善这里的时间复杂度，平均可能O（NlogN）？换句话说，找到一个更好的算法，使用递归或类似的东西？
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?
或者更好的想法是取出满足 pred ，对 std :: sort 进行排序，然后将提取的元素放回原始位置？
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?
更新：
这是基于Beta的建议（排序不迭代的迭代器） pass pred ）。但是，虽然通过 pred 的元素确实保持固定，但结尾的排序不正确。
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];
}
错误的输出是 11 9 9 8 11 3 20 2 9 >
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.
推荐答案
这是一个有趣的。我首先尝试使用一个自定义迭代器来编码IMO正确的方法，该方法只跳过满足谓词的元素。这证明是非常具有挑战性的，至少在我这样做的手机上写。
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.
基本上，这应该导致代码类似于你可以在Eric Niebler的范围v3 中找到。
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;
}
尽管我不确定是否可以分配给一个从对象移动）。 >
使用...而不是奇怪的... wrapper类而不是 std :: reference_wrapper 可以实现过滤排序，而无需使用具有值类型的（复制或移动）元素的向量： / p>
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
这是必要的，因为 std :: sort 似乎不使用 swap （通过ADL或 std :: swap
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.
现在可以通过向一个向量填充一个已过滤的视图（ not copy constructed ）实例的奇怪包装类和排序该向量。如示例中的输出所示，最多有一个堆分配值类型的副本。不包括包装器内指针所需的大小，这个类使用具有恒定空间开销的过滤排序：
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
好吧，我可能不会在生产代码中使用这个。我特别惊讶， std :: sort 没有使用我自己的 swap 实现，这导致了这个冒险的副本构造函数。
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.
您不能将您的代码推广到集和地图：这些按设计进行排序，固定顺序正常工作。并且无序的变体，无序，因此不能维持秩序。但是你可以总是（只要你不修改容器）使用 std :: reference_wrapper 在一个向量内部提供一个排序的视图的数据。
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_wrappers inside of a vector to provide a sorted "view" of your data.
这篇关于排序元素，但保持某些固定的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
