Permutations in C++

A small simple sample that illustrates how to get the various permutations of the characters of a string in C++ using std::next_permutation provided under the standard include <algorithm>.

[code]
#include<algorithm>
#include<string>
#include<vector>
#include <iostream>

int main()
{
    std::string input="ABC";
    std::vector<std::string> perms;
    perms.push_back(input);
    std::string::iterator itBegin = input.begin();
    std::string::iterator itEnd = input.end();
    while(std::next_permutation(itBegin, itEnd))
    {
        perms.push_back(std::string(itBegin, itEnd));
    }
    std::copy(perms.begin(), perms.end(), std::ostream_iterator<std::string>(std::cout, "\n"));
}
[/code]

Remove duplicates from vector

Q. How do you remove duplicates from a vector?

A. This is how:

    template<typename T>
    void removeDuplicates(std::vector<T>& vec)
    {
        std::sort(vec.begin(), vec.end());
        vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
    }

If I needed a container to keep itself populated of only unique values, I would probably choose std::set but then choosing the right container depends on so many other different factors as well.

Edit Comment : Corrected above by replacing remove with erase as there isn't such a member function in std::vector. std::erase, however, is and the code works with just that replacement.

Zero-sized arrays

It is valid to do the below:

    T * ptr = new T[0];

0 is a perfectly valid input to the array form of new expression. What is the use of it, you may ask. No use as far as the array is concerned. What use is an array if it does not have any members? What can you possibly do with it? Nothing! Right, you cannot do anything with it but the statement above being valid is atleast a little bit helpful.

It allows you to have code like this:

void f(size_t n)
{
     int * ptr = new int[n];
     //...
     delete[] ptr;
}

instead of:

void f(size_t n)
{
     if (n>0)
     {
         int * ptr = new int[n];
         //...
         delete[] ptr;
     }
}

No other use though as said earlier, because since it has zero elements, you cannot do anything with it.

This reminds of another peculiar extension related to zero sized/unsized arrays. VC++ has an extension which makes use of zero sized arrays as the last member of structures. For example, see this:

#include<cstdlib>
#include<iostream>

struct test
{
     int cb;
     int buf[];
};

int main()
{
     test* bb;
     int length = 10;
     bb = (test*) malloc(sizeof(test)+sizeof(int)*length);
     bb->cb = length;
     //fill buf with length int items or can copy from another array for length elements
     bb->buf[i]=10; //i should be less than length
     //OR--------
     test aa = {10, {1,10,22,32}};
     std::cout << aa.buf[2];
}

Since the zero size member is in there, there are few restrictions as well. You cannot create an array of the test struct. You can mimic that though like this:

    //create an array of length 10 of test pointers
    test * ptr[10];
    //set each of the pointers to individual elements created as above

Generally, you would be better off keeping a pointer member but it is
worth noting the presence of such an extension. See for details :
Unsized arrays.

The rationale as per msdn is saving the runtime pointer dereferences and that is not specific to C. How big that overhead is, with respect to the application in order to make a choice to this extension, is a different story altogether. You could even implement std::vector<T> using this extension rather than having a pointer to type T! That is, std::vector<T> implementation with VC++ might use this extension but they don't do so. :-)

Interesting one, this one... isn't it? :-)

Handling dynamic array allocations

One of the recent questions on the forums, that I answered to recently, was related to using std::auto_ptr<> with allocations from array form of new. The need to know was - if the following would work?

        std::auto_ptr<int> ptr(new int[100]);

if not then why not?

The answer was simple if one knows what std::auto_ptr<> is good for, what its deleter is. std::auto_ptr<> uses delete operator to destruct owned pointer (pointing to a dynamic allocation made via new operator). So, it comes down to mixing of constructs like array form of new and simple delete. That is undefined behaviour as per the standards. You can read up more about these operators here - Free New, Delete Malloc

By design, the standard auto_ptr<> smart pointer is not suitable for dynamic array allocations. There can be many alternatives though. Few of those are as listed below:

• Avoid self memory management and instead use std::vector<> / std::deque<> for dynamic arrays.
• Use boost::scoped_array<>/boost::shared_array<>/boost::shared_ptr<> with a custom deleter (delete[]) passed in.
• Write your own smart pointer : auto_ptr_array<> (same implementation as std::auto_ptr<>) just that it uses array form of delete instead of delete.

For the second point above - you can read more about custom deleters and shared_ptr<> here - Custom deleters with smart pointers

A boost::shared_array<>/boost::shared_ptr<> might not be the right choice if you don't want the reference count overhead of shared ownership which really should not be required when talking about auto_ptr<>s but if that's not an issue to worry about, it should work fine.

Another confusion arose, why doesn't std::auto_ptr<> do a delete[] instead of delete? Well, again, because it is not intended for array allocations. It would hence not work for singular objects created on the free store. This is because of the way delete[] might be implemented by the compiler.

There can be many ways in which delete[] could be implemented. Two of those are explained here - How does delete[] know how many elements to destroy? It is important for delete[] to know how many elements to destroy particularly since it is used with non-POD types as well and there, the destructor calls are necessary to be made for each of the to-be-destructed elements of the array.

The first method listed in the C++ FAQ Lite uses an extra allocation to remember the size you ask for at the runtime, if you used delete[] for single allocations, the compiler might try to interpret the block before the pointer you call it on as being size but since that was not allocated in the first place (new[] was not used!) - expect anything to happen, a crash or any other form of runtime error (depending upon how that error is translated on a particular system).

For the second, where array length association might not exist, it could cause anything depending upon a number of factors about the compiler implementation. One such possibility is, it could leave the variable uninitialized (yeah, its a bad thing, may not actually be happening, but who knows for sure about all compilers? We are just talking of possibilities here) - in which case the size could be anything - even 2 which goes beyond the buffer you allocated and again can cause any fault to the system/system free store. If the size is initialized to 0, it could leave the memory untouched and hence lost resulting in a leak. Memory leaks can be really dangerous particularly on systems that don't reclaim the leaked blocks by a process.

So, when the standard says, its undefined behaviour, it can result in anything. Worse could happen and thinking about these issues beyond the statement of "undefined behaviour" is rather silly. There can be many such "interesting" stories that one can write up. The key is, use std::auto_ptr<> what it is suited for, use delete/delete[] what they are suited for. Mixing them is really dangerous.

There is a peculiarity to note though. If you do the allocation for the single element using array form of new - you could use delete[] for that single element. That is:

        int * ptr = new int[1];
        delete[] ptr; //OK

Well, not really a peculiarity, but yeah, something to take note of.

Forum reference : What's wrong with std::auto_ptr<int> ptr(new int[100]);?

Functors with state - 4 (alternative solution using stable_partition)

The is the fourth installment in this series - Functors with state - 1.

Here, what we shall try to do is meet the requirements with a different algorithm. This algorithm does not suffer from the problem that remove_if does as explained in here - Functors with state - 2. But can we be real sure that it is only associated with remove_if and not any of the other algorithms using state maintaining function objects? Well, lets leave that for now.

In this alternate solution, I shall exploit the std::stable_partition algorithm that will help us partition the vector contents based on a predicate test and give the iterator to the element at the partition point. Here is the code that shows how to achieve it.

[CODE]

#include<algorithm>
#include<vector>
#include<iostream>

template<typename T>
struct IsEvenIndex{
               private:
                               mutable/*static*/ typename std::vector<T>::size_type index;
               public:
                               bool operator()(const T& t) const{
                                               if (index%2==0){
                                                               ++index;
                                                               return true;
                                               }else{
                                                               ++index;
                                                               return false;
                                               }
                               }
};

//template<typename T>
//typename std::vector<T>::size_type IsEvenIndex<T>::index=0;

template<typename T>
void PrintVector(const std::vector<T>& t){
               std::cout << std::endl << "Printing vector contents" << std::endl;
               for(typename std::vector<T>::size_type i=0; i<t.size(); ++i){
                               std::cout << t[i] << '\t';
               }
               std::cout << std::endl << std::endl;
}

int main(){
               std::vector<int> myintVector;
               std::vector<int> myanotherintVector;
               for(int i=1; i<=10; ++i){
                       myintVector.push_back(i*10);
               }
               PrintVector(myintVector);
               //std::vector<int>::iterator itend = std::remove_if(myintVector.begin(), myintVector.end(), IsEvenIndex<int>(myotherintVector));
               std::vector<int>::iterator itend = std::stable_partition(myintVector.begin(), myintVector.end(), IsEvenIndex<int>());
               
               PrintVector(myintVector);
               myanotherintVector.assign(itend, myintVector.end());
               myintVector.erase(itend, myintVector.end());
               PrintVector(myintVector);
               PrintVector(myanotherintVector);
}

[OUTPUT]

Printing vector contents
10 20 30 40 50 60 70 80 90 100
Printing vector contents
10 30 50 70 90 20 40 60 80 100
Printing vector contents
10 30 50 70 90
Printing vector contents
20 40 60 80 100


Also, note here that we don't use a static state variable anymore. Just because of the fact that stable_partition does not suffer from the issue that remove_if suffers from due to the call to find_if, passing the predicate by value.

There is another way where we can improve our original code with the static state variable. To remove the static declaration what we do is change the predicate a little as follows:

[CODE]

template<typename T>
struct IsEvenIndex
{
        private:
                 mutable typename std::vector<T>::size_type index;
                 typename std::vector<T>::size_type & index_ref;
                 std::vector<T>& refVec;
        public:
                 bool operator()(const T& t) const
                 {
                          if ( 1 & index_ref++ ) // if it is odd, increment after statement
                          {
                                   return false;
                          }
                          else
                          {
                                   refVec.push_back( t );
                                   return true;
                          }
                 }

        explicit IsEvenIndex(std::vector<T>& vec)
        : refVec(vec), index(0), index_ref( index )
        {}
};

Testing is an exercise and dissecting the logic is what I shall leave for my blog readers and close the topic here with a few references:

1. Codeguru thread where I came across this problem
2. Article that suffices the reasoning
3. Herb Sutter - Extending the standard library

Functors with state - 3 (print contents of vector using std::copy)

I had discussed an issue with function objects containing state and the problems they lead to (especially for std::remove_if algorithm) because of copy creation of those due to argument passing by value. The way they should be passed around is not guranteed by the standards. Here is the starting point for that discussion - Functors with state - 1.

There can be multiple things that can be improved in that code. The first one that I will pick up is the way the function "PrintVector" is laid down.

[CODE]

template<typename T>
void PrintVector(const std::vector<T>& t){
        std::cout << std::endl << "Printing vector contents" << std::endl;
        for(typename std::vector<T>::size_type i=0; i<t.size(); ++i){
                 std::cout << t[i] << '\t';
        }
        std::cout << std::endl << std::endl;
}

There are problems with this code. It is not flexible enough to let you choose the stream where you want the output to be pushed. Secondly, it uses loops and that loop leads to a third problem and that is the repeated call to vector<T>::size() function.

When we have algorithms at our disposal and feel they can improve the code, we should use them. Here is a better way to write the PrintVector function:

[CODE]

#include<vector>
#include<iostream>
#include<algorithm>
#include<iterator>
#include<string>

template<typename T>
void PrintVector(std::ostream& ostr, const std::vector<T>& t, const std::string& delimiter){
        std::copy(t.begin(), t.end(), std::ostream_iterator<T>(ostr, delimiter));
}

A simple one liner!

Another way to better it could be making it independent of the container type. Currently it would work for std::vector only (as demanded as the second argument). We can use iterator inputs (forward iterators should suffice). Here:

[CODE]

#include<iostream>
#include<algorithm>
#include<iterator>
#include<string>

template<typename T, typename InputIterator>
void Print(std::ostream& ostr, InputIterator itbegin, InputIterator itend, const std::string& delimiter){
        std::copy(itbegin, itend, std::ostream_iterator<T>(ostr, delimiter));
}

Now, this Print template can be used to print contents of any sequence that supports input iterators i.e. std::vector, std::deque, std::list, std::string and even plain arrays. The output stream can be anything, a file or the console or anything deriving from std::ostream and similarly we have generalized the delimiter between two subsequent elements that previously was a tab to any string.

More, later! Have fun!!

(Next installment here - Functors with state - 4)

auto_ptr and their usability with STL containers

Aaaahh... Smart pointers..aren't they one of the best things that has happened to C++. They are also sometimes called Managed pointers. I am not going to talk about them right from introduction, so if you are unaware what they are and what are their uses, then try figuring them out through the web-searches or @ codeguru... my fav place as far as C++ is concerned.

Ok..Ok..not ready to search for them...fine.. I will try giving a very brief description. Remember when you use pointers in C++ with dynamic memory management, it's such a headache to get them going and finish them off once you are done? If you did a new or new[], you need to have a corresponding delete or delete[], so that the allocated memory is freed up and the destructor for the new-ed object is called. Also, when you are done with the delete/delete[], freed-up the memory, you need to cautiously set the pointer to NULL, so that you won't try dereferencing it after the de-allocation assuming it points to a valid object. (Recall Dangling pointers. They could be disastrous if dereferenced!)

But just imagine that you could use pointers in the same way you used to do and forget about the headache of the deleting (and optionally NULLing it)? How would that be? Wouldn't that be cool and care-free? ...and that is what is made possible by these managed pointers/smart pointers. They are really smart and they exist in wide varieties.

For now, I would limit my post to just one of that category which is the standard auto_ptr (read auto-pointers). They are a part of C++. They own the dynamically allocated object and then perform the automatic cleanup whenever the object goes out of scope or is not needed. Now, if at some stage you want the manual ownership back they have this function member - release(), make a call to it and all the headache is back yours.

[CODE]
//Example showing a bad situation with naked pointers
void MyFunction()
{
        MyClass* ptr( new MyClass);
        /*.some more code.*/
        delete ptr;
        ptr=NULL;
}

In this scenario, just in case of some exception it's possible that somehow the delete ptr; did not happen...Disasterous..a memory leak! There's more - suppose, in the destructor of MyClass, you call for some resource release like close database connections, releasing file handles or release semaphores, locks etc. All resources are blocked and there's no way out. There could be many more aweful situations.

Now, lets use an auto_ptr and see how it makes life easy:

[CODE]
//Situation above tackled using auto_ptr
void MyFunction()
{
        auto_ptr<MyClass> ptr(new MyClass);
        /*.some more code.*/
}

There is no need to explicitly call a delete; as soon as ptr goes out of scope the destructor of MyClass is called and the object is freed. You should note that auto_ptr only handles allocations with new and not those done with new[] or malloc or any other memory allocation routine for that matter. For those, refer to the following posts - Handling dynamic array allocations, Custom deleters with smart pointers, Free New, Delete Malloc

You can even transfer the ownership of an auto_ptr to another auto_ptr, to another function or free/reset it to use it again.

Here's an example showing the transfer of ownership from one auto_ptr to another.

[CODE]
        //Example showing transfer of ownership.
        auto_ptr<MyClass> autoptr1(new MyClass);
        auto_ptr<MyClass> autoptr2;
        autoptr2 = autoptr1;
        //Now autoptr2 owns the pointer & autoptr1 doesn't
        autoptr1->MyFunction(); // ERROR !!!
        //autoptr1, now is a null pointer

However, one very interesting and important fact about auto_ptr's is that their copies are not equivalent as is the case with naked pointers.

• Consider STL containers or some generic algorithms/functions like sort. There is no restriction by the standard on the vendors of the STL implementers that the containers won't make a copy of the members being added into it (and probably do nothing with it!). In fact, for example, the implementations of the vector class make a copy of the original object and store inside them. We know auto_ptr copies are not equivalent due to the strict ownership semantics. You might be safe in just having those auto_ptrs stored inside a vector but you get a few examples around this in the Gotw link below that show how the problem comes out in the open, for example, with say, a sort algorithm that holds a copy of an element as a pivot? There is nothing to guarantee or prevent that.


• Another disastrous situation would be when you are initializing (setting/assigning) another auto_ptr object with an object held by the vector. You would think that the object inside the vector is okay and retains the same state but it will not. The ownership by this time would get transferred to the external object just initialized/assigned.


• What if there is a member function that returns the contained vectors element is returned by value?


• What if you make another copy of the vector? Or for that matter, create some other container out of its elements?


• Use of member functions of vector like - constructor, assign, insert, resize - will they succeed? Will they definitely succeed?

It just gets too messy to handle. Sure some operations will work out fine but quite a few will not and you would need to keep worrying about 'em.

To help us out of this disaster, the C++ standards did some tweaking. The copy constructor and the copy assignment operator of auto_ptr take a reference to a non-const right hand side objects and the standard containers' insert() takes a reference to a const and hence auto_ptr cannot be used. It will just not allow you to create a copy of auto_ptr inside the vector (standard containers) members. That will cause you compilation errors on a compliant compiler. Nice solution..isnt it? But still, as a strict guideline..we should not use the auto_ptr wherever a copy of theirs is expected to be made.

For more information, visit these : Using auto_ptr effectively by Herb Sutter, Smart Pointers - What, Why and Which, Smart pointers

Cya!