1
\$\begingroup\$

I'm learning C++, and now I have to implement a table data structure.

I don't know a lot about C++, so I have implemented using a vector of vectors. To access the rows of the tables I have defined eight constants with the name of the planets. And, to access the columns I have defined other nine constants.

This is my code:

static const int Mercury = 0;
static const int Venus = 1;
static const int Earth = 2;
static const int Mars = 3;
static const int Jupiter = 4;
static const int Saturn = 5;
static const int Uranus = 6;
static const int Neptune = 7;

static const int PeriodOrbit = 0;
static const int LogintudeAtEpoch = 1;
static const int LongitudeOfPerihelion = 2;
static const int EccentricityOfOrbit = 3;
static const int SemiMajorAxisOrbit = 4;
static const int OrbitalInclination = 5;
static const int LongitudeOfAscendingNode = 6;
static const int AngularDiameterAt1AU = 7;
static const int VisualMagnitudeAt1AU = 8;

static const std::vector<std::vector<double>> ElementsPlanetaryOrbits = {
    { 0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0 },
    { 0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0 },
    { 0.0, 1.0, 2.0, 3.0, 4.0 },
    { 0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0 },
    { 0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0 },
    { 0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0 },
    { 0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0 },
    { 0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0 }
};

With the planet's constants I will get the row for that planet. One I have its row, I will use the other nine constants to get the value that I need (i.e. the period of the orbit).

Is there a better way to do it?

UPDATE:

I'm using static const because the data in the table don't change. I have not said it before because I thought that was understood by static const.

\$\endgroup\$
3
  • \$\begingroup\$ How about struct PlanetData { double orbit; double longetudeAtEpoch; /*..*/};? \$\endgroup\$
    – Jarod42
    Dec 27, 2021 at 14:44
  • \$\begingroup\$ Good first attempt from. :-) \$\endgroup\$ Dec 27, 2021 at 21:34
  • \$\begingroup\$ You got a lot of answers saying to use a vector of structures rather than a table, but that defeats the point of the assignment. So, I submit that the example is not a good use of a table. You want both dimensions to be something that you would naturally index, not be separate kinds of data. E.g. golf scores per hole per player. \$\endgroup\$
    – JDługosz
    Dec 28, 2021 at 16:52

2 Answers 2

2
\$\begingroup\$

Use the Right Data Structure

First, since you have a fixed number of parameters in every row, consider defining it as a struct, with fields instead of column indices. Then the fields can have different types, and you cannot pass your structure an invalid column index. As these are compile-time constants, you will be able to declare them constexpr, which lets the compiler optimize calculations that it can compute at compile time. It’s faster to access an array of arrays or structures than a vector of vectors, too, and takes less memory to store and less time to allocate.

A constexpr array of struct is probably the right approach for this problem, but you can keep on reading if you want some more alternatives to a vector of vectors.

A vector of vectors is very rarely the data structure you want. A pointer to an array of pointers is even less so, which is why it’s so unfortunate that every beginner learns about char **argv first.

Generally, vectors of vectors have high overhead and poor locality of reference relative to vectors of arrays or arrays of arrays, so they perform worse.

If you have a rectangular array, that is, a table where the rows are all the same length, but where you might need to add more planets, you have several good options:

  • An array of arrays, if it’s fixed-size. These can be C-style arrays with [] or std::array.
  • A vector of arrays, if you need to be able to add rows.
  • For sparse matrices, a format such as compressed sparse row (more complicated for a beginner)
  • A Matrix class that stores the entire table in one linear vector and accepts two-dimensional indices. This would let you write something like Matrix<double> a(4, 4); a(1, 1) = 1.0;.

The basic skeleton of a container like that might look like:

#include <vector>
#include <stddef.h>
#include <stdexcept>

template<class T>
  class Matrix{
      public:
      Matrix();
      Matrix( size_t, size_t );
      // You probably want to default copy, move and assign.
      T& operator() ( size_t, size_t );
      const T& operator() ( size_t, size_t ) const;

      private:
      size_t row_size, num_columns;
      std::vector<T> private_buffer;
  };

template<class T>
  T& Matrix<T>::operator() ( const size_t i, const size_t j )
  {
    if (i >= num_columns || j >= row_size){
      throw std::out_of_range("Matrix subscripts out of range.");
    }

    return private_buffer[ i*row_size + j ];
  }

What if you really do need a ragged array, where the rows are different lengths? In most use cases, you can still use another structure than a vector of vectors. For example, you might lay out your rows consecutively in memory, storing the starting-point of each vector in an index vector. You can then easily construct a subrange or view (different names for the same thing) of a row from the starting point of your row and the next row.

There, the skeleton of an implementation might look like:

template<class T> class RaggedArray {
    public:
    RaggedArray();
    RaggedArray( size_t, size_t );
    // You probably want to default copy, move and assign.
    T& operator() ( size_t, size_t );
    const T& operator() ( size_t, size_t ) const;

    private:
    std::vector<T> private_buffer;
    std::vector<size_t> index_vector;
};

template<class T>
  T& RaggedArray<T>::operator() ( const size_t i, const size_t j )
  {
    if (i >= index_vector.size() ||
        index_vector[i] + j >= index_vector[i+1]){
      throw std::out_of_range("Matrix subscripts out of range.");
    }

    return private_buffer[ index_vector[i] + j ];
  }

This lays out the data consecutively in memory, so you have none of the overhead of an extra layer of dereferencing, locality of reference, and more straightforward copy/move/compare/etc. semantics. The major disadvantage here is if you have to resize a row other than the last. Since the rows are laid out consecutively in memory, this data structure forces you to shift everything after that row in memory, a costly operation.

Things Other than That

Although compilers are smart enough to optimize your static const declarations, you probably want your symbolic names for indices to be an enum. Then, your interface can accept a planet and a planet_info. Not only will this prevent you from accidentally passing in an invalid value, the compiler will then catch if you mix up your row and column number.

Constants known at compile time should be declared constexpr when possible. You should use const for data that must be computed at runtime, but will not change thereafter, such as const auto howMarsIsDoingToday = haveJamesWebbTelescopeLookAt(mars);.

You could, again, make the set of planet information a struct with fields rather than a vector or array with named indices.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks for your answer. The data in the table will never change. I only need to access it using the constants declared before it. \$\endgroup\$
    – VansFannel
    Dec 28, 2021 at 6:45
0
\$\begingroup\$

I don't think a vector of vectors is the way to go.

if we assume each row is the information about a planet. Then each row is structured data. So we should use a structure to represent the data:

struct PlanetData
{
    double periodOrbit;
    double logintudeAtEpoch;
    double longitudeOfPerihelion;
    double eccentricityOfOrbit;
    double semiMajorAxisOrbit;
    double orbitalInclination;
    double longitudeOfAscendingNode;
    double angularDiameterAt1AU;
    double visualMagnitudeAt1AU;
};

So now we could have a vector of this structured data:

static constexpr int CountOfPlanets = 8;
std::vector<PlanetData>   elementsPlanetaryOrbits(CountOfPlanets);

Alternatively since you don't look like you need to resize the number of planets (or you only need to do that after re-compiling (its not dynamic)) you could use a std::array rather than std::vector.

std::array<PlanetData, CountOfPlanets>   elementsPlanetaryOrbits;

I like the idea of being able to index the elementsPlanetaryOrbits by a specific name Mercury as that seems important to make sure we don't have accidents and you have done that using your constants.

static constexpr int Mercury = 0;
static constexpr int Venus = 1;
static constexpr int Earth = 2;
static constexpr int Mars = 3;
static constexpr int Jupiter = 4;
static constexpr int Saturn = 5;
static constexpr int Uranus = 6;
static constexpr int Neptune = 7;
// Notice the use of `constexpr` rather than `const`.

But here you can index into the elementsPlanetaryOrbits by an integer and that seems like you can have some accidents. You want to try and design your code so it can not be used incorrectly.

So I like the idea of using a map (or unordered map) and specifying an enum as the key. This will prevent you from accidentally using an integer.

enum class Planets {Mercury, Venus, Earth, Mars, Jupiter, Saturn, Uranus, Neptune};
std::map<Planets, PlanetData>    elementsPlanetaryOrbits;

OK. Now I have to point out that there are some disadvantages to maps (locality) is not good access time is always going to be slower than a vector. But you should weigh the use case of correctness against these factors (only you have enough information to make the correct choice). Personally I am always going to go for correctness and preventing mistakes first then optimize for speed when I prove to myself it needs that extra oomf (though that is a controversial opinion in the C++ world). :-)

I would start with the std::map as above, but if I need to improve the speed I would change to a std::vector but wrap it in structure to give accesses via the enum.

// Version 1
using PlanerHolder = std::map<Planets, PlanetData>;

// Now in the future I discover that map is not suffecient.
// Version 2
class PlanerHolder
{
    std::vector<PlanetData>    data;
    public:
        PlanerHolder()
            : data(CountOfPlanets)
        {}
        PlanetData& operator[](Planets index)
        {
            return data[static_cast<int>(index)];
        }
        // any other members you need.
};

Note: I have implemented PlanetData as a simple property bag (a structure with some unconnected data). You may want to upgrade this to a class with proper constructor and appropriate methods that support your use case (but please avoid get/set methods in preference of methods that do meaningful tasks).

Actually the first thing I would do is add a constructor so that the members are at least correctly initialized to zero. Though if you only use them in standard containers this is not required as the containers will do this for you.


// Version 1 Initialization:
#include <map>
#include <iostream>

struct PlanetData
{
    double periodOrbit;
    double logintudeAtEpoch;
    double longitudeOfPerihelion;
    double eccentricityOfOrbit;
    double semiMajorAxisOrbit;
    double orbitalInclination;
    double longitudeOfAscendingNode;
    double angularDiameterAt1AU;
    double visualMagnitudeAt1AU;
};

enum class Planet {Mercury, Venus, Earth, Mars, Jupiter, Saturn, Uranus, Neptune};
using PlanerHolder = std::map<Planet, PlanetData const>;
PlanerHolder ElementsPlanetaryOrbits{
    {Planet::Mercury, { 0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0 }},
    {Planet::Venus,   { 0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0 }},
    {Planet::Earth,   { 0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0 }},
    {Planet::Mars,    { 0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0 }},
    {Planet::Jupiter, { 0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0 }},
    {Planet::Saturn,  { 0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0 }},
    {Planet::Uranus,  { 0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0 }},
    {Planet::Neptune, { 0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0 }}
};


int main()
{
    std::cout << ElementsPlanetaryOrbits[Planet::Earth].orbitalInclination << "\n";
}
\$\endgroup\$
14
  • \$\begingroup\$ Thanks for your answer. The data in the table will never change. I only need to access it using the constants declared before it. \$\endgroup\$
    – VansFannel
    Dec 28, 2021 at 6:45
  • \$\begingroup\$ I don’t think you need to abandon the more-efficient array or map data structure here. The enum will automatically convert to an index. You might also implement a type-safe constexpr double orbitPeriod(planet) functions, etc., that look up the data in one or more constexpr arrays. Or, instead of an array with named indices, you could have nine named constexpr arrays. If you do want a map, it should be an unordered_map, which would be implemented as a hash table with constant-time access. \$\endgroup\$
    – Davislor
    Dec 28, 2021 at 12:31
  • \$\begingroup\$ @Davislor I know the enum will convert to int thats the problem. I want to make sure that I can only use the enum to access the planets. \$\endgroup\$ Dec 28, 2021 at 15:20
  • \$\begingroup\$ @Davislor Constant time does not mean faster. hash maps have a large overhead and for this small number of items that overhead way overwhelms the small access time of log(n). \$\endgroup\$ Dec 28, 2021 at 15:22
  • \$\begingroup\$ @VansFannel That fact that everything is constant does not change anything I have said above. \$\endgroup\$ Dec 28, 2021 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.