set of integers

[gnugu]

hi
i need a datastructer similar to a set (adding and removing elements) with the additional property that i can quickly find the maximum element. is there such a datastructure in stl? i cannot find one.
i can build such a dataqstructure by combining a heap and a set (implemented by a tree or hashtable). each node of the tree has a pointer to the corresponing node in the heap and vice versa. if i remove a node from one datastructer i can find and remove the corresponding node from the other structure. but i see no way to use the exisiting stl containers. i think i must implement the heap and the tree form the scratch or is ther a way to use the existing stl containers and algorithms?
for my program the elements of the set are integers in the range 1...50 000 and the set contains at most 50 elements

guenter

[helios]

That would have to be either an std::set or a sorted std::vector. A vector would be the better choice, IMO.
http://en.wikipedia.org/wiki/Insertion_sort

[gnugu]

to find the maximum in std::set it is necessary to scan the whole set this means O(n) comparison if n is the number of elements. using a std::vector where the elements are sorted makes it necessary to move O(n) elements after each insertion or delietion of an element. combining a heap and an appropriate tree allows insertion, deletion an finding max in O(log(n)) steps.
as far as i see a naive usage of std::set or std:: vector does not allow quick operations

[helios]

Uh...

std::set<int>::iterator i=set.end();
--i;
int max=*i;

You get the max in O(log n), not counting the time it takes to insert the elements, which I'm guessing it's O(n log n) or something like that.
Using a sorted vector, sorting only once with a fast sort, you can do it O(n log n).
Now, assuming you can do this, it can be done in O(n) by not sorting the vector at all and just keeping track of the max and min.

But honestly, the difference between O(n log n) and O(log n) is irrelevant for n=50. It's better to just choose a barely good but simple algorithm.

[gnugu]

thanks
i missed the sentence

Internally, the elements in a set are always sorted from lower to higher following a specific strict weak ordering criterion set on container construction.

in http://www.cplusplus.com/reference/stl/set/
therefore a std::set does perfectly what i need
guenter