c++ - 如何在我的自定义数据结构中实现 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。我想编写一个成员函数，该函数将开始迭代器返回给 _set 变量。我试着把它放进去：

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

但这导致编译错误，指出没有匹配的成员函数。我对迭代器和模板类知之甚少，无法解决这个问题。有谁知道如何实现它或有什么问题？有什么好的资源可以让我了解更多吗？

此外，该课程的一些优化技巧将不胜感激，因为这将在时间限制下使用。

编辑：我仅限于使用 c++11
EDIT2：修复了构造函数中的一个错误
EDIT3：内存泄漏和最佳实践将不是问题

标签： c++c++11data-structuresiteratorimplementation

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()or_set.contains()代替_set.operator[]来避免valbegin 添加到_setif 它尚不存在。此外，采用右值引用是没有意义的const，所以完全摆脱这个重载：

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

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

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

更新auto：在 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();
}

你可以通过在你的类中声明一个iterator别名来简化这一点（如果你的目标是让你的类像一个标准容器一样，你应该这样做），例如：

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

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

    ...

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