有这么的容器吗？关键值不重复的堆栈
有这样的容器吗？关键值不重复的堆栈
有一个大数据量的计算，用堆栈来记录计算的主线。
压数据时，要判断是否堆栈里已存在这个数。
如果存在就不能再压，返回FALSE，否则压入数据，并返回TRUE
堆栈的长度比较大，比较多的情况是在100~200之间，峰值可以到3000。
有没有Stack容器（跟STL的Stack不同哦，只是为了方便用了这个名字）可以实现
BOOL Stack::push(UINT Key);
压数、弹数操作非常频繁，估计每秒在百万次，所以效率就很关键了。顺序查找肯定是不行的。
------解决方案--------------------
#include <set>
------解决方案--------------------
如果按你所说，stl根本不适合你，它不是为这么“高效率”场合设计的。
------解决方案--------------------
1. unordered_set (C++11, 基于hash, 更快一些)
2. set (基于map, 比较适合插入删除频繁的情况, 速度也不差)
3. 如果数字范围已知, 例如1~4000, 那可以自己用bitset构造一个4000/8=625bytes的简单位图. 速度最快.
------解决方案--------------------
每秒百万次估计有点难度了
------解决方案--------------------
怎会不是太好呢，其实挺适合的，自行做个适配器就是了，例如：
嫌C++03的set性能不够的话，可以使用C++11的散列unordered_set，快得多。
如果希望适于对set的扩展，可以将_check的类型改为std::set< T > *，由MyStack的构造函数传递该指针就行了。
------解决方案--------------------
如果楼主不嫌弃麻烦的话，可以用boost库的unordered_set，速度更快
或者用google 前几个星期公布的基于B-tree的set，效果也会比用set好
有一个大数据量的计算，用堆栈来记录计算的主线。
压数据时，要判断是否堆栈里已存在这个数。
如果存在就不能再压，返回FALSE，否则压入数据，并返回TRUE
堆栈的长度比较大，比较多的情况是在100~200之间，峰值可以到3000。
有没有Stack容器（跟STL的Stack不同哦，只是为了方便用了这个名字）可以实现
BOOL Stack::push(UINT Key);
压数、弹数操作非常频繁，估计每秒在百万次，所以效率就很关键了。顺序查找肯定是不行的。
栈
------解决方案--------------------
#include <set>
------解决方案--------------------
如果按你所说，stl根本不适合你，它不是为这么“高效率”场合设计的。
------解决方案--------------------
1. unordered_set (C++11, 基于hash, 更快一些)
2. set (基于map, 比较适合插入删除频繁的情况, 速度也不差)
3. 如果数字范围已知, 例如1~4000, 那可以自己用bitset构造一个4000/8=625bytes的简单位图. 速度最快.
------解决方案--------------------
每秒百万次估计有点难度了
------解决方案--------------------
怎会不是太好呢，其实挺适合的，自行做个适配器就是了，例如：
template< typename T >
class MyStack : public std::stack< T >
{
public :
typedef typename std::stack< T >::size_type size_type;
void push( const size_type& Item )
{
if( _check.insert( Item ).second ) std::stack< T >::push( Item );
}
private :
std::set< T > _check;
};
嫌C++03的set性能不够的话，可以使用C++11的散列unordered_set，快得多。
如果希望适于对set的扩展，可以将_check的类型改为std::set< T > *，由MyStack的构造函数传递该指针就行了。
------解决方案--------------------
如果楼主不嫌弃麻烦的话，可以用boost库的unordered_set，速度更快
或者用google 前几个星期公布的基于B-tree的set，效果也会比用set好