BEFORE YOU READ: this link should be included when you just don't like the format of the question and for those that read this question for the first time, the link may give you the idea what happened here. The rest after the line is untouched.
I was asking for such structure on SO, but got only link to boost::multi_index as an answer. So, I decided to write it myself (and plan to include the final version there as self-answer, while probably rewriting/rewording the question as well - it definitely needs it).
I wanted both fast and memory-efficient set for objects (stored by pointer, allocation managed outside of the container for various reasons, e.g. deleting user with connected clients - disposing needs to be done later by last closed client) with functor to get the key from the value/object (as well as searching by both the pointer and the key). My test code showing the usage:
(class User
containing string name
, which is used as key for the set)
Usage
class User {
string name_;
public:
User(string name): name_(std::move(name)) {
return; }
const char * name() const {
return name_.c_str(); }
// the functor to be passed to the container
struct get_key {
const char * operator() (User* u) const {
return u->name(); }};};
// comparator for user names
struct str_less {
bool operator() (const char *lhs, const char *rhs) const {
return std::strcmp(lhs, rhs) < 0; }};
int main() {
// the example set
vset<User,const char*,str_less,User::get_key> users;
// few tests
users.add("firda");
for (auto p : users) cout << p->name() << endl;
auto it = users.find("firda");
cout << it->name() << endl;
it = users.find(*it);
cout << it->name() << endl;
// few more tests when the pointer is the key as well:
vset<int,int*> ints;
int* i = ints.add(new int(1));
auto j = ints.find(i);
cout << **j << endl; }
You have for sure already noticed that there is something strange about my code-styling. I have created my own preprocessor, not to get bothered by missing ;
especially at the end of a header, when I switch from C# project (I am the only programmer managing many C++ and C# projects). The real source code looks like this:
//############################################################### testing
#include <iostream> <cstring>
using std: cout, endl, string
class User
string name_
public:
User(string name): name_(std::move(name))
return
const char * name() const
return name_.c_str()
struct get_key
const char * operator() (User* u) const
return u->name()
struct str_less
bool operator() (const char *lhs, const char *rhs) const
return std::strcmp(lhs, rhs) < 0
int main()
vset<User,const char*,str_less,User::get_key> users
users.add("firda")
for auto p : users; cout << p->name() << endl
auto it = users.find("firda")
cout << it->name() << endl
it = users.find(*it)
cout << it->name() << endl
vset<int,int*> ints
int* i = ints.add(new int(1))
auto j = ints.find(i)
cout << **j << endl
Vector of Pointers
While writing the set-container, I have also created a helper vector for pointers, with altered iterators (for easier work with pointers, condpair
is e.g. for emplace
in the final set-container) and few other methods (add, remove, release, ...):
/// Vector of Pointers
template <class T, class base = std::vector<T*> >
class ptrvect: public base {
public:
class iterator: public base::iterator {
friend class ptrvect;
iterator(const typename base::const_iterator& it):
base::iterator(const_cast<T**>(&*it)) {
return; }
public:
iterator(const typename base::iterator& it):
base::iterator(it) {
return; }
T* operator->() const {
return **this; }};
class const_iterator: public base::const_iterator {
public:
const_iterator(const typename base::const_iterator& it):
base::const_iterator(it) {
return; }
const_iterator(const typename base::iterator& it):
base::const_iterator(it) {
return; }
T* operator->() const {
return **this; }};
template <class It = iterator>
class condpair: public std::pair<It,bool> {
public:
condpair(It it, bool second):
std::pair<It,bool>(it, second) {
return; }
T* operator->() const {
return *std::pair<It,bool>::first; }};
public:
iterator begin() {
return iterator(base::begin()); }
iterator end() {
return iterator(base::end()); }
const_iterator begin() const {
return const_iterator(base::begin()); }
const_iterator end() const {
return const_iterator(base::end()); }
public: // workarounds for pre-C++11 / bad C++11 implementation (should allow const_iterator)
iterator insert(const_iterator pos, T* value) {
return base::insert(iterator(pos), value); }
iterator erase(const_iterator pos) {
return base::erase(iterator(pos)); }
public: // addons
iterator find (T* key) {
return std::find(begin(), end(), key); }
const_iterator find (T* key) const {
return std::find(begin(), end(), key); }
bool contains (T* key) const {
return find(key) != end(); }
T* remove(T* key) {
auto it = find(key);
if (it == end()) return nullptr;
T* val = *it;
base::erase(it);
return val; }
T* add(T* val) {
base::push_back(val);
return val; }
void release() {
for (T* it : *this) delete it;
base::clear(); }};
And again the real unprocessed source code:
#include <vector> <algorithm>
//############################################################### ptrvect
/// Vector of Pointers
template <class T, class base = std::vector<T*> >
class ptrvect: public base
public:
class iterator: public base::iterator
friend class ptrvect
iterator(const typename base::const_iterator& it):
base::iterator(const_cast<T**>(&*it))
return
public:
iterator(const typename base::iterator& it):
base::iterator(it)
return
T* operator->() const
return **this
class const_iterator: public base::const_iterator
public:
const_iterator(const typename base::const_iterator& it):
base::const_iterator(it)
return
const_iterator(const typename base::iterator& it):
base::const_iterator(it)
return
T* operator->() const
return **this
template <class It = iterator>
class condpair: public std::pair<It,bool>
public:
condpair(It it, bool second):
std::pair<It,bool>(it, second)
return
T* operator->() const
return *std::pair<It,bool>::first
public:
iterator begin()
return iterator(base::begin())
iterator end()
return iterator(base::end())
const_iterator begin() const
return const_iterator(base::begin())
const_iterator end() const
return const_iterator(base::end())
public: // workarounds for pre-C++11 / bad C++11 implementation (should allow const_iterator)
iterator insert(const_iterator pos, T* value)
return base::insert(iterator(pos), value)
iterator erase(const_iterator pos)
return base::erase(iterator(pos))
public: // addons
iterator find (T* key)
return std::find(begin(), end(), key)
const_iterator find (T* key) const
return std::find(begin(), end(), key)
bool contains (T* key) const
return find(key) != end()
T* remove(T* key)
auto it = find(key)
if it == end(); return nullptr
T* val = *it
base::erase(it)
return val
T* add(T* val)
base::push_back(val)
return val
void release()
for T* it : *this; delete it
base::clear()
The Core
Here is the core of the final container. I am still not that good in SFINAE when it comes to conditionally-added methods (those methods that are there only when some condition on template parameters is met). So, I have decided to create few classes on the way, that help me with the specialization of the container for key=pointer.
//###################################################### vset: comparator
namespace detail { namespace vset {
/// Get Key Functor for Vector-Set
template <class T, class K>
struct get_key {
K operator() (T* it) const {
return (K)(*it); }};
template <class T>
struct get_key<T,T*> {
T* operator() (T* it) const {
return it; }};
/// Comparator Functor for Vector-Set
template <class T, class K=T,
class Less = std::less<K>, class GetKey = get_key<T,K>>
class comparator: protected GetKey, protected Less {
public:
const GetKey& get_key() const {
return static_cast<const GetKey&>(*this); }
const Less& less() const {
return static_cast<const Less&>(*this); }
K operator() (T* it) const {
return get_key()(it); }
bool operator() (K x, K y) const {
return less()(x, y); }
bool operator() (T* x, K y) const {
return less()(get_key()(x), y); }
bool operator() (K x, T* y) const {
return less()(x, get_key()(y)); }
bool operator() (T* x, T* y) const {
return less()(get_key()(x), get_key()(y)); }};
template <class T, class Less, class GetKey>
class comparator<T,T*,Less,GetKey>:
protected GetKey, protected Less {
public:
const GetKey& get_key() const {
return static_cast<const GetKey&>(*this); }
const Less& less() const {
return static_cast<const Less&>(*this); }
T* operator() (T* it) const {
return get_key()(it); }
bool operator() (T* x, T* y) const {
return less()(x, y); }};
//============================================================ vset: base
/// Vector-Set Basic Implementation
template <class T, class K=T,
class Less = std::less<K>,
class GetKey = get_key<T,K>>
class base: protected comparator<T,K,Less,GetKey>, protected ptrvect<T> {
typedef ptrvect<T> core;
protected:
// disable polymorphic destruction by hiding non-virtual destructor
~base() {
return; }
const comparator<T,K,Less,GetKey>& comp() const {
return static_cast<const comparator<T,K,Less,GetKey>&>(*this); }
public:
// pointers cannot be changed -> iterator = const_iterator
typedef typename core::const_iterator iterator, const_iterator;
typedef typename core::template condpair<iterator> condpair;
typedef T *value_type;
typedef K key_type;
using core::size_type;
using core::size;
using core::empty;
iterator begin() const {
return core::begin(); }
iterator end() const {
return core::end(); }
public:
iterator lower_bound(K key) const {
return std::lower_bound(begin(), end(), key, comp()); }
iterator upper_bound(K key) const {
return std::upper_bound(begin(), end(), key, comp()); }
std::pair<iterator, iterator> equal_range(K key) const {
return std::equal_range(begin(), end(), key, comp()); }
iterator find(K key) const {
iterator it = lower_bound(key);
return it == end() || comp()(key, *it) ? end() : it; }
bool contains(K key) const {
iterator it = lower_bound(key);
return it != end() && !comp()(key, *it); }
public:
template<class... Args>
condpair emplace(K key, Args&& ...args) {
iterator it = lower_bound(key);
if (it == end() || comp()(key, *it)) {
return condpair(core::insert(it,
new T(key, std::forward<Args>(args)...)), true); }
return condpair(it, false); }
iterator erase(iterator at) {
return core::erase(at); }
public:
T* add(T* value) {
K key = comp()(value);
iterator it = lower_bound(key);
if (it == end() || comp()(key, *it)) {
core::insert(it, value);
return value; }
return nullptr; }
template<class... Args>
T* add(K key, Args&& ...args) {
iterator it = lower_bound(key);
if (it == end() || comp()(key, *it)) {
T* value = new T(key, std::forward<Args>(args)...);
core::insert(it, value);
return value; }
return nullptr; }
T* get(K key) const {
iterator it = find(key);
return it == end() ? nullptr : *it; }
T* operator[](K key) const {
return *emplace(key).first; }
T* remove(K key) {
iterator it = find(key);
if (it == end()) return nullptr;
T* value = *it;
core::erase(it);
return value; }
void release() {
for (T* it : *this) {
delete it; }
core::clear(); }
void clear() {
core::clear(); }};
}}
The Final Class
//================================================================== vset
template <class T, class K=T,
class Less = std::less<K>,
class GetKey = detail::vset::get_key<T,K>>
class vset: public detail::vset::base<T,K,Less,GetKey> {
typedef detail::vset::base<T,K,Less,GetKey> base;
protected:
using base::comp;
public:
typedef typename base::iterator iterator;
using base::begin; using base::end; using base::remove; using base::find;
using base::lower_bound; using base::upper_bound; using base::equal_range;
T* remove(T* value) {
return remove(comp()(value)); }
iterator find(T* value) const {
K key = comp()(value);
iterator it = lower_bound(key);
return it == end() || comp()(key, *it) ? end() : it; }
iterator lower_bound(T* value) const {
return std::lower_bound(begin(), end(), value, comp()); }
iterator upper_bound(T* value) const {
return std::upper_bound(begin(), end(), value, comp()); }
std::pair<iterator, iterator> equal_range(T* value) const {
return std::equal_range(begin(), end(), value, comp()); }};
//============================================================ vset: K=T*
template <class T, class Less, class GetKey>
class vset<T,T*,Less,GetKey>:
public detail::vset::base<T,T*,Less,GetKey> {};
Full Life Demo on IdeOne.com
And the complete unprocessed source file:
#include <vector> <algorithm>
//############################################################### ptrvect
/// Vector of Pointers
template <class T, class base = std::vector<T*> >
class ptrvect: public base
public:
class iterator: public base::iterator
friend class ptrvect
iterator(const typename base::const_iterator& it):
base::iterator(const_cast<T**>(&*it))
return
public:
iterator(const typename base::iterator& it):
base::iterator(it)
return
T* operator->() const
return **this
class const_iterator: public base::const_iterator
public:
const_iterator(const typename base::const_iterator& it):
base::const_iterator(it)
return
const_iterator(const typename base::iterator& it):
base::const_iterator(it)
return
T* operator->() const
return **this
template <class It = iterator>
class condpair: public std::pair<It,bool>
public:
condpair(It it, bool second):
std::pair<It,bool>(it, second)
return
T* operator->() const
return *std::pair<It,bool>::first
public:
iterator begin()
return iterator(base::begin())
iterator end()
return iterator(base::end())
const_iterator begin() const
return const_iterator(base::begin())
const_iterator end() const
return const_iterator(base::end())
public: // workarounds for pre-C++11 / bad C++11 implementation (should allow const_iterator)
iterator insert(const_iterator pos, T* value)
return base::insert(iterator(pos), value)
iterator erase(const_iterator pos)
return base::erase(iterator(pos))
public: // addons
iterator find (T* key)
return std::find(begin(), end(), key)
const_iterator find (T* key) const
return std::find(begin(), end(), key)
bool contains (T* key) const
return find(key) != end()
T* remove(T* key)
auto it = find(key)
if it == end(); return nullptr
T* val = *it
base::erase(it)
return val
T* add(T* val)
base::push_back(val)
return val
void release()
for T* it : *this; delete it
base::clear()
//###################################################### vset: comparator
namespace detail.vset
/// Get Key Functor for Vector-Set
template <class T, class K>
struct get_key
K operator() (T* it) const
return (K)(*it)
template <class T>
struct get_key<T,T*>
T* operator() (T* it) const
return it
/// Comparator Functor for Vector-Set
template <class T, class K=T,
class Less = std::less<K>, class GetKey = get_key<T,K>>
class comparator: protected GetKey, protected Less
public:
const GetKey& get_key() const
return static_cast<const GetKey&>(*this)
const Less& less() const
return static_cast<const Less&>(*this)
K operator() (T* it) const
return get_key()(it)
bool operator() (K x, K y) const
return less()(x, y)
bool operator() (T* x, K y) const
return less()(get_key()(x), y)
bool operator() (K x, T* y) const
return less()(x, get_key()(y))
bool operator() (T* x, T* y) const
return less()(get_key()(x), get_key()(y))
template <class T, class Less, class GetKey>
class comparator<T,T*,Less,GetKey>:
protected GetKey, protected Less
public:
const GetKey& get_key() const
return static_cast<const GetKey&>(*this)
const Less& less() const
return static_cast<const Less&>(*this)
T* operator() (T* it) const
return get_key()(it)
bool operator() (T* x, T* y) const
return less()(x, y)
//============================================================ vset: base
/// Vector-Set Basic Implementation
template <class T, class K=T,
class Less = std::less<K>,
class GetKey = get_key<T,K>>
class base: protected comparator<T,K,Less,GetKey>, protected ptrvect<T>
typedef ptrvect<T> core
protected:
// disable polymorphic destruction by hiding non-virtual destructor
~base()
return
const comparator<T,K,Less,GetKey>& comp() const
return static_cast<const comparator<T,K,Less,GetKey>&>(*this)
public:
// pointers cannot be changed -> iterator = const_iterator
typedef typename core::const_iterator iterator, const_iterator
typedef typename core::template condpair<iterator> condpair
typedef T *value_type
typedef K key_type
using core::size_type
using core::size
using core::empty
iterator begin() const
return core::begin()
iterator end() const
return core::end()
public:
iterator lower_bound(K key) const
return std::lower_bound(begin(), end(), key, comp())
iterator upper_bound(K key) const
return std::upper_bound(begin(), end(), key, comp())
std::pair<iterator, iterator> equal_range(K key) const
return std::equal_range(begin(), end(), key, comp())
iterator find(K key) const
iterator it = lower_bound(key)
return it == end() || comp()(key, *it) ? end() : it
bool contains(K key) const
iterator it = lower_bound(key)
return it != end() && !comp()(key, *it)
public:
template<class... Args>
condpair emplace(K key, Args&& ...args)
iterator it = lower_bound(key)
if it == end() || comp()(key, *it)
return condpair(core::insert(it,
new T(key, std::forward<Args>(args)...)), true)
return condpair(it, false)
iterator erase(iterator at)
return core::erase(at)
public:
T* add(T* value)
K key = comp()(value)
iterator it = lower_bound(key)
if it == end() || comp()(key, *it)
core::insert(it, value)
return value
return nullptr
template<class... Args>
T* add(K key, Args&& ...args)
iterator it = lower_bound(key)
if it == end() || comp()(key, *it)
T* value = new T(key, std::forward<Args>(args)...)
core::insert(it, value)
return value
return nullptr
T* get(K key) const
iterator it = find(key)
return it == end() ? nullptr : *it
T* operator[](K key) const
return *emplace(key).first
T* remove(K key)
iterator it = find(key)
if it == end(); return nullptr
T* value = *it
core::erase(it)
return value
void release()
for T* it : *this
delete it
core::clear()
void clear()
core::clear()
//================================================================== vset
namespace
template <class T, class K=T,
class Less = std::less<K>,
class GetKey = detail::vset::get_key<T,K>>
class vset: public detail::vset::base<T,K,Less,GetKey>
typedef detail::vset::base<T,K,Less,GetKey> base
protected:
using base: comp
public:
typedef typename base::iterator iterator
using base: begin, end, remove, find
using base: lower_bound, upper_bound, equal_range
T* remove(T* value)
return remove(comp()(value))
iterator find(T* value) const
K key = comp()(value)
iterator it = lower_bound(key)
return it == end() || comp()(key, *it) ? end() : it
iterator lower_bound(T* value) const
return std::lower_bound(begin(), end(), value, comp())
iterator upper_bound(T* value) const
return std::upper_bound(begin(), end(), value, comp())
std::pair<iterator, iterator> equal_range(T* value) const
return std::equal_range(begin(), end(), value, comp())
//============================================================ vset: K=T*
template <class T, class Less, class GetKey>
class vset<T,T*,Less,GetKey>:
public detail::vset::base<T,T*,Less,GetKey>
//############################################################### testing
#include <iostream> <cstring>
using std: cout, endl, string
class User
string name_
public:
User(string name): name_(std::move(name))
return
const char * name() const
return name_.c_str()
struct get_key
const char * operator() (User* u) const
return u->name()
struct str_less
bool operator() (const char *lhs, const char *rhs) const
return std::strcmp(lhs, rhs) < 0
int main()
vset<User,const char*,str_less,User::get_key> users
users.add("firda")
for auto p : users; cout << p->name() << endl
auto it = users.find("firda")
cout << it->name() << endl
it = users.find(*it)
cout << it->name() << endl
vset<int,int*> ints
int* i = ints.add(new int(1))
auto j = ints.find(i)
cout << **j << endl