Archive

Posts Tagged ‘stl’

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.

Working with the STL iterators

February 3, 2009 Leave a comment

Almost every programmer some how gets involved with STL iterators while programming. I’m quite fond of these concepts. So what exactly is an iterator?

STL stands for the Standard Template Library which has different flavors or implementations floating around with different compilers but the concept and structure behind all of them is the same. It’s a bunch of c++ classes which makes the life of programmer’s easy by providing implementations for popular data structure algorithms like…

  1. Singly/doubly linked lists
  2. Stack
  3. Queue
  4. DQueue
  5. Vector – used by almost everyone
  6. Map
  7. Hashed maps
  8. And others

So our point of discussion is what the heck does an iterator do and what is it for? Well as the name suggests it’s a way to traverse a list of items which can be ordered or unordered, in a generic fashion. Let’s see some examples of iterators…

typedef std::vector<int> IntVector; // Represents a dynamic list of integers
IntVector Ints;
Ints.push_back( 10 ); // Add one int
Ints.push_back( 20 ); // Add one more int

Now we have a vector of integers with two ints. So to get first integer in this list we use following function…

IntVector::iterator Itr = Ints.begin(); // First int

And to get to next integer we simply use ++Itr/Itr++. Every STL container has it’s own flavor of ++(pre and post) operator. For e.g. for a list it will be moving to next element, for an output stream iterator it will be moving to next field in a file etc. So by now you might have understood how powerful the concept of an iterator is. In STL for traversing a container according to standard we must always use an iterator.

Note that it’s not correct to directly do a ‘+1’ or ‘-1’ with an iterator. It’s dangerous when container for an iterator changes. It’s quite ok with a vector (only if the iterator is a pointer) but a big disaster with lists. So for this purpose STL provides us with two functions std::advance and std::distance. As you might have understood by now std::advance advances an iterator by a count and std::distance returns the number of elements between two iterators. This will work with both ordered and unordered containers. So a poor alternative to Ints.size() will be std::distance(Ints.begin(), Ints.end()) ;). To increment our previous Itr by one we’ll do std::advance(Itr, 1) instead of Itr + 1. Also never check for NULL on an iterator, always check against corresponding container’s end() function since this is what represents an invalid case in STL containers.

If you’ve noticed a detail of iterators, it’s that they are very generic. For e.g. our previous Itr object represents an iterator for a std::vector but even if we change the container type to std::list still there won’t be any change in iterator part. That’s cool isn’t. I enjoy programming in STL these days. I’m trying to get into the details of this wonderful library. Will keep posting bits and bytes on whatever I find in this library.

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.

Some interesting uses of count_if stl algorithm function!

September 9, 2008 2 comments

STL algorithm count_if function is a fun function with some serious usages associated with it. Main benefit of using count_if is that we can use normal character arrays/pointers along with normal CRT functions like isupper, islower etc.

Using count_if to get count of lower/upper case characters in a string

Just one function call and we get count of lower/upper case characters. No loops written by us. 🙂

char SomeString[]    = "Nibu loves Jesus Christ, these Tips are dedicated to Him. Read John 3:16 for the reason.";
const size_t Len = strlen(SomeString)-1;
int LowerCaseCount   = (int)std::count_if( &SomeString[0], &SomeString[Len], islower );
int UpperCaseCount   = (int)std::count_if( &SomeString[0], &SomeString[Len], isupper );

Using count_if to get count of alpha numeric characters in a string

int AlnumCount = (int)std::count_if( &SomeString[0], &SomeString[strlen(SomeString)], isalnum );

Using count_if to get count of odd/even numbers in an integer array

bool IsOdd( const int Num ){  return ( Num % 2 != 0 ); }
bool IsEven( const int Num ){ return ( Num % 2 == 0 ); }

int Numbers[100] = { 0 };
// Fill with random numbers
std::generate( &Numbers[0], &Numbers[_countof(Numbers)], rand );
int OddCount  = (int)std::count_if( &Numbers[0], &Numbers[_countof(Numbers)], IsOdd );
int EvenCount = (int)std::count_if( &Numbers[0], &Numbers[_countof(Numbers)], IsEven );

The secret is that, compiler finds out type of template arguments passed in and also makes sure that function arguments are given appropriate types, during compilation compiler knows what are the types passed to a function hence this is possible.

Last argument to count_if is a functor. A functor is a function object with an overridden function call operator. Real cool part is that even CRT functions are treated as functors. 🙂 Isn’t this simple.

There are plenty more uses of std::count_if and I hope this post acts as a starter for you explore the stl library.

Dumping contents of a vector/list to cout

August 2, 2008 Leave a comment

Is it possible to do this with just one line of code? Oh yes!

Have a look…

typedef int VT;
typedef std::vector VTVec;

void Dump( VTVec& VecToPrint, std::ostream& stream, const char* lpszMsg )
{
// We will be wrapping every element within a square bracket.
// In the end output looks like this… [123] [864] [
stream << lpszMsg << "["; // Get iterator for given stream, every element will be seperated with second // parameter. std::ostream_iterator 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 // After this statement the series will look like [123] [864] stream << "\b\b \b\b\n"; }// End Dump int _tmain(int argc, TCHAR* argv[], TCHAR* envp[]) { VTVec VecObj( 10000, 0 ); // Fill vector with random number, see earlier post on std::generate std::generate( VecObj.begin(), VecObj.end(), rand ); // Dump to std::cout Dump( VecObj, std::cout, "Dumping vector of ints...\n" ); }// End _tmain[/sourcecode]

Filling out a vector using generate function

August 2, 2008 Leave a comment

Let us suppose that you want to fill out a vector with 10000 random elements, phew. Hmm so what you would do is to write a for loop, iterate through, and fill out the elements.

Well I can do it with just one line of code. 🙂 Look

// Typedefs
typedef int VtElem;
typedef std::vector<vtelem> Vector;
const Vector::size_type Size = 10000;

Vector VecObj( Size );
// Look at the last parameter, it needs a callback function pointer/function object/functor,
// we've given standard c "rand" function to fill out vector with random elements.
std::generate( VecObj.begin(), VecObj.end(), rand );

So now we have a vector that has been randomly been filled out. We can replace rand with any kind of filling in method. You can even have a vector full of prime numbers using a prime functor.

There is another version of std::generate called std::generate_n, which as the name suggests generates upto n elements.

Looks like this…

// Fill just 10 elements with random numbers
std::generate_n( VecObj.begin(), 10, rand );

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

Initializing vector elements to a particular value

August 2, 2008 1 comment

There are 8 constructors for std::vector class, out of which there is this constructor that takes two parameters…

vector( size_type _Count,  const Type& _Val );

First parameter is size of the vector, second is default value for all elements in the vector.

Let’s suppose you have 1000 Employees in your organization each of them has an initial salary of Rs 8000, we would like to maintain information related to them using a vector. This is how we will be declaring the vector object and initializing every Employee element in it to to have an initial salary of 8000.

class Employee
{
   public:
       Employee() : m_Salary( 0 )
       {}
       explicit Employee( const int Salary ) : m_Salary( Salary )
       {}
  private:
       int m_Salary;
};// End class Employee

// Typedefs
typedef Employee Emp;
typedef std::vector<emp> EmpVector;

// 1000 employees with salary member variable of every employee instance in
// our vector initialized to 8000
EmpVector EmpVecObj( 1000, Employee( 8000 ));

Categories: C++, VC++ Tags: , ,
%d bloggers like this: