Is the document in `SortedMap in rustc_data_structures::sorted_map` correct?

It said that

SortedMap is a data structure with similar characteristics as BTreeMap but slightly different trade-offs: lookup, insertion, and removal are O(log(n)) and elements can be iterated in order cheaply.

But according to sorted_map.rs - source, its insert method just called Vec::insert, which should be O(n)

I wonder:

  1. Am I correct?
  2. If I was correct, who I should notify to correct this document?
2 Likes

Yes. It appears that the documentation is incorrect.

The source is located here. You can file a bug in that repository.

2 Likes