0
\$\begingroup\$

I'm well versed in Python and Java, am just starting out with C++. Am enjoying the language and would really appreciate feedback on this solution.

kata:

Return positions and values of the "peaks" (or local maxima) of a numeric array
For example, the array arr = [0, 1, 2, 5, 1, 0] has a peak at position 3 with a value of 5 (since arr[3] equals 5).

The output will be returned as an object with two properties: pos and peaks. Both of these properties should be arrays. If there is no peak in the given array, then the output should be {pos: [], peaks: []}.

Example: pickPeaks([3, 2, 3, 6, 4, 1, 2, 3, 2, 1, 2, 3]) should return {pos: [3, 7], peaks: [6, 3]} (or equivalent in other languages)

All input arrays will be valid integer arrays (although it could still be empty), so you won't need to validate the input.

The first and last elements of the array will not be considered as peaks (in the context of a mathematical function, we don't know what is after and before and therefore, we don't know if it is a peak or not).

Also, beware of plateaus !!! [1, 2, 2, 2, 1] has a peak while [1, 2, 2, 2, 3] does not. In case of a plateau-peak, please only return the position and value of the beginning of the plateau. For example: pickPeaks([1, 2, 2, 2, 1]) returns {pos: [1], peaks: [2]} (or equivalent in other languages)

Have fun!

Solution:
#include <vector>
#include <iostream>

struct PeakData {
  std::vector<int> pos; 
  std::vector<int> peaks;
};

PeakData pick_peaks(const std::vector<int> &v) {
  PeakData result;
  
  for (auto& j : v) {
    std::cout << j;
  }
  std::cout << std::endl;
  
  bool plateau = false;
  unsigned long plateau_start = 0;
  
  for(unsigned long i = 1; i < (v.size() - 1); i++) {
      // if we are going down hill, skip.
      if ( v[i] < v[i-1] ) {
        continue;
      }

      if ( v[i] == v[i-1] && !plateau ) {
        continue;
      }

      if( v[i] > v[i+1] ) {
        result.pos.push_back(plateau ? plateau_start : i);
        result.peaks.push_back(v[i]);
        plateau = false;
        continue;
      }

      if ( ( v[i] == v[i+1] ) && ! plateau) {
        plateau_start = i;
        plateau = true;
        continue;
      }

      if ( v[i] < v[i+1] ) {
        plateau = false;
      }
  }
  
  return result;
}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ You'll probably revisit this kata a few times as your C++ skills develop. I definitely recommend repeating it when you start unit-testing your code and when you learn to use generic iterators to traverse containers. \$\endgroup\$ Apr 19, 2022 at 15:45
  • \$\begingroup\$ @Aganju you may have already seen but in case not: the definition of PeakData has been added. \$\endgroup\$ Apr 19, 2022 at 15:45

3 Answers 3

3
\$\begingroup\$

Style:

In C++ (unlike C) we place the type modifers with the type.

PeakData pick_peaks(const std::vector<int> &v) {

Normally I would expect it to look like this:

PeakData pick_peaks(const std::vector<int>& v) {
                                         ^^^

Personally, I like the const on the right (though nobody is going to complain about the left either).

PeakData pick_peaks(std::vector<int> const& v) {

The reason I like the right is that const binds to the type on the left, unless it is on the very left hand end then it binds right. To make things easier to read when you have multiple const always place it on the right side of the thing that is consta.

char const * const  t;    // ie. This
const char * const  t;    //     rather than this (though they mean the same).

Const correctness:

Mark things const (especially references) if you don't plan on modifying the item as a hint to the compiler.

  for (auto const& j : v) {

            ^^^^^

Don't use std::endl

The std::endl modifier adds a new line and forces a flush of the buffer.

  std::cout << std::endl;

99.999999% of the time this makes the code less efficient. The buffer will be automatically flushed when it needs to be flushed so ther is no need to do it manually.

  std::cout << "\n";   // Note prefer "\n" over '\n'
                       // As outputting a character builds a string internally.

Indexes may not be unsigned long

Its probably safe, but don't make assumptions. There is a specific type to represent array/ container indexes. std::size_t.

  unsigned long plateau_start = 0;

Use:

  std::size_t plateau_start = 0;

\$\endgroup\$
5
  • 1
    \$\begingroup\$ You will find that a majority prefers const on the left though. I hear your argument - just saying that every coder should be aware that the chance is large that any given team has a rule to put it on the left. \$\endgroup\$
    – Aganju
    Apr 18, 2022 at 21:21
  • 3
    \$\begingroup\$ @Aganju Thought you may be technically correct (the best type of correct)with the term "majority", but it is not like 99/1 . I would say it is more like 60/40 split, though like the space Vs tab split your view is usually biased by the teams you have worked on in the past. If you always worked on a team that used spaces, then you think spaces are the "da bom". But in real world if your team has a mandate then automate the check and follow the rule. Otherwise, use the one you prefer and seems more logical. \$\endgroup\$ Apr 18, 2022 at 22:16
  • \$\begingroup\$ “Note prefer "\n" over '\n'… As outputting a character builds a string internally.” Interesting, I never noticed that before. Do you know why this is? \$\endgroup\$
    – indi
    Apr 22, 2022 at 9:52
  • \$\begingroup\$ @indi This is not mandated by the standard, but was an observation of my implementation (I made one time many years ago). \$\endgroup\$ Apr 22, 2022 at 15:37
  • \$\begingroup\$ @MartinYork Yeah, I was just wondering if you knew the reason they went that way. I checked with both libstdc++ and libc++, and they both seem to do it. libstdc++ seems to be testing something in the stream (width?), and calls .put() if it’s zero. libc++ doesn’t bother, and just constructs the C-string regardless. I suppose it’s possible that no one cared to optimize single-character output. The string length is pre-calculated, so there’s really no extra cost (other than setting up the temporary C-string, and the test-and-branch in libstdc++). \$\endgroup\$
    – indi
    Apr 22, 2022 at 21:05
1
\$\begingroup\$

A loop where we use an element and its neighbour could be a candidate for clearer expression using std::adjacent_difference(). However, with suitable local variables, we should be able to read each element just once (as we might from an InputIterator); this will work very well as the first and last elements can never be peaks.

The parallel arrays of PeakData are probably better represented as an array of objects:

struct Peak {
  std::size_t pos; 
  int peak;
};

using PeakData = std::vector<Peak>;

However, it seems that the choice of structure was imposed by the functional specification, so all we can do is be aware of its problems, and not repeat them where we can avoid that.

\$\endgroup\$
2
  • \$\begingroup\$ "However, with suitable local variables, we should be able to read each element just once" - Is the compiler not smart enough to realise that as long as i hasn't changed, v[i] won't have changed? (I'm still getting to grips with the externals of c++ let alone the internals, so apologies if this is a dumb question!) \$\endgroup\$ Apr 19, 2022 at 13:21
  • 1
    \$\begingroup\$ Perhaps I was too concise there. What I meant is that in the loop, when we're processing v[i], we don't actually need to read v[i-1] or v[i+1] if we remember enough about the previously-seen values. What you have is fine when working with a vector (or any container that can be accessed bidirectionally), but for algorithms that might consume values as they are produced, then it's helpful to be able to write single-pass implementations. It's not a fault in your code: just a teaching opportunity to help you face those future challenges better! \$\endgroup\$ Apr 19, 2022 at 15:39
0
\$\begingroup\$

Prefer signed size/index type

Unsigned size/index types wrap around upon overflow. Since that is NOT undefined behavior, but undesired behavior, it is unintuitive and surprising. Before C++20, there was no choice for programmers other than using static_cast, But as now we have std::ssize, unsigned size/index types are not worth pain.

Handle edge cases

If v.size() == 0, your loop for(unsigned long i = 1; i < (v.size() - 1); i++) makes a big problem. (that's why you should use signed index/size types) Make an assertion guard or add boundary case handling.

Use type alias

using index_t = std::ptrdiff_t;
using answer_t = std::vector<std::pair<index_t, int>>;

look as reasonable choices for me here.

Test your test cases with assert

It's too common to mention.

The code I wrote for this problem:

#include <cassert>
#include <iostream>
#include <utility>
#include <vector>

using index_t = std::ptrdiff_t;
using answer_t = std::vector<std::pair<index_t, int>>;

answer_t pick_peaks(const std::vector<int> &v) {
  auto n = std::ssize(v);
  if (n < 3)
    return {};
  index_t curr = 1;
  answer_t result;
  while (curr < n - 1) {
    while (curr < n - 1 && !(v[curr] > v[curr - 1] && v[curr] >= v[curr + 1])) {
      ++curr;
    }
    index_t next = curr + 1;
    if (curr < n - 1 && v[curr] == v[next]) {
      while (next < n && v[curr] == v[next]) {
        ++next;
      }
    }
    if (curr < n - 1 && (next < n && v[curr] > v[next])) {
      result.emplace_back(curr, v[curr]);
    }
    ++curr;
  }

  return result;
}

void print(const answer_t &v) {
  for (const auto &[idx, val] : v) {
    std::cout << '{' << idx << ',' << val << "} ";
  }
  std::cout << '\n';
}

int main() {
  print(pick_peaks({0, 1, 2, 5, 1, 0}));
  print(pick_peaks({3, 2, 3, 6, 4, 1, 2, 3, 2, 1, 2, 3}));
  print(pick_peaks({1, 2, 2, 2, 1}));
  print(pick_peaks({1, 2, 2, 2, 3}));
}

Demo: https://wandbox.org/permlink/OghcFhDxfyYgxas3

EDIT : Justification for using signed size/index type

Here are two simple loops that sum four elements (n + (n + 1) + (n + 2) + (n + 3) = 4 * n + 6). The two implementations are the same except for the signedness of the iteration variable.

int f1(int n) {  // Signed 
  auto r = n; 
  for (auto k = n + 1; k < n + 4; ++k) { 
    r += k; 
  } 
  return r; 
} 
 
int f2 (unsigned n) {  // Unsigned 
  auto r = n; 
  for (auto k = n + 1; k < n + 4; ++k) { 
    r += k; 
  } 
  return r; 
} 

GCC -O3 gives (https://godbolt.org/z/84dse9xGT):

f1(int):
        lea     eax, [6+rdi*4]
        ret
f2(unsigned int):
        lea     edx, [rdi+1]
        lea     ecx, [rdi+4]
        mov     eax, edi
        cmp     edx, ecx
        jnb     .L4
        lea     eax, [rdx+2+rdi]
        add     eax, eax
.L4:
        ret

In f1, the loop variable is signed, and the overflow is undefined, so the compiler assumes that the overflow never occurs. So, the compiler can safely conclude that the loop will iterate exactly three times - k = n + 1, n + 2, n + 3, so the compiler directly calculates 4 * n + 6 with single instruction.

In f2, the loop variable is unsigned, and the overflow is well-defined, so the compiler should be aware that the valid overflow could occur. If you give n as the maximum value of unsigned, you'll get valid overflow. So, n + 4 < n + 1 is perfectly valid, the compiler can't conclude how many times the loop will iterate so we loss optimization opportunity.

So, for the question "Should we prefer unsigned integers for size/index types in C++?" - the answer is no.

\$\endgroup\$
8
  • 4
    \$\begingroup\$ I disagree with the recommendation to use signed-size for indexing. Amongst other things, I don't see how replacing unwanted wrap-around behaviour with undefined behaviour is an improvement, as you appear to claim here. \$\endgroup\$ Apr 19, 2022 at 15:41
  • \$\begingroup\$ BTW, your implementation would fail due to not reading the requirements: as noted in my answer the parallel lists of position and value are specified as the return type, rather than the more usual and better choice of a single array of pairs. \$\endgroup\$ Apr 19, 2022 at 15:48
  • 2
    \$\begingroup\$ I’m with @TobySpeight regarding signed size. I’m the first person to complain about the fact that sizes are unsigned… but that’s the universe we live in. Acknowledging the problems with the status quo is fine, but swimming against the current is silly. Suggesting to newbies to go against universal, standard conventions like that… I’m not cool with that. \$\endgroup\$
    – indi
    Apr 19, 2022 at 23:57
  • \$\begingroup\$ @indi size_t isn't modeling unsigned integers. size_t is modeling modulo group of unsigned integers, that's completely different \$\endgroup\$
    – frozenca
    Apr 20, 2022 at 1:20
  • \$\begingroup\$ @TobySpeight There are good reasons why C++ decided signed integer overflow to be undefined. It enables a lot of optimization opportunity. I'll elaborate it in my post. Also, I'm not replacing undesired behavior with undefined behavior, because using signed index/size types replaces wraparound to change to (predictable) negative values, not overflow. Therefore, I didn't replaced undesired behavior with undefined behavior, I actually removed that. \$\endgroup\$
    – frozenca
    Apr 20, 2022 at 1:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.