Vectors (half open sequence)

[kmce]

Hi, I am learning vectors, and the book I am learning from is giving me information but not explaining it well enough. So I am hoping someone might be able to clear some questions up.

1. What is a half open sequence?
2. Why is a vector notation [0:v.size()) I dont understand why its [ at one side and ) at the other?

[Ganado]

This is a slightly broader concept in mathematics and applies to more than just vectors.

Imagine a continuous number line:

+-----+-----+-----+-----+-----+-----+-----+
     -1     0     1     2     3     4

Now, let's say I want a particular set of numbers in a certain range.
I want a range representing every number from 0 to 3.

            ===================
+-----+-----+-----+-----+-----+-----+-----+
     -1     0     1     2     3     4

0.1, 2, and 2.9 are in the range.
-1, -0.1, 4, and 3.1 are all not in this range.

But what about right at 0 or right at 3? This is where [] vs () comes into play.
If I say that the range is [0, 3], this means that 0 and 3 are included in the range.
If I say that the range is (0, 3], this means that 0 is not included in the range, but 3 is.
If I say that the range is [0, 3), this means that 0 is included in range, but 3 is not.

"Not in the range" can be represented with an open circle (white), while "in the range" can be represented with a closed circle (black).

[0, 3]:

            ●=================●
+-----+-----+-----+-----+-----+-----+-----+
     -1     0     1     2     3     4

(0, 3]:

            o=================●
+-----+-----+-----+-----+-----+-----+-----+
     -1     0     1     2     3     4

[0, 3):

            ●=================o
+-----+-----+-----+-----+-----+-----+-----+
     -1     0     1     2     3     4

(0, 3):

            o=================o
+-----+-----+-----+-----+-----+-----+-----+
     -1     0     1     2     3     4

If we're only dealing with integers, it's even simpler.

kmce wrote:

1. What is a half open sequence?

Half-open sequence is when the beginning element of the sequence is included, but the last element of the sequence is not.

kmce wrote:

Why is a vector notation [0:v.size())

It means the first index 0, is included, but the index that is the size of the vector itself is not.

e.g. [0:5), for discrete sequences, means the sequence "0, 1, 2, 3, 4".

If you have a vector of size 5, then its valid elements are 0, 1, 2, 3, 4. vector[5] is not a valid element of the vector.

[Niccolo]

The "[" character is an "inclusive" endpoint. This means that in that notation, the range describe includes that value. "[0" indicates that the starting point includes zero. The "[" and "]" are referred to as closed in this way.

"(0" would indicate the sequence begins at some point immediately after 0, not including zero. This is referred to as open.

To express the return of v.size() as a closed sequence we'd have to account for the fact that the last index of an array or vector is a count starting at zero, meaning that for a vector of 10 items, the last valid item is located at position 9. The size will be one more than that, or 10 items in the vector. So, we COULD say "[0:v.size()-1]", and since v.size()-1 is 9, the range includes 9, but no more, and starts at 0.

Stating the range as "[0:v.size())" indicates that the value of v.size() is not included in the range, but is beyond the end of the range. One side is closed (the beginning), while the other is open (the size, but not really the end), and so this is called a half open sequence.

If you loop through such a vector or array, you fashion the loop:

for(int i = 0; i < v.size(); ++i ).....

The loop test indicates that i can't reach size, because size isn't a valid location in the vector. This is a "for" loop of the half open sequence.

[helios]

1. If x is in [a; b] then a <= x <= b.
2. If x is in [a; b) then a <= x < b.
3. If x is in (a; b] then a < x <= b.
4. If x is in (a; b) then a < x < b.

1 is a closed interval. 2 and 3 are half-open intervals. 4 is an open interval. Intervals are not sequences, they're sets of real numbers.

Now, to answer your questions:

1. What is a half open sequence?

There's no such thing as a "half-open sequence". Whoever used that term is abusing notation. Openness is a property of "dense" sets, such as the rationals or the reals. https://en.wikipedia.org/wiki/Open_set

2. Why is a vector notation [0:v.size()) I dont understand why its [ at one side and ) at the other?

What the person who said this meant was that if an std::vector v has size v.size(), then the valid indices for that vector are 0, ..., v.size() - 1:

std::vector<T> v;
v.push_back(1);
v.push_back(1);
v.push_back(1);
v.push_back(1);

assert(v.size() == 4);
v[0]; //valid
v[1]; //valid
v[2]; //valid
v[3]; //valid
v[4]; //invalid
v[v.size()]; //invalid
v[v.size() - 1]; //valid
v[-1]; //invalid 

[kmce]

wow these explanations were very helpful, thank you all for answering.