.NET中的multimap
我需要在C-sharp中与c ++的std::multimap<K, V, Comp, Alloc>等价。 它是否存在于标准库中？
因为几乎是圣诞节:)
////////////////////////////////////////////////////////////////////// // Algorithmia is (c) 2008 Solutions Design. All rights reserved. // http://www.sd.nl ////////////////////////////////////////////////////////////////////// // COPYRIGHTS: // Copyright (c) 2008 Solutions Design. All rights reserved. // // The Algorithmia library sourcecode and its accompanying tools, tests and support code // are released under the following license: (BSD2) // ---------------------------------------------------------------------- // Redistribution and use in source and binary forms, with or without modification, // are permitted provided that the following conditions are met: // // 1) Redistributions of source code must retain the above copyright notice, this list of // conditions and the following disclaimer. // 2) Redistributions in binary form must reproduce the above copyright notice, this list of // conditions and the following disclaimer in the documentation and/or other materials // provided with the distribution. // // THIS SOFTWARE IS PROVIDED BY SOLUTIONS DESIGN ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, // INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A // PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SOLUTIONS DESIGN OR CONTRIBUTORS BE LIABLE FOR // ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR // BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, // STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE // USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. // // The views and conclusions contained in the software and documentation are those of the authors // and should not be interpreted as representing official policies, either expressed or implied, // of Solutions Design. // ////////////////////////////////////////////////////////////////////// // Contributers to the code: // - Frans Bouma [FB] ////////////////////////////////////////////////////////////////////// using System; using System.Collections.Generic; using System.Linq; using System.Text; using SD.Tools.Algorithmia.UtilityClasses; namespace SD.Tools.Algorithmia.GeneralDataStructures { /// <summary> /// Extension to the normal Dictionary. This class can store more than one value for every key. It keeps a HashSet for every Key value. /// Calling Add with the same Key and multiple values will store each value under the same Key in the Dictionary. Obtaining the values /// for a Key will return the HashSet with the Values of the Key. /// </summary> /// <typeparam name="TKey">The type of the key.</typeparam> /// <typeparam name="TValue">The type of the value.</typeparam> public class MultiValueDictionary<TKey, TValue> : Dictionary<TKey, HashSet<TValue>> { /// <summary> /// Initializes a new instance of the <see cref="MultiValueDictionary<TKey, TValue>"/> class. /// </summary> public MultiValueDictionary() : base() { } /// <summary> /// Adds the specified value under the specified key /// </summary> /// <param name="key">The key.</param> /// <param name="value">The value.</param> public void Add(TKey key, TValue value) { ArgumentVerifier.CantBeNull(key, "key"); HashSet<TValue> container = null; if(!this.TryGetValue(key, out container)) { container = new HashSet<TValue>(); base.Add(key, container); } container.Add(value); } /// <summary> /// Determines whether this dictionary contains the specified value for the specified key /// </summary> /// <param name="key">The key.</param> /// <param name="value">The value.</param> /// <returns>true if the value is stored for the specified key in this dictionary, false otherwise</returns> public bool ContainsValue(TKey key, TValue value) { ArgumentVerifier.CantBeNull(key, "key"); bool toReturn = false; HashSet<TValue> values = null; if(this.TryGetValue(key, out values)) { toReturn = values.Contains(value); } return toReturn; } /// <summary> /// Removes the specified value for the specified key. It will leave the key in the dictionary. /// </summary> /// <param name="key">The key.</param> /// <param name="value">The value.</param> public void Remove(TKey key, TValue value) { ArgumentVerifier.CantBeNull(key, "key"); HashSet<TValue> container = null; if(this.TryGetValue(key, out container)) { container.Remove(value); if(container.Count <= 0) { this.Remove(key); } } } /// <summary> /// Merges the specified multivaluedictionary into this instance. /// </summary> /// <param name="toMergeWith">To merge with.</param> public void Merge(MultiValueDictionary<TKey, TValue> toMergeWith) { if(toMergeWith==null) { return; } foreach(KeyValuePair<TKey, HashSet<TValue>> pair in toMergeWith) { foreach(TValue value in pair.Value) { this.Add(pair.Key, value); } } } /// <summary> /// Gets the values for the key specified. This method is useful if you want to avoid an exception for key value retrieval and you can't use TryGetValue /// (eg in lambdas) /// </summary> /// <param name="key">The key.</param> /// <param name="returnEmptySet">if set to true and the key isn't found, an empty hashset is returned, otherwise, if the key isn't found, null is returned</param> /// <returns> /// This method will return null (or an empty set if returnEmptySet is true) if the key wasn't found, or /// the values if key was found. /// </returns> public HashSet<TValue> GetValues(TKey key, bool returnEmptySet) { HashSet<TValue> toReturn = null; if(!base.TryGetValue(key, out toReturn) && returnEmptySet) { toReturn = new HashSet<TValue>(); } return toReturn; } } }
ILookup对你来说可能是足够好的 – 但不幸的是没有公开的实现。 就我所知，你基本上必须经过Enumerable.ToLookup 。 这意味着这是一个“构build一次”的地图 – 你不能在以后添加。 但是，如果这就是你所需要的，只需要使用内置的东西就可以了。
在.NET 3.5中，有一个代表这个的ILookup<,> 。 常规的实现（ Lookup<,> ）是不可变的，但是我在MiscUtil中有一个EditableLookup<,>应该很好地完成这项工作。
你可以findac＃multimap collection @ http://code.google.com/p/self-balancing-avl-tree/ 。 它基于代码中包含的自平衡avl树。
如果整个集合很大BMultiMap<K,V>请考虑使用BMultiMap<K,V> 。 与Dictionary<K,List<V>>相比，它节省了大量的内存，特别是如果与每个键关联的值的数量通常很less。
