Sunday, July 22, 2012

Eliminate duplicates and sort the list

Recently I received a List of zipcodes from a carrier. The zipcodes were duplicated and were not sorted. So I just wrote a small C++ code to sort and eliminate the duplicates from the list of zipcodes.

The program simply uses the set container in C++ STL, for the task. The set has the property that, it doesn't store duplicates. So, all we need to do is, insert all the elements (from the input file), into the set. And since set is also ordered in nature (implemented as a Red Black Tree), we can iterate over it to yield a sorted list. Below is the code-

#include <fstream>
#include <sstream>
#include <string>
#include <set>

using namespace std;

inline int convert(string &s)
{
int out;
istringstream ss(s);
ss >> out;
return out;
}

int main()
{
ifstream infile("input.txt");
ofstream outfile("output.txt");

string line;
int zipcode; //zipcode is just a integer

set<int> zipcodes;

while (getline(infile, line))
{
zipcode = convert(line);
zipcodes.insert(zipcode);
}

for (auto i = zipcodes.begin(); i != zipcodes.end(); i++)
outfile << *i << '\n';

infile.close();
outfile.close();

return 0;
}

To some, one keyword might have confused, that is "auto", in the for loop as -
auto i = zipcodes.begin() ;
Well, it was introduced in C++11 standard, to let the programmer omit typing the type of variable. The compiler well deduce the type by looking at the type of RHS. And I believe it is rather nice introduction, seeing how it can save you from rather ugly expressions. If you are using gcc with version prior to 4.7, you need to add a flag -std=c++0x while compiling in terminal or enable this flag in your IDE (if it is not already).

No comments:

Post a Comment