rational behind the typedef igraph_vector

The igraph_vector are typedefined in igraph_vector_type.h as

typedef struct TYPE(igraph_vector) {
    BASE* stor_begin;
    BASE* stor_end;
    BASE* end;
} TYPE(igraph_vector);

What is the meaning of the two end ?.
I guess that they are not interchangeable, but I cannot step further.

stor_end is the end of the memory block of the allocated area. end is the end of the part of that allocated memory area that is actually used. For instance, if the vector contains 6 elements but can contain 16 elements without having to re-allocate memory, stor_end will point to stor_begin[16] but end will point to stor_begin[6]. The vector is “full” if stor_end == end; trying to add one more element to a vector that is full will make igraph re-allocate the internal memory area, most likely doubling its size.

1 Like

Also, this is analogous how std::vector works in C++: std::vector - cppreference.com

A vector has a size, but also a certain amount of already allocated storage, which can be managed separately. For example, if you know how many element you want to add using push_back() calls, you can preallocate the appropriate amount of storage. This can lead to substantial performance improvements.

Thanks for the prompt explanation.
I getting confused with indices. Guessing that you use C indices but not Fortran indices:
stor_begin may point to stor_begin[0], stor_end to stor_begin[15] and end to stor_begin[5].
Is that correct ?

Yes, we use zero-based (C indices). stor_begin is the same as &stor_begin[0]. stor_end is &stor_begin[16] because stor_end points to the first slot after the allocated area. Similarly, end points to &stor_begin[6] because it points to the first slot after the slice is currently being used. This allows us to get the current length of the vector simply with end - stor_begin and the number of allocated elements with stor_end - stor_begin (as opposed to end - stor_begin + 1 and stor_end - stor_begin + 1 if the end pointers were pointing “inside”.

The end pointers will point not to the last element, but one entry past the last element.

Thus, if there is room for n elements, then stor_end == &stor_begin[n] == stor_begin + n. Also, you should never dereference stor_end.

Once again this is consistent with how the C++ standard library does things. I.e., if one were to poke around in the internals of an igraph vector (please don’t :slight_smile: ), then you could iterate through it like this:

for (double *ptr = vec.stor_begin; ptr != vec.end; ++ptr) { ... }

@jgmbenoit I’m just curious, what are you working on, and why do you need to look into the internals of vectors? If you need any fixes for Debian, let us know.

I am acting as regular user here. I was just curious. Note that I am not familiar with C++.

As a regular user, you don’t usually need to look inside of the vector structure. Technically, the internals are not stable, and “may change in future versions” (although that’s unlikely in practice).

Normally, you iterate through a vector like this:

igraph_vector_t vec;
igraph_integer_t i, n;

/* initialize vector and store something in it */

n = igraph_vector_size(&vec);
for (i=0; i < n; ++i) {
    printf("Element %d is %g.\n", (int) i, VECTOR(vec)[i]);

I.e., to get the ith element, we use VECTOR(vec)[i].