d***a
发帖数: 316 | 1 一个用multimap的sample code，有些不明白为什么会是这样的输出结果。
code如下：
#include
#include
#include |
|
c**********e
发帖数: 2007 | 2 Associative container 是 set, multiset, map, multimap 这些东西吗？
原来C++容器也分贫下中农：
Sequence Container: vector, deque, list
Container Adaptor: stack, queue, priority_queue
Associative container: set, multiset, map, multimap ??? |
|
S**I
发帖数: 15689 | 3 multimap按key排序，不是按value。 |
|
r**h
发帖数: 1288 | 4 用一个multimap
左边是一个string，右边是对应的字符串的index
因为所有anagram，他们sort后的字符串都是一样的。
第一轮loop，sort每个string，按照sort的结果加入到multimap里
第二轮遍历multimap，输出字符串
multimap mmp;
multimap::iterator it;
vector results;
string tmp;
for(int i=0; i
tmp = strs[i];
sort(tmp.begin(), tmp.end());
mmp.insert(std::pair(tmp, i));
}
for(it=mmp.begin(); it!=mmp.end(); it++){
results.push_back(strs[(*it).second]);
}
return results; |
|
e***n
发帖数: 42 | 5 搞定.用了multimap 和两个iterator.
#include |
|
|
w****o
发帖数: 2260 | 7 1. STL中的std::unordered_map是不是等同于（或者是类似）Java中的Hashmap?
2. STL中的std::map是不是等同于（或者是类似）Java中的Treemap?
3. STL中hashtable是哪个类实现的？Java中类似的哪个类叫什么名字？问的就是在STL
和Java下都是叫什么名字。
4. 为什么在我的linux机器上的目录/usr/include/c++/4.1.2下只有set, map而没有
multiset和multimap?你们的系统里有multiset和multimap吗？
另外我发现STL的unordered_map和unordered_set是定义在/usr/include/c++/4.1.2/
tr1下面的。
谢谢！ |
|
w****o
发帖数: 2260 | 8 谢谢 SETI,
我看了一下，
set文件包含了
#include
#include
#include
map文件包含了
#include
#include
#include
现在明白了multiset和multimap都已经在STL了。非常感谢。
仍有一问题不明白，就是如果写C/C++代码，如何用hashtable?难道要自己实现吗？好
像不太容易吧如果from scratech的话。
好像在tr1/下面有一个文件hashtable,unordered_map, unordered_set的实现都用到了
tr1/hashtable,是不是可以说这个就是STL 扩展中的hashtable的实现呢？
是不是我们写代码的时候可以用tr1/hashtable去用作hashtable?
谢谢了！
multimap? |
|
r*******t
发帖数: 99 | 9 这个题相当于一个Jump Game：一排格子，每一个可以往后面的某些格子里跳，每一跳
的cost是0。同时每一个可以往紧邻的下一个格子跳，每一跳的cost是1。把格子看成
vertex,跳看成edge的话就是一个directed graph的shortest path问题，而且这个图已
经是topologically ordered，只用从前往后scan一遍所有vertices，同时update当前
vertex前方与之相连的vertices就可以了。
每一个vertex有哪些outgoing的edges可以查用anagram索引过的dictionary来确定。索
引dictionary的时候记下最大词长可以减少look up的次数。
string minSkip(vector& dictionary, string& str) {
multimap ana2word;
size_t maxLength = 0;
for (size_t i = 0; i < dictionary.size(); ++i) {
... 阅读全帖 |
|
l*********8
发帖数: 4642 | 10 My two cents:
遍历所有边，把color-color relations 存在multimap里面。
最后扫描multimap找出relation最多的color. |
|
s*w
发帖数: 729 | 11 Google 了一下，这个问题没我想象的容易啊，大致是个 data view 的意思；好像有个
view
pattern 没明白啥意思；下面的是根据有人的建议的一个简单实现。主要麻烦是 set,
map 都不能
用 sort, 只能利用插入时候的缺省 sort
#include
#include
#include |
|
w****o
发帖数: 2260 | 12 【 以下文字转载自 JobHunting 讨论区 】
发信人: winhao (勇敢的人), 信区: JobHunting
标 题: 问几个关于hash, map, set的问题
发信站: BBS 未名空间站 (Wed Mar 7 14:52:17 2012, 美东)
1. STL中的std::unordered_map是不是等同于（或者是类似）Java中的Hashmap?
2. STL中的std::map是不是等同于（或者是类似）Java中的Treemap?
3. STL中hashtable是哪个类实现的？Java中类似的哪个类叫什么名字？问的就是在STL
和Java下都是叫什么名字。
4. 为什么在我的linux机器上的目录/usr/include/c++/4.1.2下只有set, map而没有
multiset和multimap?你们的系统里有multiset和multimap吗？
另外我发现STL的unordered_map和unordered_set是定义在/usr/include/c++/4.1.2/
tr1下面的。
谢谢！ |
|
w****o
发帖数: 2260 | 13 【 以下文字转载自 JobHunting 讨论区 】
发信人: winhao (勇敢的人), 信区: JobHunting
标 题: 问几个关于hash, map, set的问题
发信站: BBS 未名空间站 (Wed Mar 7 14:52:17 2012, 美东)
1. STL中的std::unordered_map是不是等同于（或者是类似）Java中的Hashmap?
2. STL中的std::map是不是等同于（或者是类似）Java中的Treemap?
3. STL中hashtable是哪个类实现的？Java中类似的哪个类叫什么名字？问的就是在STL
和Java下都是叫什么名字。
4. 为什么在我的linux机器上的目录/usr/include/c++/4.1.2下只有set, map而没有
multiset和multimap?你们的系统里有multiset和multimap吗？
另外我发现STL的unordered_map和unordered_set是定义在/usr/include/c++/4.1.2/
tr1下面的。
谢谢！ |
|
s*********g
发帖数: 153 | 14 楼主发挥的很不错了，虽败尤荣，Bloomberg可能比较严吧。
对于第一个问题：首先
ihasleetcode 指出了查找某个level的答案，用DST做时间复杂度o(n),BST做2*O（n）
，多了n个pop_front in queue的操作。
即时打印所有level，两个时间复杂度是一样的。
第二个问题，我认为楼主的思想很正确，但是可以用更好方法：
multimap my_multimap
每次插入操作前，用 my_multimap.count（string）看看满不满20个，如果满的话
my_multimap.erase(my_mulltimap.find(string)),移出最早的第一个数据，再插入新
数据，这样就永远保持最新的20个数据了。所以说，楼主思想正确，但是忘记用最好的
STL structure了
time |
|
m**q
发帖数: 189 | 15 还是对STL不熟，multimap的话用lower_bound和upper_bound就够了，
找y坐标在lower_bound(y-h)和upper_bound(y+h)之间的点
或者用一个set，元素是pair，自动按先y坐标后x坐标排序，
然后还是用lower_bound+upper_bound. |
|
m**q
发帖数: 189 | 16 还是对STL不熟，multimap的话用lower_bound和upper_bound就够了，
找y坐标在lower_bound(y-h)和upper_bound(y+h)之间的点
或者用一个set，元素是pair，自动按先y坐标后x坐标排序，
然后还是用lower_bound+upper_bound. |
|
a**********2
发帖数: 340 | 17 1.一组用户信息，包括first name， last name，phone number等等，设计一个结构存
储这些信息，能够动态添加，并且能根据first name或者last name进行查找。
我就想到用两个multimap存储，不知道有什么好的思路
2.顺便问道老题
In our indexes, we have millions of URLs each of which has a link to some
page contents, that is, URL->contents. Now, suppose a user types a query
with wild cards *, which represent 0 or multiple occurrences of any
characters, how do you build the indexes such that such a type of query can
be executed efficiently by finding all corresponding URLs->contents
ef... 阅读全帖 |
|
q****x
发帖数: 7404 | 18 又想了一下，这个三叉树实际还是二叉树，不过把相同的键放到一个单链表里。
multiset和multimap就是用这个实现的吧？ |
|
S**I
发帖数: 15689 | 19 1. yes
2. yes
3. N/A in C++, HashTable in Java
4. Do you know which header file to include when using multiset or multimap?
unordered_map and unordered_set only became part of std recently, the
implementation hasn't been updated yet.
STL |
|
P*A
发帖数: 189 | 20 来自主题: JobHunting版 - 讨论一道题 用BST挺好，比heap维护更方便，
修改了一下，可以不用把pair当作key来排序，在hash里面记录BST结点的指针
multimap bst;
hash_map > hm;
foreach given key k
0. if(hm.find(k)==hm.end()) {
hm.insert(make_pair(k, make_pair(1, bst.end())));
if (bst.size () < K) {
// bst里元素不足K
t = bst.insert (make_pair(f, k))
hm[k].second = t;
}
continue;
}
1. f = ++hm[k].first;
2. if (hm[k].second != bst.end()) {
// bst里有k了，那么更新freq值
bst.erase (hm[k].se... 阅读全帖 |
|
G******e
发帖数: 229 | 21 How about using multimap? |
|
p****c
发帖数: 35 | 22 先是各自简单的自我介绍。然后两道很常规的题目:
1. 判断字符串不考虑标点空格的情况下是回文.
2. 给定一组字符串, 按anagram分组后，返回list of list.
当时脑子一片空白，用了半个多小时才搞定。第一题跳过标点空格时忘了检查字符越界
. 写完后，说我先测试一下. 假设输入是一个空格, 自己走了一遍说好像可以.考官问
你的测试真的可以吗？才发现了没有检查字符越界的bug. 赶快加上.考官说可以简化一
下while的条件吗？看了一下去掉了一个多余的条件,说我看看还能再简化吗. 考官说可
以了，你的程序works, 下一个吧.
第二题一开始突然不知道该用什么数据结构。我说就定义一个less_than直接排序就可
以了. 刚想写less_than, 觉得这样太复杂，我说还是用hash或者map吧。考官说key是
什么, 我说没有key,就用hash_set或者multiset吧. 考官说你可以造一个key吗？我说
可以把字符串排序作key. 然后开始定义数据结构. hash_map, 写到
这里看了一下改成multimap阅读全帖 |
|
i**********d
发帖数: 105 | 23 我用c++。一般我就assume有hashtable，他们也说可以。或者map， multimap。
总之c++比c好多了。 |
|
u*****o
发帖数: 1224 | 24 第二题可以用MULTIMAP里的COUNT吗？先建TABLE，然后扫一遍，记录MAXCOUNT？ |
|
|
t******i
发帖数: 483 | 26 为啥用multimap?每个字母，hashmap就可以啊。 |
|
u*****o
发帖数: 1224 | 27 我是想用multimap里的COUNT来数FREQUENCY啊, hashmap同样的字母只能放一次啊 |
|
t******i
发帖数: 483 | 28 2) 给出字符串，输出一个表，这个表（tab-le）要有每个字母在字符串中出现的次数
每个字母做key, value就是出现的次数就足够了啊
比如 apple hadoop pig
key value
a 2
d 1
e 1
p 4
l 1
h 1
i 1
g 1
o 2
value 就是每个字母在字符串中出现的次数
还是没懂为啥你要用multimap |
|
u*****o
发帖数: 1224 | 29 可以啊，VALUE记录FREQUENCY用hashmap就行啊，我只是当时想用VAL=index吗，就想着
用multimap了。。 |
|
s**x
发帖数: 7506 | 30 应该可以吧？ multiset, multimap etc. |
|
|
|
s*********n
发帖数: 35 | 33 前天BB onsite就遇到这道题了，交易会不断的进来，然后getTop10(或者topN)也会频
繁的调用，让设计。 刚开始说priority_queue，对面国人大哥问什么是pq, 改口说
heap，也不让，最后我用双map, 一个map存ticker->{volume, iter_of_rankmap}, 另
一个multimap rankermap, size约束成10，存volumn->ticker, 自圆其说算是解决了
，面试的说cool cool，也不知道是真酷还是忽悠我，至今没想到其他方法。 |
|
a*********0
发帖数: 2727 | 34 class Solution {
public:
vector findRepeatedDnaSequences(string s) {
int map[4];
std::fill(map, map+4, 0);
vector res;
set keySet;
multimap mmap;
if(s.size()<10) return res;
for(int i=0;i
map[toInt(s[i])]++;
if(i>=9){
if(i>=10){
map[toInt(s[i-10])]--;
}
string ss=toString(map);
... 阅读全帖 |
|
A*******e
发帖数: 2419 | 35 1.明白了。
2.直接在普通rb-tree上加个计数器不就好了吗？何必重复key？而且一直没搞懂，
multiset/multimap有什么必需应用么？ |
|
w*********e
发帖数: 49 | 36 multimap比较好理解，就是一样的key不同的value
multiset确实等同于可key－count的map，但是据说在combinatorics里有应用，看了看
wiki没看懂 |
|
A*******e
发帖数: 2419 | 37 一样的key不同value也很奇怪啊。直接key到unique value set不就可以了？无非是一
个key返回所有value，或者第k个，或者随机返回一个。
平时写代码从来没用过multimap/set。而且unordered_map/set里不存在对应的结构。 |
|
A*******e
发帖数: 2419 | 38 1.明白了。
2.直接在普通rb-tree上加个计数器不就好了吗？何必重复key？而且一直没搞懂，
multiset/multimap有什么必需应用么？ |
|
w*********e
发帖数: 49 | 39 multimap比较好理解，就是一样的key不同的value
multiset确实等同于可key－count的map，但是据说在combinatorics里有应用，看了看
wiki没看懂 |
|
A*******e
发帖数: 2419 | 40 一样的key不同value也很奇怪啊。直接key到unique value set不就可以了？无非是一
个key返回所有value，或者第k个，或者随机返回一个。
平时写代码从来没用过multimap/set。而且unordered_map/set里不存在对应的结构。 |
|
z***u
发帖数: 105 | 41 面试中遇到的数据结构设计题，请教有没有更好的办法。还有最后一问没有打上来，请
教如何设计最后一题。
问题： 有很多不同型号的汽车要测试，每分钟采集一个数据，比如实时的MPG(假设都
是整数), 数据格式如下：["car1", 19], ["car2" 22], ["car3" 21]...
1. 问： 设计一个数据结构来存储每个车最新的数据
答： unordered_map
2. 问： 如何改进来存一天的数据， 并且支持返回某时间段的MPG值，比如get("car1"
, 12：00，13：00）
答： unordered_map 加 map， 如unordered_map< string/*car name*/, map
time stamp*/, int/*MPG data*/> >.
map 是排好序的，用lower_bound，和upper_bound找出时间的区间返回值
3. 如果需要找出N个车，它们的平均MPG最高。如何改进已有的数据结构。
我给出的答案是multimap阅读全帖 |
|
P****e
发帖数: 385 | 42 时间：4月9日，本周六，下午6点
地点：安瑞斯，具体地址及交通方法见下.
人物：piano, tuir, maevis, leoq & friend,pierce
关于餐馆：
Please have a look at:
http://www.multimap.com/map/browse.cgi?pc=NW6+7QE
405 Kilburn High Road (A5), London, NW6 7QF
The restaurant is between the tube/rail stations, Kilburn and Brondsbury and
at the same side of the road.
TEL: 020 7625 2663 |
|
|
S**I
发帖数: 15689 | 44 Of course; for example, C++ STL has multiset and multimap, which allow
existence of elments with equivalent keys. Also, both of them have a member
function equal_range, which does exactly what you want.
a |
|
q*****g
发帖数: 72 | 45 string is sequential container
associative container: set, multiset, map, multimap |
|
s**p
发帖数: 207 | 46 i have a sparse matrix to solve, which need to change a little bit in the
future, will add 1 or 2 non-zero elements or delete 1 or 2 evertime.
i want to use CSR (compressed storage by row) to store it
one way is to implement with three vectors, val, row_ptr, col_idx
but this will give me trouble when i modified the matrix. changing only
several elements I need to re-do the whole procedure.
so I want to use a multimap. which should work very nicely.
then i have one concern, how can i deal with t |
|
t*********e
发帖数: 1136 | 47 为啥要load百万数据？hash multimap的performance难掌握。数据一多就得考虑连续性
。不然可能page faults很多。 |
|
|
t****t
发帖数: 6806 | 49 exactly, you select the best data structure for your problem. you seem to
want to use the integer as the key since you compared it -- then you should
use array.
so make up your mind: what do you want to use as key? the string, use map<
string, int> or map; the index, use map or multimap<
int, string> or vector or string[].
you still need to clear up your concepts. it's still a mess.
not
have |
|
d*******n
发帖数: 524 | 50 map is what I need and the string is used like a name (i.e. key).
The reason I was comparing index was because I though the map needs a
comparator for the value (class A), so I simply gave it one based on
comparing index, which is not really needed. This turned out to be a
misunderstanding that messed the logic up.
Other than that, nothing is messed up.
should
multimap< |
|
