What is contiguous memory in c plus plus?

Answer 1

Contiguous memory refers to a single block of consecutive memory addresses. All data types larger than a char require contiguous memory addresses.

For any given data type T, sizeof (T) tells us how many bytes of contiguous memory will be allocated to an object of that type:

std::cout << "sizeof (char) == " << sizeof (char) << std::endl;

std::cout << "sizeof (int) == " << sizeof (int) << std::endl;

std::cout << "sizeof (double) == " << sizeof (double) << std::endl;

struct X {/* ... */};

std::cout << "sizeof (X) == " << sizeof (X) << std::endl;

When we speak of contiguous memory, we don't usually refer to the number of bytes allocated to a given type; it can be taken as read that those bytes will be allocated contiguously such that the low-order byte refers to the whole object, regardless of its length.

Typically we use the term contiguous memory when referring to an array of objects. All objects in an array (the array elements) are exactly the same length (in bytes) and because they are allocated contiguously it is trivial to calculate the offset address of any one element relative to any other element in the same array. This is precisely how the array suffix operator works using only a zero-based index; the operator is nothing more than a convenient method of implementing pointer arithmetic. The upshot is that all arrays permit constant-time random access to any element in the array.

Arrays are dense data structures. That is, there is no additional memory required to maintain the structure. The only information we need to keep track of is the start address and the number of elements.

However, the downside of contiguous memory allocations is that whenever we wish to increase the amount of memory allocated we often have to move the entire allocation to new memory. The larger the allocation the more costly this becomes. Moreover, inserting new data means we must move elements to make room. This is why variable-length arrays typically reserve additional memory for moderate expansion while new elements are always pushed onto the end of the array rather than inserted in the middle.

Linked-lists are non-contiguous data structures which make use of additional memory to maintain links between the elements. As such, the elements need not move once allocated. If we want to change the element sequence or insert a new element into the sequence we simply update the affected links; the elements themselves remain wherever they were originally allocated.

Some data structures make use of both contiguous and non-contiguous allocations. A deque (a double-ended queue, pronounced deck) is a typical example because it is usually implemented as a linked-list of separate arrays. Each array is contiguous but the list of arrays is not necessarily contiguous.