What's the standard or common data structure for a list of objects?

What's the standard or common data structure for a list of objects?

asked Apr 17 by anonymous

2 Answers

In C++, the common data structure for a sequence ("list") of objects may be std::vector.

A vector is a dynamically resizable array. It is "The most extensively used container in the C++ Standard Library ..., offering a combination of dynamic memory management and efficient random access." -- Lock-free Dynamically Resizable Arrays

And vector is the default first data structure you should think about for a problem for its compactness and efficiency. Bjarne Stroupstrup has an excellent talk on this, check it out.

From the standard draft C++11 (with important parts highlighted):

A vector is a sequence container that supports random access iterators. In addition, it supports (amortized) constant time insert and erase operations at the end; insert and erase in the middle take linear time. Storage management is handled automatically, though hints can be given to improve efficiency. The elements of a vector are stored contiguously...

Check the standard draft section 23.3.6 for more details.

One usage example from cppreference.com:

#include <iostream>
#include <vector>
 
int main()
{
    // Create a vector containing integers
    std::vector<int> v = {7, 5, 16, 8};
 
    // Add two more integers to vector
    v.push_back(25);
    v.push_back(13);
 
    // Iterate and print values of vector
    for(int n : v) {
        std::cout << n << '\n';
    }
}

Run it on Caliru.

answered Apr 18 by zma (2,200 points)
edited Apr 20 by zma

In C, we common way to store a list/collection of objects of the same type is to use one-dimensional arrays.

In C, an array is a collection of data objects of the same type. An array is in a contiguous memory area. The lowest address of the memory area corresponds to the first element in the array and all other elements follow it one by one.

Arrays can be statically allocated or dynamically allocated:

// statically allocated
// declare a static array a1 of 100 ints
int a1[100];

// dynamically allocated on the heap
// allocate a dynamical array a1 of 100 ints
int a2_len = 100;
int *a2 = (int *)malloc(sizeof(int) * a2_len);

Element access time in an array has O(1) complexity. Memory management like increasing the size of an array should be done grammatically. Some library functions may help though. For example, void *realloc(void *ptr, size_t size) changes the size of the memory block pointed to by ptr to size bytes. The contents will be unchanged in the range from the start of the region up to the minimum of the old and new sizes, and returns a pointer to the newly allocated memory which may be different from ptr.

One example to sum the a1 and a2 together into a2:

int i = 0;
for (i = 0; i < 100; ++i) {
  a2[i] += a1[i];
}
answered Apr 19 by zma (2,200 points)

Please log in or register to answer this question.

Welcome to Do This In Various Langs (dtivl), where you can ask questions and receive solutions in various programming languages.
Copyright © SysTutorials. User contributions licensed under cc-wiki with attribution required.
Hosted on Dreamhost

...