Re: std::set as search tree - manipulate elements?
Rune Allnor a ?crit :
Hi all.
I would like to use std::set to implement a histogram.
In essence the histogram contains some elements
struct histbin{
int bin;
int count;
/* constructors */
bool operator<(const histbin& h) const {return bin < h.bin;};
};
This is equivalent to a std::map<>. I assume you have a good reason for
not using it.
where histbin::bin denotes the range of each bin and
histbin::count denotes the number of hits.
The problem is how to build the histogram. Since
std::set is specified to have O(log n) search time,
it must necessarily be implemented as some sort of
tree structure. I would like to exploit this to do
something like
std::set<histbin> histogram;
std::set<histbin>::iterator i;
while (/* data coming in */)
{
i=histogram.find(data);
if (i!=histogram.end())
{
(*i).count+=1; // <<<<<======
}
else
{
/* insert new bin */
}
}
The problem is the tagged line. Apparently, all elements
in std::set are declared 'const', so I am not allowed to
manipulate the elements directly. Do note that I do *not*
manipulate the histbin::bin element, which is used as the
key for sorting, and thus it ought to be safe to manipulate
the histbin::count elements.
A Simple Associative Container (set) does not provide mutable iterators.
Otherwise, how would the compiler know which elements are safe to modify
regarding the comparision operation provided.
Is there a convemient, safe way to be able to use std::set
as the search tree for this histogram?
You can declare 'count' mutable.
If 'no', are there other STL containesr that can be used?
Any other Simple Associative Container will have the same constraint.
I would prefer not to have to implement a tree from scratch,
but if there are no alternatives I would like to know that
early on, and just get to work...
Using map<> looks more simple.
std::map<int,int> histogram;
while (/* data coming in */)
{
histogram[data]+=1;
//if data does not exists, default value is 0
}
--
Michael
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]