CODEWITHSUNDEEP
c++arraysalgorithmduplicates
Daniel Zawadzki
Daniel Zawadzki

Reputation: 179

Creating an array without duplicates

My question is as follows. How to create an array with all the characters that were used in const char * pass in such a way that the array did not have any duplicates. For example:

const char *pass = "Qqqqqqqwwwww11111"

should create an array of 

Q  |  q  |  w  |  1

Variable pass is given by the user, so it is difficult to determine how it gonna looks like.

Upvotes: 0

Views: 2866

Answers (3)

Evgeny Panasyuk
Evgeny Panasyuk

Reputation: 9189

As I understand you want to remove all duplicates and order is imporatant, so std::unique is not enough.

While your element type is small, like char - you can use array/std::vector/std::bitset to remember which elements have been met before:

Live Demo

template<typename I, typename O>
I remove_duplicates(I first, I last, O out)
{
    using T = typename iterator_traits<I>::value_type;
    using limits = numeric_limits<T>;

    constexpr auto min = limits::lowest();
    constexpr auto max = limits::max();

    bitset<size_t(max - min) + 1> had_before;

    while(first != last)
    {
        T x = *first;
        size_t i = x - min;
        if(!had_before[i])
        {
            had_before.set(i);
            *out = x;
            ++out;
        }
        ++first;
    }
    return out;
}

int main()
{
    char s[] = "Qqqqqqqwwwww111qq1q1Qa";
    auto first = begin(s), last = end(s);
    auto new_last = remove_duplicates(first, last, first);
    for_each(first, new_last, [](char x) { cout << x; });
}

Output is:

Qqw1a

Upvotes: 1

Hiura
Hiura

Reputation: 3530

One of many solution consists in using std::sort and std::unique. It's also simpler and safer to use std::string (or std::vector, ...).

#include <iostream>
#include <algorithm>

int main() {
    char *pass = "Qqqqqqqwwwww11111"; // or by user input

    // using std::string is easier and safer (works similarly with std::vector)
    std::string data(pass);

    // Remove duplicates with std::sort and std::unique
    std::sort(data.begin(), data.end());
    auto end = std::unique(data.begin(), data.end());

    // Remove duplicates – if needed.
    data.erase(end, data.end());

    // Print the unique chars
    std::cout << data << std::endl;
    return 0;
}

Depending on what you're doing, you might not need to erase the duplicate element of data. In this case, remember that end is an iterator on the first duplicate element (or, if the data has no duplicate in the first place, it's equal to data.end()).

NB: you absolutely need to sort your data before using std::unique.

Here you can try this code.

Upvotes: 2

Vlad from Moscow
Vlad from Moscow

Reputation: 310950

If you mean to create an array without adjacent duplicate elements then at first you should count how many there are unique elements in string pass and then dynamically allocate memory for the array and copy unique elements in it. The task can be simply done with using standard algorithms. For example

char *a = 0;

size_t n = std::strlen( pass );

if ( n != 0 )
{
    size_t count = 1 + std::inner_product( pass + 1, pass + n, pass, 0u, 
                                           std::plus<size_t>(),
                                           std::not_equal_to<const char>() );

    a = new char[count + 1];

    std::unique_copy( pass, pass + n + 1, a );
}

Or maybe it will be more simpler to write

char *a = 0;

size_t n = 1 + std::strlen( pass );

size_t count = 1 + std::inner_product( pass + 1, pass + n, pass, 0u, 
                                       std::plus<size_t>(),
                                       std::not_equal_to<const char>() );

a = new char[count];

std::unique_copy( pass, pass + n, a );

Upvotes: 1

Related Questions