テンプレート クラスに対してアクションを実行する静的テンプレート メンバー関数を作成するにはどうすればよいでしょうか?
-
20-08-2019 - |
質問
std::vector から重複を削除する汎用関数を作成しようとしています。ベクトルの種類ごとに関数を作成したくないので、これを任意の種類のベクトルを受け入れることができるテンプレート関数にしたいと考えています。私が持っているものは次のとおりです。
//foo.h
Class Foo {
template<typename T>
static void RemoveVectorDuplicates(std::vector<T>& vectorToUpdate);
};
//foo.cpp
template<typename T>
void Foo::RemoveVectorDuplicates(std::vector<T>& vectorToUpdate) {
for(typename T::iterator sourceIter = vectorToUpdate.begin(); (sourceIter != vectorToUpdate.end() - 1); sourceIter++) {
for(typename T::iterator compareIter = (vectorToUpdate.begin() + 1); compareIter != vectorToUpdate.end(); compareIter++) {
if(sourceIter == compareIter) {
vectorToUpdate.erase(compareIter);
}
}
}
}
//SomeOtherClass.cpp
#include "foo.h"
...
void SomeOtherClass::SomeFunction(void) {
std::vector<int> myVector;
//fill vector with values
Foo::RemoveVectorDuplicates(myVector);
}
リンカー エラーが発生し続けますが、コンパイルは正常に行われます。私が間違っていることについて何か考えはありますか?
アップデート:Iraimbilanja からの回答に基づいて、コードを書き直しました。ただし、誰かが RemoveDuplicates 関数を実行するための実用的なコードを必要としている場合に備えて、次のとおりです。
//foo.h
Class Foo {
template<typename T>
static void RemoveVectorDuplicates(T& vectorToUpdate){
for(typename T::iterator sourceIter = vectorToUpdate.begin(); sourceIter != vectorToUpdate.end(); sourceIter++) {
for(typename T::iterator compareIter = (sourceIter + 1); compareIter != vectorToUpdate.end(); compareIter++) {
if(*sourceIter == *compareIter) {
compareIter = vectorToUpdate.erase(compareIter);
}
}
}
};
シグネチャで std::vector を指定すると、イテレータが正しく動作しないことがわかりました。そのため、より一般的なアプローチを採用する必要がありました。また、compareIter を消去すると、ループの次の反復でポインタ例外が生成されます。消去時のcompareIterのポストデクリメントにより、この問題が解決されます。また、反復子の比較と、2 番目のループの CompareIter の初期化のバグも修正しました。
更新 2:
この質問がさらに賛成票を集めているのを見たので、C++14 の利点を活用したより良いアルゴリズムで更新しようと考えました。私の以前のものは、ベクトルに格納されている型がoperator==を実装しており、大量のコピーと不要な比較が必要な場合にのみ機能しました。そして、後から考えると、それをクラスのメンバーにする必要はありません。この新しいアルゴリズムにより、カスタムの比較述語が可能になり、重複が見つかったときに比較スペースが縮小され、作成されるコピーの数が大幅に減少します。名前が変更されました erase_duplicates
STL アルゴリズムの命名規則に準拠するため。
template<typename T>
static void erase_duplicates(T& containerToUpdate)
{
erase_duplicates(containerToUpdate, nullptr);
}
template<typename T>
static void erase_duplicates(T& containerToUpdate,
std::function<bool (typename T::value_type const&, typename T::value_type const&)> pred)
{
auto lastNonDuplicateIter = begin(containerToUpdate);
auto firstDuplicateIter = end(containerToUpdate);
while (lastNonDuplicateIter != firstDuplicateIter) {
firstDuplicateIter = std::remove_if(lastNonDuplicateIter + 1, firstDuplicateIter,
[&lastNonDuplicateIter, &pred](auto const& compareItem){
if (pred != nullptr) {
return pred(*lastNonDuplicateIter, compareItem);
}
else {
return *lastNonDuplicateIter == compareItem;
}
});
++lastNonDuplicateIter;
}
containerToUpdate.erase(firstDuplicateIter, end(containerToUpdate));
}
解決
短い答え
ヘッダー内、できればクラス定義内で関数を定義します。
長い答え
.cpp 内でテンプレート関数を定義すると、 #include
d を任意の翻訳単位に変換します。定義されている翻訳単位でのみ使用できます。
したがって、 RemoveVectorDuplicates
コンパイラがテンプレート引数をテキスト置換できる唯一の方法であるため、ヘッダーで定義する必要があります。 インスタンス化する テンプレートを使用して、使用可能なクラスを生成します。
この不便に対する回避策は 2 つあります
初め, を削除できます。 #include "foo.h"
.cpp からコピーし、別のファイルを追加します。 終わり の ヘッダ:
#include "foo.cpp"
これにより、ファイルを一貫して整理できますが、個別のコンパイルの通常の利点 (依存関係が小さくなり、コンパイルが高速でまれになる) は得られません。
2番, .cpp でテンプレート関数を定義し、それが使用されるすべての型に対して明示的にインスタンス化するだけです。
たとえば、これを .cpp の最後に追加して、関数を使用できるようにすることができます。 int
s:
template void Foo::RemoveVectorDuplicates(std::vector<int>*);
ただし、これは、真の汎用性を提供するためではなく、入力の手間を省くためだけにテンプレートを使用することを前提としています。
他のヒント
あなたが持っている1つの選択肢である第1のベクトルをstd::sort()
して、重複を削除するために、既存のstd::unique()
機能を使用します。ソートはO(nlog n)の時間がかかり、そしてそれは、すべての重複が単一のブロックに表示されるだけでO(N)時間を要する後重複を除去します。あなたの現在の "すべて-VS-すべての" 比較アルゴリズムはO(n ^ 2)時間がかかります。
あなたは.cppファイル内のテンプレート機能を実装することはできません。完全な実装は、それがインスタンス化されますどこにでも見えるようにする必要があります。
ちょうどヘッダにおけるクラス定義内の関数を定義します。 これは、テンプレート関数を実装するための通常の方法です。
私はちょうど2つのイテレータを受け取る代わりにコンテナを渡すので、より多くの「一般的な」アプローチを使用することをお勧めします。
このような何かが(それはそれは最後に、最初の)remove_duplicates、および削除のように呼び出すことができますので、イテレータを返します。v.erase(remove_duplicates(v.begin(), v.end()), v.end())
template <typename It>
It remove_duplicate(It first, It last)
{
It current = first;
while(current != last) {
// Remove *current from [current+1,last)
It next = current;
++next;
last = std::remove(next, last, *current);
current = next;
}
return last;
}
あなたの問題に関係のない(既に説明されている)、なぜこの名前空間でグローバルに常駐するよりも、むしろ静的関数のですか?これは多少C ++だろう - IER
。私はコードがコンパイルされることはないと思う....
vectorToUpdate.eraseのstd ::ベクトル* vectorToUpdate ....誰が&があるはず*がある気づくでしょうか?そのコードは絶対にコンパイルされていません。 「 - >」あなたが使用しなければならないベクトルにポインタを使用するつもりなら、「」の代わりに私は、これは実際にはうるさいビットNITである知っているが、それは、コンパイラも...あなたのコードを気にしないことを指摘