基于矢量获取范围内的项目索引

Question

C++ 11引入了基于范围的for循环,它使用(const)迭代器在内部实现,因此:

std::vector<std::string> vec;

for(std::string &str : vec)
{
//...
}

基本上相当于更冗长(是的,它可以简化使用auto):

for(std::vector<std::string>::iterator it = vec.begin(); it != vec.end(); ++it)
{
//...
}

然而,通常还需要项目的索引.第二种方法很简单:

auto index = it - vec.begin();

在基于范围的情况下,for它不是那么简单.但我想知道这是否可行且可移植的解决方案完全避免了迭代器:

for(auto &str : vec)
{
    auto index = &str - &vec[0];
}

(const版本将是相同的,但需要注意不要将非const容器与const引用混合,这可能并不总是很明显.)

显然这取决于几个假设:

• vector的迭代器只是对项目的引用(可能在标准中？)

• 容器保证连续(std::vector是...)

• 基于范围的内部实现(也可能在标准中)

Answer 1

是的,但我会vec.data()改用.使用的好处.data()是非连续std容器没有它,因此当迭代的容器不能以这种方式工作时(例如deque或std::vector<bool>),您的代码可靠地停止编译.(还有其它次要的优点,如std::addressof问题,而事实上它是在空的容器明确定义,但这些都不是很重要特别是在这里.)

或者我们编写一个index_t类似迭代器的包装器:

template<class T>
struct index_t {
  T t;
  T operator*()const{ return t; }
  void operator++() { ++t; }
  friend bool operator==( index_t const& lhs, index_t const& rhs ) {
    return lhs.t == rhs.t;
  }
  friend bool operator!=( index_t const& lhs, index_t const& rhs ) {
    return lhs.t != rhs.t;
  }
};
template<class T>
index_t<T> index(T t) { return {t}; }

index_t<int>可用于创建计数for(:)循环.

index_t<iterator>可用于创建迭代器返回for(:)循环.

template<class It>
struct range_t {
  It b,e;
  It begin() const {return b;}
  It end() const {return e;}
};
template<class It>
range_t<It> range( It s, It f ) { return {s,f}; }

template<class T>
range_t<index_t<T>>
index_over( T s, T f ) {
  return {{{s}}, {{f}}};
}
template<class Container>
auto iterators_of( Container& c ) {
  using std::begin; using std::end;
  return index_over( begin(c), end(c) );
}

我们现在可以迭代容器的迭代器.

for (auto it : iterators_of(vec))

实例.

提到的迭代整数是:

for (int i : index_over( 0, 100 ) )

我们也可以直接获取容器的索引:

template<class Container>
range_t< index_t<std::size_t> >
indexes_of( Container& c ) {
  return index_over( std::size_t(0), c.size() );
}
template<class T, std::size_t N>
range_t< index_t<std::size_t> >
indexes_of( T(&)[N] ) {
  return index_over( std::size_t(0), N );
}

这让我们:

for( auto i : indexes_of( vec ) )

其中,i从变化0到vec.size()-1.我发现这有时比拉链迭代器等更容易使用.

改进省略:

做index_t一个真实的input_iterator.使用std::move和/或std::forward根据需要制作索引和范围.支持范围内的Sentinals.使range_t界面更加丰富(size,可选的随机访问[],empty,front,back,range_t range_t::without_front(n) const,等.

Answer 2

是的,这是一个有效的解决方案.基础数据保证是连续的(std::vector应该是动态数组,或多或少).

n4140§23.3.6.1[vector.overview]/1

的元素vector被存储连续的,这意味着如果v是一个vector<T, Allocator>其中T一些类型比其它bool,那么它遵循标识&v[n] == &v[0] + n所有0 <= n < v.size()