标签: iterator

我在编写旅行推销员计划时遇到过这种情况.对于内循环,我尝试了一个

for(Point x:ArrayList<Point>) {
// modify the iterator
}

但是当向该列表添加另一个点时会导致ConcurrentModicationException被抛出.

但是,当我将循环更改为

for(int x=0; x<ArrayList<Point>.size(); x++) {
// modify the array
}

循环运行良好,没有抛出异常.

两个for循环,那么为什么一个抛出异常而另一个没有呢？

我有人和地方数据如下:

• Person 实体有
  • IList<DateRangePlaces> 每个人都有
    • IList<Place> 可能的地方
  • Schedule日模式为ie.10天可用4不可用

在特定的DateRangePlaces日期范围内,人们必须遵守模仿Schedule人是否可以去某个特定的地方.

• Place 实体有
  • IList<DateRangeTiming> 每个定义每个日期范围内的开/关时间

重叠日期范围可用作LIFO.因此,对于之前已经定义的每一天,新的时间定义都会优先考虑.

问题

现在我需要做这样的事情(在伪代码中):

for each Place
{
    for each Day between minimum and maximum date in IList<DateRangeTiming>
    {
        get a set of People applicable for Place and on Day
    }
}

这意味着执行我的任务的步骤数约为:

Σ _(地方)(Σ _(天) ×Σ _(人))

这对我的理解是

O(x×y _x ×z)

并且可能与此算法的复杂性近似:

O(n ³)

我不是理论专家,所以你可以自由地纠正我的假设.真实的是,这种复杂性绝对是不可接受的,特别是考虑到我将在很多地方和人的长日期范围内运作.

从公式近似中我们可以看到人集会被多次迭代.因此,我想至少优化这一部分.为了缓解事情,我改变了一点

Person.IList<DateRangePlaces>.IList<Place>

至

Person.IList<DateRangePlaces>.IDictionary<int, Place>

无论一个人是否可以在特定日期到某个地方,这会给我一个更快的结果,因为我只会检查是否Place.Id存在于字典中而不是IList.Where()每次都必须扫描整个列表的LINQ子句.

题

1. 您是否可以建议我可以在算法中实现任何其他优化,以使其更快,甚至在大O符号方面使其更简单？

2. 您将使用哪种内存结构类型(列表,字典,堆栈,队列......)来提高性能？

附录:整个问题更加复杂 …

我基本上需要的是检查列表的每个元素,如果某些条件适合我想从列表中删除它.

例如,让我们这样说吧

list=['a','b','c','d','e']

我基本上想写(原则上而不是我尝试实现的实际代码)

如果列表中的元素为"b"或"c",请将其从列表中删除,然后执行下一个操作.

但

for s in list:
    if s=='b' or s=='c':
        list.remove(s)

失败是因为当'b'被移除时,循环取'd'而不是'c'作为下一个元素.那么有没有办法比将元素存储在单独的列表中并在之后删除它们更快？

谢谢.

说,我有元素向量和掩码数组,我想从矢量中提取具有真实对应掩码值的元素来分离向量.有没有办法std::copy_if用于此目的？问题是,我只有谓词中的元素值,而不是它的迭代器,所以我不知道实际索引来解决掩码数组.

我可以直接操作这样的地址:

vector<bool> mask;
vector<int> a, b;
copy_if(a.begin(), a.end(), b.begin(), [&] (int x) -> bool { 
  size_t index = &x - &a[0]; // Ugly...
  return mask[index];
});

但是,我发现这是一个丑陋的解决方案.有更好的想法吗？

更新:另一种可能的解决方案是在掩码上使用外部迭代器:

vector<bool> mask;
vector<int> a, b;
auto pMask = mask.begin();
copy_if(a.begin(), a.end(), b.begin(), [&] (int x) { 
  return *pMask++;
});

但是,此解决方案需要外部命名空间中的附加变量,这仍然是不可取的.

根据这个非常高度推崇的答案,迭代一组擦除一些元素的规范方法如下:

for (it = mySet.begin(); it != mySet.end(); ) {
    if (conditionToDelete(*it)) {
        mySet.erase(it++);
    }
    else {
        ++it;
    }
}

当然,这是C++ 03设置擦除不返回迭代器的结果.否则一个人就可以写了it = mySet.erase(it);很明显,一个人可以写

itToDelete = it++;
mySet.erase(itToDelete);

这个问题不是关于如何在迭代时删除元素.问题是为什么以下行显然不会导致未定义的行为.

mySet.erase(it++);

起初我确信这必须是UB,因为我在考虑后增量方面做错了.这是一种常见(但错误的)方式,将预增量视为在评估的其余部分之前发生,并且后增量发生在AFTER之后.当然,这是错误的.后增量和前增量都有增加变量的副作用.不同之处在于这些表达式的价值.

也就是说,据我所知,C++标准(至少是C++ 03标准)没有明确说明何时会发生后增量的副作用.因此,除非我们保证如果作为后增量表达式的函数参数在进入函数体之前会产生副作用,那么这不应该是UB吗？究竟是什么(标准方面),如果有的话,禁止在迭代器在函数体内失效后发生的++副作用？

标准的行情非常受欢迎.

为了一个参数,让我们假设set的迭代器是一个内置类型,这实际上是operator ++,而不是重载的operator-function

是否有一个简单的方法来检查元素是否包含在迭代或迭代器中,类似于Collection.contains(Object o)方法？

即不必写:

Iterable<String> data = getData();
for (final String name : data) {
    if (name.equals(myName)) {
        return true;
    }
}

我想写:

Iterable<String> data = getData(); 
if (Collections.contains(data, myName)) {
    return true;
}

我真的很惊讶没有这样的事情.

如果我想在稳定的Rust中使用自定义步骤进行迭代,我该怎么办？基本上就像C/C++

for (int i = 0; i < n; i += 2) {

}

我已经尝试过使用range_step_inclusive和解决方案如何使用自定义步骤迭代范围？:

use std::iter::range_step_inclusive;
for i in range_step_inclusive(0, n, 2) {
    println!("i: {}", i);
}

但似乎它在Rust 1.1中不可用:

error: unresolved import `std::iter::range_step_inclusive`. There is no `range_step_inclusive` in `std::iter`

什么是另类？可能是创建自定义范围的惯用方法.

当一个函数将一系列值作为参数时,它被认为是接受Iterator<T>而不是Vec<T>？的好风格？

这样,调用者可以自己决定如何存储系列(在a Vec,a [T; N]或其他任何内容中,实际上Option<T>应该是可能的!).此外,这消除了将所有内容转换为a的需要Vec,并且在应用一些Iterator修饰符后,.collect()不需要!所以它也应该更快!

我错过了什么或这是应该做的方式吗？

我昨天看到这个用户发帖.我认为这是输出矢量的一种很酷的方式.所以我输入了一个例子并问自己这与for each循环相比如何？

template <typename T>
void printVectorO(std::vector<T> &v)
{
    std::cout << "Ostream_iterator contents: " << std::endl;
    auto start = std::chrono::high_resolution_clock::now();
    std::ostream_iterator<T> ost(std::cout, " ");
    std::copy(begin(v), end(v), ost);
    std::cout << std::endl;

    auto end = std::chrono::high_resolution_clock::now();
    auto time = end - start;
    auto nano = std::chrono::duration_cast<std::chrono::nanoseconds>(time);
    std::cout << "Ostream_iterator computation took: " << nano.count() << " nano seconds"<< std::endl;
    std::cout << std::endl;
}

template <typename T>
void printVectorC(std::vector<T> &v)
{
    std::cout << "For Each Loop contents: …

根据文件:

一旦迭代器的__next__()方法引发StopIteration,它必须继续在后续调用中这样做.不遵守此属性的实现被视为已损坏.

但是,对于文件对象:

>>> f = open('test.txt')
>>> list(f)
['a\n', 'b\n', 'c\n', '\n']
>>> next(f)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration
>>> f.seek(0)
0
>>> next(f)
'a\n'

文件对象迭代器是否已损坏？这只是其中一个无法解决的问题,因为它会破坏过多依赖它的现有代码吗？