yee young han wrote:
I need a fast data structure and algorithm like below condition.
(1) this data structure contain only 10,000 data entry.
(2) data structure's one entry is like below
typedef struct _DataEntry_
As an aside, names starting with an underscore, followed by a capital
letter are reserved for the implementation, so you really want to use a
different name. In C++ there's also no reason to use a typedef for this
situation anyway -- you can just use 'struct X' and be done with it.
{
char szInput[4];
char szOutput[4];
int iSum;
} DataEntry;
(3) input data length is 100,000,000.
(4) if there is a same szInput & szOutput data in data structure when
input data, only sum iSum into found data.
(5) this data structure have only 10,000 data entry that has large
number of iSum.
So far, what you're really describing is what you've done so far to
attempt to solve the problem -- but you haven't really told us what
problem you're trying to solve.
As such, I'm only taking a rather wild guess at the problem, but if I'm
right, I'd structure things a bit differently:
struct key {
std::string input,
output;
key(std::string in1, std::string in2) : input(in1), output(in2) {}
bool operator<(key const &other) {
if (input >= other.input)
return false;
return output < other.output;
}
friend std::ostream &operator<<(std::ostream &os, key const &k) {
os << k.input << " " << k.output;
}
};
std::map<key, int> values;
Now, let's assume (for example) that you have a file full of records,
one record per line, formatted like:
input output number
We can then process the data like:
std::string in1, in2;
int value;
while (stream >> in1) {
stream >> in2;
stream >> value;
values[key(in1, in2)] += value;
}
Since you describe keeping things sorted, it sounds like you probably
want to be able to print out the sums in order:
typedef std::pair<key, int> Vmap;
std::ostream &operator<<(std::ostream &os, Vmap const &v) {
return os << v.first << " " << v.second;
}
std::copy(values.begin(), values.end(),
std::ostream_iterator<Vmap>(std::cout, "\n"));
--
Later,
Jerry.
The universe is a figment of its own imagination.
