Sorting

Решаем вопрос сортировки в JavaScript раз и навсегда

30.05.2021 14:10:27 |

Автор: admin

Вступление

Многим JavaScript разработчикам доводилось сортировать данные на стороне клиента. К сожалению, существующие библиотеки имеют мелкие недостатки. Но эти недостатки складываются и ограничивают то как программисты думают о сортировке. Чтобы преодолеть эти ограничения, давайте рассмотрим сортировку в разных языках. Вооруженные этими знаниями, мы сможем выбрать наиболее удобный и строгий интерфейс.

С чего все началось

В один прекрасный летний день, на проекте с AngularJS мне поручили добавить функцию сортировки в таблицу. При этом критериев для сортировки может быть сразу несколько, и направление по каждому критерию может быть независимым.

Список требований:

использовать несколько выражений как ключ для сортировки
возможность указать направление сортировки независимо по каждому из ключей
возможность сортировать строки без учета регистра, и с учетом локали
устойчивость сортировки

Что нам предлагает AngularJS для сортировки? документация по filter:orderBy

{{ orderBy_expression | orderBy : expression : reverse : comparator }}$filter('orderBy')(collection, expression, reverse, comparator)Example:<tr ng-repeat="friend in friends | orderBy:'-age'">...</tr>

У меня возникло несколько замечаний по поводу этого фильтра. Для начала, знак - в этом примере не может быть математической операцией, потому что есть значения для которых это бессмысленная операция, например строки. В документации говорится что это префикс, который указывает направление сортировки. Если продолжить разбор, что это вообще за выражение? Это, вроде как, похоже на JS, но в то же время не очень. Это синтаксис выражений для AngularJS, который так же опасен как eval, но при этом имеет свои ограничения. То что этот синтаксис исключителен для AngularJS значит что эти знания невозможно перенести на другие проекты на JS. Кроме того, нельзя использовать TypeScript для проверки этих выражений. expression кроме того может принимать не только строку, но и функцию, которая возвращает ключ для сортировки. Но если указывать функцию, то направление сортировки указать нельзя и теряется гибкость. Так же можно указать несколько критериев сортировки, если задать массив из строк или функций.

Идем дальше, направление сортировки так же можно поменять вторым параметром reverse. Но возникает проблема! Если указывать несколько критериев сортировки с помощью функций, то нельзя указать направление индивидуально для каждого критерия. Если же указывать направиление сортировки в каждом критерии индивидуально, то этот параметр лишний.

Теперь посмотрим на третий параметр comparator, который позволяет задать особый способ сравнения элементов. Но при этом если было указано несколько критериев сортировки, то один и тот же comparator будет использоваться для каждого критерия. В результате localeSensitiveComparator будет использоваться для сортировки чисел.

И спрашивается, какая мне польза использовать интерфейс который сам с собой не дружит в трех местах, несовместим с TypeScript и его можно использовать исключительно в богом позабытом фреймворке? В мире JavaScript таких примеров, к сожалению, полным полно.

lodash

Посмотрим на библиотеку lodash, В ней есть функция _.sortBy, которая позволяет сортировать массив по ключу.

var users = [    { 'user': 'fred',   'age': 48 },    { 'user': 'barney', 'age': 36 },    { 'user': 'fred',   'age': 40 },    { 'user': 'barney', 'age': 34 }]; _.sortBy(users, [(o) => o.user]);// => objects for [['barney', 36], ['barney', 34], ['fred', 48], ['fred', 40]] _.sortBy(users, ['user', 'age']);// => objects for [['barney', 34], ['barney', 36], ['fred', 40], ['fred', 48]]

Хм, эта функция не позволяет указывать направление сортировки, почему так? Из-за этого я хотел сразу отбросить lodash, но потом увидел _.orderBy.

This method is like _.sortBy except that it allows specifying the sort orders of the iteratees to sort by.

Добавление опционального параметра не должно ломать обратную совместимость, поэтому мне совсем непонятно почему это сделали отдельной функцией. Посмотрим на его использование:

// Sort by `user` in ascending order and by `age` in descending order._.orderBy(users, ['user', 'age'], ['asc', 'desc']);// => objects for [['barney', 36], ['barney', 34], ['fred', 48], ['fred', 40]]

И сразу же возникает замечание поскольку направление сортировки указывается отдельно от самого критерия, не очевидно в какую сторону он будет сортироваться. Это приведет к тому, что удаление или добавление критериев сортировки может рассинхронизовать эти два массива, и может привести к неожиданным последствиям.

В целом, _.orderBy это терпимый метод сортировки.

Array#sort

Если же мы хотим использовать только стандартную библиотеку JavaScript, у Array нам доступен метод sort. В этом методе можно указать функцию для сравнения элементов. Сам по себе этот интерфейс для сортировки позволяет указать любой возможный критерий для сортировки. Правда он не так удобен для использования как сортировка по ключу, и есть довольно много подводных камней. Самый большой подводный камень, с моей точки зрения, к этой функции есть очень строгое требование линейно упорядоченного множества. Это требование очень просто нарушить. В прошлом, несоблюдение этих требований в некоторых браузерах приводило к бесконечным циклам и крахам.

items.sort(function(a, b) {    if (b.salary < a.salary) {      return -1;    }    if (b.salary > a.salary) {      return 1;    }    if (a.id < b.id) {      return -1;    }    if (a.id > b.id) {      return 1;    }    return 0;});// Для сравнения, эквивалентный код с использованием `lodash`// намного короче и его проще читать:lodash.orderBy(items, ['salary', 'id'], ['desc', 'asc']);

Когда критериев для сортировки будет больше, то разница в удобстве будет еще больше, что приведет повторению кода. Отсутствие удобства и громоздкость обычно приводит к тому, что в код закрадываются трудно уловимые ошибки.

Если же мы хотим примеры адекватных интерфейсов, нужно смотреть в сторону других языков.

SQL / SEQUEL

Стоит начать с того что данные лучше всего нужно сортировать на стороне сервера, и отображать на клиенте как есть, без перестановок. Если можно убрать сортировку на клиенте, поздравляю, проблема решена! Но этот пост не о таких ситуациях, поэтому попробуем позаимствовать опыт SQL.

Как ни как, сортировка это часть языка SQL с 1976 года, и с его помощью люди давно сортируют данные налево и направо. Кому, как не пользователям реляционных баз данных, приходится больше всего сортировать данные по сложным критериям?

SELECT EMPNO,NAME,SALFROM EMPWHERE DNO 50ORDER BY EMPNO

SQL позволяет указывать несколько критериев сортировки, а так же независимо указывать направление сортировки по разным критериям:

SELECT EMPNO,NAME,SALFROM EMPORDER BY SAL DESC, EMPNO ASC

Вот к такому нужно стремиться. К сожалению, SQL это отдельный язык и без специального синтаксиса нет возможности внедрить это напрямую.

Haskell и Rust

Haskell и Rust предоставляют довольно элегантные методы для сортировки по ключу:

Haskell sortOn:

import Data.Ord (Down)import Data.Sort (sortOn)sortOn (\employee -> (Down (salary employee), employee_id employee)) employees

Rust slice::sort_by_key:

use std::cmp::{Reverse};slice.sort_by_key(|employee| (Reverse(employee.salary), employee.id))

Здесь сортировка по нескольким критериям достигается за счет лексикографического порядка кортежей, а сортировка по убыванию за счет оберточных типов (newtype) Down и Reverse, которые инвертирует порядок сортировки своего содержания. Это очень простой для использовани интерфейс, и он полностью совместим со всеми требованиями.

Python

В Python у списков есть встроенный метод list.sort и гобальный метод sorted, в котором можно указать критерий сортировки через именованный аргумент key.

Ранее эти методы так же принимали аргумент cmp, но его убрали потому что он не нужен.

sorted(employees, key=lambda employee: (employee.salary, employee.id))

Python, как Haskell и Rust, здесь использует кортеж для сортировки по нескольким критериям, но нельзя указывать направление сортировки отдельно для каждого критерия. К счастью, это легко исправить, создав клас-обертку для обратной сортировки. Это упростит метод сортировки, убрав один аргумент, и одновременно расширит возможности сортировки.

from ord_reverse import Reversesorted(employees, key=lambda employee: (Reverse(employee.salary), employee.id))

Java и C#

В Java метод Arrays.sort принимает Comparator (который почти состоит одной функции сравнения двух элементов). Но Comparator так же позволяет строить компараторы, добавляя новые критерии сравнения, используя метод thenComparing. Можно обратить направление сортировки используя метод reversed.

Comparator<Employee> comparator =  Comparator.comparing(Employee.getSalary).reversed()    .thenComparing(Employee.getId);Arrays.sort(array, comparator);

Здесь есть небольшой недостаток нет простого способа указать обратное направление сортировки для отдельного критерия. Давайте попробуем написать компаратор вида ORDER BY SALARY ASC, ID DESC:

// Вариант 1, создавать два компаратора, и складывать ихComparator<Employee> comparator =  Comparator.comparing(Employee.getSalary)    .thenComparing(Comparator.comparing(Employee.getId).reversed());// Вариант 2, инвертирует компаратор дважды. Таким образом первый компаратор// будет использовать прямое направиление сортировки.Comparator<Employee> comparator =  Comparator.comparing(Employee.getSalary).reversed()    .thenComparing(Employee.getId).reversed();

Если не учитывать LINQ Query, который есть прямым наследником SQL, в C# для сортировки используется Enumerable.OrderBy и Enumerable.OrderByDescending, а так же Enumerable.ThenBy и Enumerable.ThenByDescending для добавления новых критериев сортировки.

IEnumerable<Employee> query =    employees    .OrderByDescending(employee => employee.Salary)    .ThenBy(employee => employee.Id);

По сравнению с Java здесь легче указать обратною сортировку для индивидуальных ключей. Но есть и недостатки не очевидно когда именно будет происходить сортировка, и слишком множатся методы: IEnumerable 4 метода, по сравнению с 1 в Haskell/Rust/Python. Количество методов в C# можно было бы свести к двум, используя простой класс для инверсии сравнения.

В целом, как Java, так и C# удовлетворяют требования сортировки. К сожалению, оба языка используюь более громоздкий подход с использованием ООП.

C и C++

C qsort:

#include <stdlib.h>int cmp_employee(const void *p1, const void *p2){      const employee *a = (employee*)p1;      const employee *b = (employee*)p2;      if (b->salary < a->salary) {        return -1;      }      if (b->salary > a->salary) {        return 1;      }      if (a->id < b->id) {        return -1;      }      if (a->id > b->id) {        return 1;      }    return 0;  }  /* ... */  qsort(employees, count, sizeof(employee), cmp_employee);

C++ std::sort:

#include <algorithm>/* ... */std::sort(employees.begin(), employees.end(), [](const employee &a, const employee &b) {  return (b->salary < a->salary) || (a->id < b->id);});

Как в C, так и в C++ сортировать можно только предоставляя функцию сравнения элементов. Только в C сравнение элементов требует возвращать не -1, 0, 1, а в C++ проверять что первый элемент меньше второго. В каком-то смысле, так теряется часть информации о сравнении. Скорее всего, это приводит к тому что функция сравнения в C++ вызывается больше чем необходимо.

В C и в C++ нет встроенных способов сортировки по ключу и отсутствуют воспомагательные классы для сборки компараторов из нескольких частей. Array#sort, который мы рассматривали ранее имеет те же недостатки как и эти две функции.

Выбираем то что лучше подходит

Из всех перечисленных интерфейсов, наиболее компактная и выразительная сортировка в Haskell и Rust. Можем ли мы перенести ее в JavaScript?

Кортежей в JS нет, но для этих целей можно использовать массивы, так как JS позволяет хранить разные типы в массивах. Оберточных типов нет, но мы можем выбрать нужные типы и определить их форму в функции сравнения. Как это будет выглядеть?

sortBy(array, (employee) => [{ reverse: employee.salary }, employee.id]);

Определяем линейный порядок в JavaScript

Для того чтобы использовать сортировку по ключу, нужно для начала определиться как сравнивать ключи. Так как в JavaScript нет приемлимого встроенного порядка, нет интерфейсов, Trait-ов и typeclass-ов, то необходимо выбрать достаточное подмножество сравнений для которых будет определен полный порядок, или сравнение будет неуспешным.

Определяем с нуля:

null меньше всех значений. Это альтернативно использованию типа Maybe или Option.
Если типы разные, сравнение бросает ошибку.
Особое значение NaN меньше всех других чисел.
Остальные числа, строки, були и BigInt сравниваются между собой как определено в JavaScript.
Массивы сравниваются используя лексикографический порядок, рекурсивно сравнивая элементы.
Если оба значения имеют форму { reverse: xxx }, то значение xxx будет рекурсивно сравниваться в обратном порядке. Это равносильно использованию Down / Reverse
Если оба значения имеют форму { localeCompare: sss, collator: ccc }, строки sss сравниваются используя коллатор ccc. Коллаторы в обоих значений должны быть равны.
Все остальное бросает ошибку.

Из-за строгости определения, здесь должно быть достаточно ограничений чтобы сравнение удовлетворяло линейному порядку или было неуспешным. Этого подмножества должно хватить для того чтобы решать все возможные задачи сортировки.

Как только мы выбрали интерфейс для сортировки и определили линейный порядок, осталось дело за малым воплотить это в виде библиотеки: better-cmp

Бонус: почему я не использовал библиотеку X?

orderBy: не смотря на "Inspired by Angular's orderBy filter", эта библиотека довольно хороша. Но я предпочел пойти дальше.
thenby: довольно хорошая библиотека, копирует интерфейс Java для комбинации компараторов, но я решил копировать другой язык из-за эргономики.

multisort: _

if (/[^\(\r\n]*\([^\(\r\n]*\)$/.test(nextKey)) {    var indexOfOpenParenthesis = nextKey.indexOf("(");    var args = JSON.parse("[" + nextKey.slice(indexOfOpenParenthesis+1, -1) + "]");    nextKey = nextKey.slice(0, indexOfOpenParenthesis);}

Заключение

Надеюсь что этот обзор интерфейсов сортировок в разных языках был вам полезен, и что в будущем вам легче будет разобраться как сортировать данные по многим критериям.
Довольно странно что для такой распространенной операции как сортировка разные языки используют разные интерфейсы.
Ещё более странно странно что в "текущем году" в JavaScript нет широко известной и адекватной сортировки по ключу.
Лучшее решение для JavaScript что смог сделать теперь воплощено в виде библиотеки better-cmp, доступной на npm.

Подробнее..

Категории: Javascript , Программирование , Функциональное программирование , Алгоритмы , Sql , Сортировка , Angularjs , Sorting , Ordering

Под капотом сортировок в STL

08.10.2020 16:23:54 |

Автор: admin

Стандарт С++ почти никогда не указывает, как именно должен быть реализован тот или иной std алгоритм. Дается только описание того, что на входе, что на выходе и асимптотические ограничения по времени работы и памяти. В статье я постарался прикинуть, какие математические алгоритмы и структуры данных имели ввиду авторы стандарта, указывая ограничения для той или иной сортировки и для некоторых других алгоритмов. А так же как эти алгоритмы реализованы на практике.

При написании статьи я использовал стандарт C++17. В качестве реализаций рассматривал GCC 10.1.0 (май 2020) и LLVM/Clang 10.0.0 (март 2020). В каждой и них есть своя реализация STL, а значит и std алгоритмов.

1. Однопоточные реализации

1.1. Готовые сортировки

std::sort(). Еще в стандарте C++98/C++03 мы видим, что сложность алгоритма примерно n*log(n) сравнений. А также есть примечание, что если важна сложность в худшем случае, то следует использовать std::stable_sort() или std::partial_sort(). Похоже, что в качестве реализации std::sort() подразумевался quicksort (в худшем случае O(n²) сравнений). Однако, начиная с C++11 мы видим, что сложность std::sort() уже O(n*log(n)) сравнений безо всяких оговорок. GCC реализует предложенную в 1997 году introsort (O(n*log(n)) сравнений, как в среднем, так и в худшем случае). Introsort сначала сортирует как quicksort, но вскоре переключается на heapsort и в самом конце сортировки, когда остаются небольшие интервалы (в случае GCC менее 16 элементов), сортирует их при помощи insertion sort. А вот LLVM реализует весьма сложный алгоритм с множеством оптимизаций в зависимости от размеров сортируемых интервалов и того, являются ли сортируемые элементы тривиально копируемыми и тривиально конструируемыми.
std::partial_sort(). Поиск некоторого числа элементов с минимальным значением из множества элементов и их сортировка. Во всех версиях стандарта сложность примерно n*log(m) сравнений, где n количество элементов в контейнере, а m количество минимальных элементов, которое нужно найти. Задача для heapsort. Сложность в точности совпадает с этим алгоритмом. Так и реализовано в LLVM и GCC.
std::stable_sort(). Тут немного сложнее. Во-первых, в отличии от предыдущих сортировок в стандарте отмечено, что она стабильная. Т.е. не меняет местами эквивалентные элементы при сортировке. Во-вторых, сложность ее в худшем случае n*(log(n))² сравнений и n*log(n) сравнений, если есть достаточно памяти. Т.е. имеется ввиду 2 разных алгоритма стабильной сортировки. В варианте, когда памяти много подходит стандартный merge sort. Как раз ему требуется дополнительная память для работы. Сделать merge sort без дополнительной памяти за O(n*log(n)) сравнений так же возможно. Но это сложный алгоритм и не смотря на асимптотику n*log(n) сравнений константа у него велика, и в обычных условиях он будет работать не очень быстро. Поэтому обычно используется вариант merge sort без дополнительной памяти, который имеет асимптотику n*(log(n))² сравнений. И в GCC и в LLVM реализации в целом похожи. Реализованы оба алгоритма: один работает при наличии памяти, другой когда памяти не хватает. Обе реализации, когда дело доходит до небольших интервалов, используют insertion sort. Она стабильная и не требует дополнительной памяти. Но ее сложность O (n²) сравнений, что не играет роли на маленьких интервалах.
std::list::sort(), std::forward_list::sort(). Все перечисленные выше сортировки требуют итераторы произвольного доступа для задания сортируемого интервала. А что если требуется отсортировать контейнер, который не обеспечивает таких итераторов? Например, std::list или std::forward_list. У этих контейнеров есть специальный метод sort(). Согласно стандарту, он должен обеспечить стабильную сортировку за примерно n*log(n) сравнений, где n число элементов контейнера. В целом вполне подходит merge sort. Ее и реализуют GCC и LLVM и для std::list::sort(), и для std::forward_list::sort(). Но зачем вообще потребовались частные реализации сортировки для списков? Почему бы для std::stable_sort() просто не ослабить итераторы до однонаправленных или хотя бы двунаправленных, чтоб этот алгоритм можно было применять и к спискам? Дело в том, что в std::stable_sort() используются оптимизации, которые требуют итераторы произвольного доступа. Например, как я писал выше, когда дело доходит до сортировки не больших интервалов в std::stable_sort() разумно переключиться на insertion sort, а эта сортировка требует итераторы произвольного доступа.
std::make_heap(), std::sort_heap(). Алгоритмы по работе с кучей (max heap), включая сортировку. std::sort_heap() это единственный способ сортировки, алгоритм для которого указан явно. Сортировка должна быть реализована, как heapsort. Так и реализовано в LLVM и GCC.

Сводная таблица

Алгоритм	Сложность согласно стандарту C++17	Реализация в GCC	Реализация в LLVM/Clang
std::sort()	O(n*log(n))	introsort	-
std::partial_sort()	O(n*log(m))	heapsort	heapsort
std::stable_sort()	O(nlog(n))/O(n(log(n))²)	merge sort	merge sort
std::list::sort(), std::forward_list::sort()	O(n*log(n))	merge sort	merge sort
std::make_heap(), std::sort_heap()	O(n*log(n))	heapsort	heapsort

Примечание. В качестве реализации в GCC и LLVM указан алгоритм, который используется для больших сортируемых интервалов. Для особых случаев (не большие интервалы и т.п.) часто используются оптимизации.

1.2. Составляющие алгоритмов сортировки

std::merge(). Слияние двух сортированных интервалов. Этот алгоритм не меняет местами эквивалентные элементы, т.е. он стабильный. Количество сравнений не более, чем сумма длин сливаемых интервалов минус 1. На базе данного алгоритма очень просто реализовать merge sort. Однако напрямую этот алгоритм не используется в std::stable_sort() ни LLVM, ни в GCC. Для шага слияния в std::stable_sort() написаны отдельные реализации.
std::inplace_merge(). Этот алгоритм также реализует слияние двух сортированных интервалов и он также стабильный. У него есть интерфейсные отличия от std::merge(), но кроме них есть еще одно, очень важное. По сути std::inplace_merge() это два алгоритма. Один вызывается при наличии достаточного количества дополнительной памяти. Его сложность, как и в случае std::merge(), не более чем сумма длин объединяемых интервалов минус 1. А другой, если дополнительной памяти нет и нужно сделать слияние "in place". Сложность этого "in place" алгоритма n*log(n) сравнений, где n сумма элементов в сливаемых интервалах. Все это очень напоминает std::stable_sort(), и это не спроста. Как кажется, авторы стандарта предполагали использование std::inplace_merge() или подобных алгоритмов в std::stable_sort(). Эту идею отражают реализации. В LLVM для реализации std::stable_sort() используется std::inplace_merge(), в GCC для реализаций std::stable_sort() и std::inplace_merge() используются некоторые общие методы.
std::partition()/std::stable_partition(). Данные алгоритмы также можно использовать для написания сортировок. Например, для quicksort или introsort. Но ни GCC ни LLVM не использует их на прямую для реализации сортировок. Используются аналогичные им, но оптимизированные, для случая конкретной сортировки, варианты реализации.

2. Многопоточные реализации

В C++17 для многих алгоритмов появилась возможность задавать политику исполнения (ExecutionPolicy). Она обычно указывается первым параметром алгоритма. Алгоритмы сортировок не стали исключением. Политику исполнения можно задать для большинства алгоритмов рассмотренных выше. В том числе и указать, что алгоритм может выполняться в несколько потоков (std::execution::par, std::execution::par_unseq). Это значит, что именно может, а не обязан. А будет вычисляться в несколько потоков или нет зависит от целевой платформы, реализации и варианта сборки компилятора. Асимптотическая сложность также остается неизменной, однако константа может оказаться меньше за счет использования многих потоков.

Тут ключевое слово может. Дело в том, что однопоточные реализации, описанные выше, подходят для соответствующих алгоритмов, какая бы политика исполнения ни была задана. И однопоточные реализации часто используются на настоящий момент не зависимо от политики исполнения. Я рассмотрел следующие версии:

LLVM/Clang (Apple clang version 11.0.3 (clang-1103.0.32.62)) и MacOS 10.15.4. В этом случае заголовочный файл execution не нашелся. Т.е. политику многопоточности задать не получится;
LLVM/Clang 10.0.0 сборка из brew. Тот же результат, что и в случае Apple clang;
GCC 10.1.0 файл execution есть и политику задать можно. Но какая бы политика ни была задана, использоваться будет однопоточная версия. Для вызова многопоточной версии необходимо, чтобы был подключен файл tbb/tbb.h при компиляции на платформе Intel. А для этого должна быть установлена библиотека Intel Threading Building Blocks (TBB) и пути поиска заголовочных файлов были прописаны. Установлен ли TBB проверяется при помощи специальной команды в gcc: __has_include(<tbb/tbb.h>) в файле c++config.h. И если данный файл виден, то используется многопоточная версия написанная на базе Threading Building Blocks, а если нет, то последовательная. Про TBB немного подробнее ниже.
Дополнительную информацию о поддержке компиляторам параллельных вычислений, как впрочем и другой функциональности, можно посмотреть здесь: https://en.cppreference.com/w/cpp/compiler_support

3. Intel Threading Building Blocks

Чтоб стало возможным использовать многопоточные версии разных алгоритмов, на сегодня нужно использовать дополнительные библиотеку Threading Building Blocks, разрабатываемую Intel. Это не сложно:

Клонируем репозиторий Threading Building Blocks с https://github.com/oneapi-src/oneTBB
Из корня запускаем make и ждем несколько минут пока компилируется TBB или make all и ждем пару часов, чтоб прошли еще и тесты
Далее при компиляции указываем пути к includes (-I oneTBB/include) и к динамической библиотеке (у меня был такой путь -L tbb/oneTBB/build/macos_intel64_clang_cc11.0.3_os10.15.4_release -ltbb, т.к. я собирал TBB при помощи Apple clang version 11.0.3 на MacOS)

4. Эпилог

Как кажется, когда комитет C++ описывает те или иные особенности языка в стандарте, он предполагает те или иные сценарии использования и те или иные алгоритмы реализации. Часто все развивается, как предполагалось. Иногда идет своим путем. Иногда не используется вовсе. Какие бы ни были реализации тех или иных алгоритмов или структур данных сегодня, завтра это может измениться. Измениться впрочем может и стандарт. Но меняясь, стандарт почти всегда обеспечивает совместимость с ранее написанным кодом. При выпуске новых версий компиляторов, могут меняться и реализации. Но изменяясь они предполагают, что разработчики полагаются на стандарт. На мой взгляд, имеет смысл понимать, как обычно реализуются те или иные части стандартной библиотеки. Но полагаться при разработке нужно именно на ограничения заданные стандартом.

Ссылки на упомянутые алгоритмы и библиотеку:

Благодарности

Большое спасибо Ольге Serine за замечание по статье и картинку.