問題描述
我想要做什么:我想對 2、3 或 N 個向量進(jìn)行排序,鎖定在一起,不將它們復(fù)制到一個元組中.也就是說,把冗長放在一邊,比如:
What I want to do: I want to sort 2, or 3, or N vectors, locked together, without copying them into a tuple. That is, leaving verbosity aside, something like:
這應(yīng)該輸出:
我現(xiàn)在的做法:我已經(jīng)實現(xiàn)了我自己的快速排序,其中我傳遞的第一個數(shù)組用于比較,并且排列應(yīng)用于所有其他數(shù)組.我只是不知道如何重用 std::sort 來解決我的問題(例如提取排列).
How I am doing it right now: I have implemented my own quicksort, where the first array I pass is used for the comparison, and the permutations are applied to all other arrays. I just couldn't figure out how to reuse std::sort for my problem (e.g. extract permutations).
我嘗試過的: boost::zip_iterator 和 boost::zip_range(帶有 boost::combine 范圍),但 std::sort 和 boost::range::algorithm::sort 抱怨迭代器/范圍是只讀的,而不是隨機訪問......
What I've tryed: boost::zip_iterator and boost::zip_range (with boost::combine range), but both std::sort and boost::range::algorithm::sort complain that the iterators/ranges are read only and not random access...
問題: 如何在鎖步(壓縮)中對 N 個向量進(jìn)行排序?這個問題看起來非常普遍和常見,所以我想通過一個可能非常復(fù)雜的庫必須有一個簡單的解決方案,但我找不到它......
Question: How do I sort N vectors in lock step (zipped)? The problem looks pretty generic and common so I guess there must be an easy solution through a probably very complex library but I just can't find it...
備注: 是的,stackoverflow 中也有類似的問題,這個問題以不同的形式被問到很多.但是,它們總是以以下答案之一關(guān)閉:
Remarks: yes, there are similar questions in stackoverflow, this question gets asked a lot in different forms. However they are always closed with one of the following answers:
- 將您的向量復(fù)制到一對/元組中并對該元組進(jìn)行排序...
- 將您的向量復(fù)制到一個結(jié)構(gòu)中,每個向量有一個成員,并對結(jié)構(gòu)向量進(jìn)行排序...
- 針對您的特定問題實現(xiàn)您自己的排序功能...
- 使用輔助索引數(shù)組...
- 使用 boost::zip_iterator 不帶示例或帶有產(chǎn)生不良結(jié)果的示例.
提示:
- 我在 boost 郵件列表 指向 Anthony Williams 的這篇論文.雖然這似乎只適用于成對,但他們也討論了 TupleIteratorType,但我找不到它.
- user673679 找到了 這篇 帖子包含一個很好的解決方案,適用于兩個容器的情況.它還確定了問題(重點是我的):
- I've found this thread in the boost mailing list which points to this paper from Anthony Williams. Although this seems to only work for pairs, they also discus a TupleIteratorType but I haven't been able to find it.
- user673679 found this post containing a nice solution for the two container case. It also nails down the problem (the emphasis is mine):
[...] 根本問題是對"數(shù)組引用的行為不像它們應(yīng)該的那樣 [...] 我只是決定濫用迭代器的符號并編寫一些有效的東西.這實際上涉及編寫一個不符合規(guī)范的迭代器,其中值類型的引用與引用類型不同.
[...] the fundamental problem is that "pairs" of array references do not behave like they should [...] I simply decided to abuse the notation of an iterator and write something that works. This involved writing, effectively, a non-conforming iterator where the reference of the value type is not the same as the reference type.
答案:見下面 interjay 的評論(這也部分回答了未來的問題):
未來問題:上一個答案適用于序列容器.我們能否讓它也適用于 sortable 容器(例如序列和列表)?這將需要 random_access 和雙向 TupleIterator 以及適用于雙向迭代器的排序算法.
Future question: the previous answer works for sequence containers. Could we get it also to work on sortable containers (e.g. sequences and lists)? This would require random_access and bidirectional TupleIterators as well as a sort algorithm that works on bidirectional iterators.
更新:這適用于類似序列的容器的組合.但是,混合列表需要 std::sort 支持雙向迭代器(不支持).
Update: this works for combinations of sequence-like containers. However mixing a list would require that std::sort supported BidirectionalIterators (which does not).
推薦答案
這是一個基于 range-v3 的工作示例 已建議標(biāo)準(zhǔn)化的庫
Here's a working example based on the range-v3 Library that has been proposed for Standardization
實時示例(需要具有良好 C++14 支持的最新編譯器,不是 VS 2015).
Live Example (requires recent compiler with good C++14 support, not VS 2015).
這篇關(guān)于使用 boost 或 STL 在 C++ 中對壓縮(鎖定)容器進(jìn)行排序的文章就介紹到這了,希望我們推薦的答案對大家有所幫助,也希望大家多多支持html5模板網(wǎng)!