Wednesday, May 15, 2013

C++ that isn't (how to use std containers and algorithms in place of C constructs)

I like stackoverflow a lot. It saved me more than once. 

Whenever I can, I try to help other people out to pay it forward

When looking for questions tagged C++ (that I fell reasonably comfortable answering), every so often there is one that is asking a question related to data structures and algorithms. 

However, the question is almost entirely written in C code, like this one (paraphrased):


The goal of this exercise is to remove duplicates from an array. 
Ask the user to enter 10 integers and remove the duplicate array elements. For example, given the input 1,2,2,3,3,4,4,4,5,6, the output should be 1,2,3,4,5,6.
The sample (and broken) code in the question was something in the lines of nested loops:
 #include <iostream>  
 using namespace std;  
 int main()  
 {  
   int numbers[10];  
   cout << "Enter 10 integers pressing return after each one\n";  
   for( int i=0; i<10; i++ )  
    cin >> numbers[i];  
   int count=10;  
   for( int i=0; i<=10; i++ )  
   {  
    for( int x=i+1; x<=10; x++ )  
    {  
      if( numbers[x]==numbers[i] )  
      {  
       count--;  
       for( int t=x; t<=count; t++ )  
         numbers[t] = numbers[t+1];  
      }  
    }  
   }  
   cout << endl;  
   cout << " You entered "<< count << " unique numbers: " << endl;  
   for( int i=0; i<count; i++ )  
    cout << numbers[i] << " ";  
   return 0;  
 }  

The usual response is to fix the code.

However, if the question is tagged as C++, a better solution would be to point the person to C++ data structures and algorithms.

The code below solves the problem using std::sort and std::unique (with a little help of std::erase to clean up the vector).

 #include <iostream>  
 #include <vector>  
 using namespace std;  
   
 int main(int argc, const char * argv[])  
 {  
   vector<int> v;  
   
   cout << "Please input 10 integers, hitting return after each one \n";  
   for( int i = 0; i < 10; i++ ) {  
    int num;  
    cin >> num;  
    v.push_back(num);  
   }  
   
   sort( v.begin(), v.end() );  
   v.erase( unique( v.begin(), v.end() ), v.end() );  
   
   cout << endl << " You entered " << v.size() << " unique numbers: " << endl;  
   copy( v.begin(), v.end(), ostream_iterator<int>( cout, " " ) );  
 }  

After I offered that solution, a fellow stackoverflow user offered an even better one using std::set:

 #include <iostream>  
 #include <set>  
 #include <iterator>  
   
 using namespace std;  
   
 int main(int argc, const char* argv[])  
 {  
   set<int> s;  
   
   cout << "Please input 10 integers, hitting return after each one \n";  
   for( int i = 0; i < 10; i++ ) {  
    int num;  
    cin >> num;  
    s.insert(num);  
   }  
   cout << endl << " You entered " << s.size() << " unique numbers: " << endl;  
   copy( s.begin(), s.end(), ostream_iterator<int>( cout, " " ) );  
 }  
   


There are many great books out there about C++ styles and idioms (covering C++ data structures, algorithms and more). 

The ones I like the most:

Accelerated C++: Practical Programming by Example: short and to the point C++ book. If you have time for nothing else when learning C++, go over this book. I guarantee you will know more C++ than the average programmer out there (if my sample is representative). Also great when transitioning from C or Java (and related languages) to C++.

Effective C++: 55 Specific Ways to Improve Your Programs and Designs (3rd Edition): specific techniques to improve C++ programming. They can be read once a day, as individual topics. In about two months, your C++ will be much improved.

The C++ Standard Library: A Tutorial and Reference (2nd Edition): a reference book, useful even in the age of Google. One of the books I use the most when writing code. I had to buy it two or three times because my copies "created legs". I didn't mind. I'm sure it helped my fellow programmers. I'd rather work with well informed colleagues anyway. Learned a lot from this one. 

No comments:

Post a Comment