代码之家 › 专栏 › 技术社区 › firda

符合C++11的自定义键集(key_type不是value_type,而是functor获取value的键)

set stl c++11 c++

firda · 技术社区 · 10 年前

我正在搜索模板库,该模板库具有类似于集合的容器,允许通过不同的关键字进行搜索。我不想要map(键重复),想要符合C++11的代码(添加了C++14 template<class K> iterator std::set::find(const K& x) 可用于 std::set<T*,my_transparent_deref_less<T*> > 带有自定义比较函子)。

你知道吗? boost会添加这样的内容吗?还是已经添加了?

签名应如下所示: the_set<T, GetKey, Compare> 并且我希望针对大小/内存使用(因此flat_set/btre_set)和搜索速度(插入/删除速度不是那么关键)优化结构。 例子:

class User {
public:
    User(const char *name);
    const char *name();
... };
the_set<User*,const char*> USERS([](User* u) { u->name(); },
  [](const char* lhs, const char* rhs) { strcmp(lhs, rhs) < 0; });

我找到了 red-black-tree in boost::detail 看起来像我想要的-签名是 template <class Key, class Value, class KeyOfValue, class KeyCompare, class A> class rbtree 我们有这样的东西吗 flat_set 和 btree_set 我可以使用(而不用担心使用不公开使用但故意隐藏为细节的东西)?

原因: 我确实计划对许多对象和许多关键点(可能对同一对象使用不同的关键点/集)使用这些集合。
用户、单位…-全局使用btree_set,可能类似 boost::multi_index
用户::单位,…-使用flat_set设置对象

我的代码到目前为止: (问题是我必须使用 StringWrapper 现在)

#include <set>
#include <iostream>
#include <type_traits>
#include "btree_set.h"
#include "boost/container/flat_set.hpp"

// dereferencing comparator
template <class T>
  class less: public std::less<T> {
public:
    typename std::enable_if<std::is_pointer<T>::value,
      bool>::type operator() (T lhs, T rhs) const {
        return *lhs < *rhs; }};

// here I can change underlying structure to btree_set or std::set
template <class T,
  class C = less<T>,
  class A = std::allocator<T> >
  using default_set = boost::container::flat_set<T, C, A>;

// this works fine for classes derived from their primary key
template <class T, class K = T,
  class B = default_set<K*> >
  class object_set {
private:
    typename std::enable_if<std::is_base_of<K, T>::value,
      B>::type impl;
public:
    template<class... Args>
      T* add(K* key, Args&& ...args) {
        auto it = impl.insert(key);
        if (!it.second) return nullptr;
        T* value = new T(*key, std::forward<Args>(args)...);
        *it.first = value;
        return value; }
    T* operator[](K* key) {
        auto it = impl.find(key);
        if (it == impl.end()) return nullptr;
        return (T*)*it; }
    T* remove(K* key) {
        auto it = impl.find(key);
        if (it == impl.end()) return nullptr;
        T* value = (T*)*it;
        impl.erase(it);
        return value; }
public:
    template<class... Args>
      T* add(K key, Args&& ...args) {
        return add(&key, std::forward<Args>(args)...); }
    T* operator[](K key) {
        return (*this)[&key]; }
    T* remove(K key) {
        return remove(&key); }};

// workaround for above std::is_base_of constraint
class StringWrapper {
    const char *data;
public:
    StringWrapper(const char *data) {
        this->data = data; }
    operator const char *() const {
        return data; }};

// example of class I want to use the container on
class User: public StringWrapper {
public:
    User(const char *name): StringWrapper(name) {}};

// testing
object_set<User,StringWrapper> USERS;
int main() {
    USERS.add("firda"); USERS.add("firda2");
    User* firda = USERS["firda"];
    delete USERS.remove(firda);
    delete USERS.remove("firda2"); }

4 回复 | 直到 10 年前

dpington 10 年前

听起来像一份工作 boost::multi_index

http://www.boost.org/doc/libs/1_55_0/libs/multi_index/doc/index.html

firda 10 年前

这是我带来的:

#include "boost/container/flat_set.hpp"

template<class T, class K, class GetKey, class CmpKey>
  class fset {
private:
    boost::container::container_detail::flat_tree<
      K, T*, GetKey, CmpKey, std::allocator<T*> >
      impl;
public:
    template<class... Args>
      T* add(K key, Args&& ...args) {
        auto it = impl.lower_bound(key);
        if (it != impl.end() && impl.key_comp()(key, GetKey()(*it))) {
            return nullptr; }
        T* value = new T(key, std::forward<Args>(args)...);
        impl.insert_unique(it, value);
        return value; }
    T* operator[](K key) {
        auto it = impl.find(key);
        if (it == impl.end()) return nullptr;
        return *it; }
    T* remove(K key) {
        auto it = impl.find(key);
        if (it == impl.end()) return nullptr;
        T* value = *it;
        impl.erase(it);
        return value; }};

class User {
private:
    const char *name_;
public:
    User(const char *name) {
        std::size_t size = std::strlen(name) + 1;
        char *buf = new char[size];
        std::memcpy(buf, name, size);
        name_ = buf; }
    ~User() {
        delete[] name_; }
    const char *name() const {
        return name_; }
public:
    struct get_name {
        const char *operator()(User* u) const {
            return u->name(); }};
    struct cmp_name {
        bool operator()(const char* lhs, const char* rhs) const {
            return std::strcmp(lhs, rhs) < 0; }};};

fset<User,const char*,User::get_name,User::cmp_name>
  USERS;

int main() {
    USERS.add("firda");
    User* firda = USERS["firda"];
    delete USERS.remove("firda"); }

我现在应该关闭或删除此问题吗?

firda 10 年前

这是我现在使用的(看看 struct vset_adaptor )

#ifndef HEADER___VECTSET___BE8EB41D7B3971E1
#define HEADER___VECTSET___BE8EB41D7B3971E1
#include <vector>
//############################################################### ptrvect
template <class T, class base = std::vector<T*> >
  class ptrvect: public base {
public:
    class iterator: public base::iterator {
        friend class ptrvect;
    private:
        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 null;
        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 adaptor
template <class T, class K>
  struct vset_adaptor {
    K operator()(T* it) const {
        return (K)(*it); }
    bool operator()(K lhs, K rhs) const {
        return lhs < rhs; }};
template <class T>
  struct vset_adaptor<T,T*> {
    T* operator()(T* it) const {
        return it; }
    bool operator()(T* lhs, T* rhs) const {
        return lhs < rhs; }};
//================================================================== vset
template <class T, class K=T*, class F = vset_adaptor<T,K> >
  class vset {
private:
    ptrvect<T> impl;
    struct Comp {
        F f;
        K operator()(T* it) const {
            return f(it); }
        bool operator()(K lhs, K rhs) const {
            return f(lhs, rhs); }
        bool operator()(T* lhs, K rhs) const {
            return f(f(lhs), rhs); }
        bool operator()(K lhs, T* rhs) const {
            return f(lhs, f(rhs)); }
        bool operator()(T* lhs, T* rhs) const {
            return f(f(lhs), f(rhs)); }};
    Comp comp;
public:
    typedef typename ptrvect<T>::const_iterator iterator, const_iterator;
    typedef unsigned size_type;
    typedef T *value_type;
    typedef K key_type;
    typedef typename ptrvect<T>::template condpair<iterator> condpair;
public:
    iterator begin() const {
        return iterator(impl.begin()); }
    iterator end() const {
        return iterator(impl.end()); }
    size_type size() const {
        return impl.size(); }
    bool empty() const {
        return impl.empty(); }
public:
    iterator lower_bound(K key) const {
        return std::lower_bound(impl.begin(), impl.end(), key, comp); }
    iterator upper_bound(K key) const {
        return std::upper_bound(impl.begin(), impl.end(), key, comp); }
    std::pair<iterator, iterator> equal_range(K key) const {
        return std::equal_range(impl.begin(), impl.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:
    typename std::enable_if<!std::is_same<T*,K>::value,
      iterator>::type lower_bound(T* key) const {
        return std::lower_bound(impl.begin(), impl.end(), comp(key), comp); }
    typename std::enable_if<!std::is_same<T*,K>::value,
      iterator>::type upper_bound(T* key) const {
        return std::upper_bound(impl.begin(), impl.end(), comp(key), comp); }
    typename std::enable_if<!std::is_same<T*,K>::value,
      std::pair<iterator, iterator> >::type equal_range(T* key) const {
        return std::equal_range(impl.begin(), impl.end(), comp(key), comp); }
    typename std::enable_if<!std::is_same<T*,K>::value,
      iterator>::type find(T* key) const {
        iterator it = lower_bound(comp(key));
        return it == end() || comp(key, *it) ? end() : it; }
public:
    template<class... Args>
      condpair emplace(K key, Args&& ...args) {
        iterator it = lower_bound(key);
        if (it == end() || comp(key, *it)) {
            return condpair(impl.insert(it,
              new T(key, std::forward<Args>(args)...)), true); }
        return condpair(it, false); }
    iterator erase(iterator at) {
        return impl.erase(at); }
public:
    T* add(T* value) {
        iterator it = lower_bound(value);
        if (it == end() || comp(comp(value), *it)) {
            impl.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)...);
            impl.insert(it, value);
            return value; }
        return nullptr; }
    T* get(K key) const {
        iterator it = find(key);
        return it == impl.end() ? nullptr : *it; }
    T* operator[](K key) const {
        return *emplace(key).first; }
    T* remove(K key) {
        iterator it = find(key);
        if (it == impl.end()) return nullptr;
        T* value = *it;
        impl.erase(it);
        return value; }
    typename std::enable_if<!std::is_same<T*,K>::value,
      T*>::type remove(T* key) {
        return remove(comp(key)); }
    void release() {
        for (T* it : *this) {
            delete it; }
        impl.clear(); }
    void clear() {
        impl.clear(); }};
#endif

如果你想知道代码样式,它是我自己的预处理器的输出。这是真实的代码:

#include <vector>
//############################################################### ptrvect
template <class T, class base = std::vector<T*> >
  class ptrvect: public base
public:
    class iterator: public base::iterator
        friend class ptrvect
    private:
        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 null
        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 adaptor
template <class T, class K>
  struct vset_adaptor
    K operator()(T* it) const
        return (K)(*it)
    bool operator()(K lhs, K rhs) const
        return lhs < rhs
template <class T>
  struct vset_adaptor<T,T*>
    T* operator()(T* it) const
        return it
    bool operator()(T* lhs, T* rhs) const
        return lhs < rhs
//================================================================== vset
template <class T, class K=T*, class F = vset_adaptor<T,K> >
  class vset
private:
    ptrvect<T> impl
    struct Comp
        F f
        K operator()(T* it) const
            return f(it)
        bool operator()(K lhs, K rhs) const
            return f(lhs, rhs)
        bool operator()(T* lhs, K rhs) const
            return f(f(lhs), rhs)
        bool operator()(K lhs, T* rhs) const
            return f(lhs, f(rhs))
        bool operator()(T* lhs, T* rhs) const
            return f(f(lhs), f(rhs))
    Comp comp
public:
    typedef typename ptrvect<T>::const_iterator iterator, const_iterator
    typedef unsigned size_type
    typedef T *value_type
    typedef K key_type
    typedef typename ptrvect<T>::template condpair<iterator> condpair
public:
    iterator begin() const
        return iterator(impl.begin())
    iterator end() const
        return iterator(impl.end())
    size_type size() const
        return impl.size()
    bool empty() const
        return impl.empty()
public:
    iterator lower_bound(K key) const
        return std::lower_bound(impl.begin(), impl.end(), key, comp)
    iterator upper_bound(K key) const
        return std::upper_bound(impl.begin(), impl.end(), key, comp)
    std::pair<iterator, iterator> equal_range(K key) const
        return std::equal_range(impl.begin(), impl.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:
    typename std::enable_if<!std::is_same<T*,K>::value,
      iterator>::type lower_bound(T* key) const
        return std::lower_bound(impl.begin(), impl.end(), comp(key), comp)
    typename std::enable_if<!std::is_same<T*,K>::value,
      iterator>::type upper_bound(T* key) const
        return std::upper_bound(impl.begin(), impl.end(), comp(key), comp)
    typename std::enable_if<!std::is_same<T*,K>::value,
      std::pair<iterator, iterator> >::type equal_range(T* key) const
        return std::equal_range(impl.begin(), impl.end(), comp(key), comp)
    typename std::enable_if<!std::is_same<T*,K>::value,
      iterator>::type find(T* key) const
        iterator it = lower_bound(comp(key))
        return it == end() || comp(key, *it) ? end() : it
public:
    template<class... Args>
      condpair emplace(K key, Args&& ...args)
        iterator it = lower_bound(key)
        if it == end() || comp(key, *it)
            return condpair(impl.insert(it,
              new T(key, std::forward<Args>(args)...)), true)
        return condpair(it, false)
    iterator erase(iterator at)
        return impl.erase(at)
public:
    T* add(T* value)
        iterator it = lower_bound(value)
        if it == end() || comp(comp(value), *it)
            impl.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)...)
            impl.insert(it, value)
            return value
        return nullptr
    T* get(K key) const
        iterator it = find(key)
        return it == impl.end() ? nullptr : *it
    T* operator[](K key) const
        return *emplace(key).first
    T* remove(K key)
        iterator it = find(key)
        if it == impl.end(); return nullptr
        T* value = *it
        impl.erase(it)
        return value
    typename std::enable_if<!std::is_same<T*,K>::value,
      T*>::type remove(T* key)
        return remove(comp(key))
    void release()
        for T* it : *this
            delete it
        impl.clear()
    void clear()
        impl.clear()

andreaplanet 7 年前

您已经提到了c++14和模板查找函数。下面是一个简单的例子,说明谁对此感兴趣:

#include <iostream>
#include <set>
#include <vector>

using namespace std;

class Info
{
    int          num_;
public:
    explicit Info(int n) : num_(n) {}

    bool operator<(const Info &other) const { return num_ < other.num_; }

    friend inline bool operator<(const Info& lhs, const int& rhs);
    friend bool operator<(const int& lhs,  const Info& rhs);
};

inline bool operator<(const Info& lhs, const int& rhs)  { return lhs.num_ < rhs; }
inline bool operator<(const int& lhs,  const Info& rhs) { return lhs < rhs.num_; }


int main()
{
    // less<> is a is_transparent comparer
    set<Info, less<> > s;
    // insert two items
    s.insert(Info(2));
    s.insert(Info(4));
    // search
    for (auto n : {1,2,3,4,5}) {
        cout << "Searching " << n << (s.find(n) == s.end()?" not found":" found") << endl;
    }
    return 0;
}

结果:

Searching 1 not found
Searching 2 found
Searching 3 not found
Searching 4 found
Searching 5 not found