标签: multiset

我试图使用以下方法擦除multiset的最后一个元素:

minheap.erase(minheap.rbegin());

它不编译,并给出4-5个错误.

请注意,在C++多字节中,.end()最后一个元素旁边的点,而不是最后一个元素.

有任何想法吗？

编辑:

为什么这提供不同的数字？

multiset <int>::reverse_iterator it1 = minheap.rbegin();
m1=*(++it1);

multiset <int>::iterator it2 = minheap.end();
m2=*(--it2);

我已经定义了一个子接口,java.util.Collection它实际上是一个multiset(又名包).它可能不包含null元素,尽管这对我的问题并不重要.接口定义的equals合同正如您所期望的那样:

• obj instanceof MyInterface
• obj包含与this(by equals)相同的元素
• obj 每个元素包含相同数量的重复项
• 元素的顺序被忽略

现在我想写我的hashCode方法.我最初的想法是:

int hashCode = 1;
for( Object o : this ) {
    hashCode += o.hashCode();
}

但是,我注意到com.google.common.collect.Multiset(来自Guava)定义了哈希码,如下所示:

int hashCode = 0;
for( Object o : elementSet() ) {
    hashCode += ((o == null) ? 0 : o.hashCode()) ^ count(o);
}

令我感到奇怪的是,一个空的Multiset会有哈希码0,但更重要的是,我不理解^ count(o)简单地添加每个副本的哈希码的好处.也许这不是一次多次计算相同的哈希码,但为什么不* count(o)呢？

我的问题:什么是有效的哈希码计算？在我的情况下,元素的计数不能保证很便宜.

只是为了好玩,我已经实现了可以想象的最简单的排序算法:

template<typename Iterator>
void treesort(Iterator begin, Iterator end)
{
    typedef typename std::iterator_traits<Iterator>::value_type element_type;

    // copy data into the tree
    std::multiset<element_type> tree(begin, end);

    // copy data out of the tree
    std::copy(tree.begin(), tree.end(), begin);
}

它比std::sort我的测试数据慢大约20倍:)

接下来,我想通过移动语义来提高性能:

template<typename Iterator>
void treesort(Iterator begin, Iterator end)
{
    typedef typename std::iterator_traits<Iterator>::value_type element_type;

    // move data into the tree
    std::multiset<element_type> tree(std::make_move_iterator(begin),
                                     std::make_move_iterator(end));
    // move data out of the tree
    std::move(tree.begin(), tree.end(), begin);
}

但这并没有显着影响性能,即使我正在排序std::string.

然后我想起关联容器是不变的来自外部的,就是std::move和std::copy将在这里做同样的事情:(是否有移动数据从树上任何其他方式？

我在Scala尝试Facebook Hacker Cup 2013资格问题,对于第三个问题,我觉得需要一个有序的Multiset,但在scala(2.10)集合中找不到.scala的集合中是否缺少此数据结构.它将在未来版本中实施吗？如果已经实现了集合,那么Multiset是不是真的有必要？

如何在Python中统一以下列表:

all_the_ways = [(5,), (2, 2, 1), (2, 1, 2), (2, 1, 1, 1), (1, 2, 2),\
                (1, 2, 1, 1), (1, 1, 2, 1), (1, 1, 1, 2), (1, 1, 1, 1, 1)]

期望的输出是:

[(5,), (2, 2, 1), (2, 1, 1, 1), (1, 1, 1, 1, 1)]

即我需要摆脱具有相同数字但不同顺序的元组.

我试过了

set(all_the_ways)

但它只转置元素.

而当我这样做

list(map(set, all_the_ways))

事情变得更糟:

[{5}, {1, 2}, {1, 2}, {1, 2}, {1, 2}, {1, 2}, {1, 2}, {1, 2}, {1}]

换句话说,我需要将内部元组转换为允许多个相等项(不适合)的集合,set并且元素的排列不会改变集合本身(有点像C++的multiset …

有什么用的Table-CAST和CAST-Multiset？

例子 Table-Cast

SELECT count(1)
INTO   v_Temp
FROM   TABLE(CAST(Pi_Save_Data_List AS Property_data_list))
WHERE  Column_Value LIKE '%Contact';

例子 Cast-Multiset

SELECT e.last_name,
   CAST(MULTISET(SELECT p.project_name
   FROM projects p 
   WHERE p.employee_id = e.employee_id
   ORDER BY p.project_name)
   AS project_table_typ)
FROM emps_short e;

性能增益或对代码的影响是什么？

可以如下访问计数器的最大值:

c = Counter()
c['foo'] = 124123
c['bar'] = 43
c['foofro'] =5676
c['barbar'] = 234
# This only prints the max key
print max(c), src_sense[max(c)] 
# print the max key of the value
x = max(src_sense.iteritems(), key=operator.itemgetter(1))[0]
print x, src_sense[x]

如果我想要一个降序计数的排序计数器怎么办？

如何访问第二个最大值,第三个或第N个最大值？

我有一个多组 int 。C++

multiset<int>t;

我需要找到大于等于 val 的第一个元素的位置。我为此使用了lower_bound

multiset<int>::iterator it= lower_bound(t[n].begin(), t[n].end(), val);

但是找不到从多集开始的相对位置。正如 The Cplusplus.com 建议使用...作为向量。

// lower_bound/upper_bound example
#include <iostream>     // std::cout
#include <algorithm>    // std::lower_bound, std::upper_bound, std::sort
#include <vector>       // std::vector

int main () {
  int myints[] = {10,20,30,30,20,10,10,20};
  std::vector<int> v(myints,myints+8);           // 10 20 30 30 20 10 10 20

  std::sort (v.begin(), v.end());                // 10 10 10 20 20 20 30 30

  std::vector<int>::iterator low,up;
  low=std::lower_bound (v.begin(), v.end(), 20); //          ^
  up= std::upper_bound (v.begin(), v.end(), 20); //                   ^

  std::cout …

让我们说如果N中的每个元素在M中至少出现多次,则多个集合M 支配另一个多集N.

给定一个目标多集M和一个整数k> 0,我想找到一个列表,L,大小-K多集,其总和占主导地位M.我想这个名单是小的成本,我的成本函数是形式:

cost = c*m + n

其中c是常量,m是L中多重集的数量,n是L中不同多重集的数量.

我怎样才能做到这一点？找到最优解的有效算法将是理想的.

问题来自于尝试使用专门的块打印机来执行客户打印页面的订单,该打印机一次打印k页.设置块打印机以打印k页的特定模板是昂贵的,但是一旦初始化模板,使用它进行打印是便宜的.目标多集M表示客户的订单,列表L的n个不同的多集表示n个不同的k页模板.

在我的特定应用中,M通常具有> 30个元素,其多重性在[10 ^ 4,10 ^ 6]的范围内.k的值为15,c约为10 ^ -5.

在给定索引的情况下,我试图找到一种有效的算法来查找多集的排列.

例如:给定{1, 3, 3}.按升序词典顺序排列的所有排列都是{133, 313, 331}.这些元素被索引为{0, 1, 2}.鉴于index=2,结果是331.

我找到了一种算法来查找给定词典索引的集合的排列.他的算法很有效:O(n ^ 2).

但是,算法在适当的集合(例如{1, 2, 3})上进行测试,并且在我的测试中不正确.我在这里描述他的python代码,以便您可以轻松地遵循.

from math import factorial, floor #// python library
from math import factorial, floor #// python library
i=5 #// i is the lexicographic index (counting starts from 0)
n=3 #// n is the length of the permutation
p = range(1,n+1) #// p is a list from 1 to n
for k in range(1,n+1): #// k goes …