如何在自定义数据结构中实现 begin() 成员函数？

Question

我正在尝试创建自己的数据结构，该数据结构可以使用哈希映射在 O(1) 时间内确定一个值是否是其中的一个元素。

我正在努力添加更多成员函数，以便它更类似于 STL 容器。这是我目前拥有的与问题相关的内容：

template <class T>
class setfind {

private:
    long long _size = 0;
    unordered_map<T, bool> _set;

public:
    // constructors
    setfind() {}
    // initialize from some iterable
    template <class InputIterator>
    setfind(InputIterator beg, InputIterator en){
        _size = en - beg;
        while (beg != en){
            _set[*beg] = true;
            beg++;
        }
    }

    bool contains(const T &val){
        return _set[val];
    }
    bool contains(const T &&val){
        return _set[val];
    }
};

如你所见，它的核心是unordered_map。我想编写一个成员函数，该成员函数 returns 是 _set 变量的开始迭代器。我试着把这个放进去：

template <class InputIterator>
InputIterator begin()
{
    return _set.begin();
}

但这导致编译错误，指出没有匹配的成员函数。我对迭代器和 template-classes 了解不够，无法解决这个问题。有谁知道如何实施或出了什么问题？有什么好的资源可以让我了解更多吗？

另外一些针对此 class 的优化技巧将不胜感激，因为这将在时间限制内使用。

编辑：我只能使用 c++11
EDIT2：修复了构造函数中的错误
EDIT3：内存泄漏和最佳实践不会成为问题

Answer 1

我发现你的代码有几个问题。

您根本不需要 _size 成员，删除它并在需要时使用 _set.size()。

在您的构造函数中，while (*beg != *en) 需要改为 while (beg != en)。或者更好的是，完全摆脱手动循环并使用将迭代器对作为输入的 std::unordered_map 构造函数：

// initialize from some iterable
template <class InputIterator>
setfind(InputIterator beg, InputIterator en) : _set(beg, en) {}

在您的 contains() 方法中，使用 _set.find() 或 _set.contains() 而不是 _set.operator[] 以避免 val begin added to the _set if它还不存在。此外，采用 const 右值引用是没有意义的，因此完全摆脱该重载：

bool contains(const T &val) const
{
    return _set.find(val) != _set.end();
    // or:
    // return _set.contains(val);
}

最后，对于您的 begin() 方法，只需对 return 类型使用 auto 而不是模板，让编译器推断出必要的类型，例如：

auto begin()
{
    return _set.begin();
}

UPDATE：明显的 auto return 类型推导是在 C++14 中引入的。因此，对于 C++11，您只需显式声明类型，仍然不要为其使用模板，例如：

unordered_map<T, bool>::iterator begin()
{
    return _set.begin();
}

或者：

auto begin() -> unordered_map<T, bool>::iterator
{
    return _set.begin();
}

或者：

auto begin() -> decltype(_set.begin())
{
    return _set.begin();
}

您可以通过在 class 中声明一个 iterator 别名来简化此操作（如果您的目标是让 class 像标准容器一样工作，无论如何您都应该这样做），例如：

template <class T>
class setfind {
private:
    unordered_map<T, bool> _set;

public:
    using iterator = unordered_map<T, bool>::iterator;

    ...

    iterator begin(){
        return _set.begin();
    }
};

如何在自定义数据结构中实现 begin() 成员函数？

How do I implement a begin() member function in my custom data structure?

c++

implementation

iterator

data-structures

c++11