2

我刚刚熟悉 STL，但我不太明白为什么operator []会出现错误。

        int main(){
          set< int > s;
          for(int i=0; i<=1000; i++) s.insert((i*1777)%123);
          for(int i=0; i<s.size(); i++) cout<<s[i]<<endl;
        }

然后我尝试了这个并收到另一个错误消息

        int main(){
          set< int > s;
          for(int i=0; i<=1000; i++) s.insert((i*1777)%123);
          for(int i=0; i<s.size(); i++) cout<<*(s.begin() + i)<<endl;
        }

我理解为什么它没有成员 like push_back，pop_back但我不明白为什么这两种引用方法不起作用（但它们适用于vectorand string）。我知道这些运算符在库中没有重载，但为什么呢？

经过一些网络搜索后，我确实弄清楚了如何引用它

        int main(){
          set< int > s;
          for(int i=0; i<=1000; i++) s.insert((i*1777)%123);
          for(set< int >::iterator i=s.begin(); i!=s.end(); i++) cout<<*i<<endl;
        }
4

5 回答 5

6

该标准没有为集合或其迭代器指定这些运算符，因为这些不是访问集合的有效方法。集合具有双向迭代器。这意味着为了移动到迭代序列中的第 n 个元素，您需要遍历其间的每个元素。因此，例如，如果要为集合的迭代器实现 operator+，在内部，它将是这样的：

iterator operator+(iterator it, size_t n)
{
    for (int i=0; i<n; ++i)
        ++it;
    return it;
}

因此，换句话说，这将是一个 O(n) 操作。如果您要像在 for 循环中那样迭代集合，它就会变成 O(n^2) for 循环。如果实施了同样的事情operator[]。正因为如此，考虑到效率的人都不会想要使用这些运算符，因此没有实现它们。

于 2013-04-12T19:17:51.377 回答
1

STL 集不会重载下标运算符[]。您不能像使用其他容器（例如vector. 您可以在此处找到 STL 集的完整参考：STL 集

于 2013-04-12T19:14:15.017 回答
1

好吧，这是因为由于集合的性质，它std::set没有提供operator[]完全可以理解的下标。set[4] 应该是什么意思？从数学上讲，这是不正确的。在数学中 set1={1,2,3,4} 和 set2={4,3,2,1} 是相等的，所以如果这些集合中的每两个 set1[n] 和 set2[n] 仍然是正确的是不同的（如果std::set元素被排序，那么它会是相同的）？所以std::set没有下标operator[]，但是你仍然可以遍历这个容器。

int myints1[]= {10,20,30,40,50};
int myints2[]= {50,40,30,20,10}; 
std::set<int> s1 (myints1,myints1+5);
std::set<int> s2(myints2,myints2+5); // Internally, the elements in a set are 
                                     // always sorted following a specific strict
                                     // weak ordering criterion indicated by its
                                     // internal comparison object, so this set
                                     // will be the same as s2
if(s1==s2){
    printf("sets: true");
}else printf("sets: false");
std::set<int>::iterator it2=s2.begin();
for(std::set<int>::iterator it1=s1.begin();it1!=s1.end();it1++){
            printf("\ns1: %d  s2: %d",*it1,*it2);
    it2++;
}

输出：

套：真

s1：10 s2：10

s1：20 s2：20

s1：30 s2：30

s1：40 s2：40

s1：50 s2：50

于 2013-04-12T19:14:17.420 回答
1

@BenjaminLindley 正确地指出，T& operator[](std::size_t)对于没有随机访问迭代器的容器没有意义，因为所有随机访问循环都是O(N^2)复杂的（在元素的外部循环中是线性的，std::advance在迭代器上的时间是线性的）。出于这个原因，在序列容器std::array之外，只有std::vector和std::deque提供operator[]，但std::list（双向迭代器）和std::forward_list（前向迭代器）没有。

有序关联容器（、及其多个表亲）仅提供双向迭代器，而无序std::set关联容器（及其多个表亲）至少具有前向迭代器。他们也没有成为会员。因此，您需要编写而不是，这使得这种调用的复杂性非常明显。std::mapstd::unordered_setstd::unorderd_mapoperator[](std::size_t)std::advance(my_set.begin(), n)my_set[n]O(N)

作为补充说明：类似地图的容器包含键值对，这些容器的关联性质通过另一个表示operator[]，但不是由偏移量索引，而是使用“关联”键，并且它们具有签名Value& operator[](Key const&)（和自 C++11 以来的右值引用重载）。这些运算符对 具有O(log N)复杂性std::map和摊销O(1)复杂性std::unordered_map。这将分别给出这些容器的所有键O(N log N)和O(N)复杂性的循环。

关联operator[]版本还具有插入语义：调用 likemy_map[my_key] = my_value;将尝试将对插入my_key, my_value映射，如果这样的元素已经存在，则返回一个迭代器。请注意，const这些关联元素访问也没有重载：为此使用find()成员函数。

对于std::set重载operator[](Key const&)没有任何意义，因为它只会表达键与自身相关联的事实，而插入语义已经通过insert()成员函数更直接地表达了。

于 2013-04-12T20:34:03.767 回答
1

如果 BST 的每个节点都维护其后代的计数，则可以在 O(log(n)) 时间内找到 BST 的第 i 个元素，并且可以在 O(1) 时间内返回整个树的大小。每次插入和删除的开销将是 O(log(n))，这已经是 O(log(n)) 时间的操作。

于 2015-04-27T04:29:59.187 回答