1

編集：さらに詳細を追加しました。

n 個の配列の交点 (すべてに共通する点) を見つけるアルゴリズムを作成しようとしています。私のプログラムはこれらの配列を受け取り、操作が行われる 2 次元配列に格納します。たとえば、main メソッドの例を次に示します。

int a[] = { 12, 54, 42 };
int b[] = { 54, 3, 42, 7 };
int c[] = { 3, 42, 54, 57, 3 };

IntersectionTableau<int> x(3);    // Where 3 is the max number of arrays allowed
                                  // to be stored.
x.addArray(a, 3);
x.addArray(b, 4);
x.addArray(c, 9);
x.run();            // Finds the intersection.

これらの追加された配列は に保存されT** arrays、そのサイズはint* sizes. T はジェネリック型です。ジェネリック型の可変数の配列でこれを実行できる効率的なアルゴリズムは何ですか?

これが私が現在やろうとしていることです：

template <class T>
inline
void IntersectionTableau<T>::run() {
    T* commonElements = d_arrays[0];
    for (int i = 1; i < d_currentNumberOfArrays; ++i) {
        commonElements = getIntersection(commonElements, d_arrays[i], d_sizes[i - 1], d_sizes[i]);
    }
    d_results = commonElements;
}



template <class T>
inline
T* IntersectionTableau<T>::getIntersection(T* first, T* second, int sizeOfFirst, int sizeOfSecond) {
    T* commonElements;
    if (sizeOfFirst > sizeOfSecond) {
        commonElements = new T[sizeOfFirst];
    } else {
        commonElements = new T[sizeOfSecond];
    }
    for (int i = 0; i < sizeOfFirst; ++i) {
        for (int j = 0; j < sizeOfSecond; ++j) {
            if (first[i] == second[i]) {
                commonElements[i] = first[i];
            }
        }
    }
return commonElements;

}

最初の関数は、最初の 2 つの配列を受け取り、それらを 2 番目の関数に送信します。2 番目の関数は、これら 2 つの配列の交点の配列を返します。次に、最初の関数は交差配列を次の配列と比較d_arraysします。私の問題は、d_results生成されたガベージ値から要素を出力しようとするときです。その理由はわかりません。誰かが私が間違っていること、またはこれを達成するためのより良い方法を教えてもらえますか?

4

1 に答える 1

1

コードには少なくとも 2 つの問題があります。

if (first[i] == second[i])

これはする必要がありますif (first[i] == second[j])。

commonElements[i] = first[i];

これは修正するのが難しいです。別の変数が必要だと思います（どちらiでもないj）; それを呼びましょうk：

commonElements[k++] = first[i];

とにかく、C++ を使用できるので、std::vector代わりに a を使用できます。そのサイズを内部に保存します。これにより、混乱が軽減されます。

template <class T>
std::vector<T> // note: adjusted the return type!
IntersectionTableau<T>::getIntersection(...)
{
    std::vector<T> commonElements;
    for (int i = 0; i < sizeOfFirst; ++i) {
        for (int j = 0; j < sizeOfSecond; ++j) {
            if (first[i] == second[j]) {
                commonElements.push_back(first[i]);
            }
        }
    }
    return commonElements;
}

firstandをベクトルに変換することもできsecondます (ただし、現時点ではあまりメリットはありません)。

注意すべき点を次に示します。

  • 戻り値の型をに変更しましたvector<T>
  • 配列を返す古いバージョンでは、結果の長さを指定する追加のコードが必要です。このバージョンは、vector<T>オブジェクト内の長さを返します
  • 配列を返す古いバージョンではdelete[] array、メモリ リークを防ぐために、後でどこかが必要です。
  • vector-to-pointer ハック&commonElements[0]は空の場合は機能しませんvector

他のコードが配列/ポインターで動作する場合、ライフタイム ルールを尊重するために、関数の外でvector-to-pointer hack を使用できます。&commonElements[0]

T* commonElements = NULL;
for (int whatever = 0; whatever < 10; ++whatever)
{
    std::vector<T> elements = xxx.getIntersection(...); // will work
    commonElements = &elements[0]; // can pass this pointer to a function receiving T*
    print(commonElements); // will work
}
print(commonElements); // cannot possibly work, will probably segfault
print(elements); // cannot possibly work, and compiler will reject this
于 2013-10-31T21:01:56.033 に答える