Многозначная карта в Scala

Question

В Scala 2.8 у меня есть неизменный карта с несколькими значениями для каждого ключа:

Map[T,Iterable[U]]

Есть ли высшее представительство?Во-вторых, как бы вы создали такую ​​карту из

Iterable[(T,U)]

?В настоящее время я использую:

def toGroupedMap[T,U](vals: Iterable[(T,U)]): Map[T,Iterable[U]] =
  vals.groupBy(_._1).map({ case (s,it) => (s,it.map(_._2)) }).toMap

Это работает, но кажется неуклюжим.

РЕДАКТИРОВАТЬ: Я должен указать, что работаю с неизменяемыми данными.Существует ли неизменный эквивалент MultiMap?

Answer 1

Если вам действительно не нужна неизменность, то, как говорили другие, MultiMap это путь.Если вам действительно нужна неизменность, то выбранный вами подход так же прост, как и все остальное;здесь нет ничего встроенного (AFAIK), и любое создание неизменяемого MultiMap потребует гораздо больше работы, чем метод, который у вас есть.

Является ли представление лучшим, зависит от вашего использования.Часто ли вам хочется делать что-то со всеми значениями, соответствующими одному ключу?Можете ли вы вставить одно и то же значение несколько раз на карту?Если да в обоих случаях, ваше представление является правильным.

Если вы хотите, чтобы одно и то же значение было вставлено не более одного раза в один ключ, вам следует использовать Set[U] вместо Iterable[U] (что легко сделать, добавив .toSet к it.map(_._2)).

Если вам не нравится иметь дело с наборами/итерациями и вы просто миритесь с этим (т.на самом деле вы предпочитаете просто иметь пары ключ-значение, а не пары ключ-набор значений), вам придется написать класс-оболочку вокруг карты, которая представляет единый интерфейс карты и будет правильно поступать с +, - и итератором.

Вот пример, который оказался немного длиннее, чем я ожидал (здесь он отформатирован для вырезания и вставки в REPL):

import scala.collection._
class MapSet[A,B](
  val sets: Map[A,Set[B]] = Map[A,Set[B]]()
) extends Map[A,B] with MapLike[A,B,MapSet[A,B]] {
  def get(key: A) = sets.getOrElse(key,Set[B]()).headOption
  def iterator = new Iterator[(A,B)] {
    private val seti = sets.iterator
    private var thiskey:Option[A] = None
    private var singles:Iterator[B] = Nil.iterator
    private def readyNext {
      while (seti.hasNext && !singles.hasNext) {
        val kv = seti.next
        thiskey = Some(kv._1)
        singles = kv._2.iterator
      }
    }
    def hasNext = {
      if (singles.hasNext) true
      else {
        readyNext
        singles.hasNext
      }
    }
    def next = {
      if (singles.hasNext) (thiskey.get , singles.next)
      else {
        readyNext
        (thiskey.get , singles.next)
      }
    }
  }
  def +[B1 >: B](kv: (A,B1)):MapSet[A,B] = {
    val value:B = kv._2.asInstanceOf[B]
    new MapSet( sets + ((kv._1 , sets.getOrElse(kv._1,Set[B]()) + value)) )
  }
  def -(key: A):MapSet[A,B] = new MapSet( sets - key )
  def -(kv: (A,B)):MapSet[A,B] = {
    val got = sets.get(kv._1)
    if (got.isEmpty || !got.get.contains(kv._2)) this
    else new MapSet( sets + ((kv._1 , got.get - kv._2)) )
  }
  override def empty = new MapSet( Map[A,Set[B]]() )
}

и мы видим, что это работает так, как хотелось бы:

scala> new MapSet() ++ List(1->"Hi",2->"there",1->"Hello",3->"Bye")
res0: scala.collection.Map[Int,java.lang.String] = Map(1 -> Hi, 1 -> Hello, 2 -> there, 3 -> Bye)

scala> res0 + (2->"ya")
res1: scala.collection.Map[Int,java.lang.String] = Map(1 -> Hi, 1 -> Hello, 2 -> there, 2 -> ya, 3 -> Bye)

scala> res1 - 1
res2: scala.collection.Map[Int,java.lang.String] = Map(2 -> there, 2 -> ya, 3 -> Bye)

(хотя, если вы хотите вернуть MapSet после ++, вам придется переопределить ++;в иерархии карт нет собственных конструкторов, которые могли бы позаботиться о подобных вещах).

Answer 2

Посмотрите на микс-ин MultiMap для Map.

Answer 3

Мультикарта — это то, что вам нужно.Вот пример создания и последующего добавления в него записей из списка[(String, Int)].Я уверен, что есть более красивый способ.

scala> val a = new collection.mutable.HashMap[String, collection.mutable.Set[Int]]() with collection.mutable.MultiMap[String, Int]
a: scala.collection.mutable.HashMap[String,scala.collection.mutable.Set[Int]] with scala.collection.mutable.MultiMap[String,Int] = Map()

scala> List(("a", 1), ("a", 2), ("b", 3)).map(e => a.addBinding(e._1, e._2))                                                      
res0: List[scala.collection.mutable.HashMap[String,scala.collection.mutable.Set[Int]] with scala.collection.mutable.MultiMap[String,Int]] = List(Map(a -> Set(1, 2), b -> Set(3)), Map(a -> Set(1, 2), b -> Set(3)), Map(a -> Set(1, 2), b -> Set(3)))

scala> a("a")
res2: scala.collection.mutable.Set[Int] = Set(1, 2)