4
\$\begingroup\$

I use this template to lookup clients registered for data. The data is associated by name(key) and clients are shared pointers (value) to a class which will consume the data.

////////////////////////////////////////////////////////////////////
//
// Registrar Template to help manage Key to Value Registrations
//
//   T1 - Key Object
//   T2 - Value Object
//
//  For Example: Register clients (T2) for Data (T1) 
////////////////////////////////////////////////////////////////////
#ifndef _RegistrarT_hpp_
#define _RegistrarT_hpp_

#include <map>
#include <vector>
#include <set>

template <class T1,class T2, class CompareT1 = std::less<T1> >
class RegistrarT
{
public:
  typedef std::multimap<T1,T2, CompareT1> RegistrationMultiMap;
  typedef std::vector<T2>                 RegistrationVector;
  typedef std::set<T1>                    KeySet;
public:
  RegistrarT(){}
  ~RegistrarT(){}
  // 
  // Register a value; Do not allow duplicate registrations
  void Register(T1 const & key, T2 const & value)
  {
    Unregister(key, value); // Remove if it exists in the multimap
    registrations_.insert(std::make_pair(key,value));
  }
  // Lookup all Registered for Key then find and remove value
  void Unregister(T1 const & key, T2 const & value)
  {
    bool found=false;
    typename RegistrationMultiMap::iterator itr =         
        registrations_.lower_bound(key);
    while (!found && itr != registrations_.upper_bound(key))
    {
      if (itr->second == value)
        found = true;
      else
        ++itr;
    }
    if (found)
      registrations_.erase(itr);
  }
  // Remove all values registered for key
  void UnregisterByKey(T1 const & key)
  {
    registrations_.erase(registrations_.lower_bound(key),
                         registrations_.upper_bound(key));
  }
 // Find all values and remove registrations for all keys
  void UnregisterAll(T2 const & value)
  {
    typename RegistrationMultiMap::iterator itr = 
        registrations_.begin();
    while (itr != registrations_.end())
    {
      if (itr->second == value)
        registrations_.erase(itr++);
      else
        ++itr;
    }
  }
  // Find all values and remove registrations for all keys
  // return all keys affected
  void UnregisterAll(T2 const & value, KeySet& ks)
  {
    typename RegistrationMultiMap::iterator itr = 
        registrations_.begin();
    while (itr != registrations_.end())
    {
      if (itr->second == value)
      {
        ks.insert(itr->first);
        registrations_.erase(itr++);
      }
      else
       ++itr;
    }
  }
  // Get all values registered for key
  bool GetRegistrations(T1 const & key, RegistrationVector& rv)
  {
    typename RegistrationMultiMap::iterator itr = 
        registrations_.lower_bound(key);
    while (itr != registrations_.upper_bound(key))
    {
      rv.push_back(itr->second);
      ++itr;
    }
    return (rv.size() > 0);
  }
  // Get all keys; std::set will not allow duplicates
  void GetRegistrationKeys(KeySet& ks)
  {
    typename RegistrationMultiMap::iterator itr = 
        registrations_.begin();
    while (itr != registrations_.end())
    {
      ks.insert(itr->first);
      ++itr;
    }
  }
  // Check if key is registered
  bool RegistrationsExist(T1 const & key)
  {
    typename RegistrationMultiMap::iterator itr = 
        registrations_.lower_bound(key);
    return (itr != registrations_.upper_bound(key));
  }
  // Get count of registrations for key
  std::size_t RegistrationsCount(T1 const & key)
  {
    std::size_t cnt=0;
    typename RegistrationMultiMap::iterator itr = 
        registrations_.lower_bound(key);
    while (itr != registrations_.upper_bound(key))
    {
      cnt++;
      ++itr;
    }
    return (cnt);
  }
  // Is value registered for key?
  bool RegistrationsExist(T1 const & key, T2 const & value)
  {
    typedef typename RegistrationMultiMap::iterator ResIter;
    std::pair< ResIter , ResIter>  range= 
        registrations_.equal_range(key);
    ResIter it;
    for(it=range.first;it!=range.second;++it)
    {
      if(it->second==value) return true;
    }
    return false;
  }
  // Is any value registered
  bool RegistrationsExist()
  {
    return ! registrations_.empty();
  }
  // How many keys are in use
  std::size_t RegistrationCount()
  {
    return registrations_.size();
  }
  // Clean up
  void Clear()
  {
    registrations_.clear();
  }

private:
  RegistrationMultiMap  registrations_; // Holds all
};

#endif // _RegistrarT_hpp_

Sample usage:

#include "RegistrarT.hpp"
#include <string>

typedef RegistrarT<std::string,std::string> NewsRegistrations;

int main(int argc, char *argv[])
{
  NewsRegistrations sportingNews_;
  NewsRegistrations::KeySet keyset;

  std::string moe("Moe");
  std::string curly("Curly");
  std::string larry("Larry");

   sportingNews_.Register(std::string("Football"),moe);
   sportingNews_.Register(std::string("Wrestling"),moe);
   sportingNews_.Register(std::string("Wrestling"),curly);

   sportingNews_.RegistrationsCount(std::string("Wrestling"));

   sportingNews_.Register(std::string("Rugby"),curly);
   sportingNews_.Register(std::string("BeachVolleyBall"),larry);

   sportingNews_.UnregisterAll(moe,keyset);
   sportingNews_.UnregisterByKey(std::string("Wrestling"));
   sportingNews_.RegistrationsExist(std::string("Bowling"));
}

I use a test framework so for simplicity I did not post my tests. Basically I check Registration counts and if Registrations exist. Looking to learn new stuff and gain reputation points so I can attempt to give back.

\$\endgroup\$
2
\$\begingroup\$

My immediate tendency would be to consider changing data structures. Right now you have an std::multimap<key, value>. Given that you want set-like behavior for the values associated with a particular key, my first inclination would be to change the basic data structure to something like: std::map<key, std::set<value> >.

This simplifies quite a bit of the code considerably. For example, Register turns into something like: registrations_[key].insert(value);

Likewise, Unregister turns into something like this:

auto pos = registrations_.find(key);
if (pos != registrations.end)
    pos->second.erase(value);

...and GetRegistrationKeys turns into something like this:

auto pos = registrations_.find(key);
if (pos != registrations_.end()) {
    auto const &s = pos->second;
    std::copy(s.begin(), s.end(), ks);
}

Along with simplifying the code, this at least has some chance of improving speed. All your current operations on the values associated with a given key are linear in nature. Since this uses a set, most of those become logarithmic instead.

About the only operations that look like they're at all likely to become more complex/difficult are things like the no-parameter version of RegistrationsCount. If you really need this a great deal, it can be done with constant complexity by keeping track of the overall size as you insert and delete registrations, but I can't guess whether it's used often enough to justify the bother (even though the bother is pretty slight).

If you decide you need to keep the same data structure, I think you could make better use of the library in a number of places. For example Unregister can turn into something like this:

// find range with specified key:
auto range = registrations_.equal_range(key);

// find specified value within that range:
auto pos = std::find_if(range.first, range.second, 
    [&](auto v) { return v.second == value; });

// If we found the value, remove it:
if (pos != range.second)
    registrations_.erase(pos);

One other change to consider would be to get rid of RegistrationVector and KeySet. Instead of using them, I'd turn the functions that currently use them into template member functions taking a templated iterator type to which they'd write their result.

\$\endgroup\$
  • \$\begingroup\$ Good points. I'll refactor to use the auto keyword. The class is used to map clients to data. Clients drop without unregistering so the ability to iterate through the object and remove client registrations is why I used a multimap. I'll investigate the map/vector approach. \$\endgroup\$ – sfanjoy Jan 8 '16 at 13:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.