Which containers to store objects for access via different identifiers?

Question

I have to access my objects (multiple instances from one class) via several different identifiers and don't know which is the best way to store the mapping from identifier to object. I act as a kind of "connector" between two worlds and each has its own identifiers I have to use / support. If possible I'd like to prevent using pointers.

The first idea was to put the objects in a List/Vector and then create a map for each type of identifier. Soon I had to realize that the std-containers doesn't support storing references.

The next idea was to keep the objects inside the vector and just put the index in the map. The problem here is that I didn't find an index_of for vector and storing the index inside the object only works as long as nobody uses insert or erase.

The only identifer I have when creating the objects is a string and for performance I don't want to use this string as identifer for a map.

Is this a problem solved best with pointers or does anybody have an idea how to deal with it?

Thanks

Answer 1

Using pointers seems reasonable. Here's a suggested API that you could implement:

class WidgetDatabase {
 public:
  // Returns true if widget was inserted.
  // If there is a Widget in *this with the same name and/or id,
  // widget is not inserted.
  bool Insert(const std::string& name, int id, const Widget& widget);

  // Caller does NOT own returned pointer (do not delete it!).
  // null is returned if there is no such Widget.
  const Widget* GetByName(const string& name) const;
  const Widget* GetById(int id) const;

 private:
  std::set<Widget> widgets_;
  std::map<std::string, Widget*> widgets_by_name_;
  std::map<int, Widget*> widgets_by_id_;
};

I think this should be pretty straightforward to implement. You just need to make sure to maintain the following invariant:

w is in widgets_ iff a pointer to it is in widgets_by_*

I think the main pitfall that you'll encounter is making sure is that name and id are not already in widgets_by_* when Insert is called.

It should be easy to make this thread safe; just throw in a mutex member variable, and some local lock_guards. Optionally, use shared_lock_guard in the Get* methods to avoid contention; this will be especially helpful if your use-case involves more reading than writing.

Answer 2

Have you considered an in-memory SQLite database? SQL gives you many ways of accessing the same data. For example, your schema might look like this:

CREATE TABLE Widgets {
  -- Different ways of referring to the same thing.
  name STRING,
  id INTEGER,

  -- Non-identifying characteristics.
  mass_kg FLOAT,
  length_m FLOAT,
  cost_cents INTEGER,
  hue INTEGER;
}

Then you can query using different identifiers:

SELECT mass_kg from Widgets where name = $name

or

SELECT mass_kg from Widgets where id = $id

Of course, SQL allows you to do much more than this. This will allow you to easily extend your library's functionality in the future.

Another advantage is that SQL is declarative, which usually makes it more concise and readable.

In recent versions, SQLite supports concurrent access to the same database. The concurrency model has gotten stronger over time, so you'll have to make sure you understand the model that is offered by the version that you're using. The latest version of the docs can be found on sqlite's website.