c++ - 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は任意のリストを行います...

編集：

すべての返信に感謝します。私は自分が最もよく理解しているものを受け入れましたが、アルフの答えは僅差でした。私は、全員が C++11 を使用していることに注意し、C++ の初心者として、古い標準を学習する代わりに直接それを採用すべきかどうか疑問に思います。しかし、それはおそらく別の質問に最適です。

score 5 · Accepted Answer

説明するよりもコードを提示する方が短いです。

#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;
}

score 5 · Accepted Answer

奇妙なことにcross_product、C++ アルゴリズムライブラリにはがありません。簡単に追加できますが、ジェリーとアルフの回答が示すように、最善の方法については意見が異なります。実際、私はまだ違うことをします。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 のコードと同様のタプルを作成するデフォルト操作を提供する 2 番目のオーバーロードを提供します。これをさらに抽象化して、2 つ以上の範囲を許可することも考えられます。結局のところ、Python のリスト内包表記では、3 つ以上の範囲を反復処理できます)。

score 4 · Accepted Answer

あなたは確かにこれを一般的にすることができます：

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のコンパイラ）を使用している場合は、少し編集する必要があります。

score 0 · Accepted Answer

0

クラス A と B のテンプレートを作成し、ペアを作成します。std::pair<A, B>

于 2012-12-09T14:22:37.357 に答える

c++ - C ++の外積

4 に答える 4

Related

Reference