Tricky error during std::find function applied on std::string

An tricky problem is described here that is worth mentioning. Look at this code chunk:

int count(std::string& s, char c) {
 std::string::const_iterator i = std::find(s.begin(), s.end(), c);
 int n = 0;
 while (i != s.end()) {
     n++;
     i = std::find(i+1, s.end(), c);
 }
 return n;
}

If you try to compile this function (offcourse adding main function with required headers), you will find that the first call to find doesn't produce any error. But the second call within the loop generates compilation error of this form:

In function ‘int count(std::string&, char)’:
error: no matching function for call to ‘find(__gnu_cxx::__normal_iterator, std::allocator > >, __gnu_cxx::__normal_iterator, std::allocator > >, char&)’

At first look, it seems to be weird. But it's not :)

The general find function is declared as:

template
InputIterator find(
InputIterator _First,
InputIterator _Last,
const Type& _Val
);

You can see that the type of the first and second parameters of the function template correspond to the same type. The compiler cannot deduce that it is this function that you want to call if your call has a combination of string::const_iterator and string::iterator as arguments.

During first call, i.e. std::find(s.begin(), s.end(), c), the first and second arguments are of string::iterator types and the return value is also of type string::iterator. But this return value is being casted to string::const_iterator.

During second call, i.e. std::find(i+1, s.end(), c), the first argument is of type string::const_iterator (due to that earlier casting) and the second argument is of type string::iterator. So, the types of first and second arguments don't match. That's why , the compiler is generating the error.

Here goes two different types of fixes.

Fix 1:

int count(std::string& s, char c) {
 std::string::iterator i = std::find(s.begin(), s.end(), c);
 int n = 0;
 while (i != s.end()) {
     n++;
     i = std::find(i+1, s.end(), c);
 }
 return n;
}

Fix 2:

int count(const std::string& s, char c) {
 std::string::const_iterator i = std::find(s.begin(), s.end(), c);
 int n = 0;
 while (i != s.end()) {
     n++;
     i = std::find(i+1, s.end(), c);
 }
 return n;
}

Tricky error..isn't it? ;)

Two-stage name lookup issues with template code

The C++ standard prescribes that all names that are not dependent on template parameters are bound to their present definitions when parsing a template function or class. Only names that are dependent are looked up at the point of instantiation. This distinction between lookup of dependent and non-dependent names is called two-stage (or dependent) name lookup. G++ implements it since version 3.4.

Two-stage name lookup sometimes leads to situations with behavior different from non-template codes. The most common is probably this:

//vec.h

#include 

template class Vec : public std::vector {
public:
  Vec() : std::vector () {}
  Vec(int s) : std::vector (s) {}
  T& operator[] (int i) { return at(i);}                      
  const T&operator[] (int i) const { return at(i); }     
};

the call to at() is not dependent on template arguments (there are no arguments that depend on the type T, and it is also not otherwise specified that the call should be in a dependent context). Thus a global declaration of such a function must be available, since the one in the base class is not visible until instantiation time. The compiler will consequently produce the following error message:

vec.h: In member function ‘T& Vec::operator[](int)’:
vec.h:7: error: there are no arguments to ‘at’ that depend on a template parameter, so a declaration of ‘at’ must be available
vec.h:7: error: (if you use ‘-fpermissive’, G++ will accept your code, but allowing the use of an undeclared name is deprecated)
vec.h: In member function ‘const T& Vec::operator[](int) const’:
vec.h:8: error: there are no arguments to ‘at’ that depend on a template parameter, so a declaration of ‘at’ must be available

To make the code valid either use this->at(i), or vector::at(i). Using the -fpermissive flag will also let the compiler accept the code, by marking all function calls for which no declaration is visible at the time of definition of the template for later lookup at instantiation time, as if it were a dependent call. Using -fpermissive to work around invalid code is not recommended however, and it will also only catch cases where functions in base classes are called, not where variables in base classes are used (as in the example above).

Some compilers (including G++ versions prior to 3.4) get these examples wrong and accept above code without an error. Those compilers do not implement two-stage name lookup correctly.

Clear input stream in C++ - fflush(stdin) equivalent in C

You can't use flush to clear the input stream in C++, it's equivilent to using fflush(stdin) for C. Sometimes it works, sometimes it doesn't, but all of the time it's a bad idea.

cin >> flush;

To clear the input stream in C++ use cin.ignore() everytime you think the input stream may still have data in it.

cout<<"Enter your name"<cin.getline(name, 50, '\n'); //ignore not needed, getline does it

cout<<"Enter your age"<cin>>age; cin.ignore(); //clear the newline from the stream

cout>>"Enter your height"<cin>>height; //this will work now

Compilation and linking issues for C++ template classes

The common practice in C++ is to write the class definition in a header file(.h file) and to write the class implementation in a source file(.cpp file). This reason behind this is to keep the interface separate from the implementation. This source file is compiled separately. When we want to use the class in another source file say test_stack.cpp, we need to include the header file in test_stack.cpp. We then need to compile this test_stack.cpp and link the object files to make the executable.

But if we want to follow the same practice for a template class, some linking issues arise.

Linking Issue:

Here goes the source files and header file.

//stack.h



#ifndef STACK_H

#define STACK_H



template class Stack {

    T *v;

    int max_size;

    int top;

public:

    class Underflow {};

    class Overflow {};



    Stack(int s);

    ~Stack();



    void push(T);

    T pop();

};



class Bad_size {};

class Bad_pop {};



#endif



//stack.cpp



#include "stack.h"



template Stack::Stack(int s) {

    top = 0;

    if (10000 < s) throw Bad_size();

    max_size = s;

    v = new T[s];                         

}



template Stack::~Stack() {    

    delete [] v;                          

}



template void Stack::push(T c) {

    if (top == max_size) throw Overflow();

    v[top++] = c;

}



template T Stack::pop() {

    if (top == 0) throw Underflow();

    return v[--top];

}



// test_stack.cpp

#include "stack.h"

#include 

#include 

#include 



Stack sc(10);                       

Stack< std::complex > scplx(10);  

Stack< std::list > sli(10);          



void f() {           

    sc.push('a');

    sc.push('b');

    sc.push('c');

    if (sc.pop() != 'c') throw Bad_pop();



    scplx.push(std::complex(1, 2));

    scplx.push(std::complex(2, 3));

    scplx.push(std::complex(3, 4));



    if (scplx.pop() != std::complex(3, 4)) throw Bad_pop();



    std::cout << "stack of characters, sc: " << sc.pop() << ' ' << sc.pop() << '\n';

    std::cout << "stack of complex numbers, scplx: " << scplx.pop() << ' ' << scplx.pop() << '\n';

}



int main() {

    f();

    return 0;

}

When you try to link the object files created from compiling source files, some linking problems arise:

$ g++ -c stack.cpp 

$ g++ -c test_stack.cpp 

$ g++ -o test_stack stack.o test_stack.o 

test_stack.o: In function `__static_initialization_and_destruction_0(int, int)':

test_stack.cpp:(.text+0x56): undefined reference to `Stack::Stack(int)'

test_stack.cpp:(.text+0x5b): undefined reference to `Stack::~Stack()'

test_stack.cpp:(.text+0x87): undefined reference to `Stack >::Stack(int)'

test_stack.cpp:(.text+0x8c): undefined reference to `Stack >::~Stack()'

test_stack.cpp:(.text+0xb8): undefined reference to `Stack > 

-----

------

------

collect2: ld returned 1 exit status

Reason

When the compiler encounters a declaration of a Stack object of some specific type, e.g., int , it must have access to the template implementation source. Otherwise, it will have no idea how to construct the Stack member functions. And, if you have put the implementation in a source (stack.cpp) file the compiler will not be able to find it when it is trying to compile the client source file test_stack.cpp. And, includeing the header file (stack.h) will not be sufficient at that time. That only tells the compiler how to allocate for the object data and how to build the calls to the member functions, not how to build the member functions. And again, the compiler won't complain. It will assume that these functions are provided elsewhere, and leave it to the linker to find them. So, when it's time to link, you will get "unresolved references" to any of the class member functions that are not defined "inline" in the class definition.

Solution

There are different methods to solve this problem. You can select from any of the methods below depending on which is suitable for your application design:

Way 1

You can create an object of a template class in the same source file where it is implemented
(stack.cpp). So, there is no need to link the object creation code with its actual implementation in some other file. This will cause the compiler to compile these particular types so the associated class member functions will be available at link time. Here goes the changes in stack.cpp:

#include "stack.h"



template Stack::Stack(int s) {                   

    top = 0;

    if (10000 < s) throw Bad_size();

    max_size = s;

    v = new T[s];                                              

}



template Stack::~Stack() {                       

    delete [] v;                                             

}



template void Stack::push(T c) {

    if (top == max_size) throw Overflow();

    v[top++] = c;

}



template T Stack::pop() {

    if (top == 0) throw Underflow();

    return v[--top];

}



// No need to call this temporaryFunction() function,

// it's just to avoid link error.

void temporaryFunction ()

{

    // you need to use those functions here which will be called from test_stack.cpp

    Stack sc(10);

    sc.push('a');

    sc.pop();

}

The temporary function in "stack.cpp" will solve the link error. No need to call this function because it's global.

Way 2

You can #include the source file that implements your template class stack.cpp in your test_stack.cpp source file

#include "stack.h"

#include "stack.cpp"

#include 

#include 

#include 



Stack sc(10);                

Stack< std::complex > scplx(10);

Stack< std::list > sli(10);      



void f() {           

    sc.push('a');

    sc.push('b');

    sc.push('c');

    if (sc.pop() != 'c') throw Bad_pop();



    scplx.push(std::complex(1, 2));

    scplx.push(std::complex(2, 3));

    scplx.push(std::complex(3, 4));



    if (scplx.pop() != std::complex(3, 4)) throw Bad_pop();



    std::cout << "stack of characters, sc: " << sc.pop() << ' ' << sc.pop() << '\n';

    std::cout << "stack of complex numbers, scplx: " << scplx.pop() << ' ' << scplx.pop() << '\n';

}



int main() {

    f();

    return 0;

}

In this case you dont need to compile stack.cpp. You need to compile and link only test_stack.cpp

Way 3

You can #include the source file that implements your template class (stack.cpp) in your header file that defines the template class (stack.h).

#ifndef STACK_H

#define STACK_H



template class Stack {

    T *v;

    int max_size;

    int top;

public:

    class Underflow {};

    class Overflow {};



    Stack(int s);

    ~Stack();



    void push(T);

    T pop();

};



class Bad_size {};

class Bad_pop {};



#include "stack.cpp"



#endif

In this case you dont need to compile stack.cpp. You need to compile and link only test_stack.cpp

Way 4

You need to make the class functions inline i.e. implement those inside stack.h and remove stack.cpp. In this case you need to compile and link only test_stack.cpp