title: How to make a C++ map container where the key is part of the value?
body: <p>I want to store a bunch of key-value objects, but where the value object itself (and references to it) knows its key. I also want to efficiently lookup these objects given only the key.</p>
  
  <pre><code>class SomeObject
  {
  private:
      //String or integer. int seem cheap enough to duplicate with std::map, but
      //strings seem pretty expensive when there may be thousands of objects in existence.
      //Reference/Pointer to key is fine
      const SomeOtherObject key;
      ...other stuff...
  public:
      ...methods, some of which use the key in some way...
  };
  </code></pre>
  
  <ul>
  <li>std::map  
  
  <ul>
  <li>Seems to require that the storage is an std::pair, such that the value cant access the key. If the value contains the key, it needs to be duplicated.</li>
  <li>Does not actually enforce that the key inside the value does not get changed in some way</li>
  </ul></li>
  <li>std::set  
  
  <ul>
  <li>Looks like a really good solution, using a custom compare method to provide uniqueness by key, until you realise it made your entire value const, not just the key field.</li>
  </ul></li>
  <li>std::vector (or other array/list like solutions)
  
  <ul>
  <li>Can use linear search, or if the items are kept sorted binary search. However I suspect this not not optimal in performance terms, and an extra layer of some kind is needed to really implement the desired behaviour with it.</li>
  </ul></li>
  </ul>