The algorithm std::unique has a side effect that is not always desirable. That is it can change the content of a container.
 
Consider the following demonstration program.
 
#include <iostream>
#include <iterator>
#include <algorithm>
 
int main()
{
        int a[] = { 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5 };
 
        for (const auto &item : a)
        {
            std::cout << item << ' ';
        }
        std::cout << '\n';
 
        auto it = std::unique( std::begin( a ), std::end( a ) );
 
        for (auto first = std::begin( a ); first != it; ++first)
        {
            std::cout << *first << ' ';
        }
        std::cout << '\n';
 
        for ( const auto &item : a )
        {
            std::cout << item << ' ';
        }
        std::cout << '\n';
}
 
The program output might look like
 
1 2 2 3 3 3 4 4 4 4 5 5 5 5 5
1 2 3 4 5
1 2 3 4 5 3 4 4 4 4 5 5 5 5 5
 
As you can see the content of the array was changed. For example the original array contains three values 3 while the resulting array contains only two values 3.
 
I would like to suggest a modification of the algorithm that does not change the content of an array.
 
I named it stable_unique though any more suitable name may be proposed.
 
A simplified impementation of the algorithm looks the following way.
 
template <typename ForwardIterator>
ForwardIterator stable_unique3( ForwardIterator first, ForwardIterator last )
{
    auto duplicate = first;
 
    if (first != last)
    {
        for (auto current = ++duplicate; current != last; ++current )
        {
            if (*first != *current)
            {
                if (duplicate != current)
                {
                    std::rotate( duplicate, current, std::next( current ) );
                }
 
                ++first;
              ++duplicate;
            }
        }
    }
 
    return duplicate;
}
 
Instead of using the algorithm std::rotate within the body of the above algorithm there can be used a code for example based on algorithm std::shift_right. But at present it is unimportant.
 
Now consider the above demonstration program where instead of the standard algorithm std::unique there is used the algorithm stable_unique.
 
#include <iostream>
#include <iterator>
#include <algorithm>
 
template <typename ForwardIterator>
ForwardIterator stable_unique3( ForwardIterator first, ForwardIterator last )
{
    auto duplicate = first;
 
    if (first != last)
    {
        for (auto current = ++duplicate; current != last; ++current )
        {
            if (*first != *current)
            {
                if (duplicate != current)
                {
                    std::rotate( duplicate, current, std::next( current ) );
                }
 
                ++first;
                ++duplicate;
            }
        }
    }
 
    return duplicate;
}
 
int main()
{
        int a[] = { 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5 };
 
        for (const auto &item : a)
        {
            std::cout << item << ' ';
        }
        std::cout << '\n';
 
        auto it = stable_unique( std::begin( a ), std::end( a ) );
 
        for (auto first = std::begin( a ); first != it; ++first)
        {
            std::cout << *first << ' ';
        }
        std::cout << '\n';
 
        for ( const auto &item : a )
        {
            std::cout << item << ' ';
        }
        std::cout << '\n';
}
 
Now the program output is
 
1 2 2 3 3 3 4 4 4 4 5 5 5 5 5
1 2 3 4 5
1 2 3 4 5 2 3 3 4 4 4 5 5 5 5
 
As you can see all values of the original array were preserved.
 
The algorithm is useful for example when you want to split a sorted container into sub-sequences of unique elements.
 
Try for example the following code snippet.
 
        int a[] = { 1, 1, 1, 2, 2, 2, 3, 3, 3 };
 
        for (const auto &item : a)
        {
            std::cout << item << ' ';
        }
        std::cout << '\n';
 
        for (auto first = std::begin( a );
            ( first = stable_unique( first, std::end( a ) ) ) != std::end( a ); );
 
        for (const auto &item : a)
        {
            std::cout << item << ' ';
   }
        std::cout << '\n';
 
Its output is
 
1 1 1 2 2 2 3 3 3
1 2 3 1 2 3 1 2 3
 
What opinions will be?
 
With best regards,
(Vlad from Moscow)
You can meet me at http://cpp.forum24.ru/ or www.stackoverflow.com or http://ru.stackoverflow.com