title: How do you efficiently implement the observer pattern if the subject is a huge container?
body: <p>We all know the <a href="http://en.wikipedia.org/wiki/Observer_pattern" rel="nofollow noreferrer">observer pattern</a>: You have a subject which is able to notify and update a list of observers of its state changes. Now suppose that the subject you would like to observe is a container, and you would like to observe the container itself, i.e. element addition and deletion of elements, and also the contained elements, i.e. state updates of the container elements.</p>
  
  <p>How would you implement the update mechanism so that it is fast with respect to element insertion and deletions when you store massive amounts of objects in your container? In particular, </p>
  
  <ul>
  <li>would you use the same type of container in the local copy of the observers?</li>
  <li>is there a smart choice of container which the observers should use? (For instance, would it be faster to, say, always use balanced trees, even if you are observing a linked list?)</li>
  <li>how do you quickly translate an iterator into the observed container into an iterator into the observer's container? (Trivial for arrays, hard for linked lists?)</li>
  </ul>
  
  <p>If your container is a linked list for instance, then you can insert elements in constant time. If m observers have to iterate through the list containing n elements, then updating takes O(n * m) expected time.</p>
  
  <p>If your container is an array, then changing an element takes constant time, and updating m observers takes O(m) if you pass the element's index, O(n * m) if observers have to iterate through the array.</p>
  
  <p>If it helps, consider the following examples:</p>
  
  <p>Example 1. You are writing an operating system. The subject you would like to observe is the filesystem and its files. Your views are a file explorer, an indexer, and other applications. You would like to update the observers when files are added, deleted or modified.</p>
  
  <p>Example 2. You are writing an address book application which should be able to handle a city of the size of New York. The subject you would like to observe is the container of your records (a person with its address, phone numbers, email...). Your observers are several views, which should update automatically when you add, delete or modify a record. (One could image one view containing a list of people who live on 53rd and another drawing dots on a map for each person whose last name is Doe).</p>
  
  <p>How do you handle the case that a complete directory-subtree is deleted or that "53rd St" is renamed to "Dijkstra St"?</p>