C++

Forum

 
list and array dont have capacity

closed account (EwCjE3v7)
I have an exercise from my book,
Why don`t list or array have a capacity?


For array I know as it`s a fixed size and more memory will not be needed but for std::list I do not know
keskiverto (10366)
Oh Hey Its Z (20)
I am not sure what your book means by that question.
Arrays have maximum capacities. They are the set limits given to it when allocating memory for the array.

For example, if I had an array foo[5], the capacity would be 5 elements. No more than 5 elements will fit into that array.
closed account (EwCjE3v7)
I have C++ Primer 5th edition if you wanted to know, but I believe by array they meant the std::array not the built in one []. And by capacity I believe they mean the member function capacity()

@keskiverto Sry I cant find it there, it does not say why list and std::array dont have the capacity function
AbstractionAnon (6954)
The reasons are quite different.

std::list does not have a capacity() function because there is no implicit limit to the number of entries you can insert into a linked list.

std::array does not have a capacity() function because unlike a vector, there is no anchor structure in which to store the capacity.
closed account (EwCjE3v7)
Thank you for explaining that.
Lowest0ne (1536)
The question might be better as "Why do vectors have capacity?". None of the other STL containers do.

A vector is basically a resize-able array. By that, it is meant that it is an array that knows when to allocate more space and copy its data to that new space. The allocate/copy process is not 'fast', so instead of the vector allocating just enough space for the new item, it allocates space for a whole bunch of items.

Thus, capacity() is introduced to tell us how many items the vector could hold without having to allocate more space:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
#include <iostream>
#include <vector>

typedef std::vector< int > int_vector;

void vector_data( const int_vector& data, const char* message )
{
  std::cout << message << '\n';
  std::cout << "Size    : " << data.size() << '\n';
  std::cout << "Capacity: " << data.capacity() << '\n';
  std::cout << "Location: " << data.data() << "\n\n";

}

int main( void )
{
  int_vector ints;

  vector_data( ints, "Initial" );

  for ( int i = 0; i < 100; ++i )
    ints.push_back( i );

  vector_data( ints, "After push_back()" );

  int_vector::size_type capacity = ints.capacity();
  while ( ints.size() < capacity ) ints.push_back( 1 );

  vector_data( ints, "Until capacity reached" );


  ints.push_back( 0 );
  vector_data( ints, "After capacity reached" );

  return 0;
}
 
Initial
Size    : 0
Capacity: 0
Location: 0

After push_back()
Size    : 100
Capacity: 128
Location: 0x1cdb270

Until capacity reached
Size    : 128
Capacity: 128
Location: 0x1cdb270

After capacity reached
Size    : 129
Capacity: 256
Location: 0x1cdb48
Last edited on
closed account (EwCjE3v7)
@Lowest0ne I thank you for your explanation, it cleared so much up. Thank you so much I understand fully now. Becuase of you :)

Can you tell me how you did the output(right grey box) beside your code?
Lowest0ne (1536)
Put four dashes between the code and the output:

[code tag]
std::cout << "hello";
----
hello
[/code tag]
Last edited on
Topic archived. No new replies allowed.