STL What is random access and sequential access?

Question

So, I'm curious to know what random access is?

I searched a little and could not find much. Now I understand that the "blocks" in the container are placed randomly (as shown here ). Random access then means that I can access each block of the container no matter what position (so that I can read what it says in position 5 without looking at all the blocks before that), and with sequential access I have to go through 1, 2nd, 3rd and 4th to get to the 5th block.

I'm right? Or, if not, can someone explain to me what random access and sequential access are?

Answer 1

Sequential access means that the cost of accessing the 5th element is 5 times higher than the cost of accessing the first element, or at least increases the costs associated with the position of the elements in the set. This is due to the fact that to access the 5th element of the set, you must first perform an operation to search for the 1st, 2nd, 3rd and 4th elements, therefore, to access the 5th element, 5 operations are required.

Random access means that access to any element in the set has the same cost as any other element in the set. Finding the 5th set item is just one operation.

, O (1), O (n/2) → O ( n) . N/2 , , 100 , . , n , n/2 ( O n).

-, :

Hashmaps - , . , - - . , , 100% - -, .

-, , :

, - - O (n) , , , , - - Ω (n), O (1) Θ (1). Ω - , Θ - , O - .

:

. n - Ω (n), O (n/2) Θ (1), Ω (n), O (n) Θ (1).

. n - Ω (n/2), O (1) Θ (1), Ω (n), O (1) Θ (1)

, , .

@sumsar1812:

, , / , , . , , , .

, .

, .

int 8 , , :

int someInts[5];
someInts[1] = 5;

someInts - , . 1 , 8 .

(someInts+1)* //returns 5

, , , .

, . , , .

, , . , , , . , , , .

, , , .

, , , , , , . , , .

Answer 2

- , @echochamber. .

" " . std::vector - ++, . std::stack - ++, .

" " . . , , std::list.

, :

// random access. picking elements out, regardless of ordering or sequencing.
// The important factor is that we are selecting items by some kind of
// index.
auto a = some_container[25];
auto b = some_container[1];
auto c = some_container["hi"];

// sequential access. Here, there is no need for an index.
// This implies that the container has a concept of ordering, where an
// element has neighbors
for(container_type::iterator it = some_container.begin();
    it != some_container.end();
    ++ it)
{
    auto d = *it;
}

Answer 3

, , . STL , , () . - .

-

, : std::vector<T> std::list<T>. , . , : , . , , .

, node, node , . , node . , , , , , . , , . , , , , .

-

. . . , , ( ), , , .

For example, as soon as you start working with a rather large data set, even if you are working with a vector, more efficient access to all elements in a sequential order than access to all elements in a random order. In contrast, the list does not make this possible. Since list nodes do not even have sequential memory cells, even sequential access to list items may not read memory sequentially and may be more expensive because of this.