Форум

Обычно когда бегло просматриваешь, какие есть стандартные алгоритмы в С++, то глубоко не задумываешься, а всегда ли заданный алгоритм можно применить к каждому стандартному контейнеру, и почему к конкретному контейнеру этот алгоритм применить нельзя. И если такие ограничения на применение есть, то действительно ли они оправданы?

Часто опыт первого знакомства с каким-нибудь алгоритмом ограничивается запуском примера его использования для последовательных контейнеров, или для обычных массивов. Рассмотрим стандартный алгоритм std::reverse. Он имеет всего лишь две формы

template <typename BidirectionalIterator> 
 void reverse( BidiirectionalIterator first, BidirectionalIterator last );

template <typename BidirectionalIterator, typename OutputIterator> 
 OutputIterator reverse_copy( BidiirectionalIterator first, BidirectionalIterator last, OutputIterator result );

Из названия алгоритма ясно, что он осуществляет перестановку элементов контейнера в обратном порядке. Первая форма алгоритма служит для перестановки элементов контейнера "на месте", а вторая - для записи элементов заданного контейнера в обратном порядке в последовательность, начало которой указывается итератором rOutputIterator result.

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

Вот простой пример работы этого алгоритма для контейнар std::vector

#include <iostream> 
 #include <iterator> 
 #include <algorithm> 
 #include <vector> 
  
 int main() 
 { 
    std::vector<int> v( 3 ); 
  
    v[0] = 1; 
    v[1] = 2; 
    v[2] = 3; 
  
    std::copy( v.begin(), v.end(), std::ostream_iterator<int>( std::cout, " " ) ); 
    std::cout << std::endl; 
  
    std::reverse( v.begin(), v.end() ); 
  
    std::copy( v.begin(), v.end(), std::ostream_iterator<int>( std::cout, " " ) ); 
    std::cout << std::endl; 
 }

Результатом работы этого примера будет вывод на консоль двух сттрок

1 2 3
3 2 1

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

Конечно можно без проблем применить этот алгоритм к любому стандартному последовательному контейнеру С++ при условии, что контейнер предоставляет двунаправленный итератор или итератор прямого доступа. Мы могли бы в вышеприведенном примере заменить вектор на контейнер std::list (правда заменив способ заполнение списка, так как список не имеет средства прямого доступа к своим элементам по индексу), или на контейнер std::deque. Не гговоря уж о том, что этот алгоритм можно применить к обычным массивам.

У меня этот вопрос тоже не возникал до тех пор, пока я не начал внимательно изучать интерфейс ассоциативного контейнера std::map. Как известно, это контейнер, который хранит данные, упорядоченные по ключам, точно также, как это обычно делается для индексно-последовательных наборов данных на дисках. Кто работал с базами данных хорошо знает, что часто возникает задача построения инверсных таблиц, и эта задача порой вызывает серьезные проблемы при ее решении!
И я, вдруг, для себя обнаружил, что для ассоциативного контейнера std::map такого стандартного алгоритма, как reverse не существует! А стандартный глобальный алгоритм std::reverse нельяз применить к этому контейнеру, так как итератор контейнера std::map возвращает пару значений в виде стандартного класса std::pair, состоящий из ключа и отображаемоого по этому ключу значения. То есть нельзя просто поменять значения итераторов, так как нарушится порядок упорядочивания элементов в контейнере. Чтобы было понятно, то если есть контейнер std::map, который хранит пары { 0, 'A' }, { 1, 'B' }, { 2, 'C' },... { 25, 'Z' }, то хотелось бы разместить в обратном порядке только отображаемые значения, то есть вместо порядка символов от 'A' до 'Z' хранить их с теми же ключами 0 - 25, но в обратном порядке от 'Z' до 'A'. Если использовать стандартный алгоритм std::reverse, то он будет менять не значения, допустим, 'A' и 'Z' у пар { 0, 'A' } и { 25, 'Z' }, а будет целиком переставлять пары местами, то есть попытается на первое место разместить пару { 25, 'Z' }, а в конец поместить пару { 0, 'A' }. А это делать нельзя, так как нарушается порядок размещения элементов, который задается первым элементом пары. То есть элементы должны размещаться по возрастанию значений от 0 до 25, а потому их переставить нельзя.
Что в таком случае делать? Обычно предполагается, если разработчики стандарта С++ не включают в интерфейс контейнера тот или иной алгоритм, то это означает, что поставленную задачу легко выполнить унифицированным образом с помощью глобальных стандартных алгоритмов. Но мне что-то в голову не приходила идея, как наилучшим образом, используя существующие стандартные алгоритмы, составить из них алгоритм reverse специально для коонтейнера std::map. Поэтому, думая, что я просто не вижу очевидного решения, я обратился с этим вопросом на [url=http://www.rsdn.ru/?users/ActivateUser.aspx?71fca6b2-e893-45ef-afa5-21d1fb2ea9d0]форум[/url]

Но, увы, там довлльно разношерстная публика, а потому уровень комментариев в среднем достаточно невысокий. Многие даже и не поняли значение подобного вопроса. Поэтому я решил представить этот вопрос здесь, когда нет "шумов в эфире", как говорят радиотехники, создаваемых всякими низкоквалифицированными умниками.

Первое, что стало очевидно из обсуждения на том форуме, что такого простого, а самое главное общепринятого способа заменить алгоритм reverse для контейнера std::map нет! То есть каждый программист должен писать собственную функцию. Издержки такоого подхода очевиидны. Во-первых, вы не можете гарантировать правильность работы такого "самопального" алгоиртма. Во-вторых, будет чехарда с названием этого алгоритма, так как будет некорректно назвать его reverse, так как это может внести путаницу с именами и конфликты имен. То есть каждый программист помимо своего алгоритма буде тпридумывать и свое наименование этого алгоритма. Очевидно, все это делает код более трудным к восприятию. Ведь в чем одно из достоинств использования стандартных алгоритмов? Когда мы встречаем их в коде, то само имя алгоритма говорит о том, что данный код делает, а потому обычно нет необходимости каждый раз смотреть внутрь тела алгоритма, чтобы разобраться в его работе. То есть имена стандартных алгоритмов - это язык интернационального общения программистов.
Отмечу также, что предлагавшиеся на том форуме частные решения на мой взгляд были не совсем удачные. либо для цикла там вводилась дополнительная управляющая коонструкция, как деление размера контейнера пополам, чтобы установить верхнюю границу цикла, либо использование сразу же двух типов итераторов, хотя, зная, что эти контейнеры имеют двунаправленный итератор, то можно было ограничиться одним типом итератора. То есть пришло время самодеятельности со всеми ее издержками.

Второй принципиальный вопрос: а нужен ли такой алгоритм, для коонтейнера std::map?
А почему бы и нет? Давайте сравним контейнер std::vector с контейнером std::map.. Можно контейнер std::vector рассматривать с логической точки зрения как частный случай контейнера std::map, у которого ключом является порядковый номер элемента. То есть контейнер std::vector, фактически, состоит из пар (возьмем значения из примера выше) { 0, 'A' }, { 1,''B' }, ... { 25, 'Z' }. Чем эхто не контейнер std::map, для которого ключ задан как беззнаковое целое, а отображаемое значение, как символ? Посмотрим, как это будет выглядеть при заполнении контейнера std::vector

#include <vector> 
  
 int main() 
 { 
    std::vector<char> c( 26 ); 
  
    c[0] = 'A'; 
    c[1] = 'B'; 
    //  заполняем другие элементы 
    c[25] = 'Z'; 
 }

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

std::reverse( c.begin(), c.end() );

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

c[0] == 'Z';
...
c[25] == 'A';

То есть формально порядок ключей сохранен, а переставлены в обратном порядке хранимые значения.
Причем следует заметить, что порой требуется реверсировать не весь контейнер, а лишь некоторый диапазон его элементов.

Теперь рассмотрим следующий код с std::map

#include <map> 
  
 int main() 
 { 
    std::map<unsigned int, char> c; 
  
    c[0] = 'A'; 
    c[1] = 'B'; 
    //  заполняем другие элементы 
    c[25] = 'Z'; 
 }

Как можно заметить, никакой разности в заполнении контейнера нет, если использовать либо sttd::vector, либо std::map. Более того, если вы встретите в программе код

   c[0] = 'A'; 
    c[1] = 'B'; 
    //  заполняем другие элементы 
    c[25] = 'Z';

вы даже не сможете сказать, какой контейнер используется! То есть данный код инвариантен для двух типов контейнеров. Теперь наступает самое интересное, а что если вам нужно реверсировать значения элементов контейнера или какого-нибудь его диапазона? Что вы делаете? Вызываете алгоритм std:;reverse. Но это, оказывается, можно сделать только для вектора, а для отображения сделать нельзя! Мои оппоненты на том сайте, на который я привел ссылку, утверждали, что эта задача не часто встречается. Но возникает резонный вопрос, а почему она должна встречаться менее часто для отображения, чем, например, для векторов7! Вы заметили разницу в коде заполнения элементов вектора и отображения? Нет? И я не заметил. А потому нет никаких оснований заявлять, что эта задача может встречаться реже для отображений, чем для векторов, и тем более нет оснований утверждать, что для отображений эта задача не имеет смысла. Почему не имеет смысла?! Почему нельзя поменять местами отображаемые значения?! На самом деле это можно делать, но только доморощенными методами.

Но самое итересное нас ждет впереди. Я заглянул в новый стандарт С++, и вот что там написано про контейнер std::map: "A map satisfies all of the requirements of a container, of a reversible container"
Я специально выделил словосочетание a reversible container. Очевидно, что контейнер, удовлетворяющий такому определению, просто обязан иметь средство реверсивного расположения значений элементов! То есть это означает, что если стандартный алгоритм std::reverse напрямую к нему не применим из-за особенностей возвращаемого значения итератора контейнера (а как я уже указал, разыменованный итератор возвращает не просто ссылку на значение, а ссылку на пару значений), то в контейнере ддолжен быть по крайней мере аналогичный алгоритм, реализованный в виде функции-члена класса.
Теперь еще один сюрприз. Интерфейс контейнера std::map в новом стандарте С++ 2011 еще более приближен к интерфейсу контейнера std::vector! Теперь в нем появилась функция- член класса at()
То есть следующий код

   c[0] = 'A'; 
    c[1] = 'B'; 
    //  заполняем другие элементы 
    c[25] = 'Z' 
    c.at( 0 ) = 'Z';

стал еще более неразличим для двух типов контейнеров. Я сам не скоро бы узнал об этом нововведении стандарта для контейнера std::map, если бы не исходный вопрос, которым я озадачился.

А раз интерфейс работы с этими двумя контейнерами настолько близок, то тем более выглядет обоснованным претензия того, что в std::map отсутствует алгоритм для размещения отображаемых значений в контейнере в обратном порядке.

На мой взгляд, это существенное упущение стандарта С++. Ценность стандартной библиотеки в том и заключается, что мы можем применять одни и те же алгоритмы для различных контейнеров, не задумываясь над тем, с каким типом контейнера работает алгоритм, и можем рассчитывать на гарантированный правильный результат.

В новом стандарте С++ 2010 сделали шаг вперед по унифицированию иинтерфейса контейнера sttd::map с контейнером std::vector, но требуется сделать еще один шаг - это ввести метод reverse в интерфейс класса std::map, или же ввнедрить форму стандартного алгоритма std::reverse с предикатом, чтобы можно было эту форму адаптировать для контейнера std::map