c# dictionary How to add multiple values for single key?

Question

I have created dictionary object

Dictionary<string, List<string>> dictionary =
    new Dictionary<string,List<string>>();

I want to add string values to the list of string for a given single key. If the key doesn't already exists then I have to add a new key. List<string> is not predefined, I mean I didn't create any list object and then supplied to dictionary.Add("key",Listname). How to create dynamically this list object in dictionary.Add("key",Listname) and then add strings to this list. If I have to add 100 keys then do I have to create 100 lists before executing dictionary.Add instruction and also do I have to pedefine the contents of this lists ?

Thank you.

Solution 1

Update: check for existence using TryGetValue to do only one lookup in the case where you have the list:

List<int> list;

if (!dictionary.TryGetValue("foo", out list))
{
    list = new List<int>();
    dictionary.Add("foo", list);
}

list.Add(2);

---

Original:

var dictionary = new Dictionary<string, List<int>>();

if (!dictionary.ContainsKey("foo"))
    dictionary.Add("foo", new List<int>());

dictionary["foo"].Add(42);
dictionary["foo"].AddRange(oneHundredInts);

Or List<string> as in your case.

As an aside, if you know how many items you are going to add to a dynamic collection such as List<T>, favour the constructor that takes the initial list capacity: new List<int>(100);.

This will grab the memory required to satisfy the specified capacity upfront, instead of grabbing small chunks every time it starts to fill up. You can do the same with dictionaries if you know you have 100 keys.

Solution 2

If I understood what you want:

dictionary.Add("key", new List<string>()); 

later...

dictionary["key"].Add("string to your list");

Solution 3

Dictionary<string, List<string>> dictionary = new Dictionary<string,List<string>>();

foreach(string key in keys) {
    if(!dictionary.ContainsKey(key)) {
        //add
        dictionary.Add(key, new List<string>());
    }
    dictionary[key].Add("theString");
}

If the key doesn't exist, a new List is added (inside if). Else the key exists, so just add a new value to the List under that key.

Solution 4

You could use my implementation of a multimap, which derives from a Dictionary<K, List<V>>. It is not perfect, however it does a good job.

/// <summary>
/// Represents a collection of keys and values.
/// Multiple values can have the same key.
/// </summary>
/// <typeparam name="TKey">Type of the keys.</typeparam>
/// <typeparam name="TValue">Type of the values.</typeparam>
public class MultiMap<TKey, TValue> : Dictionary<TKey, List<TValue>>
{

    public MultiMap()
        : base()
    {
    }

    public MultiMap(int capacity)
        : base(capacity)
    {
    }

    /// <summary>
    /// Adds an element with the specified key and value into the MultiMap. 
    /// </summary>
    /// <param name="key">The key of the element to add.</param>
    /// <param name="value">The value of the element to add.</param>
    public void Add(TKey key, TValue value)
    {
        List<TValue> valueList;

        if (TryGetValue(key, out valueList)) {
            valueList.Add(value);
        } else {
            valueList = new List<TValue>();
            valueList.Add(value);
            Add(key, valueList);
        }
    }

    /// <summary>
    /// Removes first occurence of an element with a specified key and value.
    /// </summary>
    /// <param name="key">The key of the element to remove.</param>
    /// <param name="value">The value of the element to remove.</param>
    /// <returns>true if the an element is removed;
    /// false if the key or the value were not found.</returns>
    public bool Remove(TKey key, TValue value)
    {
        List<TValue> valueList;

        if (TryGetValue(key, out valueList)) {
            if (valueList.Remove(value)) {
                if (valueList.Count == 0) {
                    Remove(key);
                }
                return true;
            }
        }
        return false;
    }

    /// <summary>
    /// Removes all occurences of elements with a specified key and value.
    /// </summary>
    /// <param name="key">The key of the elements to remove.</param>
    /// <param name="value">The value of the elements to remove.</param>
    /// <returns>Number of elements removed.</returns>
    public int RemoveAll(TKey key, TValue value)
    {
        List<TValue> valueList;
        int n = 0;

        if (TryGetValue(key, out valueList)) {
            while (valueList.Remove(value)) {
                n++;
            }
            if (valueList.Count == 0) {
                Remove(key);
            }
        }
        return n;
    }

    /// <summary>
    /// Gets the total number of values contained in the MultiMap.
    /// </summary>
    public int CountAll
    {
        get
        {
            int n = 0;

            foreach (List<TValue> valueList in Values) {
                n += valueList.Count;
            }
            return n;
        }
    }

    /// <summary>
    /// Determines whether the MultiMap contains an element with a specific
    /// key / value pair.
    /// </summary>
    /// <param name="key">Key of the element to search for.</param>
    /// <param name="value">Value of the element to search for.</param>
    /// <returns>true if the element was found; otherwise false.</returns>
    public bool Contains(TKey key, TValue value)
    {
        List<TValue> valueList;

        if (TryGetValue(key, out valueList)) {
            return valueList.Contains(value);
        }
        return false;
    }

    /// <summary>
    /// Determines whether the MultiMap contains an element with a specific value.
    /// </summary>
    /// <param name="value">Value of the element to search for.</param>
    /// <returns>true if the element was found; otherwise false.</returns>
    public bool Contains(TValue value)
    {
        foreach (List<TValue> valueList in Values) {
            if (valueList.Contains(value)) {
                return true;
            }
        }
        return false;
    }

}

Note that the Add method looks if a key is already present. If the key is new, a new list is created, the value is added to the list and the list is added to the dictionary. If the key was already present, the new value is added to the existing list.

Solution 5

Use NameValuedCollection.

Good starting point is here. Straight from the link.

System.Collections.Specialized.NameValueCollection myCollection
    = new System.Collections.Specialized.NameValueCollection();

  myCollection.Add(“Arcane”, “http://arcanecode.com”);
  myCollection.Add(“PWOP”, “http://dotnetrocks.com”);
  myCollection.Add(“PWOP”, “http://dnrtv.com”);
  myCollection.Add(“PWOP”, “http://www.hanselminutes.com”);
  myCollection.Add(“TWIT”, “http://www.twit.tv”);
  myCollection.Add(“TWIT”, “http://www.twit.tv/SN”);

View more solutions

Comments

[Servy]

If you're going to take it to this level of abstraction why not use a Dictionary<TKey, HashSet<TValue>>. You only perform add/remove/contains checks on the inner collection, which is what a HashSet is ideal for.

[Henk Holterman]

This (always) takes 2 lookups.

[roken]

Using TryGetValue would be more performant than ContainsKey and reindexing into the dictionary.

[Adam Houldsworth]

@Roken I'm aware, but that isn't the crux of the question. Nor have I ever seen any worthwhile performance issues derived from using dictionaries in this manner. Premature or micro-optimisation at best.

[Olivier Jacot-Descombes]

The semantics is slightly different. My implementation allows you to insert the same values several times for the same key. I do not know if there are different terms for these two variants. To which one does MultiMap apply? May be MultiMap for my variant and MultiSet for your variant?

[roken]

@AdamHouldsworth We benchmark our code at the nanosecond level. Just because you don't see the value in the most efficient solution doesn't mean it isn't valuable to others who work in a different domain than you do.

[Adam Houldsworth]

@Roken Then I'd fail to see why you are using C#, .NET and a CLR you cannot control personally. In this language, I don't sweat the odd fraction of a second; and don't misconstrue my answer as not seeing the value - I just value other stuff a lot more than that.

[sailer]

Thank you. i need to add items at diffrent times.

[toong]

1. It's a NameValueCollection - without a 'd' and 2. note that you should use GetValues(String) instead of the indexer - the indexer returns a comma separated string with your values, which is problematic if your values could contain a comma and 3. the collection doesn't distinguish between null as value or null as key-not-found

[Trap]

I wouldn't have used inheritance at all. Users of this class would want the Dictionary interface completely hidden. You either want a MultiMap or a Dictionary, but not both.

[Olivier Jacot-Descombes]

This was a quick solution. Of course you could start with a new class and implement IDictionary<K,V> plus some multimap specific things for a perfect solution. Internally you would use a Dictionary<K,List<V>>. Implementing IDictionary<K,V> requires you to implement 16 properties and methods. As I wrote at the beginning of the article, the presented solution is not perfect.

[Olivier Jacot-Descombes]

Additionally, this implementation allows you to add and retrieve whole lists through the original dictionary interface.