c++ - 根据条件拆分 STL 列表

Question

我有一个 std::list 如下所示(x 标记表示某个数字小于 500)

x,x,x,x,503,x,x,x,510,x,x,x,502,x,x,x,x,x,x,600 - std::list<int> originallist

我希望将列表拆分为列表 vector std::vector<std::list<int> >如下

1st element of vector: x,x,x,x,503
2nd element of vector: x,x,x,510
...
...
last element of vector: x,x,x,x,x,x,600

我现在的代码如下:

list<int> templist; vector<list<int> > v;
for(list<int>::iterator lit=originallist.begin(); lit!=oriniallist.end(); ++lit) {
    if (*lit > 500) {
        templist.push_back(*lit);v.push_back(templist); templist.clear(); continue;
    }
    templist.push_back(*lit);
}

在不使用模板列表的情况下，在 C++ 中实现上述任务的最有效方法是什么。感谢您的帮助。

Answer 1

虽然此解决方案确实使用临时 std::list，但它不分配列表节点元素，并且在 C++03 情况下恰好分配 1 个内存(C++11 情况确实如此)返回值大小的内存分配的对数)

这是一个 C++03 解决方案。 C++11 解决方案可以一次完成。

bool big_as_500( int x ) {return x>=500;}

std::vector< std::list< int > > do_stuff( std::list<int>& original_list ) {
  // we have to do this, because resizing the return value involves lots of allocations
  // and stuff in C++03, so make sure we get the size right by precalculating it:
  std::size_t count = std::count_if( originallist.begin(), originallist.end(), big_as_500 );
  std::vector< std::list< int > > result;
  result.reserve(count+1); 

  typedef std::list<int>::const_iterator const_iterator;
  std::list< int > current;
  for(const_iterator it= originallist.begin(); it!=originallist.end();/*nothing*/) {
    ++it; // about to invalidate it! (or move lists)
    current.splice( current.end(), originallist, originallist.begin() ); // O(1) no memory allocation
    if (big_as_500(current.back())) {
      result.push_back( std::list<int>() );
      current.swap( result.back() );
    }
  }
  // original problem does not specify what to do if the original list does not end
  // with an element "big_as_500", so I'll just drop them
  return result; // rely on NRVO to eliminate the copy here, if your compiler does not
  // support it, take result as a reference parameter.
}

C++11 解决方案:

std::vector< std::list< int > > do_stuff( std::list<int>& original_list ) {
  std::vector< std::list< int > > result;

  typedef std::list<int>::const_iterator const_iterator;
  std::list< int > current;
  for(const_iterator it= originallist.begin(); it!=originallist.end();/*nothing*/) {
    ++it;// about to become invalid/in wrong list
    current.splice( current.end(), originallist, originallist.begin() ); // O(1) no memory allocation
    if (current.back() >= 500) {
      result.emplace_back( std::move(current) );
    }
  }
  // original problem does not specify what to do if the original list does not end
  // with an element "big_as_500", so I'll just drop them
  return result; // will NRVO, or move, so no worries
}

在 C++11 中，调整大小相对便宜，所以我们很好。

现在，我们可以真正了解 C++03 并模拟 C++11 的功能，并一次性完成所有工作。

template<typename T, typename A>
void efficient_grow_by_1( std::vector<T,A>& make_one_bigger ) {
  if (make_one_bigger.size()+1 > make_one_bigger.capacity() )
  {
    std::vector<T, A> swap_vec;
    swap_vec.reserve( (make_one_bigger.size()+1)*5/3 );
    for (std::vector<T, A>::iterator it = make_one_bigger.begin(); it != make_one_bigger.end(); ++it ) {
      using std::swap;
      swap_vec.push_back();
      std::swap( *it, swap_vec.back() );
    }
    swap_vec.swap( make_one_bigger );
  }
  make_one_bigger.push_back();
}
void do_stuff( std::list<int>& original_list, std::vector< std::list< int > >& result ) {
  typedef std::list<int>::const_iterator const_iterator;
  std::list< int > current;
  for(const_iterator it= originallist.begin(); it!=originallist.end();) {
    ++it;
    current.splice( current.end(), originallist, originallist.begin() ); // O(1) no memory allocation
    if (current.back()>=500) {
      efficient_grow_by_1(result);
      current.swap( result.back() );
    }
  }
  // original problem does not specify what to do if the original list does not end
  // with an element "big_as_500", so I'll just drop them
}

这太疯狂了，所以我建议升级你的编译器。

这里的技巧是我们用一次单个元素拼接填充“临时”列表。因为(大多数？许多？)std::list::splice 的实现最终不得不遍历元素以对它们进行计数(这在 C++11 中是必需的，并且在 C++ 中很常见03)，在我们确定要将哪些元素放入下一个 block 时一次一个地执行它是相当有效的。每个节点直接来自输入列表，并被收集到临时列表中(没有内存分配)。

一旦我们建立了这个列表，我们就直接将它交换到list的输出vector中。这避免了任何内存分配，除了保存 list 的(相对较小的)基本数据所需的内存分配。

在 C++03 中，我们要么执行两次解决方案并预先计算输出 std::vector 的大小，要么我们模拟 C++11 move 的效率，在包含的 list 上仔细增长和 swap 机制。您的 std 库实现可能已经伪造了这一点，但我不确定 swap-resize 优化在旧库中有多常见。

将事情简化为单次传递可能值得第二个 C++03 和 C++11 解决方案使用的分配的对数数:遍历 std::list 是一个练习缓存未命中。