Оператор ссылки [] на STL

Question

Я просто знакомлюсь с 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; 
     } 

Я понимаю, почему он не имеет членов, как push_back, pop_back и все, но я не понимаю, почему эти два метода ссылки не работают (но они делают для vector и 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; 
     } 

Answer 1

Стандарт не устанавливает эти операторы для набора или его итераторов, потому что те не эффективные способы доступа к набору. Набор имеет двунаправленные итераторы. Это означает, что для перехода к n-му элементу в последовательности итераций вам нужно перебирать каждый элемент между ними. Так, например, если оператор + должны были быть реализованы итераторы набор, в внутри, это было бы что-то вроде этого:

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

Так, другими словами, это было бы O (п) операции. Если вы должны были перебирать набор, как вы делаете в своем цикле for, он становится циклом O (n^2). То же самое применяется, если был реализован operator[]. Из-за этого никто из соображений эффективности не захочет использовать эти операторы, и поэтому они не реализованы.

Answer 2

STL набор не перегружать оператор подстрочного []. Вы не можете получить доступ к элементам STL, используя оператор индекса, как и в других контейнерах, таких как vector. Вы можете найти полное отнесение STL установить здесь: STL set

Answer 3

хорошо, это потому, что std::set не обеспечивает подстрочный operator[], что вполне понятно из-за природы множества. Что это должно означать множество [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: s2: 50 50

Answer 4

@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::map, и их кузены многоканальных) только обеспечивают двунаправленные итераторы, а Неотсортированных Ассоциативные контейнеры (std::unordered_set, std::unorderd_map и их кузены мульти) имеют по крайней мере вперед итераторы. У них также нет operator[](std::size_t) в качестве участника. Поэтому вам необходимо написать std::advance(my_set.begin(), n) вместо my_set[n], что делает сложность такого звонка болезненным помутнением O(N).

Как добавленное примечание: контейнеры, подобные карте, содержат пары «ключ-значение», а ассоциативный характер этих контейнеров выражается через другой operator[], но не индексируется по смещению, а скорее с «ассоциированным» ключом, и они имеют подпись Value& operator[](Key const&) (и переназначение rvalue-reference с C++ 11). Эти операторы имеют O(log N) сложность для std::map и амортизированы O(1) сложность для std::unordered_map. Это даст, например, петли над всеми ключами этих контейнеров O(N log N) и O(N) сложности, соответственно.

ассоциативной operator[] версия также имеет вставки семантики: вызовы, как my_map[my_key] = my_value; будут пытаться вставить пару my_key, my_value в карту, и возвращают итератор, если уже существует такой элемент. Обратите внимание, что это также не const перегрузки для доступа к ассоциативным элементам тезисов: используйте для этого функции-члены find().

Для std::set перегруженного operator[](Key const&) не имеет никакого смысла, так как это было бы только выразить тот факт, что ключ, связанные с собой, и вставной семантикой уже более непосредственно выражаются через функцию insert() члена.

Answer 5

Если каждый узел BST поддерживает подсчет его потомков, i-й элемент BST может быть найден в O (log (n)), время и размер общего дерева могут быть возвращены в O (1) раз , Накладные расходы - O (log (n)) для каждой вставки и удаления, которые уже являются O (log (n)) - операциями времени.