Re: What's the best data structure for this job?
On May 25, 4:29 am, Sam <s...@email-scan.com> wrote:
Rui Maciel writes:
I'm writing a class that processes SI units, which represents each unit=
as a vector of unit/exponent pairs.
According to my current implementation plan, the force units (the Newto=
n) would be represented as [N,1] or,
after converting to the SI base units, [kg,1],[m,1],[s,-2]. To avoid wa=
sting space with redundant
information, the unit in the unit/exponent pair is a reference index to=
a hash table that stores the unit's
name and symbol.
So, according to this scenario, what would be the best data structure f=
or this job? Currently I'm using
nothing more than the STL containers for the data stuctures and the GNU=
MP bignum library for the exponent.
More precisely, I'm storing the SI units as:
std::vector< std::pair<unsigned int, mpq_t> > expression;
The SI unit list is being stored as:
std::map<unsigned int, std::pair<std::string, std::string> > units;
Nonetheless, I feel that this solution is far from perfect, not to ment=
ion a bit overwhelming. Moreover,
the static and global nature of a SI unit list leads me to believe that=
there must be a simpler solution
than a singleton wrapper class on a simple standard map.
So, what's your take on this issue? How would you implement a data stru=
cture for this task?
Have you considered using a unified list of base and compound SI units?
There's a variety ways of implementing it:
class si_info {
public:
std::string symbol;
std::string name;
std::vector<unsigned int> base_units;
};
typedef std::map<unsigned int, si_info> units;
A compount SI unit, like a newton, would have a three-element base_units
vector, containing the index of the kg, m, and s base units. An SI base u=
nit
is represented with the base_units vector containing one element, the ind=
ex
of the SI base unit itself.
You now have a uniform reference for either a base or a compount unit, th=
e
single unsigned int handle. To be even more pedantic, rather than using
unsigned int explicitly as a handle, use a symbolic typedef:
typedef unsigned int si_handle_t;
class si_info {
public:
std::string symbol;
std::string name;
std::vector<si_handle_t> base_units;
};
typedef std::map<si_handle_t, si_info> units;
This is considered a more elegant design, and it adds additional flexibil=
ity
later down the road.
The value of an SI unit is then reduced to a single vector:
class si_value {
public:
si_handle_t si_unit;
std::vector<mpq_t> si_values;
};
si_unit gives the key to the units map. You can also use a simple
std::pair<si_unit, std::vector<mpq_t> > typedef, here.
You'll have to enforce two restrictions with this design:
1) All elements of the base_units vector in the SI map must reference onl=
y
other elements whose base_units vector is of size 1, and contain the same
si_handle_t value as the element itself -- that is, the element is either=
a
base element, or consists of only other base elements.
2) The size of your mpq_t vector must match the size of the base_units
vector in the si_info map. The nth element of the mpq_t vector gives the
value for the SI unit given by the nth element of the base_units vector.
Seems to me that with this design you can proceed and write code that
uniformly deals with base SI units and compount SI units, using the same
logic.
application_pgp-signature_part
< 1KViewDownload- Hide quoted text -
- Show quoted text -