main.cppから複数のファイルに分けるとエラーが出る

Question

C++に慣れるために、線形探索, 二部探索を自作して標準ライブラリのものと比べています。
main.cppにまとめて書いていた関数をsearch_algorithms.h / search_algorithms.cppに分けたのですが、... is used but not defined in this translation unit, and cannot be defined in any other translation unit because its type does not have linkageというエラーが出ます。
ほとんどmain.cpp以外に分けて書いたことがないので、かなり初歩的なミスをしているかもしれませんが、よろしくお願いします。

Wandboxへのリンク↓
正常に動くコード / エラーが出る分割したコード

Answer 1

普通のテンプレートであれば、main.cpp で使いたい型のインスタンスを search_algorithms.cpp で明示的に生成すればいいのですが、C++ のラムダは一つ一つ型が違う (確か...) ので、テンプレートにする場合はヘッダに実装を書くか、実装を別ファイルにしたいなら std::function でラップすればいいと思います。

search_algorithms.h

 namespace my {
 
-template<class Predicate>
+typedef std::function<bool(int)> Predicate;
 Iterator SequentialSearch(Iterator begin, Iterator end, Predicate pred);
 
-template<class Compare>
+typedef std::function<bool(int)> Compare;
 Iterator BinarySearch(Iterator begin, Iterator end, Compare comp);
 }

search_algorithms.cpp

 #include <functional>
+#include <vector>
 #include "search_algorithms.h"
 
 namespace my {
-template<class Predicate>
 Iterator SequentialSearch(Iterator begin, Iterator end, Predicate pred) {
   // 略
 }
 
-template<class Compare>
 Iterator BinarySearch(Iterator begin, Iterator end, Compare comp) {
   // 略
 }

Answer 2

C++のtemplate関数/クラスはtemplate外から利用された時にはじめて実体化されます。
そのせいもあって、宣言と実装をわけるのは大変です。

今回は、ラムダ式の型が翻訳単位に縛られているせいで、テンプレート関数へ渡せる型にならない事が問題となっています。

対処方法としては

• 宣言と実装を一緒にする。

つまりはsearch_algorithms.hにsearch_algorithms.cppの内容を書いてしまう。

• templateではなくstd::functionを用いる。

namespace my {
using Predicate = std::function<bool(int)>;
using Compare = std::function<int(int)>;
Iterator SequentialSearch(Iterator begin, Iterator end, const Predicate& pred);
Iterator BinarySearch(Iterator begin, Iterator end, const Compare& comp);
}

• std::functionを明示的に実体化する。

main.cpp側のテンプレートに渡しているラムダ式をすべてstd::function([&target](const int &cur) { return cur == target; })のように変換し
search_algorithms.cppに

template Iterator SequentialSearch(Iterator begin, Iterator end, std::function<bool(const int&)> pred);
template Iterator BinarySearch(Iterator begin, Iterator end, std::function<int(const int&)> comp);

を記述しておく

テンプレート関数としての利点がなくなりますし、ヘッダにテンプレート関数の実装を書くのが一番いいように思います。

Comments

[退会済みユーザー]

ありがとうございます。

ヘッダに実装を書くのはあまりよろしくないとされているようですが、こういうtemplate関数のときは大抵書いてしまうものなのでしょうか?
練習のコードなので気にするほどのものではないのは確かですが...

[asm]

通常の関数の場合は、確かにヘッダに実装を書いてしまうと不都合がありますが
templateの場合は分けたほうが不都合なので、通常はヘッダに実装を書きます。
STLやboostも大抵の場合はヘッダに書かれています

Answer 3

分割コンパイルのとき、テンプレートの定義はヘッダファイルに記載する必要があります。外部関数と異なり、テンプレートはコンパイル時に展開されるからです。