排列值顺序的迭代器

Question

我有一个简单的排列结构:

struct Permutation
{
   vector<string> items; // ["val_0", "val_1", "val_2", "val_3", "val_4"]
   vector<short> permutationValue;  // Let's say value is [4, 2, 0, 1, 3]
}

我希望能够在范围循环中使用它,就像那样

for(string item: permutation){
{ 
    cout << item << endl;
}

最终预期产量应为:

val_4
val_2
val_0
val_1
val_3

我应该在Permutation课堂上实施哪些方法来实现它？

Answer 1

你需要做一些工作.您需要实现自己的自定义迭代器类,begin()并且end():

struct Permutation
{
    std::vector<std::string> items;
    std::vector<short> permutationValue;

    class iterator;

    iterator begin();
    iterator end();

};

你的迭代器类将是一个随机访问迭代器:

#include <iterator>

class Permutation::iterator : public std::iterator<std::random_access_iterator_tag, std::string>
{


};

继承是非常重要的std::iterator,以便您的自定义迭代器能够正常工作<algorithm>.

有几种可能的方法来实现迭代器.但一般的想法是你的迭代器将在其私有类成员中存储指向其置换对象及其当前索引位置的指针:

private:
    Permutation *p;
    size_t pos;

它operator*是显而易见的:

public:
    std::string &operator*() const
    {
         return p->items[p->permutationValue[pos]];
    }

你将需要实现所有其他运营商的迭代器,即递增/递减提前随机访问迭代器,运营商++,--,+,-,+=,-=,简单地通过增加或减少pos.

您还需要实现所有的比较操作符的迭代器类:<,>,=,!=,<=,和>=,简单地比较pos.

这些位有点乏味,但不可避免.

现在,您所要做的就是实现begin()并end()通过构造此迭代器实例,将initial设置pos为0或者items.size();.你完成了.现在您可以使用范围迭代.

如需额外的功劳,您也可以实施const_iterator.

总之:这将是一些工作,但它并不复杂.

Answer 2

这不是前向/后向/随机访问迭代器的完整代码，但它是一个很好的起点：

struct perm_iter {
  const vector<short>& perm_;
  const vector<string>& items_;
  int idx_ {0};
  perm_iter(int idx, const vector<short>& perm, const vector<string>& items)
    : idx_(idx)
    , perm_(perm)
    , items_(items) {}

  perm_iter& operator++() {
    idx_++;
    return *this;
  }

  bool operator!=(const perm_iter& i) const {
    return idx_ != i.idx_;
  }

  string operator*() {
    return items_[perm_[idx_]];
  }

};

struct Permutation
{
  /* ... */ 
   perm_iter begin() {
      return perm_iter(0, permutationValue, items);  
   }

   perm_iter end() {
      return perm_iter(items.size(), permutationValue, items);
   }

};

 //usage:
 Permutation p;
 for (string s : p)
    cout << s << endl;