C++中的叉积运算

Question

以下是Python代码（来源：http://norvig.com/sudoku.html）：

def cross(A, B):
    "Cross product of elements in A and elements in B."
    return [a+b for a in A for b in B]

cols     = '123456789'
rows     = 'ABCDEFGHI'
squares  = cross(rows, cols)

这将产生如下结果：

['A1', 'A2', 'A3', 'A4', 'A5', 'A6', 'A7', 'A8', 'A9', 'B1', 'B2', 'B3', ...]

作为练习，我想在C++中做同样的事情。目前我有：

#include <iostream>
#include <map>
#include <vector>

using std::string;
using std::vector;

static vector<string> cross_string(const string &A, const string &B)
{
    vector<string> result;

    for (string::const_iterator itA = A.begin(); itA != A.end(); ++itA) {
        for (string::const_iterator itB = B.begin(); itB != B.end(); ++itB) {
            char s[] = {*itA, *itB, 0};
            result.push_back(string(s));
        }
    }
    return result;
}

int main(int argc, char** argv)
{
    const char digits[] = "123456789";
    const char rows[]   = "ABCDEFGHI";

    vector<string> res = cross_string(rows, digits);

    for (vector<string>::const_iterator it = res.begin();
         it != res.end(); ++it) {
        std::cout << *it << std::endl;
    }
}

这个方法是可行的，但我希望有更好的方式。此外，这仅适用于字符串，而Python可以使用任何列表...

---

编辑：

感谢所有回复。我接受了我最理解的答案，但Alf的答案也很接近。我注意到所有答案都使用了C++11，并想知道作为一个C++新手，我是否应该直接采用它，而不是学习旧标准。但这可能最好另外提问。

- William Morris

---

如果一定要发表，只有放在[codereview.se]上比较合适。 - millimoose

@millimoose：怎么了？询问如何最好地计算这个（这与询问如何改进给定的代码略有不同）似乎是SO上一个有效的问题。如果它不包括代码，那肯定属于这里，我认为显示作者已经尝试过并没有改变什么。 - Grizzly

@Grizzly SO是用于“我正在尝试做X，但因为Y而失败。” Code Review是“我已经完成了X并且它可以工作，但我不喜欢它。” 我所应用的标准是缺乏需要解决的明确定义问题。（“我认为可能有更好的解决方案”并没有提供一个清晰的答案标准。） - millimoose

@millimoose：我认为他已经阐明了一个需要解决的明确问题：“它只适用于字符串”。让它适用于其他类型对我来说似乎是一个非常明确的答案标准。 - Jerry Coffin

@millimoose：在我看来，代码审查是为了“这是我的代码，有什么建议可以改进它”，而SO则是“我有这个问题，如何解决它”。问题可能可以更清楚地表述，但对于我来说，隐含的如何使其适用于其他类型以及如何更优雅地编写（当给出更短的Python代码时，更好的自然解释）似乎足够具体，使其属于这里而不是代码审查（因此基本上我不同意问题缺少明确定义的问题的观点）。 - Grizzly

@Grizzly“如何使其适用于任何类型？”是一个有效的SO问题，但应该直接提出，而不是在代码中含蓄地暗示或提及。 OP真正想要的取决于他们自己的决定和措辞。此外，“如何更优雅地编写此代码？”只是另一种说“我不喜欢它”的方式。 - millimoose

Answer 1

其实直接呈现代码比解释更省事:

#include <iostream>         // std::wcout, std::endl
#include <string>           // std::string
#include <utility>          // std::begin, std::end
#include <vector>
using namespace std;

string sum( char const a, char const b ) { return string() + a + b; }

template< class Container >
auto cross( Container const& a, Container const& b )
    -> vector< decltype( sum( *begin( a ), *begin( b ) ) ) >
{
    typedef decltype( sum( *begin( a ), *begin( b ) ) ) ResultItem;
    vector< ResultItem >   result;

    for( auto&& itemA : a ) for( auto&& itemB : b )
    {
        result.push_back( sum( itemA, itemB ) );
    }
    return result;
}

wostream& operator<<( wostream& stream, string const& s )
{
    return (stream << s.c_str());
}

template< class Item >
wostream& operator<<( wostream& stream, vector<Item> const& v )
{
    stream << "[";
    bool isFirstItem = true;
    for( auto&& item : v )
    { 
        if( !isFirstItem ) { stream << ", "; }
        stream << item;
        isFirstItem = false;
    }
    stream << "]";
    return stream;
}

int main()
{
    string const cols       = "123456789";
    string const rows       = "ABCDEFGHI";
    auto const squares      = cross( cols, rows );

    wcout << squares << endl;
}

- Cheers and hth. - Alf

---

@William：这是C++11的特性。你需要一个更新的编译器，或者使用启用C++11特性的编译器选项。 - Cheers and hth. - Alf

将这个扩展到n元交叉积是有趣的，特别是如果你想将构建的字符串数量减少到乘积大小的对数级别。当然，这是很愚蠢的，因为输出大小随输入数量呈指数增长，但是... - Yakk - Adam Nevraumont

@William：clang与gcc非常接近，事实证明该代码可以在MinGW g++ 4.7.1上编译通过。抱歉，我没有安装clang（据报道，在Windows中异常处理无法正常工作）。 - Cheers and hth. - Alf

@WilliamMorris：作为一个原则，我反对“清理评论”，因为那是篡改历史。想象一下清理纽伯格协议，删除所有看起来现在不相关的内容，或者只删除一个观点。当然，现在我提到了与希特勒的联系，这里就没有更严肃的评论了，而且它也让你现在已经删除的评论有了不同的意义！明白了吗？ - Cheers and hth. - Alf

我认为这更多是关于评论是否对后续读者有帮助的问题。我的编译器问题可能不会 :-) - William Morris

Answer 2

奇怪的是，在C++算法库中缺少cross_product。它可以很容易地添加，但正如Jerry和Alf的回答所示，人们对如何做到最好意见不一。事实上，我会做得更不同。Jerry的接口符合其他C++算法的接口，但他没有抽象出交叉乘积操作，而我会这样做：

template <typename InputIt1,
          typename InputIt2,
          typename OutputIt,
          typename F>
void cross_product(InputIt1 begin1,
                   InputIt1 end1,
                   InputIt2 begin2,
                   InputIt2 end2,
                   OutputIt out,
                   F f) {
    for (auto i = begin1; i != end1; ++i)
        for (auto j = begin2; j != end2; ++j)
            *out++ = f(*i, *j);
}

在您的示例中，调用将如下所示：

auto digits = "1234546789";
auto chars = "ABCDEFGHI";
vector<string> result;

cross_product(digits, digits + strlen(digits),
              chars, chars + strlen(chars),
              back_inserter(result),
              [](char a, char b) { return string() + a + b; });

我是不是很喜欢C++11？是的，我很喜欢。

在一个合适的库中，我会提供第二个重载函数，它提供了一个默认的f操作，类似于Jerry的代码创建了一个元组。甚至可以进一步抽象化，允许多于两个范围的迭代 - 毕竟，Python列表推导允许您迭代超过两个范围。

- Konrad Rudolph

---

关于“最佳实践”的观点不同，我认为这些方法并不是真正的竞争对手。我选择编写OP直接要求的函数。如果有更多时间，它将被重构为内部使用类似Jerry代码的东西，也会被提供。然后，它将被重构为使用您更通用的代码，也会被提供...所以这不是非此即彼的问题。就像，一切，谢谢！ - Cheers and hth. - Alf

相关的是，我认为C++对新手来说不太容易上手的部分原因是标准库缺乏合理的默认值和适当的“全部”而不是“二选一”。例如，一个sort函数，我们可以只写sort(a)，而不是sort(begin(a), end(a))，这样太冗长了，对于最常见的情况来说自由度太高了，在我看来。 - Cheers and hth. - Alf

他们试图在C++11中添加基于容器的算法，但由于技术上的头疼而失败。可能是因为概念被遗弃了，而概念会使基于容器的算法变得容易... - Yakk - Adam Nevraumont

Answer 3

您可以将此设置为通用：

template <class InIt1, class InIt2, class OutIt>
void cross_product(InIt1 b1, InIt1 e1, InIt2 b2, InIt2 e2, OutIt out) {  
    for (auto i=b1; i != e1; ++i) 
        for (auto j=b2; j != e2; ++j) 
            *out++ = std::make_pair(*i, *j);
}

请注意，通常不要将模板参数设置为集合中对象的类型，而是应该设置为集合的迭代器类型。例如，您可以这样使用它：

std::ostream &operator<<(std::ostream &os, std::pair<char, int> const &d) { 
    return os << d.first << d.second;
}

int main() { 
    std::vector<char> a{'A', 'B', 'C', 'D'};
    std::vector<int> b{ 1, 2, 3, 4};

    cross_product(a.begin(), a.end(), b.begin(), b.end(),
        infix_ostream_iterator<std::pair<char, int> >(std::cout, ", "));
    return 0;
}

...这应该会产生类似于这样的输出：

A1, A2, A3, A4, B1, B2, B3, B4, C1, C2, C3, C4, D1, D2, D3, D4

请注意，我在这段代码中使用了一些C++11的特性。如果您使用的是较旧的编译器（或来自Microsoft的编译器），则需要进行一些编辑。

- Jerry Coffin

---

嗯，简短整洁...现在把它变成一个函数？<g> - Cheers and hth. - Alf

@Cheersandhth.-Alf：原帖中有提到他真的想要它成为一个函数吗？如果是这样，我可能错过了。他给出了一个函数，并说他希望有“更好的方法”，但我甚至没有看到任何暗示“更好的方法”必须是一个函数。 - Jerry Coffin

嗯，好吧，有些事情暗示着OP想要一个函数...比如，在Python示例之后说，“我想在C++中做同样的事情”。或者，提供一个C++函数示例怎么样？但是，无论OP是否需要它，重点是集中提供结果变量等琐碎细节，使调用代码更清晰、更表达式化。顺便说一下，这正是移动语义的重点所在，因此你可以看到它很重要。Andrei曾经在C++03中尝试过他的“Mojo”。但是C++11的解决方案更加简洁。表达式，而不是命令！ :-) - Cheers and hth. - Alf

谢谢Jerry。有没有一种非11的方法来进行向量初始化（a{'A'，'B'...）？infix_ostream_iterator是你自己的还是常见的东西？ - William Morris

@WilliamMorris：如果没有C++11，你可能最好的向量初始化方法大概是Boost.Assign。我在之前的问题中发布了infix_ostream_iterator。 - Jerry Coffin

Answer 4

为类A和B进行模板化，然后创建一对std::pair<A, B>

。

- stefan