创建一个STL map的键迭代器

Question

创建一个STL map的键迭代器

7

通常情况下，您会有一个类似于map<string,X>的映射表，其中键是映射值的名称，您需要一个API，使消费者可以查看所有名称...例如，用于填充GUI列表框。您可以构建一个向量并将其作为API调用返回，但这样效率相对较低。您也可以返回对映射的引用，但这样值也是可访问的，而您可能不希望如此。

那么，您该如何编写符合规范的KeyIterator类，它包装了映射表并提供标准迭代器访问映射表中的键。

例如：

map<string,X> m= ...
KeyIterator<string> ki(m);
for(KeyIterator<string>::iterator it=ki.begin();it!=ki.end();++it)
 cout << *it;

KeyIterator应该是轻量级的，这样你就可以从一个几乎没有开销的方法中返回它。

编辑： 我不确定我解释得完美，让我给出一个更好的用例（半伪代码）：

class PersonManager
{
 private:
  map<string,Person> people;
 public:
  //this version has to iterate the map, build a new structure and return a copy
  vector<string> getNamesStandard();

  //this version returns a lightweight container which can be iterated
  //and directly wraps the map, allowing access to the keys
  KeyIterator<string> getNames();
};

void PrintNames(PersonManager &pm)
{
 KeyIterator<string> names = pm.getNames();
 for(KeyIterator<string>::iterator it=names.begin();it!=names.end();++it)
  cout << *it << endl;
}

- Mr. Boy

让KeyIterator持有指向map的指针，并有一个迭代器包装类来包装map的迭代器，转发对++、==、--等的调用。这应该相对简单，尽管将其模板化为仅键类型将需要一些类型擦除技巧。 - Bwmat

1

这可能会有所帮助：https://dev59.com/RXRB5IYBdhLWcg3wQFLu - Abhay

嘿@John：我不认为将其包装到另一个类中有任何意义，说真的。此外，看了Mark Ransom和Mooing Duck的答案，我没有看到太多改进，仍然从begin()开始到end()结束。 - Viet

3个回答

3

#include <map>
#include <string>
#include <iterator>

template <class map>
class KeyIterator { 
    typename map::const_iterator iter_;
public:
    KeyIterator() {}
    KeyIterator(typename map::iterator iter) :iter_(iter) {}
    KeyIterator(typename map::const_iterator iter) :iter_(iter) {}
    KeyIterator(const KeyIterator& b) :iter_(b.iter_) {}
    KeyIterator& operator=(const KeyIterator& b) {iter_ = b.iter_; return *this;}
    KeyIterator& operator++() {++iter_; return *this;}
    KeyIterator operator++(int) {return KeyIterator(iter_++);}
    const typename map::key_type& operator*() {return iter_->first;}
    bool operator==(const KeyIterator& b) {return iter_==b.iter_;}
    bool operator!=(const KeyIterator& b) {return iter_!=b.iter_;}
};

int main() {
    std::map<std::string,int> m;
    KeyIterator<std::map<std::string,int> > ki;
    for(ki=m.begin(); ki!=m.end(); ++ki)
        cout << *ki;
}

http://codepad.org/4wxFGGNV
这种方法非常轻量级。不过，它要求迭代器基于map类型进行模板化，而不是键类型，这意味着如果您尝试隐藏内部实现，则必须提供一些实现细节。

- Mooing Duck

我刚刚注意到这段代码在codepad上编译并运行了，但我没有使用std::string。这是怎么回事？ - Mooing Duck

由于codepad插入了各种东西，包括using namespace std。请参见http://codepad.org/sKvDs2Et。不幸的是，我无法弄清楚我之前如何获得`prelude.h`的内容。我不知道它的位置，而且正如你所看到的，无法调用`cpp`。 - sehe

哦...还是去ideone吧（它也有C#和C++0x以及许多其他好东西。当然没有boost :)） - sehe

@sehe ideone有boost，但只能在普通的C++模式下使用，不能使用C++0x模式。而且只能使用头文件库的boost库。 - Cubbi

@Cubbi：谢谢提醒。我非常确定我已经尝试过Spirit几次了。下次我会重新检查。 - sehe

@sehe 直接从 Spirit 2.0 教程中获取：https://ideone.com/y90LL （之所以是 2.0，是因为 Ideone 的 Boost 版本是 1.39） - Cubbi

0

我觉得主要问题是你只想要一个模板参数而不是两个：KeyIterator<string>而不是KeyIterator<string, X>。

为了实现这一点，您可能需要一种称为类型擦除的技术。这将涉及动态分配和虚拟方法调用。

如果是后者，您可以简单地包装一个map<string, X>::const_iterator，使得解引用返回键的引用，并提供构造函数以接受映射的迭代器。

- UncleBens

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mark Ransom · Accepted Answer

template<typename iterator_type>
class KeyIterator
{
    iterator_type iterator;
public:
    typedef typename std::iterator_traits<iterator_type>::value_type::first_type value_type;
    KeyIterator(iterator_type i) : iterator(i) {}
    value_type operator*() { return iterator->first; }
    KeyIterator & operator++() { ++iterator; return *this; }
    bool operator!=(const KeyIterator & right) const { return iterator != right.iterator; }
    // ...
};

编辑：在看到您的编辑后，我意识到这不完全是您想要的。您通过将类称为KeyIterator使我感到困惑，更合适的名称应该是KeyContainer。您将无法仅对键类型进行模板化，因为它将必须包含对映射的某种引用；您需要映射的完整定义。

您的请求过于复杂，因为您必须定义两种不同的类型，KeyIterator和KeyIterator::iterator。

以下是使用我的类的示例代码：

class PersonManager
{
private:
    map<string,Person> people;
public:
    //this version has to iterate the map, build a new structure and return a copy 
    vector<string> getNamesStandard(); 

    //this version returns a lightweight container which can be iterated 
    //and directly wraps the map, allowing access to the keys 
    KeyIterator<map<string,Person>::iterator> getNamesBegin(); 
    KeyIterator<map<string,Person>::iterator> getNamesEnd(); 
}; 

void PrintNames(PersonManager &pm) 
{ 
    KeyIterator<map<string,Person>::iterator> it = pm.getNamesBegin();
    KeyIterator<map<string,Person>::iterator> end = pm.getNamesEnd();
    for(it; it!=end; ++it) 
        cout << *it << endl; 
}