how to get rid of two errors in template linked list code?

[misslyss]

i have two errors but I'm unsure if they're because i declared the template wrong or something. i read all the tutorials but i don't seem to understand templates very well. at line four it says C++ requires a type specifier for all declarations. and at this line: cout << find(stringList, "efg", 5) << endl; it says no matching function for call to 'find'. heres the code

#include <iostream>
#include <string>
using namespace std;

template <typename C,typename T> find (C , T , int);

template<typename T>

int find(const T list[], T key, int arraySize)
{
    int low = 0;
    int high = arraySize - 1;
    while (high >= low)
    {
        int mid = (low + high) / 2;
        if (key < list[mid])
            high = mid - 1;
        else if (key == list[mid])
            return mid;
        else
            low = mid + 1;
    }
    
    return -1;
}
int main()
{
    
    int intList[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
    double doubleList[] = {2.1, 4.2, 7.3, 10.4, 11.5, 45.6, 50.7, 59.8, 60.9, 66.10, 69.11, 70.12, 79.13};
    string stringList[] = {"abc","efg","xyz"};
    
    cout << find(intList, 2, 13) << endl;
    cout << find(doubleList, 59.8, 13) << endl;
    cout << find(stringList, "efg", 5) << endl;
    system("PAUSE");
    return 0;
}

i would appreciate if you could explain what i did wrong so i know for next time not to make the same mistakes :) thanks

[andywestken]

Well...

On line 5 of your posted code,

template <typename C,typename T> find (C , T , int);

you've forgotten the return type. C++ needs to know it (unlike C, which assumes int if you don't say otherwise.)

When I added the return type I got linker errors complaining about missing implementations of find() for types int, double, and string based on the declaration. So I just commented it out.

And for the implemented template function to work, line 35 needs to be

cout << find(stringList, string("efg"), 5) << endl;

The string() is needed as your template expects the type of the first two params to be an array of T and a T. You gave an array of strings and a constant string literal which is not compatible with the template function.

Andy

[jlb]

For the first problem please explain what you are trying to do with this line:

template <typename C,typename T> find (C , T , int);

For the second problem look at this line:
cout << find(stringList, "efg", 5) << endl;
Do you realize that "efg" is a const char* not a std::string? You either need to cast that char* to a std::string or use a string variable with that value.

[misslyss]

andywestken: thanks for looking at the code for me. how would you recommend fixing the linker errors? i thought i did implement find
jlb: i thought i was declaring the template class? and thanks for looking at the code for me :)

[andywestken]

how would you recommend fixing the linker errors?

Delete line 5 -- it's not needed.

i thought i did implement find

The signature on line 5 does not match that on line 9 -- so there is no implementation for the first version of find() that you declared.

I don't know the details of the argument-dependent name lookup (Koenig lookup) mechanism, but it appears that

template <typename C, typename T> find (C , T , int);

is a better match than

template<typename T> int find(const T list[], T key, int arraySize);

so it tries to use the unimplemented function.

Altering line 5 to:

template <typename C, typename T> find (const C[], T , int);

does allow the program to build. But neither of the follow work:

template <typename C,typename T> int find (C[], T , int);

template <typename C,typename T> int find (const C, T , int);

Andy

[andywestken]

PS

Actually, if I make all your arrays all const the compiler does decide to use the right version of the template, as now the second version is a better match.

Of if I remove the const from the signature of the find function on line 9.

If you make some but not all of the arrays const, you can reduce the number of linker errors.

Andy

#include <iostream>
#include <string>
using namespace std;

#define USE_CONST

template <typename C, typename T> int find (C, T , int); // now with int return type

#ifdef USE_CONST
template<typename T>
int find(const T list[], T key, int arraySize)
#else
template<typename T>
int find(T list[], T key, int arraySize) // no const
#endif
{
    int low = 0;
    int high = arraySize - 1;
    while (high >= low)
    {
        int mid = (low + high) / 2;
        if (key < list[mid])
            high = mid - 1;
        else if (key == list[mid])
            return mid;
        else
            low = mid + 1;
    }
    
    return -1;
}
int main()
{
#ifdef USE_CONST
    // now all const
    const int intList[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
    const double doubleList[] = {2.1, 4.2, 7.3, 10.4, 11.5, 45.6, 50.7,
                                 59.8, 60.9, 66.10, 69.11, 70.12, 79.13};
    const string stringList[] = {"abc","efg","xyz"};
#else
    int intList[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
    double doubleList[] = {2.1, 4.2, 7.3, 10.4, 11.5, 45.6, 50.7,
                           59.8, 60.9, 66.10, 69.11, 70.12, 79.13};
    string stringList[] = {"abc","efg","xyz"};
#endif

    cout << find(intList, 2, 13) << endl;
    cout << find(doubleList, 59.8, 13) << endl;
    cout << find(stringList, string("efg"), 5) << endl; // with string constructor
    system("PAUSE"); // system() it evil!!
    return 0;
}

(For a more C++ way -- than the evil system() call -- to stop the console closing down, see: Console Closing Down
http://www.cplusplus.com/forum/beginner/1988/ )

[misslyss]

why do you consider system() evil? i have used it multiple times in the past. also what does #ifndef #else and #endif do? also when i ran it it said pause command not found

[andywestken]

why do you consider system() evil?

See Duoas' post here:

Why system() is evil
http://www.cplusplus.com/forum/articles/11153/

what does #ifndef #else and #endif do?

They are preprocessor directives (like #include) -- #ifdef, #ifndef, and #endif are used to control which blocks of code get fed to the actual compiler.

When you build a C++ program (a) each source file is preprocessed to create a single 'file' known as 'translation unit', (b) the translation unit is compiled to create an object file, and (c) all the object files are linked together, along with the necessary libraries, to create the final program (or library or DLL/shared object.)

It's during the pre-processor phase all the # (preprocessor) directives are acted on to create a single temporary 'file' (don't think it's on disk these days, just in memory usually) which will include the text from not only the .cpp file but that from all the #included header files, and in which all the conditional blocks have have been kept or thrown away, and all #defines (macros and consts) resolved.

If you're curious you can get the compiler to create this preprocessor output file for you. (Sometimes this is even useful if somethings gone wrong with the prepeocessing, as you search though the file to find out what's gotten confused!) For MSVC you need to specify the /P compiler switch. For the GCC compiler it's -E

See here for the details:

Preprocessor directives
http://www.cplusplus.com/doc/tutorial/preprocessor/

Andy

[misslyss]

thanks for clearing that up for me! would you mind helping me out with 2 problems I'm having with another code? it has to do with evaluating arithmetic expressions