我有一个objecta property,这是该对象的方法所必需的:
class Object {
Property property;
}
然后我需要对这个对象进行分组.要求在该组中只有具有唯一属性的对象.将这些对象分组是很自然的set.我定义了一个operator<或者它是否unordered_set operator==和hash().没关系.然后出现另一个问题.我需要在set中找到这个对象property.所以我需要创建一个类型的对象,Object将该属性赋值给它的字段.这就是我不喜欢的地方.
另一种方法是制作一个map.并复制或指向对象的属性,然后将它们用作地图中的键.我认为这也是一项双重工作.
我想要类似的东西set,但有能力使搜索不使用整个对象,但使用对象的属性来查找它.例如,我定义以下内容:
class Object {
Property property;
bool operator<(Object obj) { return property < obj.property; }
bool operator<(Property obj) { return property < obj.property; }
};
some::set<Object> objSet;
然后我可以做以下事情:
Object obj;
objSet.insert(obj);
objSet.find(obj.property);
你可以提供一些容器的实现来帮助我吗？提升,qt是可以接受的.
对于我的程序,我需要无序密钥.为了完成工作,我使用std :: unordered_map容器.这是一个测试代码:
#include <iostream>
#include <unordered_map>
#include <string>
int main()
{
std::unordered_map<std::string, int> toto;
toto["Outlook"] = 454;
toto["Temperature"] = 4;
toto["Humidity"] = 554;
toto["Wind"] = 545454;
std::unordered_map<std::string, int>::iterator It = toto.begin();
std::cout << toto.size() << std::endl;
for (; It != toto.end(); ++It)
std::cout << (*It).first << std::endl;
getchar();
return (0);
}
在Windows(Visual Studio 2012)上,输出为:
Outlook
Temperature
Humidity
Wind
这是正确的.没有应用排序.
但在Linux上输出如下:
Humidity
Outlook
Wind
Temperature
PS:在linux上我使用-std :: c ++ 0x和-std = gnu ++ 0x编译我的程序,并且没有编译错误.
那么,如何在同一个程序中使用不同的行为呢？在此先感谢您的帮助 !
我正在另一个论坛上阅读以下帖子,这个帖子似乎对C++内部有很多关于将数千个密钥插入"字典"的知识:
e)Map-Set查找是使用Red-Black或Balanced Tree完成的,每个项目都是"单独"分配的,所以如果你要[按符号]分配500,000个仪器,并指向一个与相关的仪器对象类的指针,字符串有'N'个字节[加上开销],指针有4个字节[加上开销].并包括; 所有仪器上的1分钟,5秒,1秒的价格时间序列以及STD容器中所有这些仪器的完整贸易历史.由于小对象分配开销,这是一个很多的内存和一个很多的浪费!
f)出了名的是,STD Map&Set使用LowerBound [Less Than Compare]通过所有键到FIND,这很慢.
g)有些天才可能会说"不,他们使用未排序的地图"......好吧他们没有,但即使他们这样做,他们仍然在对一个离散分配的元素进行字符串比较.
我在C++中做的是以下(示例);
a)创建一个"自定义"就地String Class-object,它有两个个性; a)字节数组,和b)模数4和在本地边界上对齐的整数数组.b)使用自定义映射和集合,它们是基于2x维度的哈希,其中节点在平坦连续内存区域中分配[可以并且可以动态地重新调整大小].c)String [整数格式]散列由Integer完成,用于管道CPU和键比较类似地完成.
使用这些技术只能在C++,C或ASM中完成,在.NET,C#或Java中执行相同操作的性能至少有4-5倍.
如果我大致知道我将要插入多少个键,那么我可以使用哪些技术来设计我自己的unordered_map实现,这比我的特定用法更有效？
(关于设计散列函数的任何101都是最受欢迎的)
我有std::unordered_map<int, int>.我不想使用树或其他任何其他结构导致延迟要求.但是在任何时候我都需要知道当前的最大键和最小键.我怎样才能做到这一点？分布不均匀,而是经常删除和插入max和min.因此,我需要比"只删除当前最大/最小值时扫描整个地图以获得新的最大值/分钟"更聪明的东西.
我不想使用任何其他结构.我想用std::unordered_map!
UPD根据答案创建这样的结构:
struct OrderBookItem {
int64_t price;
int32_t lots;
};
typedef multi_index_container
<OrderBookItem, indexed_by<
hashed_unique<
BOOST_MULTI_INDEX_MEMBER(OrderBookItem,int64_t,price)
>,
ordered_unique<
BOOST_MULTI_INDEX_MEMBER(OrderBookItem,int64_t,price),
std::greater<int64_t>
>
>> OrderBookContainer;
我有大约20,000,000 pair<int, int>,我需要与ints联系.我这样做了unordered_map<pair<int, int>, int>.分析我的算法表明检查条目是否存在
bool exists = myMap[make_pair(a, b)] != NULL
是性能瓶颈.我认为从a中检索这些信息unordered_map会非常快,因为它是O(1).但如果常数很大,则恒定时间可能会很慢......
我的哈希函数是
template <>
struct tr1::hash<pair<int, int> > {
public:
size_t operator()(pair<int, int> x) const throw() {
size_t h = x.first * 1 + x.second * 100000;
return h;
}
};
你知道我的问题有更好的数据结构吗？
显然,我不能只将信息存储在矩阵中,因此内存量不适合现有的任何计算机.我所知道的所有分布都是myMap[make_pair(a, a)]不存在的a.并且所有ints都在从0到大约20,000,000的连续范围内.
可以把它想象成20,000,000x20,000,000的稀疏矩阵,大约有20,000,000个条目但从不在主对角线上.
将一vector<pair<int, int>>*(阵列Ñ预期的条目)要快？查找a将是微不足道的(只是数组的索引),然后我将迭代向量,比较对的first值b.
我上传了原始数据,因此您可以看到结构.
我要做的是使用prime为anagram创建哈希值; 但是struct key由于==操作员的缘故,不得不创建一个额外的东西.有没有解决方法来重载==std :: string 的现有？
#include <string>
#include <unordered_map>
#include <cstddef>
#include <iostream>
using namespace std;
int F[26] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97, 101};
size_t f(const string &s) {
size_t r = 1;
for (auto c : s) {
r *= F[c - 'a'] % 9999997;
}
return r;
}
// this …我有一个unordered_map,它包含一个枚举和一个字符串作为第二个.第一个值可能会以不同的顺序出现多次.这是一个例子:
enum SomeType
{
TYPE1,
TYPE2,
};
static std::unordered_map<SomeType, std::string> value_map =
{
{ TYPE2, "Value that shouldn't be found" },
{ TYPE1, "Value that gets found first" },
{ TYPE2, "Value that also never gets found" },
{ TYPE1, "Value that gets found second" },
{ TYPE2, "Value that gets found last" },
};
我想按如下方式遍历地图:例如,首先我想找到对TYPE1,这将为我提供第一个TYPE1值.之后,TYPE1再次搜索一个值不会让我获得第一个值,而是可以在它之后找到的下一个值.TYPE2在此之后搜索值只会净化最后一个值.
基本上我想找到下一个匹配的值,但是没有找到最后找到的值之前的值.
我多次尝试实现这样做,但我不太确定如何实现这样的算法.
如何实现这样的算法？
试图展示我想要的完整代码示例:https://godbolt.org/g/CgNZnj
请考虑以下代码:
unordered_map<string, vector<string>> hashtable;
string s = "foo";
hashtable[s].push_back("bar");
这似乎有效,但这意味着在第三行中,它通过在键"foo"处初始化字符串向量以及向此空向量添加"bar"来向哈希表添加新条目.我的困惑是我们为什么不必显式初始化一个向量,如:
unordered_map<string, vector<string>> hashtable;
string s = "foo";
vector<string> vec;
vec.push_back("bar");
hashtable[s] = vec;
令我困惑的是,当我们处理像在C++中初始化数组这样的事情时,最好显式初始化数组,如下所示:
int array[10] = {0);
如果我们想要确保数组初始化并且所有值都为0,那么这是必需的,因为没有它,可能存在存储在数组初始化的同一位置的内存中的垃圾值.回到哈希表的第一个问题,我们怎么知道
hashtable[s].push_back("bar");
是不是将"bar"推入具有垃圾值的向量中？
我意识到我的问题根本不清楚.对[]运算符的行为和STL容器的默认值的任何澄清都是一般的,我们将不胜感激.
默认函数来自std :: hash。我想知道是否有更好的哈希函数可以节省计算时间？用于整数键和字符串键。
我尝试使用Google的City Hash的整数和字符串键，但其性能比std :: hash差一些。
我有一个无序的地图,其中一个键的int值为a,值为a struct.如果找不到密钥,我希望地图创建零初始化struct.
struct TestStruct
{
int a;
};
void foo()
{
std::unordered_map<int, TestStruct> map;
TestStruct& test = map[1];
}
在调试时我可以看到这些值test.a == 0是巧合吗？
相关文章:c ++结构是否有默认构造函数？