Какой тип сортировки используется в станд.:: вид ()?
попробуйте это:
Сначала импортируйте это:
import {of} from "rxjs";
После, замените это:
this.shoppingList$ = of(this.shopping
.getShoppingList() // database list
.snapshotChanges() // gets key and value
.map(changes => { // for each change, get a new object
return changes.map(c => ({
key: c.payload.key,
...c.payload.val()
}));
}));
И переименуйте тип в вашем сервисе: [116 ]
private shoppingListRef= this.db.list<Item[]>('shopping-list');
4 ответа
Большинство реализаций std :: sort используют быструю сортировку (или обычно гибридный алгоритм, такой как интросортировка, который сочетает быструю сортировку, сортировку кучи и вставку sort).
Единственное, что требует стандарт, - это чтобы std :: sort каким-то образом отсортировал данные в соответствии с заданным порядком со сложностью приблизительно O (N log (N)); его стабильность не гарантируется. Технически интросортировка лучше отвечает требованиям сложности, чем быстрая сортировка, потому что быстрая сортировка имеет квадратичное время наихудшего случая.
GCC 9.2.0 libstdc ++ исходные другие introsort
подтверждения упомянули introsort, но вот некоторое доказательство для libstc ++, который является реализацией C++ по умолчанию на большинстве дистрибутивов Linux.
libstdc ++ является частью самого GCC, таким образом, мы изучим источник GCC.
libstdc ++-v3/include/std/algorithm является основным заголовком и содержит:
#include <bits/stl_algobase.h>
#include <bits/stl_algo.h>
Затем bits/stl_algo.h содержит определение перегрузок вида, одного из них быть:
/**
* @brief Sort the elements of a sequence.
* @ingroup sorting_algorithms
* @param __first An iterator.
* @param __last Another iterator.
* @return Nothing.
*
* Sorts the elements in the range @p [__first,__last) in ascending order,
* such that for each iterator @e i in the range @p [__first,__last-1),
* *(i+1)<*i is false.
*
* The relative ordering of equivalent elements is not preserved, use
* @p stable_sort() if this is needed.
*/
template<typename _RandomAccessIterator>
inline void
sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
__glibcxx_function_requires(_LessThanComparableConcept<
typename iterator_traits<_RandomAccessIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
__glibcxx_requires_irreflexive(__first, __last);
std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
}
, таким образом, мы видим, что это просто делает набор проверок работоспособности на входе и затем звонит std::__sort, который является определен в том же файле :
template<typename _RandomAccessIterator, typename _Compare>
inline void
__sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
if (__first != __last)
{
std::__introsort_loop(__first, __last,
std::__lg(__last - __first) * 2,
__comp);
std::__final_insertion_sort(__first, __last, __comp);
}
}
и я остановлюсь здесь, что мы достигли идентификатора, названного std::__introsort_loop, остальная часть реализации находится на том же файле, любой, все еще имеет сомнения.
Это должно также быть возможно к отладке шага GDB в std::sort без дальнейшей установки в Ubuntu 18.04, как упомянуто для std::set в: , Какова базовая структура данных набора STL в C++?
Стандарт C ++ ISO / IEC 14882: 2003
25.3.1.1 sort
шаблонvoid sort (сначала RandomAccessIterator, затем - RandomAccessIterator); шаблон <класс RandomAccessIterator, класс Сравнить> пустая сортировка (сначала RandomAccessIterator, наконец, RandomAccessIterator, Сравните comp); 1 Эффекты : сортирует элементы в диапазон [первый, последний).
2 Сложность : Приблизительно N log N (где N == last - во-первых) сравнения в среднем.
Информации о методе нет, но сложность всегда равна N log N .
Вы имеете в виду std :: sort? Если да, то это можно реализовать как угодно. Вероятно, это быстрая сортировка, но это может быть основание или что-то еще. Пока он создает отсортированный список по крайней мере за O (n log n), реализация в порядке, afaik.