std::search example on vector and string

Continuing from last weeks theme, here is a simple example of std::search.

//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
#include <iostream>
#include <vector>
#include <string>
#include <algorithm> //needed for std::search

using namespace std;

bool isOdd(int i) 
{
  return ((i%2)==1);
}

int main()
{
  vector<int> v1;
  v1.push_back(88);
  v1.push_back(99);
  v1.push_back(22);
  v1.push_back(33);
  v1.push_back(44);
  v1.push_back(55);
  v1.push_back(66);
  v1.push_back(77);

  //Demonstrating Search - Matching Case
  vector<int> v2;
  v2.push_back(22);
  v2.push_back(33);
  v2.push_back(44);

  vector<int>::const_iterator it = search(v1.begin(), v1.end(), v2.begin(), v2.end());
  if(it != v1.end())
  {
    cout<<"Found: "<<*it<<endl;
    cout<<"Position = "<<it - v1.begin() + 1<<endl;
  }
  else
  {
    cout<<"Not Found"<<endl;
    cout<<"Position = -1"<<endl;
  }

  //Demonstrating Search - Non-Matching Case
  vector<int> v3;
  v3.push_back(22);
  v3.push_back(33);
  v3.push_back(444); //non matching

  it = search(v1.begin(), v1.end(), v3.begin(), v3.end());
  if(it != v1.end())
  {
    cout<<"Found: "<<*it<<endl;
    cout<<"Position = "<<it - v1.begin() + 1<<endl;
  }
  else
  {
    cout<<"Not Found"<<endl;
    cout<<"Position = -1"<<endl;
  }

  //Use the search to find strings
  string s1="Hello, this is Zahid";

  //Matching case
  string s2="Zahid";

  string::const_iterator it2 = search(s1.begin(), s1.end(), s2.begin(), s2.end());
  if(it2 != s1.end())
  {
    cout<<"Found: "<<*it2<<endl;
    cout<<"Position = "<<it2 - s1.begin() + 1<<endl;
  }
  else
  {
    cout<<"Not Found"<<endl;
    cout<<"Position = -1"<<endl;
  }

  //Non-Matching case
  string s3="None";

  it2 = search(s1.begin(), s1.end(), s3.begin(), s3.end());
  if(it2 != s1.end())
  {
    cout<<"Found: "<<*it2<<endl;
    cout<<"Position = "<<it2 - s1.begin() + 1<<endl;
  }
  else
  {
    cout<<"Not Found"<<endl;
    cout<<"Position = -1"<<endl;
  }

  return 0;
}

The output is as follows:

std::find and std::find_if for finding information in vectors

Here is a simple program that demonstrates how to use find and find_if with vectors.

//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
#include <iostream>
#include <vector>
#include <algorithm> //needed for std::find

using namespace std;

bool isOdd(int i) 
{
  return ((i%2)==1);
}

int main()
{
  vector<int> v1;
  v1.push_back(88);
  v1.push_back(99);
  v1.push_back(22);
  v1.push_back(33);
  v1.push_back(44);
  v1.push_back(55);
  v1.push_back(66);
  v1.push_back(77);

  //Demonstrating Find - Find number 55 and its position, if present
  vector<int>::const_iterator it = find(v1.begin(), v1.end(), 55);
  if(it != v1.end())
  {
    cout<<"Found: "<<*it<<endl;
    cout<<"Position = "<<it - v1.begin() + 1<<endl;
  }
  else
  {
    cout<<"Not Found"<<endl;
    cout<<"Position = -1"<<endl;
  }

  //Demonstrating Find IF - Find the first Odd number and its position
  it = find_if(v1.begin(), v1.end(), isOdd);
  if(it != v1.end())
  {
    cout<<"Found: "<<*it<<endl;
    cout<<"Position = "<<it - v1.begin() + 1<<endl;
  }
  else
  {
    cout<<"No Odd Numbers Found"<<endl;
    cout<<"Position = -1"<<endl;
  }

  return 0;
}

The output is as follows:

Interesting Challenging problem on Code Complexity

Picked up this interesting problem from the following book:



How many execution paths can this simple three line code take:

String EvaluateSalaryAndReturnName( Employee e )
{
  if( e.Title() == "CEO" || e.Salary() > 100000 )
  {
    cout << e.First() << " " << e.Last() << " is overpaid" << endl;
  }
  return e.First() + " " + e.Last();
}

The answer may surprise you. I have embedded the actual pages from Google books. Luckily the whole problem and solution is given. See Item 18.

The size_t confusion

Apparently there could be a lot of confusion with regards to size_t. In 'C' the size_t was defined as an unsigned integer. 'C++' defines it as unsigned integer as well but it has a namespace of std around it. Some compilers may want #include<cstdlib> to use std::size_t.

In any case, it can cause quite some confusion among programmers as to why it is used and what is the size of it. Instead we can #define a type, give it a meaningful name and use it accordingly. Here is my simple example:

//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
#include<iostream>
#include<cstdlib> //Used for std::size_t ... on some compilers

#define u16 unsigned short
#define u32 unsigned //integer is implicit

int main()
{
  size_t size = sizeof(size_t);
  std::cout << "Size of size_t is " << size << std::endl;

  std::size_t size2 = sizeof(std::size_t);
  std::cout << "Size of std::size_t is " << size2 << std::endl;

  size_t size3 = sizeof(u16);
  std::cout << "Size of u16 is " << size3 << std::endl;

  size_t size4 = sizeof(u32);
  std::cout << "Size of u32 is " << size4 << std::endl;

  return 0;
}

The output is as follows:

Interview Question on the Slicing Problem

Someone was talking about the Slicing Problem with classes in one of the companies we do projects for. As the name states, the Slicing problem arises when a part of the class is Sliced away. This will happen when derived class is assigned to the base class. Here is a simple example that is also been used for interviews:

//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
#include<iostream>

using namespace std;

class Parent
{
public:
  virtual void func_a(void);
};

class Child : public Parent
{
public:
  void func_a(void);
};

void func_1(Parent p);
void func_2(Parent* p);
void func_3(Parent& p);


int main()
{
  //Using the Parent class
  Parent p;
  cout<<"\nParent Class"<<endl;
  func_1(p);
  func_2(&p);
  func_3(p);

  //Using the Child class
  Child c;
  cout<<"\n\nChild Class"<<endl;
  func_1(c);
  func_2(&c);
  func_3(c);

  //Using the Parent class that is initialised to class
  Parent p2 = c; //Note that in p2, additional info about c would be lost
  cout<<"\n\nParent p2 Class"<<endl;
  func_1(p2);
  func_2(&p2);
  func_3(p2);

  //Not possible to initialise directly from base to derived class. 
  //Child c2 = p2; - ERROR: cannot convert from 'Parent' to 'Child'
  //The way round it would be to have a constructor or overload operator = 

  return 0;
}

void Parent::func_a()
{
  cout<<"Parent::func_a()"<<endl;
}

void Child::func_a(void)
{
  cout<<"Child::func_a()"<<endl;
}

void func_1(Parent p) 
{ 
  cout<<"func_1 -> ";
  p.func_a(); 
} 

void func_2(Parent* p) 
{ 
  cout<<"func_2 -> ";
  p->func_a(); 
} 

void func_3(Parent& p) 
{ 
  cout<<"func_3 -> ";
  p.func_a(); 
} 

The output is as follows:

Printing Debug information through Macros

This example shows probably one of the most useful case for using Macro's. Since Macro's are expanded before the code is compiled, debug information like filename and line number is available in the macro to be used.

//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
#include<iostream>

using namespace std;

#define PRINT_DEBUG_INFO \
  cout<<__DATE__<<" "<<__TIME__<<": "<<__FUNCTION__<<", "<<__FILE__<<", "<<__LINE__<<endl;
//Note that __TIMESTAMP__ can be used instead of __DATE__ and __TIME__

void func1(int* someNum)
{
  if(someNum)
  {
    //Perform normal operations here
    int someVar=0;
  }
  else
  {
    //Abnormal scenario
    PRINT_DEBUG_INFO;
  }
}

void func2(int *); //forward declaration of func2

int main()
{
  int *x = NULL;
  func1(x); //Creating exception scenario
  func2(x); //Creating exception scenario

  return 0;
}

void func2(int* someNum)
{
  try
  {
    //Normal case here
    if(someNum)
      *someNum = 100;
    else
      throw 0;
  }
  catch(...) //Abnormal case
  {
    PRINT_DEBUG_INFO;
  }
}

The output is as follows:
Please note that in the above example, the __DATE__ and __TIME_ functions return the compilation date and time, not the current date and time. More details here.

To get the current execution date and time, see this example.

C++ example of 'transform'

From the CPP Reference:
#include

1. output_iterator transform( input_iterator start, input_iterator end, output_iterator result, UnaryFunction f );
2. output_iterator transform( input_iterator start1, input_iterator end1, input_iterator2 start2, output_iterator result, BinaryFunction f );

The transform algorithm applies the function f to some range of elements, storing the result of each application of the function in result.

The first version of the function applies f to each element in [start,end) and assigns the first output of the function to result, the second output to (result+1), etc.

The second version of the transform works in a similar manner, except that it is given two ranges of elements and calls a binary function on a pair of elements.

Here is an example that is modified from C++ Reference:

//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
//Program to show how transform works in C++

#include<iostream>
#include<vector>
#include<algorithm> //for the transform() function

using namespace std;

int increase (int i) { return ++i; }
int sum (int i, int j) { return i+j; }

int main()
{
  int someNums[] = {10,20,30,40,50}; //Array of 5 values
  //Another way to initialise a vector using the iterator constructor
  vector<int> vectorOne (someNums, someNums + sizeof(someNums) / sizeof(int)); 
  vector<int> vectorTwo;
  vector<int>::iterator it;

  cout<<"vectorOne elements are : ";
  for(unsigned int i = 0; i < vectorOne.size(); ++i)
    cout<<vectorOne[i]<<" ";
  cout<<endl;

  vectorTwo.resize(vectorOne.size()); //allocate space

  //OutputIterator transform ( InputIterator first1, InputIterator last1,
  //                           OutputIterator result, UnaryOperator op );
  std::transform(vectorOne.begin(), vectorOne.end(), vectorTwo.begin(), increase);

  cout<<"\nAfter transform with increase:"<<endl;
  cout<<"vectorOne elements are : ";
  for(unsigned int i = 0; i < vectorOne.size(); ++i)
    cout<<vectorOne[i]<<" ";
  cout<<endl;
  cout<<"vectorTwo elements are : ";
  for(unsigned int i = 0; i < vectorTwo.size(); ++i)
    cout<<vectorTwo[i]<<" ";
  cout<<endl;

  //OutputIterator transform ( InputIterator1 first1, InputIterator1 last1,
  //                           InputIterator2 first2, OutputIterator result,
  //                           BinaryOperator binary_op );
  transform (vectorOne.begin(), vectorOne.end(), vectorTwo.begin(), vectorOne.begin(), sum);

  cout<<"\nAfter transform with sum:"<<endl;
  cout<<"vectorOne elements are : ";
  for(unsigned int i = 0; i < vectorOne.size(); ++i)
    cout<<vectorOne[i]<<" ";
  cout<<endl;
  cout<<"vectorTwo elements are : ";
  for(unsigned int i = 0; i < vectorTwo.size(); ++i)
    cout<<vectorTwo[i]<<" ";
  cout<<endl;

  return 0;
}

The output is as follows:

Example of 'functors'

What are 'functors?'

Depending on what you prefer to read, there are many definitions and explanations of Functors.

From the function pointer tutorial:

Functors are functions with a state. In C++ you can realize them as a class with one or more private members to store the state and with an overloaded operator () to execute the function. Functors can encapsulate C and C++ function pointers employing the concepts templates and polymorphism. You can build up a list of pointers to member functions of arbitrary classes and call them all through the same interface without bothering about their class or the need of a pointer to an instance. All the functions just have got to have the same return-type and calling parameters. Sometimes functors are also known as closures. You can also use functors to implement callbacks.

From StackOverflow:

• A functor is pretty much just a class which defines the operator(). That makes it "look like" a function.
• Another advantage to a functor over a pointer to a function is that the call can be inlined in more cases.
• You can use boost::function, to create functors from functions and methods
  

Here is a simple example of functors that I have created using mishmash from various places:

//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
//Program to demonstrate the use of functors

#include<iostream>

using namespace std;

class someClass
{
public:
  someClass(int x) : someVariable(x) {}
  int operator()(int y) {return (someVariable + y);}
  int internalStateValue(){return someVariable;}

private:
  int someVariable;
};

int main()
{
  someClass class1(50);
  someClass class2(75);

  cout<<"Class1 state variable value is : "<<class1.internalStateValue()<<endl;
  cout<<"Class2 state variable value is : "<<class2.internalStateValue()<<endl;

  int test1 = class1(22);
  cout<<"Test 1 value is : "<< test1<<endl;
  int test2 = class2(22);
  cout<<"Test 2 value is : "<< test2<<endl;

  cout<<"Class1 final state variable value is : "<<class1.internalStateValue()<<endl;
  cout<<"Class2 final state variable value is : "<<class2.internalStateValue()<<endl;

  return 0;
}

The output is as follows:

Deleting of Vectors content to avoid memory leaks

Its interesting how deleting of vectors can sometimes be a problem as people tend to make simple mistakes that can cause crash and waste useful hours to debug.

The following code shows my approach to deleting of vectors. I am sure there are better approaches. In case you know one please share.

//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
//Program to demonstrate a simple way to delete vector and memory
//associated with it.

#define _CRTDBG_MAP_ALLOC
#include <stdlib.h>
#include<iostream>
#include <crtdbg.h>
#include<vector>

#ifdef _DEBUG
#define DEBUG_NEW new(_NORMAL_BLOCK, __FILE__, __LINE__)
#define new DEBUG_NEW
#endif

using namespace std;

int main()
{
  _CrtSetDbgFlag( _CRTDBG_ALLOC_MEM_DF  _CRTDBG_LEAK_CHECK_DF );
  vector<int *> someVector;
  for(int i = 0; i < 5; i++)
  {
    int* x = new int(i * 15);
    someVector.push_back(x);
  }

  //now we need to delete the elements of the vector else it will generate memory leaks
  //This is one simple and safe approach
  while (!someVector.empty())
  {
    vector<int *>::iterator it = someVector.begin();
    if(*it) //Additional safety in case a NULL pointer was stored
      delete (*it); //because *it = *int - Only the contents are deleted
    someVector.erase(it);
  }

  return 0;
}

You can check my old post on how to see if memory leaks are there. This program shows another approach but the results are the same

No output needed.

You can read more about this approach of detecting memory leaks on the MSDN site here.

Case-Insensitive String comparison

It is often a problem that we ask someone to input some string for comparison but they often put different case and the comparison fails. For example if we are expecting a string, say, 'true'. The user may input 'True' or 'TRUE'. A simple comparison will fail in this case.

The following is a simple program to convert the input string to lower case. What this would allow is to do a case-insensitive search.

//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
#include<iostream>
#include<string>

using namespace std;

//First approach for converting into lower case
string toLowerString(string& input)
{
  int length = input.length();
  string output;
  for(int i = 0; i < length; i++)
  {
    output += tolower(input[i]);
  }
  return output;
}

//Second approach for converting into lower case
string toLowerString(string& input, bool approach2) //Overloaded method
{
  int length = input.length();
  string output;
  for(int i = 0; i < length; i++)
  {
    if(input[i] >= 0x41 && input[i] <= 0x5A) //Ascii for A-Z
      output += (input[i] + 0x20); //ascii for a-z
    else 
      output += input[i];
  }
  return output;
}

int main()
{
  string s1="true";
  string s2("TRUE");
  string s3;
  s3 = "True";

  //Check if s1 = s2
  if(s1 == s2)
    cout<<"s1 == s2"<<endl;
  else
    cout<<"s1 != s2"<<endl;

  //Check if s1 = s2 with first approach
  if(s1 == toLowerString(s2))
    cout<<"s1 == Approach1::toLowerString(s2)"<<endl;
  else
    cout<<"s1 != Approach1::toLowerString(s2)"<<endl;

  //Check if s1 = s2 with second approach
  if(s1 == toLowerString(s2,true))
    cout<<"s1 == Approach2::toLowerString(s2)"<<endl;
  else
    cout<<"s1 != Approach2::toLowerString(s2)"<<endl;


  //Check if s1 = s3 with second approach
  if(s1 == s3)
    cout<<"s1 == s3"<<endl;
  else
    cout<<"s1 != s3"<<endl;

  if(s1 == toLowerString(s3,true))
    cout<<"s1 == Approach2::toLowerString(s3)"<<endl;
  else
    cout<<"s1 != Approach2::toLowerString(s3)"<<endl;

  //Check if s1 = s3 with second approach
  if(s1 == toLowerString(s3)) 
    cout<<"s1 == Approach1::toLowerString(s3)"<<endl;
  else
    cout<<"s1 != Approach1::toLowerString(s3)"<<endl;

  return 0;
}

The output is as follows:


I am aure much better approaches are possible. If you have a better example please share.