I have a question about implementing a data structure (with algorithm) that has these features:

  1. There are too many places (like stores), and each place can store too many items, I want to store items in the places. The point is we need to have optimized insertion (or deletion) and optimized search feature.

  2. Search can be done based on places (return items in the place) or base on items (return places that have the item)

I thought to use a hashmap for this, and use places ID as the key and store items as a collection (again a hashmap with item id for both key and value).

So based on this, the insertion of each item or place would be O(1) but get or remove of place will be O(n) and for item it will be O(n*k)! (assume we have "n" places and "k" items - I hope this is the correct calculation).

Is there any better data structure or algorithm for this problem?

  • 3
    Why not use a real DB for that? I think VistaDB, SQLite etc. would be perfect for the job?
    – Lucero
    Oct 17, 2010 at 20:47
  • Maybe because insertion into a DB (together with maintaining the proper indices for search) is quite slow?
    – Vlad
    Oct 17, 2010 at 20:51
  • Or maybe because a database is not an algorithm. Using a database is delegating the question of choosing the right algorithm to the database developers and database administrator (which need to make the database generic enough, so its algorithms won't necessarily be optimal for your specific case).
    – Vlad
    Oct 17, 2010 at 20:59
  • Well, even if your question does not address it I suspect that you will have some requirements regarding persistence as well. If you work on disk you may choose other algorithms and data structures than if you work in RAM, and it also depends a lot on the amount of data that you want to manage. If you think my answer was inappropriate I'm happy to delete it, but from your problem description I still believe that using a finished DB application may be the answer.
    – Lucero
    Oct 17, 2010 at 21:11
  • I think any answer can give some clue to the OP about solution to his problem. Sometimes people ask not what they exactly need to know, so any related information is useful.
    – Vlad
    Oct 17, 2010 at 21:18

1 Answer 1


Why not use balanced trees? You would need one tree at each store, mapping item ID to some internal information, and one global tree, mapping item ID to the list of the nodes having the given item. Your operations will be O(log n + log k).

the operations in this case would look like the following: (I use the fact that std::map and std::set are tree-based in C++)

using namespace std;

typedef int itemid_t;
typedef int storeid_t;

map<itemid_t, set<storeid_t>> itemID2storeList;

class Store
    storeid_t Id;

    // insert requires one lookup in the map (O(log k))
    // plus one insert into a set (O(log n)).
    void insert(itemid_t item)

    // the same as for insert
    void delete(itemid_t item)

    // search in a store requires one lookup in a map (O(log k))
    // and one search in a set (O(log n)).
    bool have(itemid_t item)
        const set<storeid_t>& storesForItem = itemID2storeList[item];
        return storesForItem.find(Id) != storesForItem.end();

class Central
    // getting the list of stores having the given item requires
    // one lookup in a map (O(log k))
    const set<storeid_t>& storesForItem(itemid_t item)
        return itemID2storeList[item];
  • Thanks for your answer, I'll try to implement that.BTW, can you provide an example (in java or C#) a link or something?
    – sander
    Oct 18, 2010 at 3:16
  • Oh, I should add something, for this problem Items only have item id nothing more, I mean no other information as internal info.
    – sander
    Oct 18, 2010 at 3:31
  • @sander: I've added a C++-based sample.
    – Vlad
    Oct 18, 2010 at 19:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.