Archive

Archive for the ‘STL’ Category

Permutation combinations in Standard C++

January 19, 2010 2 comments

Recently one of my colleagues and also another user in MSDN forum asked a question related to this. The question is as follows…

If I have a string vector with few elements like “Nibu” “Babu” “Thomas”, how can I get all combinations of these three strings? Results should look like…

“NibuBabuThomas”
“NibuThomasBabu”
“BabuNibuThomas”
“BabuThomasNibu”
“ThomasNibuBabu”
“ThomasBabuNibu”

So in C++ there is a standard C++ algorithm function called next_permutation. Use this function on an array of sorted strings to get required result. So some sample code follows…

typedef std::string VT;
typedef std::vector< VT > VTVec;

// For dumping contents of vector to a stream
void Dump( VTVec& VecToPrint, std::ostream& stream )
{
  // Get iterator for given stream, every element will be separated with second
  // parameter.
  std::ostream_iterator<VTVec::value_type> Itr( stream, ", " );
  // Just one line to dump vector contents, no loops needed
  std::copy( VecToPrint.begin(), VecToPrint.end(), Itr );

  // Remove redundant space and bracket ( ", " ) from the end
  stream << "\b\b  \b\b\n";
}// End Dump

int _tmain(int argc, TCHAR* argv[], TCHAR* envp[])
{
  int nRetCode = 0;

  VTVec vecNames;
  vecNames.push_back("Nibu");
  vecNames.push_back("Babu");
  vecNames.push_back("Thomas");

  std::sort(vecNames.begin(), vecNames.end());

  std::cout << "\nNames before applying permutations: ";
  Dump(vecNames, std::cout);
  std::cout << std::endl;

  int Count = 0;
  while(next_permutation(vecNames.begin(), vecNames.end()))
  {
    Dump(vecNames, std::cout);
    ++Count;
  }

  std::cout << "\nFound a total of " << Count << " combinations!\n";
  return nRetCode;
}

Result is as follows…

Advertisements

std::string caveat

Never access an std::string‘s buffer with an intent to increase/decrease it’s length nor pass such a buffer to functions which takes a char*. I did this mistake sometime back and got trapped in a strange bug with operator +=. This is how my code looked.

std::string str( ' ', MAX_PATH );
GetFolderName( pFullPath, &str[0] ); // Oop

Problem with above code is that you won’t get an immediate crash since it’s a properly allocated buffer with MAX_PATH chars. But if you do further operations on such string expect plenty of inconsistencies. This is how my code looked after above piece of code…

str += "\\"; // Append backslash

I was expecting a valid path with backslash appended towards it’s end, but this never happened and debugging with debugger too didn’t help.

So now let me tell you what the exact problem is! When you do &str[0] you pass the address to the first char in std::string‘s buffer. So when function GetFolderName fills in this buffer with folder path the length of std::string is not updated since it’s a C style function and it’s neither expected to do so. So the function terminates given buffer with a ” with std::string‘s length way high (MAX_PATH). So now when I do a += std::string internally fails some condition leading to unexpected results, note that this piece of code never caused a crash but I was quite lucky and watchful enough to fix this stupid bug. Sigh!

So watchout, there is no CString::GetBuffer or CString::GetBufferSetLength type of function for std::string, well at least for now.

Random shuffling of elements in STL containers

March 26, 2009 Leave a comment

Use stl algorithm random_shuffle. This function has two overloads, first version randomizes using it’s own version of random number generator, second function takes a custom random number generator from our side.

void TestShuffle()
{
    typedef short VT;
    typedef std::vector<vt> VTVector;

    // Count of elements
    const VTVector::size_type Size = 10;

    // Create two vector objects
    VTVector Vect( Size );

    // Generate 10 random numbers
    std::generate( Vect.begin(), Vect.end(), rand );
    // Sort them
    std::sort( Vect.begin(), Vect.end() );
    // Shuffle them to demonstrate shuffle!!!
    std::random_shuffle( Vect.begin(), Vect.end() );
}

//Debugger output after generate call...
//10228,19974,5968,8993,14868,12724,4693,25377,32034,7329
//Debugger output after sort
//4693,5968,7329,8993,10228,12724,14868,19974,25377,32034
//Debugger output after random_shuffle call
//4693,14868,10228,19974,12724,7329,32034,8993,25377,5968

Categories: C++, VC++, STL Tags:

back_inserter explained

back_inserter stl iterator class is an adapter class. So what is an adapter? If you buy a laptop in India and then take it to the US/Europe, plugs given won’t fit into the sockets there, so what we do is buy an adapter, which adapts our laptop’s plug to the sockets there. Adapter pattern based class adapts an existing functionality to a close relative of it’s own. Similarly back_inserter adapts a normal iterator to a more dynamic one, which means inserts an element into a vector by increasing it’s size i.e. push_back.

Back_inserter can be given as an iterator to stl algorithms. Lets take a case of reading a file. We don’t know how much bytes are there in a file, so what we do is iterate through to the end of the file along with inserting read in bytes to a vector. This functionality requires a loop, but with back_inserter, we just need one line of code. Here is a demo…

typedef std::vector<char> BytesVector;
BytesVector FileBytes;
std::ifstream file( "C:\\umdhlog.log" );
std::copy( std::istream_iterator< char >( file ), // Starts iterating file
           std::istream_iterator< char >(), // Dummy param to denote EOF
           back_inserter( FileBytes )); // Inserts elements to a vector

Last parameter to std::copy is the key, it’s a back_inserter object. Also note that we’ve given an empty vector and not a resized one. Key to this behavior is the way in which back_inserter behaves, when it inserts an element to a vector it in fact does a push_back. Had we given FileBytes.begin() instead of back_inserter( FileBytes ) there will be a crash.

Another example to fill in a vector with hundred random numbers using back_inserter…

typedef std::vector<int> IntVector;
IntVector Ints;
std::generate_n(std::back_inserter( Ints ), 100, rand);

A close relative of back_inserter is front_inserter used mainly with std::lists.

Reading contents of a file to a vector at one go!

January 19, 2009 Leave a comment

It’s quite easy to read the contents of a file to a vector at one go. For this we need to get the size of a file and ask vector to allocate a buffer to hold these many bytes (use vector::resize()). Here is a function which does this. Note that it’s a byte/char vector.

#include "vector"
#include "fstream"

void ReadFileToVector( const char* FileName, std::vector<char>& FileBuff )
{
   using namespace std;

   ifstream ifile;
   ifile.open( FileName, ios::in );

   // Get file size
   ifile.seekg(0, ios_base::end);
   streamoff FileSize = ifile.tellg();
   ifile.seekg(0, ios_base::beg);

   // Resize vector to file size
   FileBuff.resize( FileSize, 0 );
   // Read in file contents to buffer
   ifile.read(&FileBuff[0], FileSize);
}

Benefit of using a vector instead of a char pointer is that we don’t have to do memory management and also we are directly accessing this buffer so no reallocations occur internally but we’ll have to check for allocation failure after calling vector::resize since files can be of huge sizes. You can optimize this further, post a comment if you find any issue/optimization. Also note that there are other ways to achieve the same behavior for e.g. using istream_iterator and back_inserter but this does cause frequent reallocations in a vector IMO making things slower.

%d bloggers like this: