Databases
StackOverflow2013
Postsdbo
POHow do I set up data structures to efficiently delete a Monkey from a Pod?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHow do I set up data structures to efficiently delete a Monkey from a Pod?
    primarykey
    data
    text
    <p>In my C++ application, I have <code>Pod</code> objects that internally stores information about <code>Monkey</code>s in a vector. <code>MonkeyInternal</code> is a big class with a lot of properties about monkeys...</p> <p>My intention here is to create a lightweight proxy object <code>Monkey</code> that merely stores an index that can be used to access more information stored in a private vector in <code>Pod</code> (Monkeys are capricious, and their properties may change, and we want any monkey objects in the program to always be up to date.).</p> <pre><code>class Pod { public: typedef Monkey monkey_type; Monkey monkey(int monkey_index) { return Monkey(this, monkey_index); } // Lightweight proxy Monkey object that can be passed around easily. class Monkey { public: Monkey(Pod* pod, int monkey_index) { pod_ = pod; monkey_index_ = monkey_index; } private: Pod* pod_; int monkey_index_; // To get monkey internal info, index into pod. friend class Pod; // Monkey is a proxy that delegates to Pod. } private: // MonkeyInternal objects stores hefty data about monkeys. vector&lt;MonkeyInternal&gt; monkeys_; } </code></pre> <p>With these data structures, I can randomly access a monkey's internal information easily. I can also easily insert another monkey into the pod efficiently (O(1) amortized).</p> <p>However, removing a monkey is O(n) since I must shift all the monkeys to the left. I could make removal slightly more efficient by using an <code>unordered_map</code> (or some good hash table) - O(n), but is there any way I could organize my data structures to support O(1) removal of a monkey?</p> <p>Perhaps I could use a clever design pattern? </p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USJohn Hoffman
    1. USJohn Hoffman
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POHow do I set up data structures to efficiently delete a Monkey from a Pod?
      1. USemartel
      1. VTFavorite
    2. VO
      singulars
      1. POHow do I set up data structures to efficiently delete a Monkey from a Pod?
      1. This table or related slice is empty.
      1. VTUpMod
    1. COremoving an element from vector is `O(n^2)`?
      singulars
      1. POHow do I set up data structures to efficiently delete a Monkey from a Pod?
      1. USbillz
    2. CODo you need to remove specific monkeys or does that not matter?
      singulars
      1. POHow do I set up data structures to efficiently delete a Monkey from a Pod?
      1. USChris Condy
    3. COOh wait... removal is O(n) isn't it... sorry, I was thinking of inserting into a list in python.. And the signature of remove would take a Monkey object, so yes, specific monkey.
      singulars
      1. POHow do I set up data structures to efficiently delete a Monkey from a Pod?
      1. USJohn Hoffman
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload