What to assign a variable that I don't want to be equal to any possible input?

user_13699210 0
Viewed 111

The question is

Implement the function unique_in_order which takes as argument a sequence and returns a list of items without any elements with the same value next to each other and preserving the original order of elements.

For example:

uniqueInOrder("AAAABBBCCDAABBB") == {'A', 'B', 'C', 'D', 'A', 'B'}

uniqueInOrder("ABBCcAD") == {'A', 'B', 'C', 'c', 'A', 'D'}

uniqueInOrder([1,2,2,3,3]) == {1,2,3}

Now my solution is

template <typename T> 
std::vector<T> uniqueInOrder(const std::vector<T>& iterable){
  std::vector<T> unique_set;
  T last = 0;
  for(auto & element : iterable) {
    if(element != last) {
      unique_set.push_back(element);
    }
    last = element;
  }
  return unique_set;
}
std::vector<char> uniqueInOrder(const std::string& iterable){
  std::vector<char> unique_set;
  char last = 0;
  for(auto & element : iterable) {
    if(element != last) {
      unique_set.push_back(element);
    }
    last = element;
  }
  return unique_set;
}

The problem is that sometimes the first element is 0. What can I assign last that will never match an input? I tried using NULL but I think that just compiled to 0 anyway.

c++11 c++
4 Answers

There's an algorithm to do just that called std::unique_copy

template <typename T> 
std::vector<T> uniqueInOrder(const std::vector<T>& iterable){
  std::vector<T> unique_set;
  std::unique_copy(iterable.begin(), iterable.end(), std::back_inserter(unique_set));
  return unique_set;
}

// same thing for std::string
std::vector<char> uniqueInOrder(const std::string& iterable){
  std::vector<char> unique_set;
  std::unique_copy(iterable.begin(), iterable.end(), std::back_inserter(unique_set));
  return unique_set;
}
user_114884570

Depending on the type of T, there could be no impossible value. For ints and chars, every single value is possible. The best option is to use something like std::optional, which provides an explicit valueless value.

// this will be valueless and not equal to any value
std::optional<T> last{};
// assign it with
last = element;
user_59231390

As the first element in iterable will always be added you could also start with it anyways. So it get's added to the unique set and in the for loop it will be ommited anyways due to if(element != last) (or you could just start the loop with the second element).

template <typename T> 
std::vector<T> uniqueInOrder(const std::vector<T>& iterable){
  std::vector<T> unique_set;
  if(iterable.empty()) {
     return unique_set;
  }
  T last = iterable.at(0);
  unique_set.push_back(last);
  for(auto & element : iterable) {
    if(element != last) {
      unique_set.push_back(element);
    }
    last = element;
  }
  return unique_set;
}
user_76990370

With Range-v3

#include <iostream>
#include <range/v3/view/group_by.hpp>
#include <range/v3/view/transform.hpp>
#include <vector>
using ranges::views::group_by;
using ranges::views::transform;
int main() {
    std::string s1 = "AAAABBBCCDAABBB";
    std::string s2 = "ABBCcAD";
    std::vector<int> v = {1,2,2,3,3};
    auto process = group_by(std::equal_to<>{})
                 | transform([](auto x){ return x.front(); });
    std::cout << (s1 | process) << std::endl;
    std::cout << (s2 | process) << std::endl;
    std::cout << (v  | process) << std::endl;
}

I want to stress on the expressiveness of this solution. Indeed, at the "cost" of defining the following names,

    constexpr auto equal = std::equal_to<>{};
    constexpr auto pick_first = [](auto x){ return x.front(); };

which in reality adds no complexity/cost at all, the important line becomes

    auto process = group_by(equal) | transform(pick_first);

which reads almost like English: The processing consists in grouping by equality and piping (|) the result into a transformation which picks the first element of each group.

user_58252940
Related