按公共顶部和底部对一对进行排序

Question

假设您在一个元组中有 n 组元素。例如元组可以是

std::tuple<topBottomStr, topBottomStr, topBottomStr> or
std::tuple<fraction, fraction, fraction>

所以也许有一些模板代表 "topbottomthings"

template<typename T>
class TopBottomThing
{
private:
    T top;
    T bottom;
};

重点是元组中的内容具有顶部和底部的概念。我的问题是，我需要一个 return 是

的函数

std::vector<std::tuple<TopBottomThing>> ArrangeTopBottomThingFunc(std::vector<std::tuple<TopBottomThing>> tup)

其中 return 中的项目值

std::vector<std::tuple<TopBottomThing>> retVal;

的排列使得每个连续条目的 TopBottomThing，std::vector<n> 的底部匹配 std::vector<n + 1> 的顶部，匹配 std::vector<n + 2> 的底部等，或 std::vector<n> 的顶部匹配 std::vector<n + 1> 的顶部，或 std::vector<n> 的底部匹配 std::vector<n + 1> 的底部.只有一种情况可以保证作为函数的约束发生。如果输入向量的长度为n，则保证0个匹配或n - 1个匹配。

例如，如果std::vector<std::tuple<TopBottomThing>> tup 表示标准分数：

2/3 4/5 3/2,

ArrangeTopBottomThingFunc 以 std::vector<tup> 作为输入将 return 按此标准排序 和 std::vector 像这样：

[0] = 3/2 [1] = 2/3 [2] = 4/5（两场比赛 top/bottom）

of if std::tuple tup 有这些分数：

4/7 3/2 1/2

[0] = 3/2 [1] = 1/2 [2] = 4/7（两场比赛 bottom/bottom）

或

4/5 7/8 4/6

[0] 4/5 [1] = 4/6 [2] = 7/8（两场比赛 top/top）

或退化的情况

4/5 6/3 2/7（无匹配项）

会return按照给定的顺序。

或者说std::tuple tup 代表这样的字符串

"Straberry/Banana" "Blueberry/Kiwi" "Kiwi/Banana"

[0] = "Kiwi/Banana" [1] = "Straberry/Banana" [2] = "Blueberry/Kiwi"

三 (n) 个顶部或底部中至少有两个保证匹配。如果该算法适用于

的任何长度，那就太好了

std::vector<std::tuple<TopBottomThing>> input.

它只是对 return 和 std::vector 那些 top/top 或 bottom/bottom 或 top/bottom 匹配的东西进行升序排序。其余不匹配的直接按任意顺序添加。

最后，如果调用函数能够理解事物是如何通过 returning 枚举这样排序的，那就太好了：

enum class WHICHSORT { NO_MATCHES, BOTH_TOP, BOTH_BOTTOM, MIXED_TOP_BOTTOM };

Answer 1

如果我没有正确理解您的问题，我想您是在说您想要确定所有顶部与其他条目匹配或底部与其他条目匹配的 TopBottomThing。然后你想按最小值（顶部，底部）对那些 TopBottomThing 进行排序。

这是我用来做这样的事情的算法。创建一个 std::map 来存储从类型 T（来自 TopBottomThing 的定义）到 size_t 的映射。遍历您的输入，并为每个 TopBottomThing 添加顶部和底部（但前提是与顶部不同）项目到地图。添加新条目时，将值初始化为零。否则，增加现有值。

下一步是创建两个向量：一个用于保存那些匹配某些内容的 TopBottomThing，另一个用于保存不匹配的内容。第二次遍历 TopBottomThing 的列表，并从地图中获取 select max(map[top], map[bottom])。如果该最大值至少为 1，则结果至少与其他条目中的一个匹配，因此将其添加到匹配向量中。否则，将其添加到不匹配向量中。之后，对匹配向量进行排序，然后附加非匹配向量，然后 return 结果。代码如下：

#include <algorithm>
#include <iostream>
#include <map>
#include <random>
#include <vector>

using namespace std;

template<class T>
class TopBottom {
public:
    T top;
    T bottom;

    TopBottom(T _top, T _bottom) : top(_top), bottom(_bottom) {
    }
};

void print(vector<TopBottom<int>> myThings) {
    for (auto topBottom = myThings.begin(); topBottom != myThings.end(); ++topBottom) {
        cout << (topBottom == myThings.begin() ? "(" : "  ");
        cout << topBottom->top << '/' << topBottom->bottom;
    }
    cout << ')';
}

template<class T>
void Arrange(vector<TopBottom<T>> &topBottoms) {
    // Determine the number of TopBottom's with each value for either top or bottom
    map<T, size_t> countOfObjects;
    for (auto topBottom = topBottoms.cbegin(); topBottom != topBottoms.cend(); ++topBottom) {
        ++countOfObjects[topBottom->top];
        if (topBottom->top != topBottom->bottom) {
            ++countOfObjects[topBottom->bottom];
        }
    }

    // Split the input into two lists; one with things that match, and the remainder
    vector<TopBottom<T>> matches;
    vector<TopBottom<T>> nonMatches;
    for (auto topBottom = topBottoms.cbegin(); topBottom != topBottoms.cend(); ++topBottom) {
        auto matchingObjectCount = max(countOfObjects[topBottom->top],
            countOfObjects[topBottom->bottom]) - 1;
        (0 < matchingObjectCount ? matches : nonMatches).push_back(*topBottom);
    }

    // Here you can sort the matches however you want

    // Populate the result
    topBottoms.clear();
    topBottoms.insert(topBottoms.end(), matches.cbegin(), matches.cend());
    topBottoms.insert(topBottoms.end(), nonMatches.cbegin(), nonMatches.cend());
}

int main(int argc, char *argv[]) {
    vector<TopBottom<int>> myThings;
    mt19937 rng;

    for (auto i = 0; i < 20; ++i) {
        myThings.clear();
        myThings.push_back(TopBottom<int>(rng() % 10, rng() % 10));
        myThings.push_back(TopBottom<int>(rng() % 10, rng() % 10));
        myThings.push_back(TopBottom<int>(rng() % 10, rng() % 10));
        myThings.push_back(TopBottom<int>(rng() % 10, rng() % 10));

        print(myThings);
        cout << "  =>  ";

        Arrange(myThings);
        print(myThings);
        cout << endl;
    }

    cin.get();
    return 0;
}

运行此代码生成以下输出：

(2/2  5/4  1/4  5/9)  =>  (5/4  1/4  5/9  2/2)
(3/8  5/5  6/0  0/9)  =>  (6/0  0/9  3/8  5/5)
(4/9  6/7  9/9  9/3)  =>  (4/9  9/9  9/3  6/7)
(6/6  3/6  1/0  9/2)  =>  (6/6  3/6  1/0  9/2)
(8/9  5/6  3/3  8/7)  =>  (8/9  8/7  5/6  3/3)
(6/4  0/5  6/7  4/5)  =>  (6/4  0/5  6/7  4/5)
(2/7  3/8  6/0  6/2)  =>  (2/7  6/0  6/2  3/8)
(7/6  6/4  1/9  8/6)  =>  (7/6  6/4  8/6  1/9)
(0/2  2/2  3/1  2/5)  =>  (0/2  2/2  2/5  3/1)
(9/9  6/1  0/9  8/8)  =>  (9/9  0/9  6/1  8/8)
(3/8  0/9  3/6  3/2)  =>  (3/8  3/6  3/2  0/9)
(9/0  4/9  5/4  6/7)  =>  (9/0  4/9  5/4  6/7)
(1/2  4/0  9/1  5/8)  =>  (1/2  9/1  4/0  5/8)
(0/2  8/1  7/1  8/6)  =>  (8/1  7/1  8/6  0/2)
(8/7  4/6  9/2  0/8)  =>  (8/7  0/8  4/6  9/2)
(5/4  3/7  9/3  5/5)  =>  (5/4  3/7  9/3  5/5)
(5/2  0/1  6/0  1/8)  =>  (0/1  6/0  1/8  5/2)
(0/4  5/8  6/4  0/2)  =>  (0/4  6/4  0/2  5/8)
(0/3  6/9  5/5  8/5)  =>  (5/5  8/5  0/3  6/9)
(8/5  5/8  1/7  3/3)  =>  (8/5  5/8  1/7  3/3)

Answer 2

只需使用std::sort:

template<typename T>
bool MIXED_TOP_BOTTOM(const TopBottom<T>& v1,  const TopBottom<T>&v2)
{
    if( v1.bottom == v2.top )
            return true;
    return false;
}

...

std::vector<TopBottom<int> > data;

data.push_back(TopBottom<int>(2, 3));
data.push_back(TopBottom<int>(4, 5));
data.push_back(TopBottom<int>(3, 2));

std::sort(data.begin(), data.end(), MIXED_TOP_BOTTOM<int>);

生产

3/2 2/3 4/5

按公共顶部和底部对一对进行排序

sort a pair by common top and bottom

c++

sorting

algorithm

variadic-templates