How to access neighbouring elements in an array in C++?

Question

I would implement a function, accessing a given element's neighbouring elements.

This is a simple example: to sum elements within a radius distance from the given element in a 1D array. The C code would be:

int sum(int *elem_ptr, int radius) {
    int sum = 0;
    for (int *ptr = elem_ptr - radius; ptr <= elem_ptr + radius; ptr++) {
        sum += *ptr; 
    }
    return sum;
}

But, the above code doesn't check the case the ptr runs out of the array boundary. So, I want to provide this boundary check function automatically. In other words, we don't need add the boundary check code into the above code.

What I am considering is to use C++ operator overload, which lets '*' operator to check boundary. However, I'm not sure how to do that.

Possible duplicate of [Operator overloading](http://stackoverflow.com/questions/4421706/operator-overloading) — Rakete1111, Apr 07 '16 at 16:25
Why not pass in the length of the array as an argument and do the boundary checking in the sum function? — shouston, Apr 07 '16 at 16:30
I would suggest using `std::accumulate` (http://en.cppreference.com/w/cpp/algorithm/accumulate) instead. — Jesper Juhl, Apr 07 '16 at 16:33
In C++ you can use a template with an int parameter. If you have true arrays as arguments you can write a template function which takes a reference to an array (which is not possible in C) and thus knows the array size and can check boundaries. If you *must* use pointers (for example, if you use vector data or other dynamically allocated memory) you *have to* provide the bounds to the function. You *should* use C++ containers though in any case. — Peter - Reinstate Monica, Apr 07 '16 at 16:37
How can you determine anything about the array when all you passed to that function is an `int*`? You have no information as to where the array starts or ends. — PaulMcKenzie, Apr 07 '16 at 16:38
In C++, you can reduce these issues by using `std::vector`. No need to pass a pointer to the array or the capacity of the array. Pass the `std::vector` by reference. — Thomas Matthews, Apr 07 '16 at 16:41
What do you want to *do* when you run out of array boundary? Whatever that is, you need to build it into your "automatic" boundary check somehow... — comingstorm, Apr 07 '16 at 16:42
This is a classic X-Y problem. You ask how to do some X, but you don't tell us why you're doing the Y that precipitates X, or whether you even should be doing Y at all. Your code is written as if it was C code. You should be writing C++ instead... It requires a different mindset. Iterating using pointers is something you'll do very rarely, only to interoperate with old APIs, or to write resource management classes. You seem to be doing neither. — Kuba hasn't forgotten Monica, Apr 07 '16 at 17:47

giant_teapot · Answer 1 · 2016-04-07T17:41:34.477

In C++, using iterators on containers is the way to go, rather that doing pointer arithmetic as shown in you code sample. Iterators are also preferable to raw indexes, because it makes your code compatible with any container (for instance a set or a map don't have indexes).

With a recent STL, the toolkit available to manipulate iterators has become quite versatile:

std::prev(iterator, n) moves an iterator n ranks backwards (towards the beginning of the collection) (ref)
std::next(iterator, n) moves forward (ref)
std::distance(a, b) computes the number of elements between to iterators, it is very useful for checking that you're not out of bounds (ref)

Using iterators will also have another nice side-effect: you will be able to use one of the many algorithms already available in the standard library, for example from <algorithm> or <numeric>.

It turns out there IS a function that already computes the sum of a range of elements : std::accumulate. All you need to do is to use it according to your needs (ref. on accumulate).

Here is the beginning of an implementation that is not perfect but that should do OK most of the time.

#include <functional>
#include <numeric>

int sum(const std::vector<int>& v,
        const std::vector<int>::const_iterator elem,
        size_t radius)
{
    auto first_radius = (std::abs(std::distance(std::cbegin(v), elem)) < radius)
                        ? std::cbegin(v)
                        : std::prev(elem, radius);

    auto last_radius = (std::abs(std::distance(elem, std::cend(v))) < radius)
                       ? std::cend(v)
                       : std::prev(elem, radius);

    return std::accumulate(first_radius, last_radius, 0, std::plus<int>());
}

It could seem a bit overwhelming if you are not used to the syntax, but most of this is bound checking. first_radius and last_radius are iterators to the bounds of you "mask" radius, making sure that they are not "outside" of the vector (note that I'm not sure this code is 100% bug-free). Afterwards, just let std::accumulate do the heavy lifting for us!

You can use this code like that:

std::vector<int> x = { 0, 1, 0, 1, 0, 1};
const int a = sum(x, std::next(std::cbegin(x), 3), 15);
const int b = sum(x, std::prev(std::cend(x), 1), 2);

Depending on how familiar you are with the language, it can be a lot of information. It is worth taking some time to look up the documentation for the function I used here, since it is really the idiomatic way to do it (for C++, mind you).

As a closing note : you must have noticed I worked on a std::vector in my example. Well, nice thing with iterators: we could make this function completely container agnostic!

Using templates, it could work for maps, arrays, sets, your custom container... you name it. But this should be enough for this time... Don't mind asking me about that template trick if you're interested.

Have fun!

score 0 · Answer 2 · answered Apr 07 '16 at 16:56

Since arrays are a pain, I will first present a solution using std::vector.

int sum_vector_neighbor(const std::vector<int>& values, 
                        unsigned int position,  // negative positions are weird. 
                        unsigned int radius)    // negative radii are weird.
{
   if (values.empty())
   {
     return 0;
   }
   const unsigned int size = values.length();
   unsigned int start_index = 0U;
   unsigned int end_index = size - 1;
   if (radius < position)
   {
     start_index = position - radius;
   }
   if ((position + radius) < size)
   {
     end_index = position + radius;
   }
   sum = 0;
   for (; start_index < end_index; ++start_index)
   {
      sum += values[start_index];
   }
   return sum;
}

The solution above is using indices rather than pointers because indices are easier to compare than pointers.

The idiom of using indices can be applied to an array. With the array version, you will need to additionally pass the capacity of the array since the capacity attribute is dropped when the array is converted to a pointer to the first element.

I don't recommend using pointers because you will have to subtract the radius value from a pointer (which is a valid operation), but comparing for less than or greater than is not a supported operation for all platforms.

Better yet, instead of passing a container and indices of a fixed type, parametrize the method on the types of two iterators. It'll then be universal, and only require two iterator parameters. — Kuba hasn't forgotten Monica, Apr 07 '16 at 17:49

How to access neighbouring elements in an array in C++?

2 Answers2