/usr/bin/../lib/gcc/x86_64-redhat-linux/10/../../../../include/c++/10/bits/predefined

Bug Summary

File:	usr/bin/../lib/gcc/x86_64-redhat-linux/10/../../../../include/c++/10/bits/predefined_ops.h
Warning:	line 43, column 23 The left operand of '<' is a garbage value

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

clang -cc1 -cc1 -triple x86_64-unknown-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name hashmgr.cxx -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 2 -mframe-pointer=all -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -fno-split-dwarf-inlining -debugger-tuning=gdb -resource-dir /usr/lib64/clang/11.0.0 -D HAVE_CONFIG_H -I . -I ../.. -D BUILDING_LIBHUNSPELL -D PIC -internal-isystem /usr/bin/../lib/gcc/x86_64-redhat-linux/10/../../../../include/c++/10 -internal-isystem /usr/bin/../lib/gcc/x86_64-redhat-linux/10/../../../../include/c++/10/x86_64-redhat-linux -internal-isystem /usr/bin/../lib/gcc/x86_64-redhat-linux/10/../../../../include/c++/10/backward -internal-isystem /usr/local/include -internal-isystem /usr/lib64/clang/11.0.0/include -internal-externc-isystem /include -internal-externc-isystem /usr/include -O0 -fdeprecated-macro -fdebug-compilation-dir /home/maarten/src/libreoffice/core/workdir/UnpackedTarball/hunspell/src/hunspell -ferror-limit 19 -fvisibility hidden -fgnuc-version=4.2.1 -fcxx-exceptions -fexceptions -debug-info-kind=constructor -analyzer-output=html -faddrsig -o /home/maarten/tmp/wis/scan-build-libreoffice/output/report/2020-10-07-141433-9725-1 -x c++ hashmgr.cxx

hashmgr.cxx

→

1/* ***** BEGIN LICENSE BLOCK *****
* Version: MPL 1.1/GPL 2.0/LGPL 2.1
*
* Copyright (C) 2002-2017 Németh László
*
* The contents of this file are subject to the Mozilla Public License Version
* 1.1 (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
* http://www.mozilla.org/MPL/
*
* Software distributed under the License is distributed on an "AS IS" basis,
* WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
* for the specific language governing rights and limitations under the
* License.
*
* Hunspell is based on MySpell which is Copyright (C) 2002 Kevin Hendricks.
*
* Contributor(s): David Einstein, Davide Prina, Giuseppe Modugno,
* Gianluca Turconi, Simon Brouwer, Noll János, Bíró Árpád,
* Goldman Eleonóra, Sarlós Tamás, Bencsáth Boldizsár, Halácsy Péter,
* Dvornik László, Gefferth András, Nagy Viktor, Varga Dániel, Chris Halls,
* Rene Engelhard, Bram Moolenaar, Dafydd Jones, Harri Pitkänen
*
* Alternatively, the contents of this file may be used under the terms of
* either the GNU General Public License Version 2 or later (the "GPL"), or
* the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
* in which case the provisions of the GPL or the LGPL are applicable instead
* of those above. If you wish to allow use of your version of this file only
* under the terms of either the GPL or the LGPL, and not to allow others to
* use your version of this file under the terms of the MPL, indicate your
* decision by deleting the provisions above and replace them with the notice
* and other provisions required by the GPL or the LGPL. If you do not delete
* the provisions above, a recipient may use your version of this file under
* the terms of any one of the MPL, the GPL or the LGPL.
*
* ***** END LICENSE BLOCK ***** */
37/*
* Copyright 2002 Kevin B. Hendricks, Stratford, Ontario, Canada
* And Contributors.  All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
*    notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
*    notice, this list of conditions and the following disclaimer in the
*    documentation and/or other materials provided with the distribution.
*
* 3. All modifications to the source code must be clearly marked as
*    such.  Binary redistributions based on modified source code
*    must be clearly marked as modified versions in the documentation
*    and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY KEVIN B. HENDRICKS AND CONTRIBUTORS
* ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
* FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL
* KEVIN B. HENDRICKS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
* BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*/

71#include <stdlib.h>
72#include <string.h>
73#include <stdio.h>
74#include <ctype.h>
75#include <limits>
76#include <sstream>

78#include "hashmgr.hxx"
79#include "csutil.hxx"
80#include "atypes.hxx"
81#include "langnum.hxx"

83// build a hash table from a munched word list

85HashMgr::HashMgr(const char* tpath, const char* apath, const char* key)
  : tablesize(0),
    tableptr(NULL__null),
    flag_mode(FLAG_CHAR),
    complexprefixes(0),
    utf8(0),
    forbiddenword(FORBIDDENWORD65510)  // forbidden word signing flag
    ,
    numaliasf(0),
    aliasf(NULL__null),
    aliasflen(0),
    numaliasm(0),
    aliasm(NULL__null) {
langnum = 0;
csconv = 0;
load_config(apath, key);
int ec = load_tables(tpath, key);
1
Calling 'HashMgr::load_tables'→
if (ec) {
  /* error condition - what should we do here */
  HUNSPELL_WARNING(stderrstderr, "Hash Manager Error : %d\n", ec);
  free(tableptr);
  //keep tablesize to 1 to fix possible division with zero
  tablesize = 1;
  tableptr = (struct hentry**)calloc(tablesize, sizeof(struct hentry*));
  if (!tableptr) {
    tablesize = 0;
  }
}
113}

115HashMgr::~HashMgr() {
if (tableptr) {
  // now pass through hash table freeing up everything
  // go through column by column of the table
  for (int i = 0; i < tablesize; i++) {
    struct hentry* pt = tableptr[i];
    struct hentry* nt = NULL__null;
    while (pt) {
      nt = pt->next;
      if (pt->astr &&
          (!aliasf || TESTAFF(pt->astr, ONLYUPCASEFLAG, pt->alen)(std::binary_search(pt->astr, pt->astr + pt->alen, 65511
))))
        free(pt->astr);
      free(pt);
      pt = nt;
    }
  }
  free(tableptr);
}
tablesize = 0;

if (aliasf) {
  for (int j = 0; j < (numaliasf); j++)
    free(aliasf[j]);
  free(aliasf);
  aliasf = NULL__null;
  if (aliasflen) {
    free(aliasflen);
    aliasflen = NULL__null;
  }
}
if (aliasm) {
  for (int j = 0; j < (numaliasm); j++)
    free(aliasm[j]);
  free(aliasm);
  aliasm = NULL__null;
}

152#ifndef OPENOFFICEORG
153#ifndef MOZILLA_CLIENT
if (utf8)
  free_utf_tbl();
156#endif
157#endif

159#ifdef MOZILLA_CLIENT
delete[] csconv;
161#endif
162}

164// lookup a root word in the hashtable

166struct hentry* HashMgr::lookup(const char* word) const {
struct hentry* dp;
if (tableptr) {
  dp = tableptr[hash(word)];
  if (!dp)
    return NULL__null;
  for (; dp != NULL__null; dp = dp->next) {
    if (strcmp(word, dp->word) == 0)
      return dp;
  }
}
return NULL__null;
178}

180// add a word to the hash table (private)
181int HashMgr::add_word(const std::string& in_word,
                    int wcl,
                    unsigned short* aff,
                    int al,
                    const std::string* in_desc,
                    bool onlyupcase,
                    int captype) {
const std::string* word = &in_word;
const std::string* desc = in_desc;

std::string *word_copy = NULL__null;
std::string *desc_copy = NULL__null;
if ((!ignorechars.empty() && !has_no_ignored_chars(in_word, ignorechars)) || complexprefixes) {
  word_copy = new std::string(in_word);

  if (!ignorechars.empty()) {
    if (utf8) {
      wcl = remove_ignored_chars_utf(*word_copy, ignorechars_utf16);
    } else {
      remove_ignored_chars(*word_copy, ignorechars);
    }
  }

  if (complexprefixes) {
    if (utf8)
      wcl = reverseword_utf(*word_copy);
    else
      reverseword(*word_copy);

    if (in_desc && !aliasm) {
      desc_copy = new std::string(*in_desc);

      if (complexprefixes) {
        if (utf8)
          reverseword_utf(*desc_copy);
        else
          reverseword(*desc_copy);
      }
      desc = desc_copy;
    }
  }

  word = word_copy;
}

bool upcasehomonym = false;
int descl = desc ? (aliasm ? sizeof(char*) : desc->size() + 1) : 0;
// variable-length hash record with word and optional fields
struct hentry* hp =
    (struct hentry*)malloc(sizeof(struct hentry) + word->size() + descl);
if (!hp) {
  delete desc_copy;
  delete word_copy;
  return 1;
}

char* hpw = hp->word;
strcpy(hpw, word->c_str());

int i = hash(hpw);

hp->blen = (unsigned char)word->size();
hp->clen = (unsigned char)wcl;
hp->alen = (short)al;
hp->astr = aff;
hp->next = NULL__null;
hp->next_homonym = NULL__null;
hp->var = (captype == INITCAP1) ? H_OPT_INITCAP(1 << 3) : 0;

// store the description string or its pointer
if (desc) {
  hp->var += H_OPT(1 << 0);
  if (aliasm) {
    hp->var += H_OPT_ALIASM(1 << 1);
    store_pointer(hpw + word->size() + 1, get_aliasm(atoi(desc->c_str())));
  } else {
    strcpy(hpw + word->size() + 1, desc->c_str());
  }
  if (strstr(HENTRY_DATA(hp), MORPH_PHON"ph:")) {
    hp->var += H_OPT_PHON(1 << 2);
    // store ph: fields (pronounciation, misspellings, old orthography etc.)
    // of a morphological description in reptable to use in REP replacements.
    if (reptable.capacity() < (unsigned int)(tablesize/MORPH_PHON_RATIO500))
        reptable.reserve(tablesize/MORPH_PHON_RATIO500);
    std::string fields = HENTRY_DATA(hp);
    std::string::const_iterator iter = fields.begin();
    std::string::const_iterator start_piece = mystrsep(fields, iter);
    while (start_piece != fields.end()) {
      if (std::string(start_piece, iter).find(MORPH_PHON"ph:") == 0) {
        std::string ph = std::string(start_piece, iter).substr(sizeof MORPH_PHON"ph:" - 1);
        if (ph.size() > 0) {
          std::vector<w_char> w;
          size_t strippatt;
          std::string wordpart;
          // dictionary based REP replacement, separated by "->"
          // for example "pretty ph:prity ph:priti->pretti" to handle
          // both prity -> pretty and pritier -> prettiest suggestions.
          if (((strippatt = ph.find("->")) != std::string::npos) &&
                  (strippatt > 0) && (strippatt < ph.size() - 2)) {
              wordpart = ph.substr(strippatt + 2);
              ph.erase(ph.begin() + strippatt, ph.end());
          } else
              wordpart = in_word;
          // when the ph: field ends with the character *,
          // strip last character of the pattern and the replacement
          // to match in REP suggestions also at character changes,
          // for example, "pretty ph:prity*" results "prit->prett"
          // REP replacement instead of "prity->pretty", to get
          // prity->pretty and pritiest->prettiest suggestions.
          if (ph.at(ph.size()-1) == '*') {
            strippatt = 1;
            size_t stripword = 0;
            if (utf8) {
              while ((strippatt < ph.size()) &&
                ((ph.at(ph.size()-strippatt-1) & 0xc0) == 0x80))
                   ++strippatt;
              while ((stripword < wordpart.size()) &&
                ((wordpart.at(wordpart.size()-stripword-1) & 0xc0) == 0x80))
                   ++stripword;
            }
            ++strippatt;
            ++stripword;
            if ((ph.size() > strippatt) && (wordpart.size() > stripword)) {
              ph.erase(ph.size()-strippatt, strippatt);
              wordpart.erase(in_word.size()-stripword, stripword);
            }
          }
          // capitalize lowercase pattern for capitalized words to support
          // good suggestions also for capitalized misspellings, eg.
          // Wednesday ph:wendsay
          // results wendsay -> Wednesday and Wendsay -> Wednesday, too.
          if (captype==INITCAP1) {
            std::string ph_capitalized;
            if (utf8) {
              u8_u16(w, ph);
              if (get_captype_utf8(w, langnum) == NOCAP0) {
                mkinitcap_utf(w, langnum);
                u16_u8(ph_capitalized, w);
              }
            } else if (get_captype(ph, csconv) == NOCAP0)
                mkinitcap(ph_capitalized, csconv);

            if (ph_capitalized.size() > 0) {
              // add also lowercase word in the case of German or
              // Hungarian to support lowercase suggestions lowercased by
              // compound word generation or derivational suffixes
              // (for example by adjectival suffix "-i" of geographical
              // names in Hungarian:
              // Massachusetts ph:messzecsuzec
              // messzecsuzeci -> massachusettsi (adjective)
              // For lowercasing by conditional PFX rules, see
              // tests/germancompounding test example or the
              // Hungarian dictionary.)
              if (langnum == LANG_de || langnum == LANG_hu) {
                std::string wordpart_lower(wordpart);
                if (utf8) {
                  u8_u16(w, wordpart_lower);
                  mkallsmall_utf(w, langnum);
                  u16_u8(wordpart_lower, w);
                } else {
                  mkallsmall(wordpart_lower, csconv);
                }
                reptable.push_back(replentry());
                reptable.back().pattern.assign(ph);
                reptable.back().outstrings[0].assign(wordpart_lower);
              }
              reptable.push_back(replentry());
              reptable.back().pattern.assign(ph_capitalized);
              reptable.back().outstrings[0].assign(wordpart);
            }
          }
          reptable.push_back(replentry());
          reptable.back().pattern.assign(ph);
          reptable.back().outstrings[0].assign(wordpart);
        }
      }
      start_piece = mystrsep(fields, iter);
    }
  }
}

struct hentry* dp = tableptr[i];
if (!dp) {
  tableptr[i] = hp;
  delete desc_copy;
  delete word_copy;
  return 0;
}
while (dp->next != NULL__null) {
  if ((!dp->next_homonym) && (strcmp(hp->word, dp->word) == 0)) {
    // remove hidden onlyupcase homonym
    if (!onlyupcase) {
      if ((dp->astr) && TESTAFF(dp->astr, ONLYUPCASEFLAG, dp->alen)(std::binary_search(dp->astr, dp->astr + dp->alen, 65511
))) {
        free(dp->astr);
        dp->astr = hp->astr;
        dp->alen = hp->alen;
        free(hp);
        delete desc_copy;
        delete word_copy;
        return 0;
      } else {
        dp->next_homonym = hp;
      }
    } else {
      upcasehomonym = true;
    }
  }
  dp = dp->next;
}
if (strcmp(hp->word, dp->word) == 0) {
  // remove hidden onlyupcase homonym
  if (!onlyupcase) {
    if ((dp->astr) && TESTAFF(dp->astr, ONLYUPCASEFLAG, dp->alen)(std::binary_search(dp->astr, dp->astr + dp->alen, 65511
))) {
      free(dp->astr);
      dp->astr = hp->astr;
      dp->alen = hp->alen;
      free(hp);
      delete desc_copy;
      delete word_copy;
      return 0;
    } else {
      dp->next_homonym = hp;
    }
  } else {
    upcasehomonym = true;
  }
}
if (!upcasehomonym) {
  dp->next = hp;
} else {
  // remove hidden onlyupcase homonym
  if (hp->astr)
    free(hp->astr);
  free(hp);
}

delete desc_copy;
delete word_copy;
return 0;
420}

422int HashMgr::add_hidden_capitalized_word(const std::string& word,
                                       int wcl,
                                       unsigned short* flags,
                                       int flagslen,
                                       const std::string* dp,
                                       int captype) {
if (flags == NULL__null)
  flagslen = 0;

// add inner capitalized forms to handle the following allcap forms:
// Mixed caps: OpenOffice.org -> OPENOFFICE.ORG
// Allcaps with suffixes: CIA's -> CIA'S
if (((captype == HUHCAP3) || (captype == HUHINITCAP4) ||
     ((captype == ALLCAP2) && (flagslen != 0))) &&
    !((flagslen != 0) && TESTAFF(flags, forbiddenword, flagslen)(std::binary_search(flags, flags + flagslen, forbiddenword)))) {
  unsigned short* flags2 =
      (unsigned short*)malloc(sizeof(unsigned short) * (flagslen + 1));
  if (!flags2)
    return 1;
  if (flagslen)
    memcpy(flags2, flags, flagslen * sizeof(unsigned short));
  flags2[flagslen] = ONLYUPCASEFLAG65511;
  if (utf8) {
    std::string st;
    std::vector<w_char> w;
    u8_u16(w, word);
    mkallsmall_utf(w, langnum);
    mkinitcap_utf(w, langnum);
    u16_u8(st, w);
    return add_word(st, wcl, flags2, flagslen + 1, dp, true, INITCAP1);
  } else {
    std::string new_word(word);
    mkallsmall(new_word, csconv);
    mkinitcap(new_word, csconv);
    int ret = add_word(new_word, wcl, flags2, flagslen + 1, dp, true, INITCAP1);
    return ret;
  }
}
return 0;
461}

463// detect captype and modify word length for UTF-8 encoding
464int HashMgr::get_clen_and_captype(const std::string& word, int* captype, std::vector<w_char> &workbuf) {
int len;
if (utf8) {
  len = u8_u16(workbuf, word);
  *captype = get_captype_utf8(workbuf, langnum);
} else {
  len = word.size();
  *captype = get_captype(word, csconv);
}
return len;
474}

476int HashMgr::get_clen_and_captype(const std::string& word, int* captype) {
std::vector<w_char> workbuf;
return get_clen_and_captype(word, captype, workbuf);
479}

481// remove word (personal dictionary function for standalone applications)
482int HashMgr::remove(const std::string& word) {
struct hentry* dp = lookup(word.c_str());
while (dp) {
  if (dp->alen == 0 || !TESTAFF(dp->astr, forbiddenword, dp->alen)(std::binary_search(dp->astr, dp->astr + dp->alen, forbiddenword
))) {
    unsigned short* flags =
        (unsigned short*)malloc(sizeof(unsigned short) * (dp->alen + 1));
    if (!flags)
      return 1;
    for (int i = 0; i < dp->alen; i++)
      flags[i] = dp->astr[i];
    flags[dp->alen] = forbiddenword;
    free(dp->astr);
    dp->astr = flags;
    dp->alen++;
    std::sort(flags, flags + dp->alen);
  }
  dp = dp->next_homonym;
}
return 0;
501}

503/* remove forbidden flag to add a personal word to the hash */
504int HashMgr::remove_forbidden_flag(const std::string& word) {
struct hentry* dp = lookup(word.c_str());
if (!dp)
  return 1;
while (dp) {
  if (dp->astr && TESTAFF(dp->astr, forbiddenword, dp->alen)(std::binary_search(dp->astr, dp->astr + dp->alen, forbiddenword
)))
    dp->alen = 0;  // XXX forbidden words of personal dic.
  dp = dp->next_homonym;
}
return 0;
514}

516// add a custom dic. word to the hash table (public)
517int HashMgr::add(const std::string& word) {
if (remove_forbidden_flag(word)) {
  int captype;
  int al = 0;
  unsigned short* flags = NULL__null;
  int wcl = get_clen_and_captype(word, &captype);
  add_word(word, wcl, flags, al, NULL__null, false, captype);
  return add_hidden_capitalized_word(word, wcl, flags, al, NULL__null,
                                     captype);
}
return 0;
528}

530int HashMgr::add_with_affix(const std::string& word, const std::string& example) {
// detect captype and modify word length for UTF-8 encoding
struct hentry* dp = lookup(example.c_str());
remove_forbidden_flag(word);
if (dp && dp->astr) {
  int captype;
  int wcl = get_clen_and_captype(word, &captype);
  if (aliasf) {
    add_word(word, wcl, dp->astr, dp->alen, NULL__null, false, captype);
  } else {
    unsigned short* flags =
        (unsigned short*)malloc(dp->alen * sizeof(unsigned short));
    if (flags) {
      memcpy((void*)flags, (void*)dp->astr,
             dp->alen * sizeof(unsigned short));
      add_word(word, wcl, flags, dp->alen, NULL__null, false, captype);
    } else
      return 1;
  }
  return add_hidden_capitalized_word(word, wcl, dp->astr,
                                     dp->alen, NULL__null, captype);
}
return 1;
553}

555// walk the hash table entry by entry - null at end
556// initialize: col=-1; hp = NULL; hp = walk_hashtable(&col, hp);
557struct hentry* HashMgr::walk_hashtable(int& col, struct hentry* hp) const {
if (hp && hp->next != NULL__null)
  return hp->next;
for (col++; col < tablesize; col++) {
  if (tableptr[col])
    return tableptr[col];
}
// null at end and reset to start
col = -1;
return NULL__null;
567}

569// load a munched word list and build a hash table on the fly
570int HashMgr::load_tables(const char* tpath, const char* key) {
// open dictionary file
FileMgr* dict = new FileMgr(tpath, key);
if (dict1.1
'dict' is not equal to NULL
1
'dict' is not equal to NULL
1
'dict' is not equal to NULL
 == NULL__null)
2
←
Taking false branch→
  return 1;

// first read the first line of file to get hash table size */
std::string ts;
if (!dict->getline(ts)) {
3
←
Assuming the condition is false→
4
←
Taking false branch→
  HUNSPELL_WARNING(stderrstderr, "error: empty dic file %s\n", tpath);
  delete dict;
  return 2;
}
mychomp(ts);

/* remove byte order mark */
if (ts.compare(0, 3, "\xEF\xBB\xBF", 3) == 0) {
5
←
Assuming the condition is false→
6
←
Taking false branch→
  ts.erase(0, 3);
}

tablesize = atoi(ts.c_str());

int nExtra = 5 + USERWORD1000;

if (tablesize <= 0 ||
7
←
Assuming field 'tablesize' is > 0→
9
←
Taking false branch→
    (tablesize >= (std::numeric_limits<int>::max() - 1 - nExtra) /
8
←
Assuming the condition is false→
                      int(sizeof(struct hentry*)))) {
  HUNSPELL_WARNING(
      stderrstderr, "error: line 1: missing or bad word count in the dic file\n");
  delete dict;
  return 4;
}
tablesize += nExtra;
if ((tablesize % 2) == 0)
10
←
Assuming the condition is false→
11
←
Taking false branch→
  tablesize++;

// allocate the hash table
tableptr = (struct hentry**)calloc(tablesize, sizeof(struct hentry*));
if (!tableptr) {
12
←
Assuming field 'tableptr' is non-null→
13
←
Taking false branch→
  delete dict;
  return 3;
}

// loop through all words on much list and add to hash
// table and create word and affix strings

std::vector<w_char> workbuf;

while (dict->getline(ts)) {
14
←
Loop condition is true.  Entering loop body→
  mychomp(ts);
  // split each line into word and morphological description
  size_t dp_pos = 0;
  while ((dp_pos = ts.find(':', dp_pos)) != std::string::npos) {
15
←
Assuming the condition is false→
16
←
Loop condition is false. Execution continues on line 637→
    if ((dp_pos > 3) && (ts[dp_pos - 3] == ' ' || ts[dp_pos - 3] == '\t')) {
      for (dp_pos -= 3; dp_pos > 0 && (ts[dp_pos-1] == ' ' || ts[dp_pos-1] == '\t'); --dp_pos)
        ;
      if (dp_pos == 0) {  // missing word
        dp_pos = std::string::npos;
      } else {
        ++dp_pos;
      }
      break;
    }
    ++dp_pos;
  }

  // tabulator is the old morphological field separator
  size_t dp2_pos = ts.find('\t');
  if (dp2_pos != std::string::npos && (dp_pos == std::string::npos || dp2_pos < dp_pos)) {
17
←
Assuming 'dp2_pos' is equal to 'npos'→
    dp_pos = dp2_pos + 1;
  }

  std::string dp;
  if (dp_pos17.1
'dp_pos' is equal to 'npos'
1
'dp_pos' is equal to 'npos'
1
'dp_pos' is equal to 'npos'
 != std::string::npos) {
18
←
Taking false branch→
    dp.assign(ts.substr(dp_pos));
    ts.resize(dp_pos - 1);
  }

  // split each line into word and affix char strings
  // "\/" signs slash in words (not affix separator)
  // "/" at beginning of the line is word character (not affix separator)
  size_t ap_pos = ts.find('/');
  while (ap_pos != std::string::npos) {
19
←
Assuming 'ap_pos' is not equal to 'npos'→
20
←
Loop condition is true.  Entering loop body→
    if (ap_pos == 0) {
21
←
Assuming 'ap_pos' is not equal to 0→
22
←
Taking false branch→
      ++ap_pos;
      continue;
    } else if (ts[ap_pos - 1] != '\\')
23
←
Assuming the condition is true→
24
←
Taking true branch→
      break;
25
←
 Execution continues on line 663→
    // replace "\/" with "/"
    ts.erase(ap_pos - 1, 1);
    ap_pos = ts.find('/', ap_pos);
  }

  unsigned short* flags;
  int al;
  if (ap_pos25.1
'ap_pos' is not equal to 'npos'
1
'ap_pos' is not equal to 'npos'
1
'ap_pos' is not equal to 'npos'
 != std::string::npos && ap_pos != ts.size()) {
26
←
Assuming the condition is true→
27
←
Taking true branch→
    std::string ap(ts.substr(ap_pos + 1));
    ts.resize(ap_pos);
    if (aliasf) {
28
←
Assuming field 'aliasf' is null→
29
←
Taking false branch→
      int index = atoi(ap.c_str());
      al = get_aliasf(index, &flags, dict);
      if (!al) {
        HUNSPELL_WARNING(stderrstderr, "error: line %d: bad flag vector alias\n",
                         dict->getlinenum());
      }
    } else {
      al = decode_flags(&flags, ap.c_str(), dict);
30
←
Calling 'HashMgr::decode_flags'→
39
←
Returning from 'HashMgr::decode_flags'→
      if (al == -1) {
40
←
Assuming the condition is false→
41
←
Taking false branch→
        HUNSPELL_WARNING(stderrstderr, "Can't allocate memory.\n");
        delete dict;
        return 6;
      }
      std::sort(flags, flags + al);
42
←
Calling 'sort<unsigned short *>'→
    }
  } else {
    al = 0;
    flags = NULL__null;
  }

  int captype;
  int wcl = get_clen_and_captype(ts, &captype, workbuf);
  const std::string *dp_str = dp.empty() ? NULL__null : &dp;
  // add the word and its index plus its capitalized form optionally
  if (add_word(ts, wcl, flags, al, dp_str, false, captype) ||
      add_hidden_capitalized_word(ts, wcl, flags, al, dp_str, captype)) {
    delete dict;
    return 5;
  }
}

delete dict;
return 0;
702}

704// the hash function is a simple load and rotate
705// algorithm borrowed
706int HashMgr::hash(const char* word) const {
unsigned long hv = 0;
for (int i = 0; i < 4 && *word != 0; i++)
  hv = (hv << 8) | (*word++);
while (*word != 0) {
  ROTATE(hv, ROTATE_LEN)(hv) = ((hv) << (5)) | (((hv) >> (32 - 5)) & (
(1 << (5)) - 1));;
  hv ^= (*word++);
}
return (unsigned long)hv % tablesize;
715}

717int HashMgr::decode_flags(unsigned short** result, const std::string& flags, FileMgr* af) const {
int len;
if (flags.empty()) {
31
←
Assuming the condition is false→
32
←
Taking false branch→
  *result = NULL__null;
  return 0;
}
switch (flag_mode) {
33
←
Control jumps to the 'default' case at line 788→
  case FLAG_LONG: {  // two-character flags (1x2yZz -> 1x 2y Zz)
    len = flags.size();
    if (len % 2 == 1)
      HUNSPELL_WARNING(stderrstderr, "error: line %d: bad flagvector\n",
                       af->getlinenum());
    len /= 2;
    *result = (unsigned short*)malloc(len * sizeof(unsigned short));
    if (!*result)
      return -1;
    for (int i = 0; i < len; i++) {
      (*result)[i] = ((unsigned short)((unsigned char)flags[i * 2]) << 8) +
                     (unsigned char)flags[i * 2 + 1];
    }
    break;
  }
  case FLAG_NUM: {  // decimal numbers separated by comma (4521,23,233 -> 4521
                    // 23 233)
    len = 1;
    unsigned short* dest;
    for (size_t i = 0; i < flags.size(); ++i) {
      if (flags[i] == ',')
        len++;
    }
    *result = (unsigned short*)malloc(len * sizeof(unsigned short));
    if (!*result)
      return -1;
    dest = *result;
    const char* src = flags.c_str();
    for (const char* p = src; *p; p++) {
      if (*p == ',') {
        int i = atoi(src);
        if (i >= DEFAULTFLAGS65510)
          HUNSPELL_WARNING(
              stderrstderr, "error: line %d: flag id %d is too large (max: %d)\n",
              af->getlinenum(), i, DEFAULTFLAGS65510 - 1);
        *dest = (unsigned short)i;
        if (*dest == 0)
          HUNSPELL_WARNING(stderrstderr, "error: line %d: 0 is wrong flag id\n",
                           af->getlinenum());
        src = p + 1;
        dest++;
      }
    }
    int i = atoi(src);
    if (i >= DEFAULTFLAGS65510)
      HUNSPELL_WARNING(stderrstderr,
                       "error: line %d: flag id %d is too large (max: %d)\n",
                       af->getlinenum(), i, DEFAULTFLAGS65510 - 1);
    *dest = (unsigned short)i;
    if (*dest == 0)
      HUNSPELL_WARNING(stderrstderr, "error: line %d: 0 is wrong flag id\n",
                       af->getlinenum());
    break;
  }
  case FLAG_UNI: {  // UTF-8 characters
    std::vector<w_char> w;
    u8_u16(w, flags);
    len = w.size();
    *result = (unsigned short*)malloc(len * sizeof(unsigned short));
    if (!*result)
      return -1;
    memcpy(*result, &w[0], len * sizeof(short));
    break;
  }
  default: {  // Ispell's one-character flags (erfg -> e r f g)
    unsigned short* dest;
    len = flags.size();
    *result = (unsigned short*)malloc(len * sizeof(unsigned short));
34
←
Storing uninitialized value→
    if (!*result)
35
←
Assuming the condition is false→
36
←
Taking false branch→
      return -1;
    dest = *result;
    for (size_t i = 0; i < flags.size(); ++i) {
37
←
Assuming the condition is false→
38
←
Loop condition is false. Execution continues on line 801→
      *dest = (unsigned char)flags[i];
      dest++;
    }
  }
}
return len;
802}

804bool HashMgr::decode_flags(std::vector<unsigned short>& result, const std::string& flags, FileMgr* af) const {
if (flags.empty()) {
  return false;
}
switch (flag_mode) {
  case FLAG_LONG: {  // two-character flags (1x2yZz -> 1x 2y Zz)
    size_t len = flags.size();
    if (len % 2 == 1)
      HUNSPELL_WARNING(stderrstderr, "error: line %d: bad flagvector\n",
                       af->getlinenum());
    len /= 2;
    result.reserve(result.size() + len);
    for (size_t i = 0; i < len; ++i) {
      result.push_back(((unsigned short)((unsigned char)flags[i * 2]) << 8) +
                       (unsigned char)flags[i * 2 + 1]);
    }
    break;
  }
  case FLAG_NUM: {  // decimal numbers separated by comma (4521,23,233 -> 4521
                    // 23 233)
    const char* src = flags.c_str();
    for (const char* p = src; *p; p++) {
      if (*p == ',') {
        int i = atoi(src);
        if (i >= DEFAULTFLAGS65510)
          HUNSPELL_WARNING(
              stderrstderr, "error: line %d: flag id %d is too large (max: %d)\n",
              af->getlinenum(), i, DEFAULTFLAGS65510 - 1);
        result.push_back((unsigned short)i);
        if (result.back() == 0)
          HUNSPELL_WARNING(stderrstderr, "error: line %d: 0 is wrong flag id\n",
                           af->getlinenum());
        src = p + 1;
      }
    }
    int i = atoi(src);
    if (i >= DEFAULTFLAGS65510)
      HUNSPELL_WARNING(stderrstderr,
                       "error: line %d: flag id %d is too large (max: %d)\n",
                       af->getlinenum(), i, DEFAULTFLAGS65510 - 1);
    result.push_back((unsigned short)i);
    if (result.back() == 0)
      HUNSPELL_WARNING(stderrstderr, "error: line %d: 0 is wrong flag id\n",
                       af->getlinenum());
    break;
  }
  case FLAG_UNI: {  // UTF-8 characters
    std::vector<w_char> w;
    u8_u16(w, flags);
    size_t len = w.size();
    size_t origsize = result.size();
    result.resize(origsize + len);
    memcpy(&result[origsize], &w[0], len * sizeof(short));
    break;
  }
  default: {  // Ispell's one-character flags (erfg -> e r f g)
    result.reserve(flags.size());
    for (size_t i = 0; i < flags.size(); ++i) {
      result.push_back((unsigned char)flags[i]);
    }
  }
}
return true;
867}

869unsigned short HashMgr::decode_flag(const char* f) const {
unsigned short s = 0;
int i;
switch (flag_mode) {
  case FLAG_LONG:
    s = ((unsigned short)((unsigned char)f[0]) << 8) + (unsigned char)f[1];
    break;
  case FLAG_NUM:
    i = atoi(f);
    if (i >= DEFAULTFLAGS65510)
      HUNSPELL_WARNING(stderrstderr, "error: flag id %d is too large (max: %d)\n",
                       i, DEFAULTFLAGS65510 - 1);
    s = (unsigned short)i;
    break;
  case FLAG_UNI: {
    std::vector<w_char> w;
    u8_u16(w, f);
    if (!w.empty())
        memcpy(&s, &w[0], 1 * sizeof(short));
    break;
  }
  default:
    s = *(unsigned char*)f;
}
if (s == 0)
  HUNSPELL_WARNING(stderrstderr, "error: 0 is wrong flag id\n");
return s;
896}

898char* HashMgr::encode_flag(unsigned short f) const {
if (f == 0)
  return mystrdup("(NULL)");
std::string ch;
if (flag_mode == FLAG_LONG) {
  ch.push_back((unsigned char)(f >> 8));
  ch.push_back((unsigned char)(f - ((f >> 8) << 8)));
} else if (flag_mode == FLAG_NUM) {
  std::ostringstream stream;
  stream << f;
  ch = stream.str();
} else if (flag_mode == FLAG_UNI) {
  const w_char* w_c = (const w_char*)&f;
  std::vector<w_char> w(w_c, w_c + 1);
  u16_u8(ch, w);
} else {
  ch.push_back((unsigned char)(f));
}
return mystrdup(ch.c_str());
917}

919// read in aff file and set flag mode
920int HashMgr::load_config(const char* affpath, const char* key) {
int firstline = 1;

// open the affix file
FileMgr* afflst = new FileMgr(affpath, key);
if (!afflst) {
  HUNSPELL_WARNING(
      stderrstderr, "Error - could not open affix description file %s\n", affpath);
  return 1;
}

// read in each line ignoring any that do not
// start with a known line type indicator

std::string line;
while (afflst->getline(line)) {
  mychomp(line);

  /* remove byte order mark */
  if (firstline) {
    firstline = 0;
    if (line.compare(0, 3, "\xEF\xBB\xBF", 3) == 0) {
      line.erase(0, 3);
    }
  }

  /* parse in the try string */
  if ((line.compare(0, 4, "FLAG", 4) == 0) && line.size() > 4 && isspace(line[4])) {
    if (flag_mode != FLAG_CHAR) {
      HUNSPELL_WARNING(stderrstderr,
                       "error: line %d: multiple definitions of the FLAG "
                       "affix file parameter\n",
                       afflst->getlinenum());
    }
    if (line.find("long") != std::string::npos)
      flag_mode = FLAG_LONG;
    if (line.find("num") != std::string::npos)
      flag_mode = FLAG_NUM;
    if (line.find("UTF-8") != std::string::npos)
      flag_mode = FLAG_UNI;
    if (flag_mode == FLAG_CHAR) {
      HUNSPELL_WARNING(
          stderrstderr,
          "error: line %d: FLAG needs `num', `long' or `UTF-8' parameter\n",
          afflst->getlinenum());
    }
  }

  if (line.compare(0, 13, "FORBIDDENWORD", 13) == 0) {
    std::string st;
    if (!parse_string(line, st, afflst->getlinenum())) {
      delete afflst;
      return 1;
    }
    forbiddenword = decode_flag(st.c_str());
  }

  if (line.compare(0, 3, "SET", 3) == 0) {
    if (!parse_string(line, enc, afflst->getlinenum())) {
      delete afflst;
      return 1;
    }
    if (enc == "UTF-8") {
      utf8 = 1;
984#ifndef OPENOFFICEORG
985#ifndef MOZILLA_CLIENT
      initialize_utf_tbl();
987#endif
988#endif
    } else
      csconv = get_current_cs(enc);
  }

  if (line.compare(0, 4, "LANG", 4) == 0) {
    if (!parse_string(line, lang, afflst->getlinenum())) {
      delete afflst;
      return 1;
    }
    langnum = get_lang_num(lang);
  }

  /* parse in the ignored characters (for example, Arabic optional diacritics
   * characters */
  if (line.compare(0, 6, "IGNORE", 6) == 0) {
    if (!parse_array(line, ignorechars, ignorechars_utf16,
                     utf8, afflst->getlinenum())) {
      delete afflst;
      return 1;
    }
  }

  if ((line.compare(0, 2, "AF", 2) == 0) && line.size() > 2 && isspace(line[2])) {
    if (!parse_aliasf(line, afflst)) {
      delete afflst;
      return 1;
    }
  }

  if ((line.compare(0, 2, "AM", 2) == 0) && line.size() > 2 && isspace(line[2])) {
    if (!parse_aliasm(line, afflst)) {
      delete afflst;
      return 1;
    }
  }

  if (line.compare(0, 15, "COMPLEXPREFIXES", 15) == 0)
    complexprefixes = 1;

  /* parse in the typical fault correcting table */
  if (line.compare(0, 3, "REP", 3) == 0) {
    if (!parse_reptable(line, afflst)) {
      delete afflst;
      return 1;
    }
  }

  // don't check the full affix file, yet
  if (((line.compare(0, 3, "SFX", 3) == 0) ||
       (line.compare(0, 3, "PFX", 3) == 0)) &&
          line.size() > 3 && isspace(line[3]) &&
          !reptable.empty()) // (REP table is in the end of Afrikaans aff file)
    break;
}

if (csconv == NULL__null)
  csconv = get_current_cs(SPELL_ENCODING"ISO8859-1");
delete afflst;
return 0;
1048}

1050/* parse in the ALIAS table */
1051bool HashMgr::parse_aliasf(const std::string& line, FileMgr* af) {
if (numaliasf != 0) {
  HUNSPELL_WARNING(stderrstderr, "error: line %d: multiple table definitions\n",
                   af->getlinenum());
  return false;
}
int i = 0;
int np = 0;
std::string::const_iterator iter = line.begin();
std::string::const_iterator start_piece = mystrsep(line, iter);
while (start_piece != line.end()) {
  switch (i) {
    case 0: {
      np++;
      break;
    }
    case 1: {
      numaliasf = atoi(std::string(start_piece, iter).c_str());
      if (numaliasf < 1) {
        numaliasf = 0;
        aliasf = NULL__null;
        aliasflen = NULL__null;
        HUNSPELL_WARNING(stderrstderr, "error: line %d: bad entry number\n",
                         af->getlinenum());
        return false;
      }
      aliasf =
          (unsigned short**)malloc(numaliasf * sizeof(unsigned short*));
      aliasflen =
          (unsigned short*)malloc(numaliasf * sizeof(unsigned short));
      if (!aliasf || !aliasflen) {
        numaliasf = 0;
        if (aliasf)
          free(aliasf);
        if (aliasflen)
          free(aliasflen);
        aliasf = NULL__null;
        aliasflen = NULL__null;
        return false;
      }
      np++;
      break;
    }
    default:
      break;
  }
  ++i;
  start_piece = mystrsep(line, iter);
}
if (np != 2) {
  numaliasf = 0;
  free(aliasf);
  free(aliasflen);
  aliasf = NULL__null;
  aliasflen = NULL__null;
  HUNSPELL_WARNING(stderrstderr, "error: line %d: missing data\n",
                   af->getlinenum());
  return false;
}

/* now parse the numaliasf lines to read in the remainder of the table */
for (int j = 0; j < numaliasf; j++) {
  std::string nl;
  if (!af->getline(nl))
    return false;
  mychomp(nl);
  i = 0;
  aliasf[j] = NULL__null;
  aliasflen[j] = 0;
  iter = nl.begin();
  start_piece = mystrsep(nl, iter);
  while (start_piece != nl.end()) {
    switch (i) {
      case 0: {
        if (nl.compare(start_piece - nl.begin(), 2, "AF", 2) != 0) {
          numaliasf = 0;
          free(aliasf);
          free(aliasflen);
          aliasf = NULL__null;
          aliasflen = NULL__null;
          HUNSPELL_WARNING(stderrstderr, "error: line %d: table is corrupt\n",
                           af->getlinenum());
          return false;
        }
        break;
      }
      case 1: {
        std::string piece(start_piece, iter);
        aliasflen[j] =
            (unsigned short)decode_flags(&(aliasf[j]), piece, af);
        std::sort(aliasf[j], aliasf[j] + aliasflen[j]);
        break;
      }
      default:
        break;
    }
    ++i;
    start_piece = mystrsep(nl, iter);
  }
  if (!aliasf[j]) {
    free(aliasf);
    free(aliasflen);
    aliasf = NULL__null;
    aliasflen = NULL__null;
    numaliasf = 0;
    HUNSPELL_WARNING(stderrstderr, "error: line %d: table is corrupt\n",
                     af->getlinenum());
    return false;
  }
}
return true;
1162}

1164int HashMgr::is_aliasf() const {
return (aliasf != NULL__null);
1166}

1168int HashMgr::get_aliasf(int index, unsigned short** fvec, FileMgr* af) const {
if ((index > 0) && (index <= numaliasf)) {
  *fvec = aliasf[index - 1];
  return aliasflen[index - 1];
}
HUNSPELL_WARNING(stderrstderr, "error: line %d: bad flag alias index: %d\n",
                 af->getlinenum(), index);
*fvec = NULL__null;
return 0;
1177}

1179/* parse morph alias definitions */
1180bool HashMgr::parse_aliasm(const std::string& line, FileMgr* af) {
if (numaliasm != 0) {
  HUNSPELL_WARNING(stderrstderr, "error: line %d: multiple table definitions\n",
                   af->getlinenum());
  return false;
}
int i = 0;
int np = 0;
std::string::const_iterator iter = line.begin();
std::string::const_iterator start_piece = mystrsep(line, iter);
while (start_piece != line.end()) {
  switch (i) {
    case 0: {
      np++;
      break;
    }
    case 1: {
      numaliasm = atoi(std::string(start_piece, iter).c_str());
      if (numaliasm < 1) {
        HUNSPELL_WARNING(stderrstderr, "error: line %d: bad entry number\n",
                         af->getlinenum());
        return false;
      }
      aliasm = (char**)malloc(numaliasm * sizeof(char*));
      if (!aliasm) {
        numaliasm = 0;
        return false;
      }
      np++;
      break;
    }
    default:
      break;
  }
  ++i;
  start_piece = mystrsep(line, iter);
}
if (np != 2) {
  numaliasm = 0;
  free(aliasm);
  aliasm = NULL__null;
  HUNSPELL_WARNING(stderrstderr, "error: line %d: missing data\n",
                   af->getlinenum());
  return false;
}

/* now parse the numaliasm lines to read in the remainder of the table */
for (int j = 0; j < numaliasm; j++) {
  std::string nl;
  if (!af->getline(nl))
    return false;
  mychomp(nl);
  aliasm[j] = NULL__null;
  iter = nl.begin();
  i = 0;
  start_piece = mystrsep(nl, iter);
  while (start_piece != nl.end()) {
    switch (i) {
      case 0: {
        if (nl.compare(start_piece - nl.begin(), 2, "AM", 2) != 0) {
          HUNSPELL_WARNING(stderrstderr, "error: line %d: table is corrupt\n",
                           af->getlinenum());
          numaliasm = 0;
          free(aliasm);
          aliasm = NULL__null;
          return false;
        }
        break;
      }
      case 1: {
        // add the remaining of the line
        std::string::const_iterator end = nl.end();
        std::string chunk(start_piece, end);
        if (complexprefixes) {
          if (utf8)
            reverseword_utf(chunk);
          else
            reverseword(chunk);
        }
        aliasm[j] = mystrdup(chunk.c_str());
        break;
      }
      default:
        break;
    }
    ++i;
    start_piece = mystrsep(nl, iter);
  }
  if (!aliasm[j]) {
    numaliasm = 0;
    free(aliasm);
    aliasm = NULL__null;
    HUNSPELL_WARNING(stderrstderr, "error: line %d: table is corrupt\n",
                     af->getlinenum());
    return false;
  }
}
return true;
1278}

1280int HashMgr::is_aliasm() const {
return (aliasm != NULL__null);
1282}

1284char* HashMgr::get_aliasm(int index) const {
if ((index > 0) && (index <= numaliasm))
  return aliasm[index - 1];
HUNSPELL_WARNING(stderrstderr, "error: bad morph. alias index: %d\n", index);
return NULL__null;
1289}

1291/* parse in the typical fault correcting table */
1292bool HashMgr::parse_reptable(const std::string& line, FileMgr* af) {
if (!reptable.empty()) {
  HUNSPELL_WARNING(stderrstderr, "error: line %d: multiple table definitions\n",
                   af->getlinenum());
  return false;
}
int numrep = -1;
int i = 0;
int np = 0;
std::string::const_iterator iter = line.begin();
std::string::const_iterator start_piece = mystrsep(line, iter);
while (start_piece != line.end()) {
  switch (i) {
    case 0: {
      np++;
      break;
    }
    case 1: {
      numrep = atoi(std::string(start_piece, iter).c_str());
      if (numrep < 1) {
        HUNSPELL_WARNING(stderrstderr, "error: line %d: incorrect entry number\n",
                         af->getlinenum());
        return false;
      }
      reptable.reserve(numrep);
      np++;
      break;
    }
    default:
      break;
  }
  ++i;
  start_piece = mystrsep(line, iter);
}
if (np != 2) {
  HUNSPELL_WARNING(stderrstderr, "error: line %d: missing data\n",
                   af->getlinenum());
  return false;
}

/* now parse the numrep lines to read in the remainder of the table */
for (int j = 0; j < numrep; ++j) {
  std::string nl;
  if (!af->getline(nl))
    return false;
  mychomp(nl);
  reptable.push_back(replentry());
  iter = nl.begin();
  i = 0;
  int type = 0;
  start_piece = mystrsep(nl, iter);
  while (start_piece != nl.end()) {
    switch (i) {
      case 0: {
        if (nl.compare(start_piece - nl.begin(), 3, "REP", 3) != 0) {
          HUNSPELL_WARNING(stderrstderr, "error: line %d: table is corrupt\n",
                           af->getlinenum());
          reptable.clear();
          return false;
        }
        break;
      }
      case 1: {
        if (*start_piece == '^')
          type = 1;
        reptable.back().pattern.assign(start_piece + type, iter);
        mystrrep(reptable.back().pattern, "_", " ");
        if (!reptable.back().pattern.empty() && reptable.back().pattern[reptable.back().pattern.size() - 1] == '$') {
          type += 2;
          reptable.back().pattern.resize(reptable.back().pattern.size() - 1);
        }
        break;
      }
      case 2: {
        reptable.back().outstrings[type].assign(start_piece, iter);
        mystrrep(reptable.back().outstrings[type], "_", " ");
        break;
      }
      default:
        break;
    }
    ++i;
    start_piece = mystrsep(nl, iter);
  }
  if (reptable.back().pattern.empty() || reptable.back().outstrings[type].empty()) {
    HUNSPELL_WARNING(stderrstderr, "error: line %d: table is corrupt\n",
                     af->getlinenum());
    reptable.clear();
    return false;
  }
}
return true;
1384}

1386// return replacing table
1387const std::vector<replentry>& HashMgr::get_reptable() const {
return reptable;
1389}

←

/usr/bin/../lib/gcc/x86_64-redhat-linux/10/../../../../include/c++/10/bits/stl_algo.h

→

1// Algorithm implementation -*- C++ -*-

3// Copyright (C) 2001-2020 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library.  This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.

11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14// GNU General Public License for more details.

16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.

20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23// <http://www.gnu.org/licenses/>.

25/*
*
* Copyright (c) 1994
* Hewlett-Packard Company
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation.  Hewlett-Packard Company makes no
* representations about the suitability of this software for any
* purpose.  It is provided "as is" without express or implied warranty.
*
*
* Copyright (c) 1996
* Silicon Graphics Computer Systems, Inc.
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation.  Silicon Graphics makes no
* representations about the suitability of this software for any
* purpose.  It is provided "as is" without express or implied warranty.
*/

51/** @file bits/stl_algo.h
*  This is an internal header file, included by other library headers.
*  Do not attempt to use it directly. @headername{algorithm}
*/

56#ifndef _STL_ALGO_H1
57#define _STL_ALGO_H1 1

59#include <cstdlib>	     // for rand
60#include <bits/algorithmfwd.h>
61#include <bits/stl_heap.h>
62#include <bits/stl_tempbuf.h>  // for _Temporary_buffer
63#include <bits/predefined_ops.h>

65#if __cplusplus201402L >= 201103L
66#include <bits/uniform_int_dist.h>
67#endif

69// See concept_check.h for the __glibcxx_*_requires macros.

71namespace std _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
72{
73_GLIBCXX_BEGIN_NAMESPACE_VERSION

/// Swaps the median value of *__a, *__b and *__c under __comp to *__result
template<typename _Iterator, typename _Compare>
  _GLIBCXX20_CONSTEXPR
  void
  __move_median_to_first(_Iterator __result,_Iterator __a, _Iterator __b,
	   _Iterator __c, _Compare __comp)
  {
    if (__comp(__a, __b))
53
←
Calling '_Iter_less_iter::operator()'→
{
 if (__comp(__b, __c))
   std::iter_swap(__result, __b);
 else if (__comp(__a, __c))
   std::iter_swap(__result, __c);
 else
   std::iter_swap(__result, __a);
}
    else if (__comp(__a, __c))
std::iter_swap(__result, __a);
    else if (__comp(__b, __c))
std::iter_swap(__result, __c);
    else
std::iter_swap(__result, __b);
  }

/// Provided for stable_partition to use.
template<typename _InputIterator, typename _Predicate>
  _GLIBCXX20_CONSTEXPR
  inline _InputIterator
  __find_if_not(_InputIterator __first, _InputIterator __last,
  _Predicate __pred)
  {
    return std::__find_if(__first, __last,
	    __gnu_cxx::__ops::__negate(__pred),
	    std::__iterator_category(__first));
  }

/// Like find_if_not(), but uses and updates a count of the
/// remaining range length instead of comparing against an end
/// iterator.
template<typename _InputIterator, typename _Predicate, typename _Distance>
  _GLIBCXX20_CONSTEXPR
  _InputIterator
  __find_if_not_n(_InputIterator __first, _Distance& __len, _Predicate __pred)
  {
    for (; __len; --__len,  (void) ++__first)
if (!__pred(__first))
 break;
    return __first;
  }

// set_difference
// set_intersection
// set_symmetric_difference
// set_union
// for_each
// find
// find_if
// find_first_of
// adjacent_find
// count
// count_if
// search

template<typename _ForwardIterator1, typename _ForwardIterator2,
  typename _BinaryPredicate>
  _GLIBCXX20_CONSTEXPR
  _ForwardIterator1
  __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
    _ForwardIterator2 __first2, _ForwardIterator2 __last2,
    _BinaryPredicate  __predicate)
  {
    // Test for empty ranges
    if (__first1 == __last1 || __first2 == __last2)
return __first1;

    // Test for a pattern of length 1.
    _ForwardIterator2 __p1(__first2);
    if (++__p1 == __last2)
return std::__find_if(__first1, __last1,
__gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));

    // General case.
    _ForwardIterator1 __current = __first1;

    for (;;)
{
 __first1 =
   std::__find_if(__first1, __last1,
__gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));

 if (__first1 == __last1)
   return __last1;

 _ForwardIterator2 __p = __p1;
 __current = __first1;
 if (++__current == __last1)
   return __last1;

 while (__predicate(__current, __p))
   {
     if (++__p == __last2)
return __first1;
     if (++__current == __last1)
return __last1;
   }
 ++__first1;
}
    return __first1;
  }

// search_n

/**
 *  This is an helper function for search_n overloaded for forward iterators.
*/
template<typename _ForwardIterator, typename _Integer,
  typename _UnaryPredicate>
  _GLIBCXX20_CONSTEXPR
  _ForwardIterator
  __search_n_aux(_ForwardIterator __first, _ForwardIterator __last,
   _Integer __count, _UnaryPredicate __unary_pred,
   std::forward_iterator_tag)
  {
    __first = std::__find_if(__first, __last, __unary_pred);
    while (__first != __last)
{
 typename iterator_traits<_ForwardIterator>::difference_type
   __n = __count;
 _ForwardIterator __i = __first;
 ++__i;
 while (__i != __last && __n != 1 && __unary_pred(__i))
   {
     ++__i;
     --__n;
   }
 if (__n == 1)
   return __first;
 if (__i == __last)
   return __last;
 __first = std::__find_if(++__i, __last, __unary_pred);
}
    return __last;
  }

/**
 *  This is an helper function for search_n overloaded for random access
 *  iterators.
*/
template<typename _RandomAccessIter, typename _Integer,
  typename _UnaryPredicate>
  _GLIBCXX20_CONSTEXPR
  _RandomAccessIter
  __search_n_aux(_RandomAccessIter __first, _RandomAccessIter __last,
   _Integer __count, _UnaryPredicate __unary_pred,
   std::random_access_iterator_tag)
  {
    typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
_DistanceType;

    _DistanceType __tailSize = __last - __first;
    _DistanceType __remainder = __count;

    while (__remainder <= __tailSize) // the main loop...
{
 __first += __remainder;
 __tailSize -= __remainder;
 // __first here is always pointing to one past the last element of
 // next possible match.
 _RandomAccessIter __backTrack = __first; 
 while (__unary_pred(--__backTrack))
   {
     if (--__remainder == 0)
return (__first - __count); // Success
   }
 __remainder = __count + 1 - (__first - __backTrack);
}
    return __last; // Failure
  }

template<typename _ForwardIterator, typename _Integer,
  typename _UnaryPredicate>
  _GLIBCXX20_CONSTEXPR
  _ForwardIterator
  __search_n(_ForwardIterator __first, _ForwardIterator __last,
      _Integer __count,
      _UnaryPredicate __unary_pred)
  {
    if (__count <= 0)
return __first;

    if (__count == 1)
return std::__find_if(__first, __last, __unary_pred);

    return std::__search_n_aux(__first, __last, __count, __unary_pred,
		 std::__iterator_category(__first));
  }

// find_end for forward iterators.
template<typename _ForwardIterator1, typename _ForwardIterator2,
  typename _BinaryPredicate>
  _GLIBCXX20_CONSTEXPR
  _ForwardIterator1
  __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
      _ForwardIterator2 __first2, _ForwardIterator2 __last2,
      forward_iterator_tag, forward_iterator_tag,
      _BinaryPredicate __comp)
  {
    if (__first2 == __last2)
return __last1;

    _ForwardIterator1 __result = __last1;
    while (1)
{
 _ForwardIterator1 __new_result
   = std::__search(__first1, __last1, __first2, __last2, __comp);
 if (__new_result == __last1)
   return __result;
 else
   {
     __result = __new_result;
     __first1 = __new_result;
     ++__first1;
   }
}
  }

// find_end for bidirectional iterators (much faster).
template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
  typename _BinaryPredicate>
  _GLIBCXX20_CONSTEXPR
  _BidirectionalIterator1
  __find_end(_BidirectionalIterator1 __first1,
      _BidirectionalIterator1 __last1,
      _BidirectionalIterator2 __first2,
      _BidirectionalIterator2 __last2,
      bidirectional_iterator_tag, bidirectional_iterator_tag,
      _BinaryPredicate __comp)
  {
    // concept requirements
    __glibcxx_function_requires(_BidirectionalIteratorConcept<
		  _BidirectionalIterator1>)
    __glibcxx_function_requires(_BidirectionalIteratorConcept<
		  _BidirectionalIterator2>)

    typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
    typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;

    _RevIterator1 __rlast1(__first1);
    _RevIterator2 __rlast2(__first2);
    _RevIterator1 __rresult = std::__search(_RevIterator1(__last1), __rlast1,
			      _RevIterator2(__last2), __rlast2,
			      __comp);

    if (__rresult == __rlast1)
return __last1;
    else
{
 _BidirectionalIterator1 __result = __rresult.base();
 std::advance(__result, -std::distance(__first2, __last2));
 return __result;
}
  }

/**
 *  @brief  Find last matching subsequence in a sequence.
 *  @ingroup non_mutating_algorithms
 *  @param  __first1  Start of range to search.
 *  @param  __last1   End of range to search.
 *  @param  __first2  Start of sequence to match.
 *  @param  __last2   End of sequence to match.
 *  @return   The last iterator @c i in the range
 *  @p [__first1,__last1-(__last2-__first2)) such that @c *(i+N) ==
 *  @p *(__first2+N) for each @c N in the range @p
 *  [0,__last2-__first2), or @p __last1 if no such iterator exists.
 *
 *  Searches the range @p [__first1,__last1) for a sub-sequence that
 *  compares equal value-by-value with the sequence given by @p
 *  [__first2,__last2) and returns an iterator to the __first
 *  element of the sub-sequence, or @p __last1 if the sub-sequence
 *  is not found.  The sub-sequence will be the last such
 *  subsequence contained in [__first1,__last1).
 *
 *  Because the sub-sequence must lie completely within the range @p
 *  [__first1,__last1) it must start at a position less than @p
 *  __last1-(__last2-__first2) where @p __last2-__first2 is the
 *  length of the sub-sequence.  This means that the returned
 *  iterator @c i will be in the range @p
 *  [__first1,__last1-(__last2-__first2))
*/
template<typename _ForwardIterator1, typename _ForwardIterator2>
  _GLIBCXX20_CONSTEXPR
  inline _ForwardIterator1
  find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
    _ForwardIterator2 __first2, _ForwardIterator2 __last2)
  {
    // concept requirements
    __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
    __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
    __glibcxx_function_requires(_EqualOpConcept<
   typename iterator_traits<_ForwardIterator1>::value_type,
   typename iterator_traits<_ForwardIterator2>::value_type>)
    __glibcxx_requires_valid_range(__first1, __last1);
    __glibcxx_requires_valid_range(__first2, __last2);

    return std::__find_end(__first1, __last1, __first2, __last2,
	     std::__iterator_category(__first1),
	     std::__iterator_category(__first2),
	     __gnu_cxx::__ops::__iter_equal_to_iter());
  }

/**
 *  @brief  Find last matching subsequence in a sequence using a predicate.
 *  @ingroup non_mutating_algorithms
 *  @param  __first1  Start of range to search.
 *  @param  __last1   End of range to search.
 *  @param  __first2  Start of sequence to match.
 *  @param  __last2   End of sequence to match.
 *  @param  __comp    The predicate to use.
 *  @return The last iterator @c i in the range @p
 *  [__first1,__last1-(__last2-__first2)) such that @c
 *  predicate(*(i+N), @p (__first2+N)) is true for each @c N in the
 *  range @p [0,__last2-__first2), or @p __last1 if no such iterator
 *  exists.
 *
 *  Searches the range @p [__first1,__last1) for a sub-sequence that
 *  compares equal value-by-value with the sequence given by @p
 *  [__first2,__last2) using comp as a predicate and returns an
 *  iterator to the first element of the sub-sequence, or @p __last1
 *  if the sub-sequence is not found.  The sub-sequence will be the
 *  last such subsequence contained in [__first,__last1).
 *
 *  Because the sub-sequence must lie completely within the range @p
 *  [__first1,__last1) it must start at a position less than @p
 *  __last1-(__last2-__first2) where @p __last2-__first2 is the
 *  length of the sub-sequence.  This means that the returned
 *  iterator @c i will be in the range @p
 *  [__first1,__last1-(__last2-__first2))
*/
template<typename _ForwardIterator1, typename _ForwardIterator2,
  typename _BinaryPredicate>
  _GLIBCXX20_CONSTEXPR
  inline _ForwardIterator1
  find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
    _ForwardIterator2 __first2, _ForwardIterator2 __last2,
    _BinaryPredicate __comp)
  {
    // concept requirements
    __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
    __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
   typename iterator_traits<_ForwardIterator1>::value_type,
   typename iterator_traits<_ForwardIterator2>::value_type>)
    __glibcxx_requires_valid_range(__first1, __last1);
    __glibcxx_requires_valid_range(__first2, __last2);

    return std::__find_end(__first1, __last1, __first2, __last2,
	     std::__iterator_category(__first1),
	     std::__iterator_category(__first2),
	     __gnu_cxx::__ops::__iter_comp_iter(__comp));
  }

436#if __cplusplus201402L >= 201103L
/**
 *  @brief  Checks that a predicate is true for all the elements
 *          of a sequence.
 *  @ingroup non_mutating_algorithms
 *  @param  __first   An input iterator.
 *  @param  __last    An input iterator.
 *  @param  __pred    A predicate.
 *  @return  True if the check is true, false otherwise.
 *
 *  Returns true if @p __pred is true for each element in the range
 *  @p [__first,__last), and false otherwise.
*/
template<typename _InputIterator, typename _Predicate>
  _GLIBCXX20_CONSTEXPR
  inline bool
  all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
  { return __last == std::find_if_not(__first, __last, __pred); }

/**
 *  @brief  Checks that a predicate is false for all the elements
 *          of a sequence.
 *  @ingroup non_mutating_algorithms
 *  @param  __first   An input iterator.
 *  @param  __last    An input iterator.
 *  @param  __pred    A predicate.
 *  @return  True if the check is true, false otherwise.
 *
 *  Returns true if @p __pred is false for each element in the range
 *  @p [__first,__last), and false otherwise.
*/
template<typename _InputIterator, typename _Predicate>
  _GLIBCXX20_CONSTEXPR
  inline bool
  none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
  { return __last == _GLIBCXX_STD_Astd::find_if(__first, __last, __pred); }

/**
 *  @brief  Checks that a predicate is false for at least an element
 *          of a sequence.
 *  @ingroup non_mutating_algorithms
 *  @param  __first   An input iterator.
 *  @param  __last    An input iterator.
 *  @param  __pred    A predicate.
 *  @return  True if the check is true, false otherwise.
 *
 *  Returns true if an element exists in the range @p
 *  [__first,__last) such that @p __pred is true, and false
 *  otherwise.
*/
template<typename _InputIterator, typename _Predicate>
  _GLIBCXX20_CONSTEXPR
  inline bool
  any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
  { return !std::none_of(__first, __last, __pred); }

/**
 *  @brief  Find the first element in a sequence for which a
 *          predicate is false.
 *  @ingroup non_mutating_algorithms
 *  @param  __first  An input iterator.
 *  @param  __last   An input iterator.
 *  @param  __pred   A predicate.
 *  @return   The first iterator @c i in the range @p [__first,__last)
 *  such that @p __pred(*i) is false, or @p __last if no such iterator exists.
*/
template<typename _InputIterator, typename _Predicate>
  _GLIBCXX20_CONSTEXPR
  inline _InputIterator
  find_if_not(_InputIterator __first, _InputIterator __last,
_Predicate __pred)
  {
    // concept requirements
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
    __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
     typename iterator_traits<_InputIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __last);
    return std::__find_if_not(__first, __last,
		__gnu_cxx::__ops::__pred_iter(__pred));
  }

/**
 *  @brief  Checks whether the sequence is partitioned.
 *  @ingroup mutating_algorithms
 *  @param  __first  An input iterator.
 *  @param  __last   An input iterator.
 *  @param  __pred   A predicate.
 *  @return  True if the range @p [__first,__last) is partioned by @p __pred,
 *  i.e. if all elements that satisfy @p __pred appear before those that
 *  do not.
*/
template<typename _InputIterator, typename _Predicate>
  _GLIBCXX20_CONSTEXPR
  inline bool
  is_partitioned(_InputIterator __first, _InputIterator __last,
   _Predicate __pred)
  {
    __first = std::find_if_not(__first, __last, __pred);
    if (__first == __last)
return true;
    ++__first;
    return std::none_of(__first, __last, __pred);
  }

/**
 *  @brief  Find the partition point of a partitioned range.
 *  @ingroup mutating_algorithms
 *  @param  __first   An iterator.
 *  @param  __last    Another iterator.
 *  @param  __pred    A predicate.
 *  @return  An iterator @p mid such that @p all_of(__first, mid, __pred)
 *           and @p none_of(mid, __last, __pred) are both true.
*/
template<typename _ForwardIterator, typename _Predicate>
  _GLIBCXX20_CONSTEXPR
  _ForwardIterator
  partition_point(_ForwardIterator __first, _ForwardIterator __last,
    _Predicate __pred)
  {
    // concept requirements
    __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
    __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
     typename iterator_traits<_ForwardIterator>::value_type>)

    // A specific debug-mode test will be necessary...
    __glibcxx_requires_valid_range(__first, __last);

    typedef typename iterator_traits<_ForwardIterator>::difference_type
_DistanceType;

    _DistanceType __len = std::distance(__first, __last);

    while (__len > 0)
{
 _DistanceType __half = __len >> 1;
 _ForwardIterator __middle = __first;
 std::advance(__middle, __half);
 if (__pred(*__middle))
   {
     __first = __middle;
     ++__first;
     __len = __len - __half - 1;
   }
 else
   __len = __half;
}
    return __first;
  }
584#endif

template<typename _InputIterator, typename _OutputIterator,
  typename _Predicate>
  _GLIBCXX20_CONSTEXPR
  _OutputIterator
  __remove_copy_if(_InputIterator __first, _InputIterator __last,
     _OutputIterator __result, _Predicate __pred)
  {
    for (; __first != __last; ++__first)
if (!__pred(__first))
 {
   *__result = *__first;
   ++__result;
 }
    return __result;
  }

/**
 *  @brief Copy a sequence, removing elements of a given value.
 *  @ingroup mutating_algorithms
 *  @param  __first   An input iterator.
 *  @param  __last    An input iterator.
 *  @param  __result  An output iterator.
 *  @param  __value   The value to be removed.
 *  @return   An iterator designating the end of the resulting sequence.
 *
 *  Copies each element in the range @p [__first,__last) not equal
 *  to @p __value to the range beginning at @p __result.
 *  remove_copy() is stable, so the relative order of elements that
 *  are copied is unchanged.
*/
template<typename _InputIterator, typename _OutputIterator, typename _Tp>
  _GLIBCXX20_CONSTEXPR
  inline _OutputIterator
  remove_copy(_InputIterator __first, _InputIterator __last,
_OutputIterator __result, const _Tp& __value)
  {
    // concept requirements
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
    __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
   typename iterator_traits<_InputIterator>::value_type>)
    __glibcxx_function_requires(_EqualOpConcept<
   typename iterator_traits<_InputIterator>::value_type, _Tp>)
    __glibcxx_requires_valid_range(__first, __last);

    return std::__remove_copy_if(__first, __last, __result,
__gnu_cxx::__ops::__iter_equals_val(__value));
  }

/**
 *  @brief Copy a sequence, removing elements for which a predicate is true.
 *  @ingroup mutating_algorithms
 *  @param  __first   An input iterator.
 *  @param  __last    An input iterator.
 *  @param  __result  An output iterator.
 *  @param  __pred    A predicate.
 *  @return   An iterator designating the end of the resulting sequence.
 *
 *  Copies each element in the range @p [__first,__last) for which
 *  @p __pred returns false to the range beginning at @p __result.
 *
 *  remove_copy_if() is stable, so the relative order of elements that are
 *  copied is unchanged.
*/
template<typename _InputIterator, typename _OutputIterator,
  typename _Predicate>
  _GLIBCXX20_CONSTEXPR
  inline _OutputIterator
  remove_copy_if(_InputIterator __first, _InputIterator __last,
   _OutputIterator __result, _Predicate __pred)
  {
    // concept requirements
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
    __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
   typename iterator_traits<_InputIterator>::value_type>)
    __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
   typename iterator_traits<_InputIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __last);

    return std::__remove_copy_if(__first, __last, __result,
		   __gnu_cxx::__ops::__pred_iter(__pred));
  }

668#if __cplusplus201402L >= 201103L
/**
 *  @brief Copy the elements of a sequence for which a predicate is true.
 *  @ingroup mutating_algorithms
 *  @param  __first   An input iterator.
 *  @param  __last    An input iterator.
 *  @param  __result  An output iterator.
 *  @param  __pred    A predicate.
 *  @return   An iterator designating the end of the resulting sequence.
 *
 *  Copies each element in the range @p [__first,__last) for which
 *  @p __pred returns true to the range beginning at @p __result.
 *
 *  copy_if() is stable, so the relative order of elements that are
 *  copied is unchanged.
*/
template<typename _InputIterator, typename _OutputIterator,
  typename _Predicate>
  _GLIBCXX20_CONSTEXPR
  _OutputIterator
  copy_if(_InputIterator __first, _InputIterator __last,
   _OutputIterator __result, _Predicate __pred)
  {
    // concept requirements
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
    __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
   typename iterator_traits<_InputIterator>::value_type>)
    __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
   typename iterator_traits<_InputIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __last);

    for (; __first != __last; ++__first)
if (__pred(*__first))
 {
   *__result = *__first;
   ++__result;
 }
    return __result;
  }

template<typename _InputIterator, typename _Size, typename _OutputIterator>
  _GLIBCXX20_CONSTEXPR
  _OutputIterator
  __copy_n_a(_InputIterator __first, _Size __n, _OutputIterator __result)
  {
    if (__n > 0)
{
 while (true)
   {
     *__result = *__first;
     ++__result;
     if (--__n > 0)
++__first;
     else
break;
   }
}
    return __result;
  }

template<typename _CharT, typename _Size>
  __enable_if_t<__is_char<_CharT>::__value, _CharT*>
  __copy_n_a(istreambuf_iterator<_CharT, char_traits<_CharT>>,
      _Size, _CharT*);

template<typename _InputIterator, typename _Size, typename _OutputIterator>
  _GLIBCXX20_CONSTEXPR
  _OutputIterator
  __copy_n(_InputIterator __first, _Size __n,
    _OutputIterator __result, input_iterator_tag)
  {
    return std::__niter_wrap(__result,
	       __copy_n_a(__first, __n,
			  std::__niter_base(__result)));
  }

template<typename _RandomAccessIterator, typename _Size,
  typename _OutputIterator>
  _GLIBCXX20_CONSTEXPR
  inline _OutputIterator
  __copy_n(_RandomAccessIterator __first, _Size __n,
    _OutputIterator __result, random_access_iterator_tag)
  { return std::copy(__first, __first + __n, __result); }

/**
 *  @brief Copies the range [first,first+n) into [result,result+n).
 *  @ingroup mutating_algorithms
 *  @param  __first  An input iterator.
 *  @param  __n      The number of elements to copy.
 *  @param  __result An output iterator.
 *  @return  result+n.
 *
 *  This inline function will boil down to a call to @c memmove whenever
 *  possible.  Failing that, if random access iterators are passed, then the
 *  loop count will be known (and therefore a candidate for compiler
 *  optimizations such as unrolling).
*/
template<typename _InputIterator, typename _Size, typename _OutputIterator>
  _GLIBCXX20_CONSTEXPR
  inline _OutputIterator
  copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
  {
    // concept requirements
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
    __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
   typename iterator_traits<_InputIterator>::value_type>)
    __glibcxx_requires_can_increment(__first, __n);
    __glibcxx_requires_can_increment(__result, __n);

    return std::__copy_n(__first, __n, __result,
	   std::__iterator_category(__first));
  }

/**
 *  @brief Copy the elements of a sequence to separate output sequences
 *         depending on the truth value of a predicate.
 *  @ingroup mutating_algorithms
 *  @param  __first   An input iterator.
 *  @param  __last    An input iterator.
 *  @param  __out_true   An output iterator.
 *  @param  __out_false  An output iterator.
 *  @param  __pred    A predicate.
 *  @return   A pair designating the ends of the resulting sequences.
 *
 *  Copies each element in the range @p [__first,__last) for which
 *  @p __pred returns true to the range beginning at @p out_true
 *  and each element for which @p __pred returns false to @p __out_false.
*/
template<typename _InputIterator, typename _OutputIterator1,
  typename _OutputIterator2, typename _Predicate>
  _GLIBCXX20_CONSTEXPR
  pair<_OutputIterator1, _OutputIterator2>
  partition_copy(_InputIterator __first, _InputIterator __last,
   _OutputIterator1 __out_true, _OutputIterator2 __out_false,
   _Predicate __pred)
  {
    // concept requirements
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
    __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1,
   typename iterator_traits<_InputIterator>::value_type>)
    __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2,
   typename iterator_traits<_InputIterator>::value_type>)
    __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
   typename iterator_traits<_InputIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __last);
    
    for (; __first != __last; ++__first)
if (__pred(*__first))
 {
   *__out_true = *__first;
   ++__out_true;
 }
else
 {
   *__out_false = *__first;
   ++__out_false;
 }

    return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
  }
828#endif // C++11

template<typename _ForwardIterator, typename _Predicate>
  _GLIBCXX20_CONSTEXPR
  _ForwardIterator
  __remove_if(_ForwardIterator __first, _ForwardIterator __last,
_Predicate __pred)
  {
    __first = std::__find_if(__first, __last, __pred);
    if (__first == __last)
return __first;
    _ForwardIterator __result = __first;
    ++__first;
    for (; __first != __last; ++__first)
if (!__pred(__first))
 {
   *__result = _GLIBCXX_MOVE(*__first)std::move(*__first);
   ++__result;
 }
    return __result;
  }

/**
 *  @brief Remove elements from a sequence.
 *  @ingroup mutating_algorithms
 *  @param  __first  An input iterator.
 *  @param  __last   An input iterator.
 *  @param  __value  The value to be removed.
 *  @return   An iterator designating the end of the resulting sequence.
 *
 *  All elements equal to @p __value are removed from the range
 *  @p [__first,__last).
 *
 *  remove() is stable, so the relative order of elements that are
 *  not removed is unchanged.
 *
 *  Elements between the end of the resulting sequence and @p __last
 *  are still present, but their value is unspecified.
*/
template<typename _ForwardIterator, typename _Tp>
  _GLIBCXX20_CONSTEXPR
  inline _ForwardIterator
  remove(_ForwardIterator __first, _ForwardIterator __last,
  const _Tp& __value)
  {
    // concept requirements
    __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
		  _ForwardIterator>)
    __glibcxx_function_requires(_EqualOpConcept<
   typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
    __glibcxx_requires_valid_range(__first, __last);

    return std::__remove_if(__first, __last,
__gnu_cxx::__ops::__iter_equals_val(__value));
  }

/**
 *  @brief Remove elements from a sequence using a predicate.
 *  @ingroup mutating_algorithms
 *  @param  __first  A forward iterator.
 *  @param  __last   A forward iterator.
 *  @param  __pred   A predicate.
 *  @return   An iterator designating the end of the resulting sequence.
 *
 *  All elements for which @p __pred returns true are removed from the range
 *  @p [__first,__last).
 *
 *  remove_if() is stable, so the relative order of elements that are
 *  not removed is unchanged.
 *
 *  Elements between the end of the resulting sequence and @p __last
 *  are still present, but their value is unspecified.
*/
template<typename _ForwardIterator, typename _Predicate>
  _GLIBCXX20_CONSTEXPR
  inline _ForwardIterator
  remove_if(_ForwardIterator __first, _ForwardIterator __last,
     _Predicate __pred)
  {
    // concept requirements
    __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
		  _ForwardIterator>)
    __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
   typename iterator_traits<_ForwardIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __last);

    return std::__remove_if(__first, __last,
	      __gnu_cxx::__ops::__pred_iter(__pred));
  }

template<typename _ForwardIterator, typename _BinaryPredicate>
  _GLIBCXX20_CONSTEXPR
  _ForwardIterator
  __adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
    _BinaryPredicate __binary_pred)
  {
    if (__first == __last)
return __last;
    _ForwardIterator __next = __first;
    while (++__next != __last)
{
 if (__binary_pred(__first, __next))
   return __first;
 __first = __next;
}
    return __last;
  }

template<typename _ForwardIterator, typename _BinaryPredicate>
  _GLIBCXX20_CONSTEXPR
  _ForwardIterator
  __unique(_ForwardIterator __first, _ForwardIterator __last,
    _BinaryPredicate __binary_pred)
  {
    // Skip the beginning, if already unique.
    __first = std::__adjacent_find(__first, __last, __binary_pred);
    if (__first == __last)
return __last;

    // Do the real copy work.
    _ForwardIterator __dest = __first;
    ++__first;
    while (++__first != __last)
if (!__binary_pred(__dest, __first))
 *++__dest = _GLIBCXX_MOVE(*__first)std::move(*__first);
    return ++__dest;
  }

/**
 *  @brief Remove consecutive duplicate values from a sequence.
 *  @ingroup mutating_algorithms
 *  @param  __first  A forward iterator.
 *  @param  __last   A forward iterator.
 *  @return  An iterator designating the end of the resulting sequence.
 *
 *  Removes all but the first element from each group of consecutive
 *  values that compare equal.
 *  unique() is stable, so the relative order of elements that are
 *  not removed is unchanged.
 *  Elements between the end of the resulting sequence and @p __last
 *  are still present, but their value is unspecified.
*/
template<typename _ForwardIterator>
  _GLIBCXX20_CONSTEXPR
  inline _ForwardIterator
  unique(_ForwardIterator __first, _ForwardIterator __last)
  {
    // concept requirements
    __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
		  _ForwardIterator>)
    __glibcxx_function_requires(_EqualityComparableConcept<
     typename iterator_traits<_ForwardIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __last);

    return std::__unique(__first, __last,
	   __gnu_cxx::__ops::__iter_equal_to_iter());
  }

/**
 *  @brief Remove consecutive values from a sequence using a predicate.
 *  @ingroup mutating_algorithms
 *  @param  __first        A forward iterator.
 *  @param  __last         A forward iterator.
 *  @param  __binary_pred  A binary predicate.
 *  @return  An iterator designating the end of the resulting sequence.
 *
 *  Removes all but the first element from each group of consecutive
 *  values for which @p __binary_pred returns true.
 *  unique() is stable, so the relative order of elements that are
 *  not removed is unchanged.
 *  Elements between the end of the resulting sequence and @p __last
 *  are still present, but their value is unspecified.
*/
template<typename _ForwardIterator, typename _BinaryPredicate>
  _GLIBCXX20_CONSTEXPR
  inline _ForwardIterator
  unique(_ForwardIterator __first, _ForwardIterator __last,
  _BinaryPredicate __binary_pred)
  {
    // concept requirements
    __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
		  _ForwardIterator>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
typename iterator_traits<_ForwardIterator>::value_type,
typename iterator_traits<_ForwardIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __last);

    return std::__unique(__first, __last,
	   __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
  }

/**
 *  This is an uglified
 *  unique_copy(_InputIterator, _InputIterator, _OutputIterator,
 *              _BinaryPredicate)
 *  overloaded for forward iterators and output iterator as result.
*/
template<typename _ForwardIterator, typename _OutputIterator,
  typename _BinaryPredicate>
  _GLIBCXX20_CONSTEXPR
  _OutputIterator
  __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
  _OutputIterator __result, _BinaryPredicate __binary_pred,
  forward_iterator_tag, output_iterator_tag)
  {
    // concept requirements -- iterators already checked
    __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
 typename iterator_traits<_ForwardIterator>::value_type,
 typename iterator_traits<_ForwardIterator>::value_type>)

    _ForwardIterator __next = __first;
    *__result = *__first;
    while (++__next != __last)
if (!__binary_pred(__first, __next))
 {
   __first = __next;
   *++__result = *__first;
 }
    return ++__result;
  }

/**
 *  This is an uglified
 *  unique_copy(_InputIterator, _InputIterator, _OutputIterator,
 *              _BinaryPredicate)
 *  overloaded for input iterators and output iterator as result.
*/
template<typename _InputIterator, typename _OutputIterator,
  typename _BinaryPredicate>
  _GLIBCXX20_CONSTEXPR
  _OutputIterator
  __unique_copy(_InputIterator __first, _InputIterator __last,
  _OutputIterator __result, _BinaryPredicate __binary_pred,
  input_iterator_tag, output_iterator_tag)
  {
    // concept requirements -- iterators already checked
    __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
 typename iterator_traits<_InputIterator>::value_type,
 typename iterator_traits<_InputIterator>::value_type>)

    typename iterator_traits<_InputIterator>::value_type __value = *__first;
    __decltype(__gnu_cxx::__ops::__iter_comp_val(__binary_pred))
__rebound_pred
= __gnu_cxx::__ops::__iter_comp_val(__binary_pred);
    *__result = __value;
    while (++__first != __last)
if (!__rebound_pred(__first, __value))
 {
   __value = *__first;
   *++__result = __value;
 }
    return ++__result;
  }

/**
 *  This is an uglified
 *  unique_copy(_InputIterator, _InputIterator, _OutputIterator,
 *              _BinaryPredicate)
 *  overloaded for input iterators and forward iterator as result.
*/
template<typename _InputIterator, typename _ForwardIterator,
  typename _BinaryPredicate>
  _GLIBCXX20_CONSTEXPR
  _ForwardIterator
  __unique_copy(_InputIterator __first, _InputIterator __last,
  _ForwardIterator __result, _BinaryPredicate __binary_pred,
  input_iterator_tag, forward_iterator_tag)
  {
    // concept requirements -- iterators already checked
    __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
 typename iterator_traits<_ForwardIterator>::value_type,
 typename iterator_traits<_InputIterator>::value_type>)
    *__result = *__first;
    while (++__first != __last)
if (!__binary_pred(__result, __first))
 *++__result = *__first;
    return ++__result;
  }

/**
 *  This is an uglified reverse(_BidirectionalIterator,
 *                              _BidirectionalIterator)
 *  overloaded for bidirectional iterators.
*/
template<typename _BidirectionalIterator>
  _GLIBCXX20_CONSTEXPR
  void
  __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
     bidirectional_iterator_tag)
  {
    while (true)
if (__first == __last || __first == --__last)
 return;
else
 {
   std::iter_swap(__first, __last);
   ++__first;
 }
  }

/**
 *  This is an uglified reverse(_BidirectionalIterator,
 *                              _BidirectionalIterator)
 *  overloaded for random access iterators.
*/
template<typename _RandomAccessIterator>
  _GLIBCXX20_CONSTEXPR
  void
  __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
     random_access_iterator_tag)
  {
    if (__first == __last)
return;
    --__last;
    while (__first < __last)
{
 std::iter_swap(__first, __last);
 ++__first;
 --__last;
}
  }

/**
 *  @brief Reverse a sequence.
 *  @ingroup mutating_algorithms
 *  @param  __first  A bidirectional iterator.
 *  @param  __last   A bidirectional iterator.
 *  @return   reverse() returns no value.
 *
 *  Reverses the order of the elements in the range @p [__first,__last),
 *  so that the first element becomes the last etc.
 *  For every @c i such that @p 0<=i<=(__last-__first)/2), @p reverse()
 *  swaps @p *(__first+i) and @p *(__last-(i+1))
*/
template<typename _BidirectionalIterator>
  _GLIBCXX20_CONSTEXPR
  inline void
  reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
  {
    // concept requirements
    __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
		  _BidirectionalIterator>)
    __glibcxx_requires_valid_range(__first, __last);
    std::__reverse(__first, __last, std::__iterator_category(__first));
  }

/**
 *  @brief Copy a sequence, reversing its elements.
 *  @ingroup mutating_algorithms
 *  @param  __first   A bidirectional iterator.
 *  @param  __last    A bidirectional iterator.
 *  @param  __result  An output iterator.
 *  @return  An iterator designating the end of the resulting sequence.
 *
 *  Copies the elements in the range @p [__first,__last) to the
 *  range @p [__result,__result+(__last-__first)) such that the
 *  order of the elements is reversed.  For every @c i such that @p
 *  0<=i<=(__last-__first), @p reverse_copy() performs the
 *  assignment @p *(__result+(__last-__first)-1-i) = *(__first+i).
 *  The ranges @p [__first,__last) and @p
 *  [__result,__result+(__last-__first)) must not overlap.
*/
template<typename _BidirectionalIterator, typename _OutputIterator>
  _GLIBCXX20_CONSTEXPR
  _OutputIterator
  reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
 _OutputIterator __result)
  {
    // concept requirements
    __glibcxx_function_requires(_BidirectionalIteratorConcept<
		  _BidirectionalIterator>)
    __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
typename iterator_traits<_BidirectionalIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __last);

    while (__first != __last)
{
 --__last;
 *__result = *__last;
 ++__result;
}
    return __result;
  }

/**
 *  This is a helper function for the rotate algorithm specialized on RAIs.
 *  It returns the greatest common divisor of two integer values.
*/
template<typename _EuclideanRingElement>
  _GLIBCXX20_CONSTEXPR
  _EuclideanRingElement
  __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
  {
    while (__n != 0)
{
 _EuclideanRingElement __t = __m % __n;
 __m = __n;
 __n = __t;
}
    return __m;
  }

inline namespace _V2
{

/// This is a helper function for the rotate algorithm.
template<typename _ForwardIterator>
  _GLIBCXX20_CONSTEXPR
  _ForwardIterator
  __rotate(_ForwardIterator __first,
    _ForwardIterator __middle,
    _ForwardIterator __last,
    forward_iterator_tag)
  {
    if (__first == __middle)
return __last;
    else if (__last == __middle)
return __first;

    _ForwardIterator __first2 = __middle;
    do
{
 std::iter_swap(__first, __first2);
 ++__first;
 ++__first2;
 if (__first == __middle)
   __middle = __first2;
}
    while (__first2 != __last);

    _ForwardIterator __ret = __first;

    __first2 = __middle;

    while (__first2 != __last)
{
 std::iter_swap(__first, __first2);
 ++__first;
 ++__first2;
 if (__first == __middle)
   __middle = __first2;
 else if (__first2 == __last)
   __first2 = __middle;
}
    return __ret;
  }

 /// This is a helper function for the rotate algorithm.
template<typename _BidirectionalIterator>
  _GLIBCXX20_CONSTEXPR
  _BidirectionalIterator
  __rotate(_BidirectionalIterator __first,
    _BidirectionalIterator __middle,
    _BidirectionalIterator __last,
     bidirectional_iterator_tag)
  {
    // concept requirements
    __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
		  _BidirectionalIterator>)

    if (__first == __middle)
return __last;
    else if (__last == __middle)
return __first;

    std::__reverse(__first,  __middle, bidirectional_iterator_tag());
    std::__reverse(__middle, __last,   bidirectional_iterator_tag());

    while (__first != __middle && __middle != __last)
{
 std::iter_swap(__first, --__last);
 ++__first;
}

    if (__first == __middle)
{
 std::__reverse(__middle, __last,   bidirectional_iterator_tag());
 return __last;
}
    else
{
 std::__reverse(__first,  __middle, bidirectional_iterator_tag());
 return __first;
}
  }

/// This is a helper function for the rotate algorithm.
template<typename _RandomAccessIterator>
  _GLIBCXX20_CONSTEXPR
  _RandomAccessIterator
  __rotate(_RandomAccessIterator __first,
    _RandomAccessIterator __middle,
    _RandomAccessIterator __last,
    random_access_iterator_tag)
  {
    // concept requirements
    __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
		  _RandomAccessIterator>)

    if (__first == __middle)
return __last;
    else if (__last == __middle)
return __first;

    typedef typename iterator_traits<_RandomAccessIterator>::difference_type
_Distance;
    typedef typename iterator_traits<_RandomAccessIterator>::value_type
_ValueType;

    _Distance __n = __last   - __first;
    _Distance __k = __middle - __first;

    if (__k == __n - __k)
{
 std::swap_ranges(__first, __middle, __middle);
 return __middle;
}

    _RandomAccessIterator __p = __first;
    _RandomAccessIterator __ret = __first + (__last - __middle);

    for (;;)
{
 if (__k < __n - __k)
   {
     if (__is_pod(_ValueType) && __k == 1)
{
  _ValueType __t = _GLIBCXX_MOVE(*__p)std::move(*__p);
  _GLIBCXX_MOVE3(__p + 1, __p + __n, __p)std::move(__p + 1, __p + __n, __p);
  *(__p + __n - 1) = _GLIBCXX_MOVE(__t)std::move(__t);
  return __ret;
}
     _RandomAccessIterator __q = __p + __k;
     for (_Distance __i = 0; __i < __n - __k; ++ __i)
{
  std::iter_swap(__p, __q);
  ++__p;
  ++__q;
}
     __n %= __k;
     if (__n == 0)
return __ret;
     std::swap(__n, __k);
     __k = __n - __k;
   }
 else
   {
     __k = __n - __k;
     if (__is_pod(_ValueType) && __k == 1)
{
  _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1))std::move(*(__p + __n - 1));
  _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n)std::move_backward(__p, __p + __n - 1, __p + __n);
  *__p = _GLIBCXX_MOVE(__t)std::move(__t);
  return __ret;
}
     _RandomAccessIterator __q = __p + __n;
     __p = __q - __k;
     for (_Distance __i = 0; __i < __n - __k; ++ __i)
{
  --__p;
  --__q;
  std::iter_swap(__p, __q);
}
     __n %= __k;
     if (__n == 0)
return __ret;
     std::swap(__n, __k);
   }
}
  }

 // _GLIBCXX_RESOLVE_LIB_DEFECTS
 // DR 488. rotate throws away useful information
/**
 *  @brief Rotate the elements of a sequence.
 *  @ingroup mutating_algorithms
 *  @param  __first   A forward iterator.
 *  @param  __middle  A forward iterator.
 *  @param  __last    A forward iterator.
 *  @return  first + (last - middle).
 *
 *  Rotates the elements of the range @p [__first,__last) by 
 *  @p (__middle - __first) positions so that the element at @p __middle
 *  is moved to @p __first, the element at @p __middle+1 is moved to
 *  @p __first+1 and so on for each element in the range
 *  @p [__first,__last).
 *
 *  This effectively swaps the ranges @p [__first,__middle) and
 *  @p [__middle,__last).
 *
 *  Performs
 *   @p *(__first+(n+(__last-__middle))%(__last-__first))=*(__first+n)
 *  for each @p n in the range @p [0,__last-__first).
*/
template<typename _ForwardIterator>
  _GLIBCXX20_CONSTEXPR
  inline _ForwardIterator
  rotate(_ForwardIterator __first, _ForwardIterator __middle,
  _ForwardIterator __last)
  {
    // concept requirements
    __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
		  _ForwardIterator>)
    __glibcxx_requires_valid_range(__first, __middle);
    __glibcxx_requires_valid_range(__middle, __last);

    return std::__rotate(__first, __middle, __last,
	   std::__iterator_category(__first));
  }

} // namespace _V2

/**
 *  @brief Copy a sequence, rotating its elements.
 *  @ingroup mutating_algorithms
 *  @param  __first   A forward iterator.
 *  @param  __middle  A forward iterator.
 *  @param  __last    A forward iterator.
 *  @param  __result  An output iterator.
 *  @return   An iterator designating the end of the resulting sequence.
 *
 *  Copies the elements of the range @p [__first,__last) to the
 *  range beginning at @result, rotating the copied elements by 
 *  @p (__middle-__first) positions so that the element at @p __middle
 *  is moved to @p __result, the element at @p __middle+1 is moved
 *  to @p __result+1 and so on for each element in the range @p
 *  [__first,__last).
 *
 *  Performs 
 *  @p *(__result+(n+(__last-__middle))%(__last-__first))=*(__first+n)
 *  for each @p n in the range @p [0,__last-__first).
*/
template<typename _ForwardIterator, typename _OutputIterator>
  _GLIBCXX20_CONSTEXPR
  inline _OutputIterator
  rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
_ForwardIterator __last, _OutputIterator __result)
  {
    // concept requirements
    __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
    __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
typename iterator_traits<_ForwardIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __middle);
    __glibcxx_requires_valid_range(__middle, __last);

    return std::copy(__first, __middle,
       std::copy(__middle, __last, __result));
  }

/// This is a helper function...
template<typename _ForwardIterator, typename _Predicate>
  _GLIBCXX20_CONSTEXPR
  _ForwardIterator
  __partition(_ForwardIterator __first, _ForwardIterator __last,
_Predicate __pred, forward_iterator_tag)
  {
    if (__first == __last)
return __first;

    while (__pred(*__first))
if (++__first == __last)
 return __first;

    _ForwardIterator __next = __first;

    while (++__next != __last)
if (__pred(*__next))
 {
   std::iter_swap(__first, __next);
   ++__first;
 }

    return __first;
  }

/// This is a helper function...
template<typename _BidirectionalIterator, typename _Predicate>
  _GLIBCXX20_CONSTEXPR
  _BidirectionalIterator
  __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
_Predicate __pred, bidirectional_iterator_tag)
  {
    while (true)
{
 while (true)
   if (__first == __last)
     return __first;
   else if (__pred(*__first))
     ++__first;
   else
     break;
 --__last;
 while (true)
   if (__first == __last)
     return __first;
   else if (!bool(__pred(*__last)))
     --__last;
   else
     break;
 std::iter_swap(__first, __last);
 ++__first;
}
  }

// partition

/// This is a helper function...
/// Requires __first != __last and !__pred(__first)
/// and __len == distance(__first, __last).
///
/// !__pred(__first) allows us to guarantee that we don't
/// move-assign an element onto itself.
template<typename _ForwardIterator, typename _Pointer, typename _Predicate,
  typename _Distance>
  _ForwardIterator
  __stable_partition_adaptive(_ForwardIterator __first,
		_ForwardIterator __last,
		_Predicate __pred, _Distance __len,
		_Pointer __buffer,
		_Distance __buffer_size)
  {
    if (__len == 1)
return __first;

    if (__len <= __buffer_size)
{
 _ForwardIterator __result1 = __first;
 _Pointer __result2 = __buffer;

 // The precondition guarantees that !__pred(__first), so
 // move that element to the buffer before starting the loop.
 // This ensures that we only call __pred once per element.
 *__result2 = _GLIBCXX_MOVE(*__first)std::move(*__first);
 ++__result2;
 ++__first;
 for (; __first != __last; ++__first)
   if (__pred(__first))
     {
*__result1 = _GLIBCXX_MOVE(*__first)std::move(*__first);
++__result1;
     }
   else
     {
*__result2 = _GLIBCXX_MOVE(*__first)std::move(*__first);
++__result2;
     }

 _GLIBCXX_MOVE3(__buffer, __result2, __result1)std::move(__buffer, __result2, __result1);
 return __result1;
}

    _ForwardIterator __middle = __first;
    std::advance(__middle, __len / 2);
    _ForwardIterator __left_split =
std::__stable_partition_adaptive(__first, __middle, __pred,
			 __len / 2, __buffer,
			 __buffer_size);

    // Advance past true-predicate values to satisfy this
    // function's preconditions.
    _Distance __right_len = __len - __len / 2;
    _ForwardIterator __right_split =
std::__find_if_not_n(__middle, __right_len, __pred);

    if (__right_len)
__right_split =
 std::__stable_partition_adaptive(__right_split, __last, __pred,
			   __right_len,
			   __buffer, __buffer_size);

    return std::rotate(__left_split, __middle, __right_split);
  }

template<typename _ForwardIterator, typename _Predicate>
  _ForwardIterator
  __stable_partition(_ForwardIterator __first, _ForwardIterator __last,
       _Predicate __pred)
  {
    __first = std::__find_if_not(__first, __last, __pred);

    if (__first == __last)
return __first;

    typedef typename iterator_traits<_ForwardIterator>::value_type
_ValueType;
    typedef typename iterator_traits<_ForwardIterator>::difference_type
_DistanceType;

    _Temporary_buffer<_ForwardIterator, _ValueType>
__buf(__first, std::distance(__first, __last));
    return
std::__stable_partition_adaptive(__first, __last, __pred,
			 _DistanceType(__buf.requested_size()),
			 __buf.begin(),
			 _DistanceType(__buf.size()));
  }

/**
 *  @brief Move elements for which a predicate is true to the beginning
 *         of a sequence, preserving relative ordering.
 *  @ingroup mutating_algorithms
 *  @param  __first   A forward iterator.
 *  @param  __last    A forward iterator.
 *  @param  __pred    A predicate functor.
 *  @return  An iterator @p middle such that @p __pred(i) is true for each
 *  iterator @p i in the range @p [first,middle) and false for each @p i
 *  in the range @p [middle,last).
 *
 *  Performs the same function as @p partition() with the additional
 *  guarantee that the relative ordering of elements in each group is
 *  preserved, so any two elements @p x and @p y in the range
 *  @p [__first,__last) such that @p __pred(x)==__pred(y) will have the same
 *  relative ordering after calling @p stable_partition().
*/
template<typename _ForwardIterator, typename _Predicate>
  inline _ForwardIterator
  stable_partition(_ForwardIterator __first, _ForwardIterator __last,
     _Predicate __pred)
  {
    // concept requirements
    __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
		  _ForwardIterator>)
    __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
   typename iterator_traits<_ForwardIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __last);

    return std::__stable_partition(__first, __last,
		     __gnu_cxx::__ops::__pred_iter(__pred));
  }

/// This is a helper function for the sort routines.
template<typename _RandomAccessIterator, typename _Compare>
  _GLIBCXX20_CONSTEXPR
  void
  __heap_select(_RandomAccessIterator __first,
  _RandomAccessIterator __middle,
  _RandomAccessIterator __last, _Compare __comp)
  {
    std::__make_heap(__first, __middle, __comp);
    for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
if (__comp(__i, __first))
 std::__pop_heap(__first, __middle, __i, __comp);
  }

// partial_sort

template<typename _InputIterator, typename _RandomAccessIterator,
  typename _Compare>
  _GLIBCXX20_CONSTEXPR
  _RandomAccessIterator
  __partial_sort_copy(_InputIterator __first, _InputIterator __last,
	_RandomAccessIterator __result_first,
	_RandomAccessIterator __result_last,
	_Compare __comp)
  {
    typedef typename iterator_traits<_InputIterator>::value_type
_InputValueType;
    typedef iterator_traits<_RandomAccessIterator> _RItTraits;
    typedef typename _RItTraits::difference_type _DistanceType;

    if (__result_first == __result_last)
return __result_last;
    _RandomAccessIterator __result_real_last = __result_first;
    while (__first != __last && __result_real_last != __result_last)
{
 *__result_real_last = *__first;
 ++__result_real_last;
 ++__first;
}
    
    std::__make_heap(__result_first, __result_real_last, __comp);
    while (__first != __last)
{
 if (__comp(__first, __result_first))
   std::__adjust_heap(__result_first, _DistanceType(0),
	       _DistanceType(__result_real_last
			     - __result_first),
	       _InputValueType(*__first), __comp);
 ++__first;
}
    std::__sort_heap(__result_first, __result_real_last, __comp);
    return __result_real_last;
  }

/**
 *  @brief Copy the smallest elements of a sequence.
 *  @ingroup sorting_algorithms
 *  @param  __first   An iterator.
 *  @param  __last    Another iterator.
 *  @param  __result_first   A random-access iterator.
 *  @param  __result_last    Another random-access iterator.
 *  @return   An iterator indicating the end of the resulting sequence.
 *
 *  Copies and sorts the smallest N values from the range @p [__first,__last)
 *  to the range beginning at @p __result_first, where the number of
 *  elements to be copied, @p N, is the smaller of @p (__last-__first) and
 *  @p (__result_last-__result_first).
 *  After the sort if @e i and @e j are iterators in the range
 *  @p [__result_first,__result_first+N) such that i precedes j then
 *  *j<*i is false.
 *  The value returned is @p __result_first+N.
*/
template<typename _InputIterator, typename _RandomAccessIterator>
  _GLIBCXX20_CONSTEXPR
  inline _RandomAccessIterator
  partial_sort_copy(_InputIterator __first, _InputIterator __last,
      _RandomAccessIterator __result_first,
      _RandomAccessIterator __result_last)
  {
1737#ifdef _GLIBCXX_CONCEPT_CHECKS
    typedef typename iterator_traits<_InputIterator>::value_type
_InputValueType;
    typedef typename iterator_traits<_RandomAccessIterator>::value_type
_OutputValueType;
1742#endif

    // concept requirements
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
    __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
		  _OutputValueType>)
    __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
				     _OutputValueType>)
    __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
    __glibcxx_requires_valid_range(__first, __last);
    __glibcxx_requires_irreflexive(__first, __last);
    __glibcxx_requires_valid_range(__result_first, __result_last);

    return std::__partial_sort_copy(__first, __last,
		      __result_first, __result_last,
		      __gnu_cxx::__ops::__iter_less_iter());
  }

/**
 *  @brief Copy the smallest elements of a sequence using a predicate for
 *         comparison.
 *  @ingroup sorting_algorithms
 *  @param  __first   An input iterator.
 *  @param  __last    Another input iterator.
 *  @param  __result_first   A random-access iterator.
 *  @param  __result_last    Another random-access iterator.
 *  @param  __comp    A comparison functor.
 *  @return   An iterator indicating the end of the resulting sequence.
 *
 *  Copies and sorts the smallest N values from the range @p [__first,__last)
 *  to the range beginning at @p result_first, where the number of
 *  elements to be copied, @p N, is the smaller of @p (__last-__first) and
 *  @p (__result_last-__result_first).
 *  After the sort if @e i and @e j are iterators in the range
 *  @p [__result_first,__result_first+N) such that i precedes j then
 *  @p __comp(*j,*i) is false.
 *  The value returned is @p __result_first+N.
*/
template<typename _InputIterator, typename _RandomAccessIterator,
  typename _Compare>
  _GLIBCXX20_CONSTEXPR
  inline _RandomAccessIterator
  partial_sort_copy(_InputIterator __first, _InputIterator __last,
      _RandomAccessIterator __result_first,
      _RandomAccessIterator __result_last,
      _Compare __comp)
  {
1789#ifdef _GLIBCXX_CONCEPT_CHECKS
    typedef typename iterator_traits<_InputIterator>::value_type
_InputValueType;
    typedef typename iterator_traits<_RandomAccessIterator>::value_type
_OutputValueType;
1794#endif

    // concept requirements
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
    __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
		  _RandomAccessIterator>)
    __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
		  _OutputValueType>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
		  _InputValueType, _OutputValueType>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
		  _OutputValueType, _OutputValueType>)
    __glibcxx_requires_valid_range(__first, __last);
    __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
    __glibcxx_requires_valid_range(__result_first, __result_last);

    return std::__partial_sort_copy(__first, __last,
		      __result_first, __result_last,
		__gnu_cxx::__ops::__iter_comp_iter(__comp));
  }

/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Compare>
  _GLIBCXX20_CONSTEXPR
  void
  __unguarded_linear_insert(_RandomAccessIterator __last,
	      _Compare __comp)
  {
    typename iterator_traits<_RandomAccessIterator>::value_type
__val = _GLIBCXX_MOVE(*__last)std::move(*__last);
    _RandomAccessIterator __next = __last;
    --__next;
    while (__comp(__val, __next))
{
 *__last = _GLIBCXX_MOVE(*__next)std::move(*__next);
 __last = __next;
 --__next;
}
    *__last = _GLIBCXX_MOVE(__val)std::move(__val);
  }

/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Compare>
  _GLIBCXX20_CONSTEXPR
  void
  __insertion_sort(_RandomAccessIterator __first,
     _RandomAccessIterator __last, _Compare __comp)
  {
    if (__first == __last) return;

    for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
{
 if (__comp(__i, __first))
   {
     typename iterator_traits<_RandomAccessIterator>::value_type
__val = _GLIBCXX_MOVE(*__i)std::move(*__i);
     _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1)std::move_backward(__first, __i, __i + 1);
     *__first = _GLIBCXX_MOVE(__val)std::move(__val);
   }
 else
   std::__unguarded_linear_insert(__i,
		__gnu_cxx::__ops::__val_comp_iter(__comp));
}
  }

/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Compare>
  _GLIBCXX20_CONSTEXPR
  inline void
  __unguarded_insertion_sort(_RandomAccessIterator __first,
	       _RandomAccessIterator __last, _Compare __comp)
  {
    for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
std::__unguarded_linear_insert(__i,
		__gnu_cxx::__ops::__val_comp_iter(__comp));
  }

/**
 *  @doctodo
 *  This controls some aspect of the sort routines.
*/
enum { _S_threshold = 16 };

/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Compare>
  _GLIBCXX20_CONSTEXPR
  void
  __final_insertion_sort(_RandomAccessIterator __first,
	   _RandomAccessIterator __last, _Compare __comp)
  {
    if (__last - __first > int(_S_threshold))
{
 std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
 std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
			  __comp);
}
    else
std::__insertion_sort(__first, __last, __comp);
  }

/// This is a helper function...
template<typename _RandomAccessIterator, typename _Compare>
  _GLIBCXX20_CONSTEXPR
  _RandomAccessIterator
  __unguarded_partition(_RandomAccessIterator __first,
	  _RandomAccessIterator __last,
	  _RandomAccessIterator __pivot, _Compare __comp)
  {
    while (true)
{
 while (__comp(__first, __pivot))
   ++__first;
 --__last;
 while (__comp(__pivot, __last))
   --__last;
 if (!(__first < __last))
   return __first;
 std::iter_swap(__first, __last);
 ++__first;
}
  }

/// This is a helper function...
template<typename _RandomAccessIterator, typename _Compare>
  _GLIBCXX20_CONSTEXPR
  inline _RandomAccessIterator
  __unguarded_partition_pivot(_RandomAccessIterator __first,
		_RandomAccessIterator __last, _Compare __comp)
  {
    _RandomAccessIterator __mid = __first + (__last - __first) / 2;
    std::__move_median_to_first(__first, __first + 1, __mid, __last - 1,
52
←
Calling '__move_median_to_first<unsigned short *, __gnu_cxx::__ops::_Iter_less_iter>'→
		  __comp);
    return std::__unguarded_partition(__first + 1, __last, __first, __comp);
  }

template<typename _RandomAccessIterator, typename _Compare>
  _GLIBCXX20_CONSTEXPR
  inline void
  __partial_sort(_RandomAccessIterator __first,
   _RandomAccessIterator __middle,
   _RandomAccessIterator __last,
   _Compare __comp)
  {
    std::__heap_select(__first, __middle, __last, __comp);
    std::__sort_heap(__first, __middle, __comp);
  }

/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Size, typename _Compare>
  _GLIBCXX20_CONSTEXPR
  void
  __introsort_loop(_RandomAccessIterator __first,
     _RandomAccessIterator __last,
     _Size __depth_limit, _Compare __comp)
  {
    while (__last - __first > int(_S_threshold))
47
←
Assuming the condition is true→
48
←
Loop condition is true.  Entering loop body→
{
 if (__depth_limit == 0)
49
←
Assuming '__depth_limit' is not equal to 0→
50
←
Taking false branch→
   {
     std::__partial_sort(__first, __last, __last, __comp);
     return;
   }
 --__depth_limit;
 _RandomAccessIterator __cut =
   std::__unguarded_partition_pivot(__first, __last, __comp);
51
←
Calling '__unguarded_partition_pivot<unsigned short *, __gnu_cxx::__ops::_Iter_less_iter>'→
 std::__introsort_loop(__cut, __last, __depth_limit, __comp);
 __last = __cut;
}
  }

// sort

template<typename _RandomAccessIterator, typename _Compare>
  _GLIBCXX20_CONSTEXPR
  inline void
  __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
  _Compare __comp)
  {
    if (__first != __last)
44
←
Assuming '__first' is not equal to '__last'→
45
←
Taking true branch→
{
 std::__introsort_loop(__first, __last,
46
←
Calling '__introsort_loop<unsigned short *, long, __gnu_cxx::__ops::_Iter_less_iter>'→
		std::__lg(__last - __first) * 2,
		__comp);
 std::__final_insertion_sort(__first, __last, __comp);
}
  }

template<typename _RandomAccessIterator, typename _Size, typename _Compare>
  _GLIBCXX20_CONSTEXPR
  void
  __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
  _RandomAccessIterator __last, _Size __depth_limit,
  _Compare __comp)
  {
    while (__last - __first > 3)
{
 if (__depth_limit == 0)
   {
     std::__heap_select(__first, __nth + 1, __last, __comp);
     // Place the nth largest element in its final position.
     std::iter_swap(__first, __nth);
     return;
   }
 --__depth_limit;
 _RandomAccessIterator __cut =
   std::__unguarded_partition_pivot(__first, __last, __comp);
 if (__cut <= __nth)
   __first = __cut;
 else
   __last = __cut;
}
    std::__insertion_sort(__first, __last, __comp);
  }

// nth_element

// lower_bound moved to stl_algobase.h

/**
 *  @brief Finds the first position in which @p __val could be inserted
 *         without changing the ordering.
 *  @ingroup binary_search_algorithms
 *  @param  __first   An iterator.
 *  @param  __last    Another iterator.
 *  @param  __val     The search term.
 *  @param  __comp    A functor to use for comparisons.
 *  @return An iterator pointing to the first element <em>not less
 *           than</em> @p __val, or end() if every element is less
 *           than @p __val.
 *  @ingroup binary_search_algorithms
 *
 *  The comparison function should have the same effects on ordering as
 *  the function used for the initial sort.
*/
template<typename _ForwardIterator, typename _Tp, typename _Compare>
  _GLIBCXX20_CONSTEXPR
  inline _ForwardIterator
  lower_bound(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __val, _Compare __comp)
  {
    // concept requirements
    __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
    __glibcxx_requires_partitioned_lower_pred(__first, __last,
				__val, __comp);

    return std::__lower_bound(__first, __last, __val,
		__gnu_cxx::__ops::__iter_comp_val(__comp));
  }

template<typename _ForwardIterator, typename _Tp, typename _Compare>
  _GLIBCXX20_CONSTEXPR
  _ForwardIterator
  __upper_bound(_ForwardIterator __first, _ForwardIterator __last,
  const _Tp& __val, _Compare __comp)
  {
    typedef typename iterator_traits<_ForwardIterator>::difference_type
_DistanceType;

    _DistanceType __len = std::distance(__first, __last);

    while (__len > 0)
{
 _DistanceType __half = __len >> 1;
 _ForwardIterator __middle = __first;
 std::advance(__middle, __half);
 if (__comp(__val, __middle))
   __len = __half;
 else
   {
     __first = __middle;
     ++__first;
     __len = __len - __half - 1;
   }
}
    return __first;
  }

/**
 *  @brief Finds the last position in which @p __val could be inserted
 *         without changing the ordering.
 *  @ingroup binary_search_algorithms
 *  @param  __first   An iterator.
 *  @param  __last    Another iterator.
 *  @param  __val     The search term.
 *  @return  An iterator pointing to the first element greater than @p __val,
 *           or end() if no elements are greater than @p __val.
 *  @ingroup binary_search_algorithms
*/
template<typename _ForwardIterator, typename _Tp>
  _GLIBCXX20_CONSTEXPR
  inline _ForwardIterator
  upper_bound(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __val)
  {
    // concept requirements
    __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
    __glibcxx_function_requires(_LessThanOpConcept<
_Tp, typename iterator_traits<_ForwardIterator>::value_type>)
    __glibcxx_requires_partitioned_upper(__first, __last, __val);

    return std::__upper_bound(__first, __last, __val,
		__gnu_cxx::__ops::__val_less_iter());
  }

/**
 *  @brief Finds the last position in which @p __val could be inserted
 *         without changing the ordering.
 *  @ingroup binary_search_algorithms
 *  @param  __first   An iterator.
 *  @param  __last    Another iterator.
 *  @param  __val     The search term.
 *  @param  __comp    A functor to use for comparisons.
 *  @return  An iterator pointing to the first element greater than @p __val,
 *           or end() if no elements are greater than @p __val.
 *  @ingroup binary_search_algorithms
 *
 *  The comparison function should have the same effects on ordering as
 *  the function used for the initial sort.
*/
template<typename _ForwardIterator, typename _Tp, typename _Compare>
  _GLIBCXX20_CONSTEXPR
  inline _ForwardIterator
  upper_bound(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __val, _Compare __comp)
  {
    // concept requirements
    __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
_Tp, typename iterator_traits<_ForwardIterator>::value_type>)
    __glibcxx_requires_partitioned_upper_pred(__first, __last,
				__val, __comp);

    return std::__upper_bound(__first, __last, __val,
		__gnu_cxx::__ops::__val_comp_iter(__comp));
  }

template<typename _ForwardIterator, typename _Tp,
  typename _CompareItTp, typename _CompareTpIt>
  _GLIBCXX20_CONSTEXPR
  pair<_ForwardIterator, _ForwardIterator>
  __equal_range(_ForwardIterator __first, _ForwardIterator __last,
  const _Tp& __val,
  _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it)
  {
    typedef typename iterator_traits<_ForwardIterator>::difference_type
_DistanceType;

    _DistanceType __len = std::distance(__first, __last);

    while (__len > 0)
{
 _DistanceType __half = __len >> 1;
 _ForwardIterator __middle = __first;
 std::advance(__middle, __half);
 if (__comp_it_val(__middle, __val))
   {
     __first = __middle;
     ++__first;
     __len = __len - __half - 1;
   }
 else if (__comp_val_it(__val, __middle))
   __len = __half;
 else
   {
     _ForwardIterator __left
= std::__lower_bound(__first, __middle, __val, __comp_it_val);
     std::advance(__first, __len);
     _ForwardIterator __right
= std::__upper_bound(++__middle, __first, __val, __comp_val_it);
     return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
   }
}
    return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
  }

/**
 *  @brief Finds the largest subrange in which @p __val could be inserted
 *         at any place in it without changing the ordering.
 *  @ingroup binary_search_algorithms
 *  @param  __first   An iterator.
 *  @param  __last    Another iterator.
 *  @param  __val     The search term.
 *  @return  An pair of iterators defining the subrange.
 *  @ingroup binary_search_algorithms
 *
 *  This is equivalent to
 *  @code
 *    std::make_pair(lower_bound(__first, __last, __val),
 *                   upper_bound(__first, __last, __val))
 *  @endcode
 *  but does not actually call those functions.
*/
template<typename _ForwardIterator, typename _Tp>
  _GLIBCXX20_CONSTEXPR
  inline pair<_ForwardIterator, _ForwardIterator>
  equal_range(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __val)
  {
    // concept requirements
    __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
    __glibcxx_function_requires(_LessThanOpConcept<
typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
    __glibcxx_function_requires(_LessThanOpConcept<
_Tp, typename iterator_traits<_ForwardIterator>::value_type>)
    __glibcxx_requires_partitioned_lower(__first, __last, __val);
    __glibcxx_requires_partitioned_upper(__first, __last, __val);

    return std::__equal_range(__first, __last, __val,
		__gnu_cxx::__ops::__iter_less_val(),
		__gnu_cxx::__ops::__val_less_iter());
  }

/**
 *  @brief Finds the largest subrange in which @p __val could be inserted
 *         at any place in it without changing the ordering.
 *  @param  __first   An iterator.
 *  @param  __last    Another iterator.
 *  @param  __val     The search term.
 *  @param  __comp    A functor to use for comparisons.
 *  @return  An pair of iterators defining the subrange.
 *  @ingroup binary_search_algorithms
 *
 *  This is equivalent to
 *  @code
 *    std::make_pair(lower_bound(__first, __last, __val, __comp),
 *                   upper_bound(__first, __last, __val, __comp))
 *  @endcode
 *  but does not actually call those functions.
*/
template<typename _ForwardIterator, typename _Tp, typename _Compare>
  _GLIBCXX20_CONSTEXPR
  inline pair<_ForwardIterator, _ForwardIterator>
  equal_range(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __val, _Compare __comp)
  {
    // concept requirements
    __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
_Tp, typename iterator_traits<_ForwardIterator>::value_type>)
    __glibcxx_requires_partitioned_lower_pred(__first, __last,
				__val, __comp);
    __glibcxx_requires_partitioned_upper_pred(__first, __last,
				__val, __comp);

    return std::__equal_range(__first, __last, __val,
		__gnu_cxx::__ops::__iter_comp_val(__comp),
		__gnu_cxx::__ops::__val_comp_iter(__comp));
  }

/**
 *  @brief Determines whether an element exists in a range.
 *  @ingroup binary_search_algorithms
 *  @param  __first   An iterator.
 *  @param  __last    Another iterator.
 *  @param  __val     The search term.
 *  @return True if @p __val (or its equivalent) is in [@p
 *  __first,@p __last ].
 *
 *  Note that this does not actually return an iterator to @p __val.  For
 *  that, use std::find or a container's specialized find member functions.
*/
template<typename _ForwardIterator, typename _Tp>
  _GLIBCXX20_CONSTEXPR
  bool
  binary_search(_ForwardIterator __first, _ForwardIterator __last,
  const _Tp& __val)
  {
    // concept requirements
    __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
    __glibcxx_function_requires(_LessThanOpConcept<
_Tp, typename iterator_traits<_ForwardIterator>::value_type>)
    __glibcxx_requires_partitioned_lower(__first, __last, __val);
    __glibcxx_requires_partitioned_upper(__first, __last, __val);

    _ForwardIterator __i
= std::__lower_bound(__first, __last, __val,
	     __gnu_cxx::__ops::__iter_less_val());
    return __i != __last && !(__val < *__i);
  }

/**
 *  @brief Determines whether an element exists in a range.
 *  @ingroup binary_search_algorithms
 *  @param  __first   An iterator.
 *  @param  __last    Another iterator.
 *  @param  __val     The search term.
 *  @param  __comp    A functor to use for comparisons.
 *  @return  True if @p __val (or its equivalent) is in @p [__first,__last].
 *
 *  Note that this does not actually return an iterator to @p __val.  For
 *  that, use std::find or a container's specialized find member functions.
 *
 *  The comparison function should have the same effects on ordering as
 *  the function used for the initial sort.
*/
template<typename _ForwardIterator, typename _Tp, typename _Compare>
  _GLIBCXX20_CONSTEXPR
  bool
  binary_search(_ForwardIterator __first, _ForwardIterator __last,
  const _Tp& __val, _Compare __comp)
  {
    // concept requirements
    __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
_Tp, typename iterator_traits<_ForwardIterator>::value_type>)
    __glibcxx_requires_partitioned_lower_pred(__first, __last,
				__val, __comp);
    __glibcxx_requires_partitioned_upper_pred(__first, __last,
				__val, __comp);

    _ForwardIterator __i
= std::__lower_bound(__first, __last, __val,
	     __gnu_cxx::__ops::__iter_comp_val(__comp));
    return __i != __last && !bool(__comp(__val, *__i));
  }

// merge

/// This is a helper function for the __merge_adaptive routines.
template<typename _InputIterator1, typename _InputIterator2,
  typename _OutputIterator, typename _Compare>
  void
  __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1,
	  _InputIterator2 __first2, _InputIterator2 __last2,
	  _OutputIterator __result, _Compare __comp)
  {
    while (__first1 != __last1 && __first2 != __last2)
{
 if (__comp(__first2, __first1))
   {
     *__result = _GLIBCXX_MOVE(*__first2)std::move(*__first2);
     ++__first2;
   }
 else
   {
     *__result = _GLIBCXX_MOVE(*__first1)std::move(*__first1);
     ++__first1;
   }
 ++__result;
}
    if (__first1 != __last1)
_GLIBCXX_MOVE3(__first1, __last1, __result)std::move(__first1, __last1, __result);
  }

/// This is a helper function for the __merge_adaptive routines.
template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
  typename _BidirectionalIterator3, typename _Compare>
  void
  __move_merge_adaptive_backward(_BidirectionalIterator1 __first1,
		   _BidirectionalIterator1 __last1,
		   _BidirectionalIterator2 __first2,
		   _BidirectionalIterator2 __last2,
		   _BidirectionalIterator3 __result,
		   _Compare __comp)
  {
    if (__first1 == __last1)
{
 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result)std::move_backward(__first2, __last2, __result);
 return;
}
    else if (__first2 == __last2)
return;

    --__last1;
    --__last2;
    while (true)
{
 if (__comp(__last2, __last1))
   {
     *--__result = _GLIBCXX_MOVE(*__last1)std::move(*__last1);
     if (__first1 == __last1)
{
  _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result)std::move_backward(__first2, ++__last2, __result);
  return;
}
     --__last1;
   }
 else
   {
     *--__result = _GLIBCXX_MOVE(*__last2)std::move(*__last2);
     if (__first2 == __last2)
return;
     --__last2;
   }
}
  }

/// This is a helper function for the merge routines.
template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
  typename _Distance>
  _BidirectionalIterator1
  __rotate_adaptive(_BidirectionalIterator1 __first,
      _BidirectionalIterator1 __middle,
      _BidirectionalIterator1 __last,
      _Distance __len1, _Distance __len2,
      _BidirectionalIterator2 __buffer,
      _Distance __buffer_size)
  {
    _BidirectionalIterator2 __buffer_end;
    if (__len1 > __len2 && __len2 <= __buffer_size)
{
 if (__len2)
   {
     __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer)std::move(__middle, __last, __buffer);
     _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last)std::move_backward(__first, __middle, __last);
     return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first)std::move(__buffer, __buffer_end, __first);
   }
 else
   return __first;
}
    else if (__len1 <= __buffer_size)
{
 if (__len1)
   {
     __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer)std::move(__first, __middle, __buffer);
     _GLIBCXX_MOVE3(__middle, __last, __first)std::move(__middle, __last, __first);
     return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last)std::move_backward(__buffer, __buffer_end, __last);
   }
 else
   return __last;
}
    else
return std::rotate(__first, __middle, __last);
  }

/// This is a helper function for the merge routines.
template<typename _BidirectionalIterator, typename _Distance, 
  typename _Pointer, typename _Compare>
  void
  __merge_adaptive(_BidirectionalIterator __first,
     _BidirectionalIterator __middle,
     _BidirectionalIterator __last,
     _Distance __len1, _Distance __len2,
     _Pointer __buffer, _Distance __buffer_size,
     _Compare __comp)
  {
    if (__len1 <= __len2 && __len1 <= __buffer_size)
{
 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer)std::move(__first, __middle, __buffer);
 std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last,
		     __first, __comp);
}
    else if (__len2 <= __buffer_size)
{
 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer)std::move(__middle, __last, __buffer);
 std::__move_merge_adaptive_backward(__first, __middle, __buffer,
			      __buffer_end, __last, __comp);
}
    else
{
 _BidirectionalIterator __first_cut = __first;
 _BidirectionalIterator __second_cut = __middle;
 _Distance __len11 = 0;
 _Distance __len22 = 0;
 if (__len1 > __len2)
   {
     __len11 = __len1 / 2;
     std::advance(__first_cut, __len11);
     __second_cut
= std::__lower_bound(__middle, __last, *__first_cut,
		     __gnu_cxx::__ops::__iter_comp_val(__comp));
     __len22 = std::distance(__middle, __second_cut);
   }
 else
   {
     __len22 = __len2 / 2;
     std::advance(__second_cut, __len22);
     __first_cut
= std::__upper_bound(__first, __middle, *__second_cut,
		     __gnu_cxx::__ops::__val_comp_iter(__comp));
     __len11 = std::distance(__first, __first_cut);
   }

 _BidirectionalIterator __new_middle
   = std::__rotate_adaptive(__first_cut, __middle, __second_cut,
		     __len1 - __len11, __len22, __buffer,
		     __buffer_size);
 std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
		__len22, __buffer, __buffer_size, __comp);
 std::__merge_adaptive(__new_middle, __second_cut, __last,
		__len1 - __len11,
		__len2 - __len22, __buffer,
		__buffer_size, __comp);
}
  }

/// This is a helper function for the merge routines.
template<typename _BidirectionalIterator, typename _Distance,
  typename _Compare>
  void
  __merge_without_buffer(_BidirectionalIterator __first,
	   _BidirectionalIterator __middle,
	   _BidirectionalIterator __last,
	   _Distance __len1, _Distance __len2,
	   _Compare __comp)
  {
    if (__len1 == 0 || __len2 == 0)
return;

    if (__len1 + __len2 == 2)
{
 if (__comp(__middle, __first))
   std::iter_swap(__first, __middle);
 return;
}

    _BidirectionalIterator __first_cut = __first;
    _BidirectionalIterator __second_cut = __middle;
    _Distance __len11 = 0;
    _Distance __len22 = 0;
    if (__len1 > __len2)
{
 __len11 = __len1 / 2;
 std::advance(__first_cut, __len11);
 __second_cut
   = std::__lower_bound(__middle, __last, *__first_cut,
		 __gnu_cxx::__ops::__iter_comp_val(__comp));
 __len22 = std::distance(__middle, __second_cut);
}
    else
{
 __len22 = __len2 / 2;
 std::advance(__second_cut, __len22);
 __first_cut
   = std::__upper_bound(__first, __middle, *__second_cut,
		 __gnu_cxx::__ops::__val_comp_iter(__comp));
 __len11 = std::distance(__first, __first_cut);
}

    _BidirectionalIterator __new_middle
= std::rotate(__first_cut, __middle, __second_cut);
    std::__merge_without_buffer(__first, __first_cut, __new_middle,
		  __len11, __len22, __comp);
    std::__merge_without_buffer(__new_middle, __second_cut, __last,
		  __len1 - __len11, __len2 - __len22, __comp);
  }

template<typename _BidirectionalIterator, typename _Compare>
  void
  __inplace_merge(_BidirectionalIterator __first,
    _BidirectionalIterator __middle,
    _BidirectionalIterator __last,
    _Compare __comp)
  {
    typedef typename iterator_traits<_BidirectionalIterator>::value_type
 _ValueType;
    typedef typename iterator_traits<_BidirectionalIterator>::difference_type
 _DistanceType;

    if (__first == __middle || __middle == __last)
return;

    const _DistanceType __len1 = std::distance(__first, __middle);
    const _DistanceType __len2 = std::distance(__middle, __last);

    typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
    _TmpBuf __buf(__first, __len1 + __len2);

    if (__buf.begin() == 0)
std::__merge_without_buffer
 (__first, __middle, __last, __len1, __len2, __comp);
    else
std::__merge_adaptive
 (__first, __middle, __last, __len1, __len2, __buf.begin(),
  _DistanceType(__buf.size()), __comp);
  }

/**
 *  @brief Merges two sorted ranges in place.
 *  @ingroup sorting_algorithms
 *  @param  __first   An iterator.
 *  @param  __middle  Another iterator.
 *  @param  __last    Another iterator.
 *  @return  Nothing.
 *
 *  Merges two sorted and consecutive ranges, [__first,__middle) and
 *  [__middle,__last), and puts the result in [__first,__last).  The
 *  output will be sorted.  The sort is @e stable, that is, for
 *  equivalent elements in the two ranges, elements from the first
 *  range will always come before elements from the second.
 *
 *  If enough additional memory is available, this takes (__last-__first)-1
 *  comparisons.  Otherwise an NlogN algorithm is used, where N is
 *  distance(__first,__last).
*/
template<typename _BidirectionalIterator>
  inline void
  inplace_merge(_BidirectionalIterator __first,
  _BidirectionalIterator __middle,
  _BidirectionalIterator __last)
  {
    // concept requirements
    __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
   _BidirectionalIterator>)
    __glibcxx_function_requires(_LessThanComparableConcept<
   typename iterator_traits<_BidirectionalIterator>::value_type>)
    __glibcxx_requires_sorted(__first, __middle);
    __glibcxx_requires_sorted(__middle, __last);
    __glibcxx_requires_irreflexive(__first, __last);

    std::__inplace_merge(__first, __middle, __last,
	   __gnu_cxx::__ops::__iter_less_iter());
  }

/**
 *  @brief Merges two sorted ranges in place.
 *  @ingroup sorting_algorithms
 *  @param  __first   An iterator.
 *  @param  __middle  Another iterator.
 *  @param  __last    Another iterator.
 *  @param  __comp    A functor to use for comparisons.
 *  @return  Nothing.
 *
 *  Merges two sorted and consecutive ranges, [__first,__middle) and
 *  [middle,last), and puts the result in [__first,__last).  The output will
 *  be sorted.  The sort is @e stable, that is, for equivalent
 *  elements in the two ranges, elements from the first range will always
 *  come before elements from the second.
 *
 *  If enough additional memory is available, this takes (__last-__first)-1
 *  comparisons.  Otherwise an NlogN algorithm is used, where N is
 *  distance(__first,__last).
 *
 *  The comparison function should have the same effects on ordering as
 *  the function used for the initial sort.
*/
template<typename _BidirectionalIterator, typename _Compare>
  inline void
  inplace_merge(_BidirectionalIterator __first,
  _BidirectionalIterator __middle,
  _BidirectionalIterator __last,
  _Compare __comp)
  {
    // concept requirements
    __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
   _BidirectionalIterator>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
   typename iterator_traits<_BidirectionalIterator>::value_type,
   typename iterator_traits<_BidirectionalIterator>::value_type>)
    __glibcxx_requires_sorted_pred(__first, __middle, __comp);
    __glibcxx_requires_sorted_pred(__middle, __last, __comp);
    __glibcxx_requires_irreflexive_pred(__first, __last, __comp);

    std::__inplace_merge(__first, __middle, __last,
	   __gnu_cxx::__ops::__iter_comp_iter(__comp));
  }


/// This is a helper function for the __merge_sort_loop routines.
template<typename _InputIterator, typename _OutputIterator,
  typename _Compare>
  _OutputIterator
  __move_merge(_InputIterator __first1, _InputIterator __last1,
 _InputIterator __first2, _InputIterator __last2,
 _OutputIterator __result, _Compare __comp)
  {
    while (__first1 != __last1 && __first2 != __last2)
{
 if (__comp(__first2, __first1))
   {
     *__result = _GLIBCXX_MOVE(*__first2)std::move(*__first2);
     ++__first2;
   }
 else
   {
     *__result = _GLIBCXX_MOVE(*__first1)std::move(*__first1);
     ++__first1;
   }
 ++__result;
}
    return _GLIBCXX_MOVE3(__first2, __last2,std::move(__first2, __last2, std::move(__first1, __last1, __result
))
	    _GLIBCXX_MOVE3(__first1, __last1,std::move(__first2, __last2, std::move(__first1, __last1, __result
))
			   __result))std::move(__first2, __last2, std::move(__first1, __last1, __result
));
  }

template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
  typename _Distance, typename _Compare>
  void
  __merge_sort_loop(_RandomAccessIterator1 __first,
      _RandomAccessIterator1 __last,
      _RandomAccessIterator2 __result, _Distance __step_size,
      _Compare __comp)
  {
    const _Distance __two_step = 2 * __step_size;

    while (__last - __first >= __two_step)
{
 __result = std::__move_merge(__first, __first + __step_size,
		       __first + __step_size,
		       __first + __two_step,
		       __result, __comp);
 __first += __two_step;
}
    __step_size = std::min(_Distance(__last - __first), __step_size);

    std::__move_merge(__first, __first + __step_size,
	__first + __step_size, __last, __result, __comp);
  }

template<typename _RandomAccessIterator, typename _Distance,
  typename _Compare>
  _GLIBCXX20_CONSTEXPR
  void
  __chunk_insertion_sort(_RandomAccessIterator __first,
	   _RandomAccessIterator __last,
	   _Distance __chunk_size, _Compare __comp)
  {
    while (__last - __first >= __chunk_size)
{
 std::__insertion_sort(__first, __first + __chunk_size, __comp);
 __first += __chunk_size;
}
    std::__insertion_sort(__first, __last, __comp);
  }

enum { _S_chunk_size = 7 };

template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
  void
  __merge_sort_with_buffer(_RandomAccessIterator __first,
	     _RandomAccessIterator __last,
	     _Pointer __buffer, _Compare __comp)
  {
    typedef typename iterator_traits<_RandomAccessIterator>::difference_type
_Distance;

    const _Distance __len = __last - __first;
    const _Pointer __buffer_last = __buffer + __len;

    _Distance __step_size = _S_chunk_size;
    std::__chunk_insertion_sort(__first, __last, __step_size, __comp);

    while (__step_size < __len)
{
 std::__merge_sort_loop(__first, __last, __buffer,
		 __step_size, __comp);
 __step_size *= 2;
 std::__merge_sort_loop(__buffer, __buffer_last, __first,
		 __step_size, __comp);
 __step_size *= 2;
}
  }

template<typename _RandomAccessIterator, typename _Pointer,
  typename _Distance, typename _Compare>
  void
  __stable_sort_adaptive(_RandomAccessIterator __first,
	   _RandomAccessIterator __last,
	   _Pointer __buffer, _Distance __buffer_size,
	   _Compare __comp)
  {
    const _Distance __len = (__last - __first + 1) / 2;
    const _RandomAccessIterator __middle = __first + __len;
    if (__len > __buffer_size)
{
 std::__stable_sort_adaptive(__first, __middle, __buffer,
		      __buffer_size, __comp);
 std::__stable_sort_adaptive(__middle, __last, __buffer,
		      __buffer_size, __comp);
}
    else
{
 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
}
    std::__merge_adaptive(__first, __middle, __last,
	    _Distance(__middle - __first),
	    _Distance(__last - __middle),
	    __buffer, __buffer_size,
	    __comp);
  }

/// This is a helper function for the stable sorting routines.
template<typename _RandomAccessIterator, typename _Compare>
  void
  __inplace_stable_sort(_RandomAccessIterator __first,
	  _RandomAccessIterator __last, _Compare __comp)
  {
    if (__last - __first < 15)
{
 std::__insertion_sort(__first, __last, __comp);
 return;
}
    _RandomAccessIterator __middle = __first + (__last - __first) / 2;
    std::__inplace_stable_sort(__first, __middle, __comp);
    std::__inplace_stable_sort(__middle, __last, __comp);
    std::__merge_without_buffer(__first, __middle, __last,
		  __middle - __first,
		  __last - __middle,
		  __comp);
  }

// stable_sort

// Set algorithms: includes, set_union, set_intersection, set_difference,
// set_symmetric_difference.  All of these algorithms have the precondition
// that their input ranges are sorted and the postcondition that their output
// ranges are sorted.

template<typename _InputIterator1, typename _InputIterator2,
  typename _Compare>
  _GLIBCXX20_CONSTEXPR
  bool
  __includes(_InputIterator1 __first1, _InputIterator1 __last1,
      _InputIterator2 __first2, _InputIterator2 __last2,
      _Compare __comp)
  {
    while (__first1 != __last1 && __first2 != __last2)
if (__comp(__first2, __first1))
 return false;
else if (__comp(__first1, __first2))
 ++__first1;
else
 {
   ++__first1;
   ++__first2;
 }

    return __first2 == __last2;
  }

/**
 *  @brief Determines whether all elements of a sequence exists in a range.
 *  @param  __first1  Start of search range.
 *  @param  __last1   End of search range.
 *  @param  __first2  Start of sequence
 *  @param  __last2   End of sequence.
 *  @return  True if each element in [__first2,__last2) is contained in order
 *  within [__first1,__last1).  False otherwise.
 *  @ingroup set_algorithms
 *
 *  This operation expects both [__first1,__last1) and
 *  [__first2,__last2) to be sorted.  Searches for the presence of
 *  each element in [__first2,__last2) within [__first1,__last1).
 *  The iterators over each range only move forward, so this is a
 *  linear algorithm.  If an element in [__first2,__last2) is not
 *  found before the search iterator reaches @p __last2, false is
 *  returned.
*/
template<typename _InputIterator1, typename _InputIterator2>
  _GLIBCXX20_CONSTEXPR
  inline bool
  includes(_InputIterator1 __first1, _InputIterator1 __last1,
    _InputIterator2 __first2, _InputIterator2 __last2)
  {
    // concept requirements
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
    __glibcxx_function_requires(_LessThanOpConcept<
   typename iterator_traits<_InputIterator1>::value_type,
   typename iterator_traits<_InputIterator2>::value_type>)
    __glibcxx_function_requires(_LessThanOpConcept<
   typename iterator_traits<_InputIterator2>::value_type,
   typename iterator_traits<_InputIterator1>::value_type>)
    __glibcxx_requires_sorted_set(__first1, __last1, __first2);
    __glibcxx_requires_sorted_set(__first2, __last2, __first1);
    __glibcxx_requires_irreflexive2(__first1, __last1);
    __glibcxx_requires_irreflexive2(__first2, __last2);

    return std::__includes(__first1, __last1, __first2, __last2,
	     __gnu_cxx::__ops::__iter_less_iter());
  }

/**
 *  @brief Determines whether all elements of a sequence exists in a range
 *  using comparison.
 *  @ingroup set_algorithms
 *  @param  __first1  Start of search range.
 *  @param  __last1   End of search range.
 *  @param  __first2  Start of sequence
 *  @param  __last2   End of sequence.
 *  @param  __comp    Comparison function to use.
 *  @return True if each element in [__first2,__last2) is contained
 *  in order within [__first1,__last1) according to comp.  False
 *  otherwise.  @ingroup set_algorithms
 *
 *  This operation expects both [__first1,__last1) and
 *  [__first2,__last2) to be sorted.  Searches for the presence of
 *  each element in [__first2,__last2) within [__first1,__last1),
 *  using comp to decide.  The iterators over each range only move
 *  forward, so this is a linear algorithm.  If an element in
 *  [__first2,__last2) is not found before the search iterator
 *  reaches @p __last2, false is returned.
*/
template<typename _InputIterator1, typename _InputIterator2,
  typename _Compare>
  _GLIBCXX20_CONSTEXPR
  inline bool
  includes(_InputIterator1 __first1, _InputIterator1 __last1,
    _InputIterator2 __first2, _InputIterator2 __last2,
    _Compare __comp)
  {
    // concept requirements
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
   typename iterator_traits<_InputIterator1>::value_type,
   typename iterator_traits<_InputIterator2>::value_type>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
   typename iterator_traits<_InputIterator2>::value_type,
   typename iterator_traits<_InputIterator1>::value_type>)
    __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
    __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
    __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
    __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);

    return std::__includes(__first1, __last1, __first2, __last2,
	     __gnu_cxx::__ops::__iter_comp_iter(__comp));
  }

// nth_element
// merge
// set_difference
// set_intersection
// set_union
// stable_sort
// set_symmetric_difference
// min_element
// max_element

template<typename _BidirectionalIterator, typename _Compare>
  _GLIBCXX20_CONSTEXPR
  bool
  __next_permutation(_BidirectionalIterator __first,
       _BidirectionalIterator __last, _Compare __comp)
  {
    if (__first == __last)
return false;
    _BidirectionalIterator __i = __first;
    ++__i;
    if (__i == __last)
return false;
    __i = __last;
    --__i;

    for(;;)
{
 _BidirectionalIterator __ii = __i;
 --__i;
 if (__comp(__i, __ii))
   {
     _BidirectionalIterator __j = __last;
     while (!__comp(__i, --__j))
{}
     std::iter_swap(__i, __j);
     std::__reverse(__ii, __last,
	     std::__iterator_category(__first));
     return true;
   }
 if (__i == __first)
   {
     std::__reverse(__first, __last,
	     std::__iterator_category(__first));
     return false;
   }
}
  }

/**
 *  @brief  Permute range into the next @e dictionary ordering.
 *  @ingroup sorting_algorithms
 *  @param  __first  Start of range.
 *  @param  __last   End of range.
 *  @return  False if wrapped to first permutation, true otherwise.
 *
 *  Treats all permutations of the range as a set of @e dictionary sorted
 *  sequences.  Permutes the current sequence into the next one of this set.
 *  Returns true if there are more sequences to generate.  If the sequence
 *  is the largest of the set, the smallest is generated and false returned.
*/
template<typename _BidirectionalIterator>
  _GLIBCXX20_CONSTEXPR
  inline bool
  next_permutation(_BidirectionalIterator __first,
     _BidirectionalIterator __last)
  {
    // concept requirements
    __glibcxx_function_requires(_BidirectionalIteratorConcept<
		  _BidirectionalIterator>)
    __glibcxx_function_requires(_LessThanComparableConcept<
   typename iterator_traits<_BidirectionalIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __last);
    __glibcxx_requires_irreflexive(__first, __last);

    return std::__next_permutation
(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
  }

/**
 *  @brief  Permute range into the next @e dictionary ordering using
 *          comparison functor.
 *  @ingroup sorting_algorithms
 *  @param  __first  Start of range.
 *  @param  __last   End of range.
 *  @param  __comp   A comparison functor.
 *  @return  False if wrapped to first permutation, true otherwise.
 *
 *  Treats all permutations of the range [__first,__last) as a set of
 *  @e dictionary sorted sequences ordered by @p __comp.  Permutes the current
 *  sequence into the next one of this set.  Returns true if there are more
 *  sequences to generate.  If the sequence is the largest of the set, the
 *  smallest is generated and false returned.
*/
template<typename _BidirectionalIterator, typename _Compare>
  _GLIBCXX20_CONSTEXPR
  inline bool
  next_permutation(_BidirectionalIterator __first,
     _BidirectionalIterator __last, _Compare __comp)
  {
    // concept requirements
    __glibcxx_function_requires(_BidirectionalIteratorConcept<
		  _BidirectionalIterator>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
   typename iterator_traits<_BidirectionalIterator>::value_type,
   typename iterator_traits<_BidirectionalIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __last);
    __glibcxx_requires_irreflexive_pred(__first, __last, __comp);

    return std::__next_permutation
(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
  }

template<typename _BidirectionalIterator, typename _Compare>
  _GLIBCXX20_CONSTEXPR
  bool
  __prev_permutation(_BidirectionalIterator __first,
       _BidirectionalIterator __last, _Compare __comp)
  {
    if (__first == __last)
return false;
    _BidirectionalIterator __i = __first;
    ++__i;
    if (__i == __last)
return false;
    __i = __last;
    --__i;

    for(;;)
{
 _BidirectionalIterator __ii = __i;
 --__i;
 if (__comp(__ii, __i))
   {
     _BidirectionalIterator __j = __last;
     while (!__comp(--__j, __i))
{}
     std::iter_swap(__i, __j);
     std::__reverse(__ii, __last,
	     std::__iterator_category(__first));
     return true;
   }
 if (__i == __first)
   {
     std::__reverse(__first, __last,
	     std::__iterator_category(__first));
     return false;
   }
}
  }

/**
 *  @brief  Permute range into the previous @e dictionary ordering.
 *  @ingroup sorting_algorithms
 *  @param  __first  Start of range.
 *  @param  __last   End of range.
 *  @return  False if wrapped to last permutation, true otherwise.
 *
 *  Treats all permutations of the range as a set of @e dictionary sorted
 *  sequences.  Permutes the current sequence into the previous one of this
 *  set.  Returns true if there are more sequences to generate.  If the
 *  sequence is the smallest of the set, the largest is generated and false
 *  returned.
*/
template<typename _BidirectionalIterator>
  _GLIBCXX20_CONSTEXPR
  inline bool
  prev_permutation(_BidirectionalIterator __first,
     _BidirectionalIterator __last)
  {
    // concept requirements
    __glibcxx_function_requires(_BidirectionalIteratorConcept<
		  _BidirectionalIterator>)
    __glibcxx_function_requires(_LessThanComparableConcept<
   typename iterator_traits<_BidirectionalIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __last);
    __glibcxx_requires_irreflexive(__first, __last);

    return std::__prev_permutation(__first, __last,
		     __gnu_cxx::__ops::__iter_less_iter());
  }

/**
 *  @brief  Permute range into the previous @e dictionary ordering using
 *          comparison functor.
 *  @ingroup sorting_algorithms
 *  @param  __first  Start of range.
 *  @param  __last   End of range.
 *  @param  __comp   A comparison functor.
 *  @return  False if wrapped to last permutation, true otherwise.
 *
 *  Treats all permutations of the range [__first,__last) as a set of
 *  @e dictionary sorted sequences ordered by @p __comp.  Permutes the current
 *  sequence into the previous one of this set.  Returns true if there are
 *  more sequences to generate.  If the sequence is the smallest of the set,
 *  the largest is generated and false returned.
*/
template<typename _BidirectionalIterator, typename _Compare>
  _GLIBCXX20_CONSTEXPR
  inline bool
  prev_permutation(_BidirectionalIterator __first,
     _BidirectionalIterator __last, _Compare __comp)
  {
    // concept requirements
    __glibcxx_function_requires(_BidirectionalIteratorConcept<
		  _BidirectionalIterator>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
   typename iterator_traits<_BidirectionalIterator>::value_type,
   typename iterator_traits<_BidirectionalIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __last);
    __glibcxx_requires_irreflexive_pred(__first, __last, __comp);

    return std::__prev_permutation(__first, __last,
		__gnu_cxx::__ops::__iter_comp_iter(__comp));
  }

// replace
// replace_if

template<typename _InputIterator, typename _OutputIterator,
  typename _Predicate, typename _Tp>
  _GLIBCXX20_CONSTEXPR
  _OutputIterator
  __replace_copy_if(_InputIterator __first, _InputIterator __last,
      _OutputIterator __result,
      _Predicate __pred, const _Tp& __new_value)
  {
    for (; __first != __last; ++__first, (void)++__result)
if (__pred(__first))
 *__result = __new_value;
else
 *__result = *__first;
    return __result;
  }

/**
 *  @brief Copy a sequence, replacing each element of one value with another
 *         value.
 *  @param  __first      An input iterator.
 *  @param  __last       An input iterator.
 *  @param  __result     An output iterator.
 *  @param  __old_value  The value to be replaced.
 *  @param  __new_value  The replacement value.
 *  @return   The end of the output sequence, @p result+(last-first).
 *
 *  Copies each element in the input range @p [__first,__last) to the
 *  output range @p [__result,__result+(__last-__first)) replacing elements
 *  equal to @p __old_value with @p __new_value.
*/
template<typename _InputIterator, typename _OutputIterator, typename _Tp>
  _GLIBCXX20_CONSTEXPR
  inline _OutputIterator
  replace_copy(_InputIterator __first, _InputIterator __last,
 _OutputIterator __result,
 const _Tp& __old_value, const _Tp& __new_value)
  {
    // concept requirements
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
    __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
   typename iterator_traits<_InputIterator>::value_type>)
    __glibcxx_function_requires(_EqualOpConcept<
   typename iterator_traits<_InputIterator>::value_type, _Tp>)
    __glibcxx_requires_valid_range(__first, __last);

    return std::__replace_copy_if(__first, __last, __result,
	__gnu_cxx::__ops::__iter_equals_val(__old_value),
			      __new_value);
  }

/**
 *  @brief Copy a sequence, replacing each value for which a predicate
 *         returns true with another value.
 *  @ingroup mutating_algorithms
 *  @param  __first      An input iterator.
 *  @param  __last       An input iterator.
 *  @param  __result     An output iterator.
 *  @param  __pred       A predicate.
 *  @param  __new_value  The replacement value.
 *  @return   The end of the output sequence, @p __result+(__last-__first).
 *
 *  Copies each element in the range @p [__first,__last) to the range
 *  @p [__result,__result+(__last-__first)) replacing elements for which
 *  @p __pred returns true with @p __new_value.
*/
template<typename _InputIterator, typename _OutputIterator,
  typename _Predicate, typename _Tp>
  _GLIBCXX20_CONSTEXPR
  inline _OutputIterator
  replace_copy_if(_InputIterator __first, _InputIterator __last,
    _OutputIterator __result,
    _Predicate __pred, const _Tp& __new_value)
  {
    // concept requirements
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
    __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
   typename iterator_traits<_InputIterator>::value_type>)
    __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
   typename iterator_traits<_InputIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __last);

    return std::__replace_copy_if(__first, __last, __result,
		__gnu_cxx::__ops::__pred_iter(__pred),
			      __new_value);
  }

3212#if __cplusplus201402L >= 201103L
/**
 *  @brief  Determines whether the elements of a sequence are sorted.
 *  @ingroup sorting_algorithms
 *  @param  __first   An iterator.
 *  @param  __last    Another iterator.
 *  @return  True if the elements are sorted, false otherwise.
*/
template<typename _ForwardIterator>
  _GLIBCXX20_CONSTEXPR
  inline bool
  is_sorted(_ForwardIterator __first, _ForwardIterator __last)
  { return std::is_sorted_until(__first, __last) == __last; }

/**
 *  @brief  Determines whether the elements of a sequence are sorted
 *          according to a comparison functor.
 *  @ingroup sorting_algorithms
 *  @param  __first   An iterator.
 *  @param  __last    Another iterator.
 *  @param  __comp    A comparison functor.
 *  @return  True if the elements are sorted, false otherwise.
*/
template<typename _ForwardIterator, typename _Compare>
  _GLIBCXX20_CONSTEXPR
  inline bool
  is_sorted(_ForwardIterator __first, _ForwardIterator __last,
     _Compare __comp)
  { return std::is_sorted_until(__first, __last, __comp) == __last; }

template<typename _ForwardIterator, typename _Compare>
  _GLIBCXX20_CONSTEXPR
  _ForwardIterator
  __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
      _Compare __comp)
  {
    if (__first == __last)
return __last;

    _ForwardIterator __next = __first;
    for (++__next; __next != __last; __first = __next, (void)++__next)
if (__comp(__next, __first))
 return __next;
    return __next;
  }

/**
 *  @brief  Determines the end of a sorted sequence.
 *  @ingroup sorting_algorithms
 *  @param  __first   An iterator.
 *  @param  __last    Another iterator.
 *  @return  An iterator pointing to the last iterator i in [__first, __last)
 *           for which the range [__first, i) is sorted.
*/
template<typename _ForwardIterator>
  _GLIBCXX20_CONSTEXPR
  inline _ForwardIterator
  is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
  {
    // concept requirements
    __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
    __glibcxx_function_requires(_LessThanComparableConcept<
   typename iterator_traits<_ForwardIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __last);
    __glibcxx_requires_irreflexive(__first, __last);

    return std::__is_sorted_until(__first, __last,
		    __gnu_cxx::__ops::__iter_less_iter());
  }

/**
 *  @brief  Determines the end of a sorted sequence using comparison functor.
 *  @ingroup sorting_algorithms
 *  @param  __first   An iterator.
 *  @param  __last    Another iterator.
 *  @param  __comp    A comparison functor.
 *  @return  An iterator pointing to the last iterator i in [__first, __last)
 *           for which the range [__first, i) is sorted.
*/
template<typename _ForwardIterator, typename _Compare>
  _GLIBCXX20_CONSTEXPR
  inline _ForwardIterator
  is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
    _Compare __comp)
  {
    // concept requirements
    __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
   typename iterator_traits<_ForwardIterator>::value_type,
   typename iterator_traits<_ForwardIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __last);
    __glibcxx_requires_irreflexive_pred(__first, __last, __comp);

    return std::__is_sorted_until(__first, __last,
		    __gnu_cxx::__ops::__iter_comp_iter(__comp));
  }

/**
 *  @brief  Determines min and max at once as an ordered pair.
 *  @ingroup sorting_algorithms
 *  @param  __a  A thing of arbitrary type.
 *  @param  __b  Another thing of arbitrary type.
 *  @return A pair(__b, __a) if __b is smaller than __a, pair(__a,
 *  __b) otherwise.
*/
template<typename _Tp>
  _GLIBCXX14_CONSTEXPRconstexpr
  inline pair<const _Tp&, const _Tp&>
  minmax(const _Tp& __a, const _Tp& __b)
  {
    // concept requirements
    __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)

    return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
       : pair<const _Tp&, const _Tp&>(__a, __b);
  }

/**
 *  @brief  Determines min and max at once as an ordered pair.
 *  @ingroup sorting_algorithms
 *  @param  __a  A thing of arbitrary type.
 *  @param  __b  Another thing of arbitrary type.
 *  @param  __comp  A @link comparison_functors comparison functor @endlink.
 *  @return A pair(__b, __a) if __b is smaller than __a, pair(__a,
 *  __b) otherwise.
*/
template<typename _Tp, typename _Compare>
  _GLIBCXX14_CONSTEXPRconstexpr
  inline pair<const _Tp&, const _Tp&>
  minmax(const _Tp& __a, const _Tp& __b, _Compare __comp)
  {
    return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a)
	      : pair<const _Tp&, const _Tp&>(__a, __b);
  }

template<typename _ForwardIterator, typename _Compare>
  _GLIBCXX14_CONSTEXPRconstexpr
  pair<_ForwardIterator, _ForwardIterator>
  __minmax_element(_ForwardIterator __first, _ForwardIterator __last,
     _Compare __comp)
  {
    _ForwardIterator __next = __first;
    if (__first == __last
 || ++__next == __last)
return std::make_pair(__first, __first);

    _ForwardIterator __min{}, __max{};
    if (__comp(__next, __first))
{
 __min = __next;
 __max = __first;
}
    else
{
 __min = __first;
 __max = __next;
}

    __first = __next;
    ++__first;

    while (__first != __last)
{
 __next = __first;
 if (++__next == __last)
   {
     if (__comp(__first, __min))
__min = __first;
     else if (!__comp(__first, __max))
__max = __first;
     break;
   }

 if (__comp(__next, __first))
   {
     if (__comp(__next, __min))
__min = __next;
     if (!__comp(__first, __max))
__max = __first;
   }
 else
   {
     if (__comp(__first, __min))
__min = __first;
     if (!__comp(__next, __max))
__max = __next;
   }

 __first = __next;
 ++__first;
}

    return std::make_pair(__min, __max);
  }

/**
 *  @brief  Return a pair of iterators pointing to the minimum and maximum
 *          elements in a range.
 *  @ingroup sorting_algorithms
 *  @param  __first  Start of range.
 *  @param  __last   End of range.
 *  @return  make_pair(m, M), where m is the first iterator i in 
 *           [__first, __last) such that no other element in the range is
 *           smaller, and where M is the last iterator i in [__first, __last)
 *           such that no other element in the range is larger.
*/
template<typename _ForwardIterator>
  _GLIBCXX14_CONSTEXPRconstexpr
  inline pair<_ForwardIterator, _ForwardIterator>
  minmax_element(_ForwardIterator __first, _ForwardIterator __last)
  {
    // concept requirements
    __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
    __glibcxx_function_requires(_LessThanComparableConcept<
   typename iterator_traits<_ForwardIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __last);
    __glibcxx_requires_irreflexive(__first, __last);

    return std::__minmax_element(__first, __last,
		   __gnu_cxx::__ops::__iter_less_iter());
  }

/**
 *  @brief  Return a pair of iterators pointing to the minimum and maximum
 *          elements in a range.
 *  @ingroup sorting_algorithms
 *  @param  __first  Start of range.
 *  @param  __last   End of range.
 *  @param  __comp   Comparison functor.
 *  @return  make_pair(m, M), where m is the first iterator i in 
 *           [__first, __last) such that no other element in the range is
 *           smaller, and where M is the last iterator i in [__first, __last)
 *           such that no other element in the range is larger.
*/
template<typename _ForwardIterator, typename _Compare>
  _GLIBCXX14_CONSTEXPRconstexpr
  inline pair<_ForwardIterator, _ForwardIterator>
  minmax_element(_ForwardIterator __first, _ForwardIterator __last,
   _Compare __comp)
  {
    // concept requirements
    __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
   typename iterator_traits<_ForwardIterator>::value_type,
   typename iterator_traits<_ForwardIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __last);
    __glibcxx_requires_irreflexive_pred(__first, __last, __comp);

    return std::__minmax_element(__first, __last,
		   __gnu_cxx::__ops::__iter_comp_iter(__comp));
  }

// N2722 + DR 915.
template<typename _Tp>
  _GLIBCXX14_CONSTEXPRconstexpr
  inline _Tp
  min(initializer_list<_Tp> __l)
  { return *std::min_element(__l.begin(), __l.end()); }

template<typename _Tp, typename _Compare>
  _GLIBCXX14_CONSTEXPRconstexpr
  inline _Tp
  min(initializer_list<_Tp> __l, _Compare __comp)
  { return *std::min_element(__l.begin(), __l.end(), __comp); }

template<typename _Tp>
  _GLIBCXX14_CONSTEXPRconstexpr
  inline _Tp
  max(initializer_list<_Tp> __l)
  { return *std::max_element(__l.begin(), __l.end()); }

template<typename _Tp, typename _Compare>
  _GLIBCXX14_CONSTEXPRconstexpr
  inline _Tp
  max(initializer_list<_Tp> __l, _Compare __comp)
  { return *std::max_element(__l.begin(), __l.end(), __comp); }

template<typename _Tp>
  _GLIBCXX14_CONSTEXPRconstexpr
  inline pair<_Tp, _Tp>
  minmax(initializer_list<_Tp> __l)
  {
    pair<const _Tp*, const _Tp*> __p =
std::minmax_element(__l.begin(), __l.end());
    return std::make_pair(*__p.first, *__p.second);
  }

template<typename _Tp, typename _Compare>
  _GLIBCXX14_CONSTEXPRconstexpr
  inline pair<_Tp, _Tp>
  minmax(initializer_list<_Tp> __l, _Compare __comp)
  {
    pair<const _Tp*, const _Tp*> __p =
std::minmax_element(__l.begin(), __l.end(), __comp);
    return std::make_pair(*__p.first, *__p.second);
  }

/**
 *  @brief  Checks whether a permutation of the second sequence is equal
 *          to the first sequence.
 *  @ingroup non_mutating_algorithms
 *  @param  __first1  Start of first range.
 *  @param  __last1   End of first range.
 *  @param  __first2  Start of second range.
 *  @param  __pred    A binary predicate.
 *  @return true if there exists a permutation of the elements in
 *          the range [__first2, __first2 + (__last1 - __first1)),
 *          beginning with ForwardIterator2 begin, such that
 *          equal(__first1, __last1, __begin, __pred) returns true;
 *          otherwise, returns false.
*/
template<typename _ForwardIterator1, typename _ForwardIterator2,
  typename _BinaryPredicate>
  _GLIBCXX20_CONSTEXPR
  inline bool
  is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
   _ForwardIterator2 __first2, _BinaryPredicate __pred)
  {
    // concept requirements
    __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
    __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
   typename iterator_traits<_ForwardIterator1>::value_type,
   typename iterator_traits<_ForwardIterator2>::value_type>)
    __glibcxx_requires_valid_range(__first1, __last1);

    return std::__is_permutation(__first1, __last1, __first2,
		   __gnu_cxx::__ops::__iter_comp_iter(__pred));
  }

3542#if __cplusplus201402L > 201103L
template<typename _ForwardIterator1, typename _ForwardIterator2,
  typename _BinaryPredicate>
  _GLIBCXX20_CONSTEXPR
  bool
  __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
     _ForwardIterator2 __first2, _ForwardIterator2 __last2,
     _BinaryPredicate __pred)
  {
    using _Cat1
= typename iterator_traits<_ForwardIterator1>::iterator_category;
    using _Cat2
= typename iterator_traits<_ForwardIterator2>::iterator_category;
    using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
    using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
    constexpr bool __ra_iters = _It1_is_RA() && _It2_is_RA();
    if (__ra_iters)
{
 auto __d1 = std::distance(__first1, __last1);
 auto __d2 = std::distance(__first2, __last2);
 if (__d1 != __d2)
   return false;
}

    // Efficiently compare identical prefixes:  O(N) if sequences
    // have the same elements in the same order.
    for (; __first1 != __last1 && __first2 != __last2;
 ++__first1, (void)++__first2)
if (!__pred(__first1, __first2))
 break;

    if (__ra_iters)
{
 if (__first1 == __last1)
   return true;
}
    else
{
 auto __d1 = std::distance(__first1, __last1);
 auto __d2 = std::distance(__first2, __last2);
 if (__d1 == 0 && __d2 == 0)
   return true;
 if (__d1 != __d2)
   return false;
}

    for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
{
 if (__scan != std::__find_if(__first1, __scan,
	__gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
   continue; // We've seen this one before.

 auto __matches = std::__count_if(__first2, __last2,
__gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
 if (0 == __matches
     || std::__count_if(__scan, __last1,
	__gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
     != __matches)
   return false;
}
    return true;
  }

/**
 *  @brief  Checks whether a permutaion of the second sequence is equal
 *          to the first sequence.
 *  @ingroup non_mutating_algorithms
 *  @param  __first1  Start of first range.
 *  @param  __last1   End of first range.
 *  @param  __first2  Start of second range.
 *  @param  __last2   End of first range.
 *  @return true if there exists a permutation of the elements in the range
 *          [__first2, __last2), beginning with ForwardIterator2 begin,
 *          such that equal(__first1, __last1, begin) returns true;
 *          otherwise, returns false.
*/
template<typename _ForwardIterator1, typename _ForwardIterator2>
  _GLIBCXX20_CONSTEXPR
  inline bool
  is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
   _ForwardIterator2 __first2, _ForwardIterator2 __last2)
  {
    __glibcxx_requires_valid_range(__first1, __last1);
    __glibcxx_requires_valid_range(__first2, __last2);

    return
std::__is_permutation(__first1, __last1, __first2, __last2,
	      __gnu_cxx::__ops::__iter_equal_to_iter());
  }

/**
 *  @brief  Checks whether a permutation of the second sequence is equal
 *          to the first sequence.
 *  @ingroup non_mutating_algorithms
 *  @param  __first1  Start of first range.
 *  @param  __last1   End of first range.
 *  @param  __first2  Start of second range.
 *  @param  __last2   End of first range.
 *  @param  __pred    A binary predicate.
 *  @return true if there exists a permutation of the elements in the range
 *          [__first2, __last2), beginning with ForwardIterator2 begin,
 *          such that equal(__first1, __last1, __begin, __pred) returns true;
 *          otherwise, returns false.
*/
template<typename _ForwardIterator1, typename _ForwardIterator2,
  typename _BinaryPredicate>
  _GLIBCXX20_CONSTEXPR
  inline bool
  is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
   _ForwardIterator2 __first2, _ForwardIterator2 __last2,
   _BinaryPredicate __pred)
  {
    __glibcxx_requires_valid_range(__first1, __last1);
    __glibcxx_requires_valid_range(__first2, __last2);

    return std::__is_permutation(__first1, __last1, __first2, __last2,
		   __gnu_cxx::__ops::__iter_comp_iter(__pred));
  }

3661#if __cplusplus201402L > 201402L

3663#define __cpp_lib_clamp 201603

/**
 *  @brief  Returns the value clamped between lo and hi.
 *  @ingroup sorting_algorithms
 *  @param  __val  A value of arbitrary type.
 *  @param  __lo   A lower limit of arbitrary type.
 *  @param  __hi   An upper limit of arbitrary type.
 *  @return max(__val, __lo) if __val < __hi or min(__val, __hi) otherwise.
 */
template<typename _Tp>
  constexpr const _Tp&
  clamp(const _Tp& __val, const _Tp& __lo, const _Tp& __hi)
  {
    __glibcxx_assert(!(__hi < __lo));
    return (__val < __lo) ? __lo : (__hi < __val) ? __hi : __val;
  }

/**
 *  @brief  Returns the value clamped between lo and hi.
 *  @ingroup sorting_algorithms
 *  @param  __val   A value of arbitrary type.
 *  @param  __lo    A lower limit of arbitrary type.
 *  @param  __hi    An upper limit of arbitrary type.
 *  @param  __comp  A comparison functor.
 *  @return max(__val, __lo, __comp) if __comp(__val, __hi)
 *	      or min(__val, __hi, __comp) otherwise.
 */
template<typename _Tp, typename _Compare>
  constexpr const _Tp&
  clamp(const _Tp& __val, const _Tp& __lo, const _Tp& __hi, _Compare __comp)
  {
    __glibcxx_assert(!__comp(__hi, __lo));
    return __comp(__val, __lo) ? __lo : __comp(__hi, __val) ? __hi : __val;
  }
3698#endif // C++17
3699#endif // C++14

3701#ifdef _GLIBCXX_USE_C99_STDINT_TR11
/**
 *  @brief Generate two uniformly distributed integers using a
 *         single distribution invocation.
 *  @param  __b0    The upper bound for the first integer.
 *  @param  __b1    The upper bound for the second integer.
 *  @param  __g     A UniformRandomBitGenerator.
 *  @return  A pair (i, j) with i and j uniformly distributed
 *           over [0, __b0) and [0, __b1), respectively.
 *
 *  Requires: __b0 * __b1 <= __g.max() - __g.min().
 *
 *  Using uniform_int_distribution with a range that is very
 *  small relative to the range of the generator ends up wasting
 *  potentially expensively generated randomness, since
 *  uniform_int_distribution does not store leftover randomness
 *  between invocations.
 *
 *  If we know we want two integers in ranges that are sufficiently
 *  small, we can compose the ranges, use a single distribution
 *  invocation, and significantly reduce the waste.
*/
template<typename _IntType, typename _UniformRandomBitGenerator>
  pair<_IntType, _IntType>
  __gen_two_uniform_ints(_IntType __b0, _IntType __b1,
	   _UniformRandomBitGenerator&& __g)
  {
    _IntType __x
= uniform_int_distribution<_IntType>{0, (__b0 * __b1) - 1}(__g);
    return std::make_pair(__x / __b1, __x % __b1);
  }

/**
 *  @brief Shuffle the elements of a sequence using a uniform random
 *         number generator.
 *  @ingroup mutating_algorithms
 *  @param  __first   A forward iterator.
 *  @param  __last    A forward iterator.
 *  @param  __g       A UniformRandomNumberGenerator (26.5.1.3).
 *  @return  Nothing.
 *
 *  Reorders the elements in the range @p [__first,__last) using @p __g to
 *  provide random numbers.
*/
template<typename _RandomAccessIterator,
  typename _UniformRandomNumberGenerator>
  void
  shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
   _UniformRandomNumberGenerator&& __g)
  {
    // concept requirements
    __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
   _RandomAccessIterator>)
    __glibcxx_requires_valid_range(__first, __last);

    if (__first == __last)
return;

    typedef typename iterator_traits<_RandomAccessIterator>::difference_type
_DistanceType;

    typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
    typedef typename std::uniform_int_distribution<__ud_type> __distr_type;
    typedef typename __distr_type::param_type __p_type;

    typedef typename remove_reference<_UniformRandomNumberGenerator>::type
_Gen;
    typedef typename common_type<typename _Gen::result_type, __ud_type>::type
__uc_type;

    const __uc_type __urngrange = __g.max() - __g.min();
    const __uc_type __urange = __uc_type(__last - __first);

    if (__urngrange / __urange >= __urange)
      // I.e. (__urngrange >= __urange * __urange) but without wrap issues.
    {
_RandomAccessIterator __i = __first + 1;

// Since we know the range isn't empty, an even number of elements
// means an uneven number of elements /to swap/, in which case we
// do the first one up front:

if ((__urange % 2) == 0)
{
 __distr_type __d{0, 1};
 std::iter_swap(__i++, __first + __d(__g));
}

// Now we know that __last - __i is even, so we do the rest in pairs,
// using a single distribution invocation to produce swap positions
// for two successive elements at a time:

while (__i != __last)
{
 const __uc_type __swap_range = __uc_type(__i - __first) + 1;

 const pair<__uc_type, __uc_type> __pospos =
   __gen_two_uniform_ints(__swap_range, __swap_range + 1, __g);

 std::iter_swap(__i++, __first + __pospos.first);
 std::iter_swap(__i++, __first + __pospos.second);
}

return;
    }

    __distr_type __d;

    for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
  }
3812#endif

3814#endif // C++11

3816_GLIBCXX_BEGIN_NAMESPACE_ALGO

/**
 *  @brief Apply a function to every element of a sequence.
 *  @ingroup non_mutating_algorithms
 *  @param  __first  An input iterator.
 *  @param  __last   An input iterator.
 *  @param  __f      A unary function object.
 *  @return   @p __f
 *
 *  Applies the function object @p __f to each element in the range
 *  @p [first,last).  @p __f must not modify the order of the sequence.
 *  If @p __f has a return value it is ignored.
*/
template<typename _InputIterator, typename _Function>
  _GLIBCXX20_CONSTEXPR
  _Function
  for_each(_InputIterator __first, _InputIterator __last, _Function __f)
  {
    // concept requirements
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
    __glibcxx_requires_valid_range(__first, __last);
    for (; __first != __last; ++__first)
__f(*__first);
    return __f; // N.B. [alg.foreach] says std::move(f) but it's redundant.
  }

3843#if __cplusplus201402L >= 201703L
/**
 *  @brief Apply a function to every element of a sequence.
 *  @ingroup non_mutating_algorithms
 *  @param  __first  An input iterator.
 *  @param  __n      A value convertible to an integer.
 *  @param  __f      A unary function object.
 *  @return   `__first+__n`
 *
 *  Applies the function object `__f` to each element in the range
 *  `[first, first+n)`.  `__f` must not modify the order of the sequence.
 *  If `__f` has a return value it is ignored.
*/
template<typename _InputIterator, typename _Size, typename _Function>
  _InputIterator
  for_each_n(_InputIterator __first, _Size __n, _Function __f)
  {
    auto __n2 = std::__size_to_integer(__n);
    using _Cat = typename iterator_traits<_InputIterator>::iterator_category;
    if constexpr (is_base_of_v<random_access_iterator_tag, _Cat>)
{
 if (__n2 <= 0)
   return __first;
 auto __last = __first + __n2;
 std::for_each(__first, __last, std::move(__f));
 return __last;
}
    else
{
 while (__n2-->0)
   {
     __f(*__first);
     ++__first;
   }
 return __first;
}
  }
3880#endif // C++17

/**
 *  @brief Find the first occurrence of a value in a sequence.
 *  @ingroup non_mutating_algorithms
 *  @param  __first  An input iterator.
 *  @param  __last   An input iterator.
 *  @param  __val    The value to find.
 *  @return   The first iterator @c i in the range @p [__first,__last)
 *  such that @c *i == @p __val, or @p __last if no such iterator exists.
*/
template<typename _InputIterator, typename _Tp>
  _GLIBCXX20_CONSTEXPR
  inline _InputIterator
  find(_InputIterator __first, _InputIterator __last,
const _Tp& __val)
  {
    // concept requirements
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
    __glibcxx_function_requires(_EqualOpConcept<
typename iterator_traits<_InputIterator>::value_type, _Tp>)
    __glibcxx_requires_valid_range(__first, __last);
    return std::__find_if(__first, __last,
	    __gnu_cxx::__ops::__iter_equals_val(__val));
  }

/**
 *  @brief Find the first element in a sequence for which a
 *         predicate is true.
 *  @ingroup non_mutating_algorithms
 *  @param  __first  An input iterator.
 *  @param  __last   An input iterator.
 *  @param  __pred   A predicate.
 *  @return   The first iterator @c i in the range @p [__first,__last)
 *  such that @p __pred(*i) is true, or @p __last if no such iterator exists.
*/
template<typename _InputIterator, typename _Predicate>
  _GLIBCXX20_CONSTEXPR
  inline _InputIterator
  find_if(_InputIterator __first, _InputIterator __last,
   _Predicate __pred)
  {
    // concept requirements
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
    __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
     typename iterator_traits<_InputIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __last);

    return std::__find_if(__first, __last,
	    __gnu_cxx::__ops::__pred_iter(__pred));
  }

/**
 *  @brief  Find element from a set in a sequence.
 *  @ingroup non_mutating_algorithms
 *  @param  __first1  Start of range to search.
 *  @param  __last1   End of range to search.
 *  @param  __first2  Start of match candidates.
 *  @param  __last2   End of match candidates.
 *  @return   The first iterator @c i in the range
 *  @p [__first1,__last1) such that @c *i == @p *(i2) such that i2 is an
 *  iterator in [__first2,__last2), or @p __last1 if no such iterator exists.
 *
 *  Searches the range @p [__first1,__last1) for an element that is
 *  equal to some element in the range [__first2,__last2).  If
 *  found, returns an iterator in the range [__first1,__last1),
 *  otherwise returns @p __last1.
*/
template<typename _InputIterator, typename _ForwardIterator>
  _GLIBCXX20_CONSTEXPR
  _InputIterator
  find_first_of(_InputIterator __first1, _InputIterator __last1,
  _ForwardIterator __first2, _ForwardIterator __last2)
  {
    // concept requirements
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
    __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
    __glibcxx_function_requires(_EqualOpConcept<
   typename iterator_traits<_InputIterator>::value_type,
   typename iterator_traits<_ForwardIterator>::value_type>)
    __glibcxx_requires_valid_range(__first1, __last1);
    __glibcxx_requires_valid_range(__first2, __last2);

    for (; __first1 != __last1; ++__first1)
for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
 if (*__first1 == *__iter)
   return __first1;
    return __last1;
  }

/**
 *  @brief  Find element from a set in a sequence using a predicate.
 *  @ingroup non_mutating_algorithms
 *  @param  __first1  Start of range to search.
 *  @param  __last1   End of range to search.
 *  @param  __first2  Start of match candidates.
 *  @param  __last2   End of match candidates.
 *  @param  __comp    Predicate to use.
 *  @return   The first iterator @c i in the range
 *  @p [__first1,__last1) such that @c comp(*i, @p *(i2)) is true
 *  and i2 is an iterator in [__first2,__last2), or @p __last1 if no
 *  such iterator exists.
 *

 *  Searches the range @p [__first1,__last1) for an element that is
 *  equal to some element in the range [__first2,__last2).  If
 *  found, returns an iterator in the range [__first1,__last1),
 *  otherwise returns @p __last1.
*/
template<typename _InputIterator, typename _ForwardIterator,
  typename _BinaryPredicate>
  _GLIBCXX20_CONSTEXPR
  _InputIterator
  find_first_of(_InputIterator __first1, _InputIterator __last1,
  _ForwardIterator __first2, _ForwardIterator __last2,
  _BinaryPredicate __comp)
  {
    // concept requirements
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
    __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
   typename iterator_traits<_InputIterator>::value_type,
   typename iterator_traits<_ForwardIterator>::value_type>)
    __glibcxx_requires_valid_range(__first1, __last1);
    __glibcxx_requires_valid_range(__first2, __last2);

    for (; __first1 != __last1; ++__first1)
for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
 if (__comp(*__first1, *__iter))
   return __first1;
    return __last1;
  }

/**
 *  @brief Find two adjacent values in a sequence that are equal.
 *  @ingroup non_mutating_algorithms
 *  @param  __first  A forward iterator.
 *  @param  __last   A forward iterator.
 *  @return   The first iterator @c i such that @c i and @c i+1 are both
 *  valid iterators in @p [__first,__last) and such that @c *i == @c *(i+1),
 *  or @p __last if no such iterator exists.
*/
template<typename _ForwardIterator>
  _GLIBCXX20_CONSTEXPR
  inline _ForwardIterator
  adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
  {
    // concept requirements
    __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
    __glibcxx_function_requires(_EqualityComparableConcept<
   typename iterator_traits<_ForwardIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __last);

    return std::__adjacent_find(__first, __last,
		  __gnu_cxx::__ops::__iter_equal_to_iter());
  }

/**
 *  @brief Find two adjacent values in a sequence using a predicate.
 *  @ingroup non_mutating_algorithms
 *  @param  __first         A forward iterator.
 *  @param  __last          A forward iterator.
 *  @param  __binary_pred   A binary predicate.
 *  @return   The first iterator @c i such that @c i and @c i+1 are both
 *  valid iterators in @p [__first,__last) and such that
 *  @p __binary_pred(*i,*(i+1)) is true, or @p __last if no such iterator
 *  exists.
*/
template<typename _ForwardIterator, typename _BinaryPredicate>
  _GLIBCXX20_CONSTEXPR
  inline _ForwardIterator
  adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
  _BinaryPredicate __binary_pred)
  {
    // concept requirements
    __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
   typename iterator_traits<_ForwardIterator>::value_type,
   typename iterator_traits<_ForwardIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __last);

    return std::__adjacent_find(__first, __last,
	__gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
  }

/**
 *  @brief Count the number of copies of a value in a sequence.
 *  @ingroup non_mutating_algorithms
 *  @param  __first  An input iterator.
 *  @param  __last   An input iterator.
 *  @param  __value  The value to be counted.
 *  @return   The number of iterators @c i in the range @p [__first,__last)
 *  for which @c *i == @p __value
*/
template<typename _InputIterator, typename _Tp>
  _GLIBCXX20_CONSTEXPR
  inline typename iterator_traits<_InputIterator>::difference_type
  count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
  {
    // concept requirements
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
    __glibcxx_function_requires(_EqualOpConcept<
   typename iterator_traits<_InputIterator>::value_type, _Tp>)
    __glibcxx_requires_valid_range(__first, __last);

    return std::__count_if(__first, __last,
	     __gnu_cxx::__ops::__iter_equals_val(__value));
  }

/**
 *  @brief Count the elements of a sequence for which a predicate is true.
 *  @ingroup non_mutating_algorithms
 *  @param  __first  An input iterator.
 *  @param  __last   An input iterator.
 *  @param  __pred   A predicate.
 *  @return   The number of iterators @c i in the range @p [__first,__last)
 *  for which @p __pred(*i) is true.
*/
template<typename _InputIterator, typename _Predicate>
  _GLIBCXX20_CONSTEXPR
  inline typename iterator_traits<_InputIterator>::difference_type
  count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
  {
    // concept requirements
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
    __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
   typename iterator_traits<_InputIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __last);

    return std::__count_if(__first, __last,
	     __gnu_cxx::__ops::__pred_iter(__pred));
  }

/**
 *  @brief Search a sequence for a matching sub-sequence.
 *  @ingroup non_mutating_algorithms
 *  @param  __first1  A forward iterator.
 *  @param  __last1   A forward iterator.
 *  @param  __first2  A forward iterator.
 *  @param  __last2   A forward iterator.
 *  @return The first iterator @c i in the range @p
 *  [__first1,__last1-(__last2-__first2)) such that @c *(i+N) == @p
 *  *(__first2+N) for each @c N in the range @p
 *  [0,__last2-__first2), or @p __last1 if no such iterator exists.
 *
 *  Searches the range @p [__first1,__last1) for a sub-sequence that
 *  compares equal value-by-value with the sequence given by @p
 *  [__first2,__last2) and returns an iterator to the first element
 *  of the sub-sequence, or @p __last1 if the sub-sequence is not
 *  found.
 *
 *  Because the sub-sequence must lie completely within the range @p
 *  [__first1,__last1) it must start at a position less than @p
 *  __last1-(__last2-__first2) where @p __last2-__first2 is the
 *  length of the sub-sequence.
 *
 *  This means that the returned iterator @c i will be in the range
 *  @p [__first1,__last1-(__last2-__first2))
*/
template<typename _ForwardIterator1, typename _ForwardIterator2>
  _GLIBCXX20_CONSTEXPR
  inline _ForwardIterator1
  search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
  _ForwardIterator2 __first2, _ForwardIterator2 __last2)
  {
    // concept requirements
    __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
    __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
    __glibcxx_function_requires(_EqualOpConcept<
   typename iterator_traits<_ForwardIterator1>::value_type,
   typename iterator_traits<_ForwardIterator2>::value_type>)
    __glibcxx_requires_valid_range(__first1, __last1);
    __glibcxx_requires_valid_range(__first2, __last2);

    return std::__search(__first1, __last1, __first2, __last2,
	   __gnu_cxx::__ops::__iter_equal_to_iter());
  }

/**
 *  @brief Search a sequence for a matching sub-sequence using a predicate.
 *  @ingroup non_mutating_algorithms
 *  @param  __first1     A forward iterator.
 *  @param  __last1      A forward iterator.
 *  @param  __first2     A forward iterator.
 *  @param  __last2      A forward iterator.
 *  @param  __predicate  A binary predicate.
 *  @return   The first iterator @c i in the range
 *  @p [__first1,__last1-(__last2-__first2)) such that
 *  @p __predicate(*(i+N),*(__first2+N)) is true for each @c N in the range
 *  @p [0,__last2-__first2), or @p __last1 if no such iterator exists.
 *
 *  Searches the range @p [__first1,__last1) for a sub-sequence that
 *  compares equal value-by-value with the sequence given by @p
 *  [__first2,__last2), using @p __predicate to determine equality,
 *  and returns an iterator to the first element of the
 *  sub-sequence, or @p __last1 if no such iterator exists.
 *
 *  @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
*/
template<typename _ForwardIterator1, typename _ForwardIterator2,
  typename _BinaryPredicate>
  _GLIBCXX20_CONSTEXPR
  inline _ForwardIterator1
  search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
  _ForwardIterator2 __first2, _ForwardIterator2 __last2,
  _BinaryPredicate  __predicate)
  {
    // concept requirements
    __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
    __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
   typename iterator_traits<_ForwardIterator1>::value_type,
   typename iterator_traits<_ForwardIterator2>::value_type>)
    __glibcxx_requires_valid_range(__first1, __last1);
    __glibcxx_requires_valid_range(__first2, __last2);

    return std::__search(__first1, __last1, __first2, __last2,
	   __gnu_cxx::__ops::__iter_comp_iter(__predicate));
  }

/**
 *  @brief Search a sequence for a number of consecutive values.
 *  @ingroup non_mutating_algorithms
 *  @param  __first  A forward iterator.
 *  @param  __last   A forward iterator.
 *  @param  __count  The number of consecutive values.
 *  @param  __val    The value to find.
 *  @return The first iterator @c i in the range @p
 *  [__first,__last-__count) such that @c *(i+N) == @p __val for
 *  each @c N in the range @p [0,__count), or @p __last if no such
 *  iterator exists.
 *
 *  Searches the range @p [__first,__last) for @p count consecutive elements
 *  equal to @p __val.
*/
template<typename _ForwardIterator, typename _Integer, typename _Tp>
  _GLIBCXX20_CONSTEXPR
  inline _ForwardIterator
  search_n(_ForwardIterator __first, _ForwardIterator __last,
    _Integer __count, const _Tp& __val)
  {
    // concept requirements
    __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
    __glibcxx_function_requires(_EqualOpConcept<
   typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
    __glibcxx_requires_valid_range(__first, __last);

    return std::__search_n(__first, __last, __count,
	     __gnu_cxx::__ops::__iter_equals_val(__val));
  }


/**
 *  @brief Search a sequence for a number of consecutive values using a
 *         predicate.
 *  @ingroup non_mutating_algorithms
 *  @param  __first        A forward iterator.
 *  @param  __last         A forward iterator.
 *  @param  __count        The number of consecutive values.
 *  @param  __val          The value to find.
 *  @param  __binary_pred  A binary predicate.
 *  @return The first iterator @c i in the range @p
 *  [__first,__last-__count) such that @p
 *  __binary_pred(*(i+N),__val) is true for each @c N in the range
 *  @p [0,__count), or @p __last if no such iterator exists.
 *
 *  Searches the range @p [__first,__last) for @p __count
 *  consecutive elements for which the predicate returns true.
*/
template<typename _ForwardIterator, typename _Integer, typename _Tp,
  typename _BinaryPredicate>
  _GLIBCXX20_CONSTEXPR
  inline _ForwardIterator
  search_n(_ForwardIterator __first, _ForwardIterator __last,
    _Integer __count, const _Tp& __val,
    _BinaryPredicate __binary_pred)
  {
    // concept requirements
    __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
   typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
    __glibcxx_requires_valid_range(__first, __last);

    return std::__search_n(__first, __last, __count,
__gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val));
  }

4267#if __cplusplus201402L > 201402L
/** @brief Search a sequence using a Searcher object.
 *
 *  @param  __first        A forward iterator.
 *  @param  __last         A forward iterator.
 *  @param  __searcher     A callable object.
 *  @return @p __searcher(__first,__last).first
*/
template<typename _ForwardIterator, typename _Searcher>
  inline _ForwardIterator
  search(_ForwardIterator __first, _ForwardIterator __last,
  const _Searcher& __searcher)
  { return __searcher(__first, __last).first; }
4280#endif

/**
 *  @brief Perform an operation on a sequence.
 *  @ingroup mutating_algorithms
 *  @param  __first     An input iterator.
 *  @param  __last      An input iterator.
 *  @param  __result    An output iterator.
 *  @param  __unary_op  A unary operator.
 *  @return   An output iterator equal to @p __result+(__last-__first).
 *
 *  Applies the operator to each element in the input range and assigns
 *  the results to successive elements of the output sequence.
 *  Evaluates @p *(__result+N)=unary_op(*(__first+N)) for each @c N in the
 *  range @p [0,__last-__first).
 *
 *  @p unary_op must not alter its argument.
*/
template<typename _InputIterator, typename _OutputIterator,
  typename _UnaryOperation>
  _GLIBCXX20_CONSTEXPR
  _OutputIterator
  transform(_InputIterator __first, _InputIterator __last,
     _OutputIterator __result, _UnaryOperation __unary_op)
  {
    // concept requirements
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
    __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
   // "the type returned by a _UnaryOperation"
   __typeof__(__unary_op(*__first))>)
    __glibcxx_requires_valid_range(__first, __last);

    for (; __first != __last; ++__first, (void)++__result)
*__result = __unary_op(*__first);
    return __result;
  }

/**
 *  @brief Perform an operation on corresponding elements of two sequences.
 *  @ingroup mutating_algorithms
 *  @param  __first1     An input iterator.
 *  @param  __last1      An input iterator.
 *  @param  __first2     An input iterator.
 *  @param  __result     An output iterator.
 *  @param  __binary_op  A binary operator.
 *  @return   An output iterator equal to @p result+(last-first).
 *
 *  Applies the operator to the corresponding elements in the two
 *  input ranges and assigns the results to successive elements of the
 *  output sequence.
 *  Evaluates @p
 *  *(__result+N)=__binary_op(*(__first1+N),*(__first2+N)) for each
 *  @c N in the range @p [0,__last1-__first1).
 *
 *  @p binary_op must not alter either of its arguments.
*/
template<typename _InputIterator1, typename _InputIterator2,
  typename _OutputIterator, typename _BinaryOperation>
  _GLIBCXX20_CONSTEXPR
  _OutputIterator
  transform(_InputIterator1 __first1, _InputIterator1 __last1,
     _InputIterator2 __first2, _OutputIterator __result,
     _BinaryOperation __binary_op)
  {
    // concept requirements
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
    __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
   // "the type returned by a _BinaryOperation"
   __typeof__(__binary_op(*__first1,*__first2))>)
    __glibcxx_requires_valid_range(__first1, __last1);

    for (; __first1 != __last1; ++__first1, (void)++__first2, ++__result)
*__result = __binary_op(*__first1, *__first2);
    return __result;
  }

/**
 *  @brief Replace each occurrence of one value in a sequence with another
 *         value.
 *  @ingroup mutating_algorithms
 *  @param  __first      A forward iterator.
 *  @param  __last       A forward iterator.
 *  @param  __old_value  The value to be replaced.
 *  @param  __new_value  The replacement value.
 *  @return   replace() returns no value.
 *
 *  For each iterator @c i in the range @p [__first,__last) if @c *i ==
 *  @p __old_value then the assignment @c *i = @p __new_value is performed.
*/
template<typename _ForwardIterator, typename _Tp>
  _GLIBCXX20_CONSTEXPR
  void
  replace(_ForwardIterator __first, _ForwardIterator __last,
   const _Tp& __old_value, const _Tp& __new_value)
  {
    // concept requirements
    __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
		  _ForwardIterator>)
    __glibcxx_function_requires(_EqualOpConcept<
   typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
    __glibcxx_function_requires(_ConvertibleConcept<_Tp,
   typename iterator_traits<_ForwardIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __last);

    for (; __first != __last; ++__first)
if (*__first == __old_value)
 *__first = __new_value;
  }

/**
 *  @brief Replace each value in a sequence for which a predicate returns
 *         true with another value.
 *  @ingroup mutating_algorithms
 *  @param  __first      A forward iterator.
 *  @param  __last       A forward iterator.
 *  @param  __pred       A predicate.
 *  @param  __new_value  The replacement value.
 *  @return   replace_if() returns no value.
 *
 *  For each iterator @c i in the range @p [__first,__last) if @p __pred(*i)
 *  is true then the assignment @c *i = @p __new_value is performed.
*/
template<typename _ForwardIterator, typename _Predicate, typename _Tp>
  _GLIBCXX20_CONSTEXPR
  void
  replace_if(_ForwardIterator __first, _ForwardIterator __last,
      _Predicate __pred, const _Tp& __new_value)
  {
    // concept requirements
    __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
		  _ForwardIterator>)
    __glibcxx_function_requires(_ConvertibleConcept<_Tp,
   typename iterator_traits<_ForwardIterator>::value_type>)
    __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
   typename iterator_traits<_ForwardIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __last);

    for (; __first != __last; ++__first)
if (__pred(*__first))
 *__first = __new_value;
  }

/**
 *  @brief Assign the result of a function object to each value in a
 *         sequence.
 *  @ingroup mutating_algorithms
 *  @param  __first  A forward iterator.
 *  @param  __last   A forward iterator.
 *  @param  __gen    A function object taking no arguments and returning
 *                 std::iterator_traits<_ForwardIterator>::value_type
 *  @return   generate() returns no value.
 *
 *  Performs the assignment @c *i = @p __gen() for each @c i in the range
 *  @p [__first,__last).
*/
template<typename _ForwardIterator, typename _Generator>
  _GLIBCXX20_CONSTEXPR
  void
  generate(_ForwardIterator __first, _ForwardIterator __last,
    _Generator __gen)
  {
    // concept requirements
    __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
    __glibcxx_function_requires(_GeneratorConcept<_Generator,
   typename iterator_traits<_ForwardIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __last);

    for (; __first != __last; ++__first)
*__first = __gen();
  }

/**
 *  @brief Assign the result of a function object to each value in a
 *         sequence.
 *  @ingroup mutating_algorithms
 *  @param  __first  A forward iterator.
 *  @param  __n      The length of the sequence.
 *  @param  __gen    A function object taking no arguments and returning
 *                 std::iterator_traits<_ForwardIterator>::value_type
 *  @return   The end of the sequence, @p __first+__n
 *
 *  Performs the assignment @c *i = @p __gen() for each @c i in the range
 *  @p [__first,__first+__n).
 *
 * If @p __n is negative, the function does nothing and returns @p __first.
*/
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// DR 865. More algorithms that throw away information
// DR 426. search_n(), fill_n(), and generate_n() with negative n
template<typename _OutputIterator, typename _Size, typename _Generator>
  _GLIBCXX20_CONSTEXPR
  _OutputIterator
  generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
  {
    // concept requirements
    __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
   // "the type returned by a _Generator"
   __typeof__(__gen())>)

    typedef __decltype(std::__size_to_integer(__n)) _IntSize;
    for (_IntSize __niter = std::__size_to_integer(__n);
  __niter > 0; --__niter, (void) ++__first)
*__first = __gen();
    return __first;
  }

/**
 *  @brief Copy a sequence, removing consecutive duplicate values.
 *  @ingroup mutating_algorithms
 *  @param  __first   An input iterator.
 *  @param  __last    An input iterator.
 *  @param  __result  An output iterator.
 *  @return   An iterator designating the end of the resulting sequence.
 *
 *  Copies each element in the range @p [__first,__last) to the range
 *  beginning at @p __result, except that only the first element is copied
 *  from groups of consecutive elements that compare equal.
 *  unique_copy() is stable, so the relative order of elements that are
 *  copied is unchanged.
 *
 *  _GLIBCXX_RESOLVE_LIB_DEFECTS
 *  DR 241. Does unique_copy() require CopyConstructible and Assignable?
 *  
 *  _GLIBCXX_RESOLVE_LIB_DEFECTS
 *  DR 538. 241 again: Does unique_copy() require CopyConstructible and 
 *  Assignable?
*/
template<typename _InputIterator, typename _OutputIterator>
  _GLIBCXX20_CONSTEXPR
  inline _OutputIterator
  unique_copy(_InputIterator __first, _InputIterator __last,
_OutputIterator __result)
  {
    // concept requirements
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
    __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
   typename iterator_traits<_InputIterator>::value_type>)
    __glibcxx_function_requires(_EqualityComparableConcept<
   typename iterator_traits<_InputIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __last);

    if (__first == __last)
return __result;
    return std::__unique_copy(__first, __last, __result,
		__gnu_cxx::__ops::__iter_equal_to_iter(),
		std::__iterator_category(__first),
		std::__iterator_category(__result));
  }

/**
 *  @brief Copy a sequence, removing consecutive values using a predicate.
 *  @ingroup mutating_algorithms
 *  @param  __first        An input iterator.
 *  @param  __last         An input iterator.
 *  @param  __result       An output iterator.
 *  @param  __binary_pred  A binary predicate.
 *  @return   An iterator designating the end of the resulting sequence.
 *
 *  Copies each element in the range @p [__first,__last) to the range
 *  beginning at @p __result, except that only the first element is copied
 *  from groups of consecutive elements for which @p __binary_pred returns
 *  true.
 *  unique_copy() is stable, so the relative order of elements that are
 *  copied is unchanged.
 *
 *  _GLIBCXX_RESOLVE_LIB_DEFECTS
 *  DR 241. Does unique_copy() require CopyConstructible and Assignable?
*/
template<typename _InputIterator, typename _OutputIterator,
  typename _BinaryPredicate>
  _GLIBCXX20_CONSTEXPR
  inline _OutputIterator
  unique_copy(_InputIterator __first, _InputIterator __last,
_OutputIterator __result,
_BinaryPredicate __binary_pred)
  {
    // concept requirements -- predicates checked later
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
    __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
   typename iterator_traits<_InputIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __last);

    if (__first == __last)
return __result;
    return std::__unique_copy(__first, __last, __result,
	__gnu_cxx::__ops::__iter_comp_iter(__binary_pred),
		std::__iterator_category(__first),
		std::__iterator_category(__result));
  }

4571#if _GLIBCXX_HOSTED1
/**
 *  @brief Randomly shuffle the elements of a sequence.
 *  @ingroup mutating_algorithms
 *  @param  __first   A forward iterator.
 *  @param  __last    A forward iterator.
 *  @return  Nothing.
 *
 *  Reorder the elements in the range @p [__first,__last) using a random
 *  distribution, so that every possible ordering of the sequence is
 *  equally likely.
*/
template<typename _RandomAccessIterator>
  inline void
  random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
  {
    // concept requirements
    __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
   _RandomAccessIterator>)
    __glibcxx_requires_valid_range(__first, __last);

    if (__first != __last)
for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
 {
   // XXX rand() % N is not uniformly distributed
   _RandomAccessIterator __j = __first
			+ std::rand() % ((__i - __first) + 1);
   if (__i != __j)
     std::iter_swap(__i, __j);
 }
  }
4602#endif

/**
 *  @brief Shuffle the elements of a sequence using a random number
 *         generator.
 *  @ingroup mutating_algorithms
 *  @param  __first   A forward iterator.
 *  @param  __last    A forward iterator.
 *  @param  __rand    The RNG functor or function.
 *  @return  Nothing.
 *
 *  Reorders the elements in the range @p [__first,__last) using @p __rand to
 *  provide a random distribution. Calling @p __rand(N) for a positive
 *  integer @p N should return a randomly chosen integer from the
 *  range [0,N).
*/
template<typename _RandomAccessIterator, typename _RandomNumberGenerator>
  void
  random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4621#if __cplusplus201402L >= 201103L
   _RandomNumberGenerator&& __rand)
4623#else
   _RandomNumberGenerator& __rand)
4625#endif
  {
    // concept requirements
    __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
   _RandomAccessIterator>)
    __glibcxx_requires_valid_range(__first, __last);

    if (__first == __last)
return;
    for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
{
 _RandomAccessIterator __j = __first + __rand((__i - __first) + 1);
 if (__i != __j)
   std::iter_swap(__i, __j);
}
  }


/**
 *  @brief Move elements for which a predicate is true to the beginning
 *         of a sequence.
 *  @ingroup mutating_algorithms
 *  @param  __first   A forward iterator.
 *  @param  __last    A forward iterator.
 *  @param  __pred    A predicate functor.
 *  @return  An iterator @p middle such that @p __pred(i) is true for each
 *  iterator @p i in the range @p [__first,middle) and false for each @p i
 *  in the range @p [middle,__last).
 *
 *  @p __pred must not modify its operand. @p partition() does not preserve
 *  the relative ordering of elements in each group, use
 *  @p stable_partition() if this is needed.
*/
template<typename _ForwardIterator, typename _Predicate>
  _GLIBCXX20_CONSTEXPR
  inline _ForwardIterator
  partition(_ForwardIterator __first, _ForwardIterator __last,
     _Predicate   __pred)
  {
    // concept requirements
    __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
		  _ForwardIterator>)
    __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
   typename iterator_traits<_ForwardIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __last);

    return std::__partition(__first, __last, __pred,
	      std::__iterator_category(__first));
  }


/**
 *  @brief Sort the smallest elements of a sequence.
 *  @ingroup sorting_algorithms
 *  @param  __first   An iterator.
 *  @param  __middle  Another iterator.
 *  @param  __last    Another iterator.
 *  @return  Nothing.
 *
 *  Sorts the smallest @p (__middle-__first) elements in the range
 *  @p [first,last) and moves them to the range @p [__first,__middle). The
 *  order of the remaining elements in the range @p [__middle,__last) is
 *  undefined.
 *  After the sort if @e i and @e j are iterators in the range
 *  @p [__first,__middle) such that i precedes j and @e k is an iterator in
 *  the range @p [__middle,__last) then *j<*i and *k<*i are both false.
*/
template<typename _RandomAccessIterator>
  _GLIBCXX20_CONSTEXPR
  inline void
  partial_sort(_RandomAccessIterator __first,
 _RandomAccessIterator __middle,
 _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, __middle);
    __glibcxx_requires_valid_range(__middle, __last);
    __glibcxx_requires_irreflexive(__first, __last);

    std::__partial_sort(__first, __middle, __last,
	  __gnu_cxx::__ops::__iter_less_iter());
  }

/**
 *  @brief Sort the smallest elements of a sequence using a predicate
 *         for comparison.
 *  @ingroup sorting_algorithms
 *  @param  __first   An iterator.
 *  @param  __middle  Another iterator.
 *  @param  __last    Another iterator.
 *  @param  __comp    A comparison functor.
 *  @return  Nothing.
 *
 *  Sorts the smallest @p (__middle-__first) elements in the range
 *  @p [__first,__last) and moves them to the range @p [__first,__middle). The
 *  order of the remaining elements in the range @p [__middle,__last) is
 *  undefined.
 *  After the sort if @e i and @e j are iterators in the range
 *  @p [__first,__middle) such that i precedes j and @e k is an iterator in
 *  the range @p [__middle,__last) then @p *__comp(j,*i) and @p __comp(*k,*i)
 *  are both false.
*/
template<typename _RandomAccessIterator, typename _Compare>
  _GLIBCXX20_CONSTEXPR
  inline void
  partial_sort(_RandomAccessIterator __first,
 _RandomAccessIterator __middle,
 _RandomAccessIterator __last,
 _Compare __comp)
  {
    // concept requirements
    __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
   _RandomAccessIterator>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
   typename iterator_traits<_RandomAccessIterator>::value_type,
   typename iterator_traits<_RandomAccessIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __middle);
    __glibcxx_requires_valid_range(__middle, __last);
    __glibcxx_requires_irreflexive_pred(__first, __last, __comp);

    std::__partial_sort(__first, __middle, __last,
	  __gnu_cxx::__ops::__iter_comp_iter(__comp));
  }

/**
 *  @brief Sort a sequence just enough to find a particular position.
 *  @ingroup sorting_algorithms
 *  @param  __first   An iterator.
 *  @param  __nth     Another iterator.
 *  @param  __last    Another iterator.
 *  @return  Nothing.
 *
 *  Rearranges the elements in the range @p [__first,__last) so that @p *__nth
 *  is the same element that would have been in that position had the
 *  whole sequence been sorted. The elements either side of @p *__nth are
 *  not completely sorted, but for any iterator @e i in the range
 *  @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it
 *  holds that *j < *i is false.
*/
template<typename _RandomAccessIterator>
  _GLIBCXX20_CONSTEXPR
  inline void
  nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
_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, __nth);
    __glibcxx_requires_valid_range(__nth, __last);
    __glibcxx_requires_irreflexive(__first, __last);

    if (__first == __last || __nth == __last)
return;

    std::__introselect(__first, __nth, __last,
	 std::__lg(__last - __first) * 2,
	 __gnu_cxx::__ops::__iter_less_iter());
  }

/**
 *  @brief Sort a sequence just enough to find a particular position
 *         using a predicate for comparison.
 *  @ingroup sorting_algorithms
 *  @param  __first   An iterator.
 *  @param  __nth     Another iterator.
 *  @param  __last    Another iterator.
 *  @param  __comp    A comparison functor.
 *  @return  Nothing.
 *
 *  Rearranges the elements in the range @p [__first,__last) so that @p *__nth
 *  is the same element that would have been in that position had the
 *  whole sequence been sorted. The elements either side of @p *__nth are
 *  not completely sorted, but for any iterator @e i in the range
 *  @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it
 *  holds that @p __comp(*j,*i) is false.
*/
template<typename _RandomAccessIterator, typename _Compare>
  _GLIBCXX20_CONSTEXPR
  inline void
  nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
_RandomAccessIterator __last, _Compare __comp)
  {
    // concept requirements
    __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
		  _RandomAccessIterator>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
   typename iterator_traits<_RandomAccessIterator>::value_type,
   typename iterator_traits<_RandomAccessIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __nth);
    __glibcxx_requires_valid_range(__nth, __last);
    __glibcxx_requires_irreflexive_pred(__first, __last, __comp);

    if (__first == __last || __nth == __last)
return;

    std::__introselect(__first, __nth, __last,
	 std::__lg(__last - __first) * 2,
	 __gnu_cxx::__ops::__iter_comp_iter(__comp));
  }

/**
 *  @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>
  _GLIBCXX20_CONSTEXPR
  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());
43
←
Calling '__sort<unsigned short *, __gnu_cxx::__ops::_Iter_less_iter>'→
  }

/**
 *  @brief Sort the elements of a sequence using a predicate for comparison.
 *  @ingroup sorting_algorithms
 *  @param  __first   An iterator.
 *  @param  __last    Another iterator.
 *  @param  __comp    A comparison functor.
 *  @return  Nothing.
 *
 *  Sorts the elements in the range @p [__first,__last) in ascending order,
 *  such that @p __comp(*(i+1),*i) is false for every iterator @e i in the
 *  range @p [__first,__last-1).
 *
 *  The relative ordering of equivalent elements is not preserved, use
 *  @p stable_sort() if this is needed.
*/
template<typename _RandomAccessIterator, typename _Compare>
  _GLIBCXX20_CONSTEXPR
  inline void
  sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
  {
    // concept requirements
    __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
   _RandomAccessIterator>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
   typename iterator_traits<_RandomAccessIterator>::value_type,
   typename iterator_traits<_RandomAccessIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __last);
    __glibcxx_requires_irreflexive_pred(__first, __last, __comp);

    std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
  }

template<typename _InputIterator1, typename _InputIterator2,
  typename _OutputIterator, typename _Compare>
  _GLIBCXX20_CONSTEXPR
  _OutputIterator
  __merge(_InputIterator1 __first1, _InputIterator1 __last1,
   _InputIterator2 __first2, _InputIterator2 __last2,
   _OutputIterator __result, _Compare __comp)
  {
    while (__first1 != __last1 && __first2 != __last2)
{
 if (__comp(__first2, __first1))
   {
     *__result = *__first2;
     ++__first2;
   }
 else
   {
     *__result = *__first1;
     ++__first1;
   }
 ++__result;
}
    return std::copy(__first2, __last2,
       std::copy(__first1, __last1, __result));
  }

/**
 *  @brief Merges two sorted ranges.
 *  @ingroup sorting_algorithms
 *  @param  __first1  An iterator.
 *  @param  __first2  Another iterator.
 *  @param  __last1   Another iterator.
 *  @param  __last2   Another iterator.
 *  @param  __result  An iterator pointing to the end of the merged range.
 *  @return   An output iterator equal to @p __result + (__last1 - __first1)
 *            + (__last2 - __first2).
 *
 *  Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
 *  the sorted range @p [__result, __result + (__last1-__first1) +
 *  (__last2-__first2)).  Both input ranges must be sorted, and the
 *  output range must not overlap with either of the input ranges.
 *  The sort is @e stable, that is, for equivalent elements in the
 *  two ranges, elements from the first range will always come
 *  before elements from the second.
*/
template<typename _InputIterator1, typename _InputIterator2,
  typename _OutputIterator>
  _GLIBCXX20_CONSTEXPR
  inline _OutputIterator
  merge(_InputIterator1 __first1, _InputIterator1 __last1,
 _InputIterator2 __first2, _InputIterator2 __last2,
 _OutputIterator __result)
  {
    // concept requirements
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
    __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
   typename iterator_traits<_InputIterator1>::value_type>)
    __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
   typename iterator_traits<_InputIterator2>::value_type>)
    __glibcxx_function_requires(_LessThanOpConcept<
   typename iterator_traits<_InputIterator2>::value_type,
   typename iterator_traits<_InputIterator1>::value_type>)	
    __glibcxx_requires_sorted_set(__first1, __last1, __first2);
    __glibcxx_requires_sorted_set(__first2, __last2, __first1);
    __glibcxx_requires_irreflexive2(__first1, __last1);
    __glibcxx_requires_irreflexive2(__first2, __last2);

    return _GLIBCXX_STD_Astd::__merge(__first1, __last1,
		     __first2, __last2, __result,
		     __gnu_cxx::__ops::__iter_less_iter());
  }

/**
 *  @brief Merges two sorted ranges.
 *  @ingroup sorting_algorithms
 *  @param  __first1  An iterator.
 *  @param  __first2  Another iterator.
 *  @param  __last1   Another iterator.
 *  @param  __last2   Another iterator.
 *  @param  __result  An iterator pointing to the end of the merged range.
 *  @param  __comp    A functor to use for comparisons.
 *  @return   An output iterator equal to @p __result + (__last1 - __first1)
 *            + (__last2 - __first2).
 *
 *  Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
 *  the sorted range @p [__result, __result + (__last1-__first1) +
 *  (__last2-__first2)).  Both input ranges must be sorted, and the
 *  output range must not overlap with either of the input ranges.
 *  The sort is @e stable, that is, for equivalent elements in the
 *  two ranges, elements from the first range will always come
 *  before elements from the second.
 *
 *  The comparison function should have the same effects on ordering as
 *  the function used for the initial sort.
*/
template<typename _InputIterator1, typename _InputIterator2,
  typename _OutputIterator, typename _Compare>
  _GLIBCXX20_CONSTEXPR
  inline _OutputIterator
  merge(_InputIterator1 __first1, _InputIterator1 __last1,
 _InputIterator2 __first2, _InputIterator2 __last2,
 _OutputIterator __result, _Compare __comp)
  {
    // concept requirements
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
    __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
   typename iterator_traits<_InputIterator1>::value_type>)
    __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
   typename iterator_traits<_InputIterator2>::value_type>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
   typename iterator_traits<_InputIterator2>::value_type,
   typename iterator_traits<_InputIterator1>::value_type>)
    __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
    __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
    __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
    __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);

    return _GLIBCXX_STD_Astd::__merge(__first1, __last1,
		__first2, __last2, __result,
		__gnu_cxx::__ops::__iter_comp_iter(__comp));
  }

template<typename _RandomAccessIterator, typename _Compare>
  inline void
  __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
  _Compare __comp)
  {
    typedef typename iterator_traits<_RandomAccessIterator>::value_type
_ValueType;
    typedef typename iterator_traits<_RandomAccessIterator>::difference_type
_DistanceType;

    typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
    _TmpBuf __buf(__first, std::distance(__first, __last));

    if (__buf.begin() == 0)
std::__inplace_stable_sort(__first, __last, __comp);
    else
std::__stable_sort_adaptive(__first, __last, __buf.begin(),
		    _DistanceType(__buf.size()), __comp);
  }

/**
 *  @brief Sort the elements of a sequence, preserving the relative order
 *         of equivalent elements.
 *  @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 @p i in the range @p [__first,__last-1),
 *  @p *(i+1)<*i is false.
 *
 *  The relative ordering of equivalent elements is preserved, so any two
 *  elements @p x and @p y in the range @p [__first,__last) such that
 *  @p x<y is false and @p y<x is false will have the same relative
 *  ordering after calling @p stable_sort().
*/
template<typename _RandomAccessIterator>
  inline void
  stable_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);

    _GLIBCXX_STD_Astd::__stable_sort(__first, __last,
		    __gnu_cxx::__ops::__iter_less_iter());
  }

/**
 *  @brief Sort the elements of a sequence using a predicate for comparison,
 *         preserving the relative order of equivalent elements.
 *  @ingroup sorting_algorithms
 *  @param  __first   An iterator.
 *  @param  __last    Another iterator.
 *  @param  __comp    A comparison functor.
 *  @return  Nothing.
 *
 *  Sorts the elements in the range @p [__first,__last) in ascending order,
 *  such that for each iterator @p i in the range @p [__first,__last-1),
 *  @p __comp(*(i+1),*i) is false.
 *
 *  The relative ordering of equivalent elements is preserved, so any two
 *  elements @p x and @p y in the range @p [__first,__last) such that
 *  @p __comp(x,y) is false and @p __comp(y,x) is false will have the same
 *  relative ordering after calling @p stable_sort().
*/
template<typename _RandomAccessIterator, typename _Compare>
  inline void
  stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
  {
    // concept requirements
    __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
   _RandomAccessIterator>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
   typename iterator_traits<_RandomAccessIterator>::value_type,
   typename iterator_traits<_RandomAccessIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __last);
    __glibcxx_requires_irreflexive_pred(__first, __last, __comp);

    _GLIBCXX_STD_Astd::__stable_sort(__first, __last,
		    __gnu_cxx::__ops::__iter_comp_iter(__comp));
  }

template<typename _InputIterator1, typename _InputIterator2,
  typename _OutputIterator,
  typename _Compare>
  _GLIBCXX20_CONSTEXPR
  _OutputIterator
  __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2,
_OutputIterator __result, _Compare __comp)
  {
    while (__first1 != __last1 && __first2 != __last2)
{
 if (__comp(__first1, __first2))
   {
     *__result = *__first1;
     ++__first1;
   }
 else if (__comp(__first2, __first1))
   {
     *__result = *__first2;
     ++__first2;
   }
 else
   {
     *__result = *__first1;
     ++__first1;
     ++__first2;
   }
 ++__result;
}
    return std::copy(__first2, __last2,
       std::copy(__first1, __last1, __result));
  }

/**
 *  @brief Return the union of two sorted ranges.
 *  @ingroup set_algorithms
 *  @param  __first1  Start of first range.
 *  @param  __last1   End of first range.
 *  @param  __first2  Start of second range.
 *  @param  __last2   End of second range.
 *  @param  __result  Start of output range.
 *  @return  End of the output range.
 *  @ingroup set_algorithms
 *
 *  This operation iterates over both ranges, copying elements present in
 *  each range in order to the output range.  Iterators increment for each
 *  range.  When the current element of one range is less than the other,
 *  that element is copied and the iterator advanced.  If an element is
 *  contained in both ranges, the element from the first range is copied and
 *  both ranges advance.  The output range may not overlap either input
 *  range.
*/
template<typename _InputIterator1, typename _InputIterator2,
  typename _OutputIterator>
  _GLIBCXX20_CONSTEXPR
  inline _OutputIterator
  set_union(_InputIterator1 __first1, _InputIterator1 __last1,
     _InputIterator2 __first2, _InputIterator2 __last2,
     _OutputIterator __result)
  {
    // concept requirements
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
    __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
   typename iterator_traits<_InputIterator1>::value_type>)
    __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
   typename iterator_traits<_InputIterator2>::value_type>)
    __glibcxx_function_requires(_LessThanOpConcept<
   typename iterator_traits<_InputIterator1>::value_type,
   typename iterator_traits<_InputIterator2>::value_type>)
    __glibcxx_function_requires(_LessThanOpConcept<
   typename iterator_traits<_InputIterator2>::value_type,
   typename iterator_traits<_InputIterator1>::value_type>)
    __glibcxx_requires_sorted_set(__first1, __last1, __first2);
    __glibcxx_requires_sorted_set(__first2, __last2, __first1);
    __glibcxx_requires_irreflexive2(__first1, __last1);
    __glibcxx_requires_irreflexive2(__first2, __last2);

    return _GLIBCXX_STD_Astd::__set_union(__first1, __last1,
		__first2, __last2, __result,
		__gnu_cxx::__ops::__iter_less_iter());
  }

/**
 *  @brief Return the union of two sorted ranges using a comparison functor.
 *  @ingroup set_algorithms
 *  @param  __first1  Start of first range.
 *  @param  __last1   End of first range.
 *  @param  __first2  Start of second range.
 *  @param  __last2   End of second range.
 *  @param  __result  Start of output range.
 *  @param  __comp    The comparison functor.
 *  @return  End of the output range.
 *  @ingroup set_algorithms
 *
 *  This operation iterates over both ranges, copying elements present in
 *  each range in order to the output range.  Iterators increment for each
 *  range.  When the current element of one range is less than the other
 *  according to @p __comp, that element is copied and the iterator advanced.
 *  If an equivalent element according to @p __comp is contained in both
 *  ranges, the element from the first range is copied and both ranges
 *  advance.  The output range may not overlap either input range.
*/
template<typename _InputIterator1, typename _InputIterator2,
  typename _OutputIterator, typename _Compare>
  _GLIBCXX20_CONSTEXPR
  inline _OutputIterator
  set_union(_InputIterator1 __first1, _InputIterator1 __last1,
     _InputIterator2 __first2, _InputIterator2 __last2,
     _OutputIterator __result, _Compare __comp)
  {
    // concept requirements
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
    __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
   typename iterator_traits<_InputIterator1>::value_type>)
    __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
   typename iterator_traits<_InputIterator2>::value_type>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
   typename iterator_traits<_InputIterator1>::value_type,
   typename iterator_traits<_InputIterator2>::value_type>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
   typename iterator_traits<_InputIterator2>::value_type,
   typename iterator_traits<_InputIterator1>::value_type>)
    __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
    __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
    __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
    __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);

    return _GLIBCXX_STD_Astd::__set_union(__first1, __last1,
		__first2, __last2, __result,
		__gnu_cxx::__ops::__iter_comp_iter(__comp));
  }

template<typename _InputIterator1, typename _InputIterator2,
  typename _OutputIterator,
  typename _Compare>
  _GLIBCXX20_CONSTEXPR
  _OutputIterator
  __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
       _InputIterator2 __first2, _InputIterator2 __last2,
       _OutputIterator __result, _Compare __comp)
  {
    while (__first1 != __last1 && __first2 != __last2)
if (__comp(__first1, __first2))
 ++__first1;
else if (__comp(__first2, __first1))
 ++__first2;
else
 {
   *__result = *__first1;
   ++__first1;
   ++__first2;
   ++__result;
 }
    return __result;
  }

/**
 *  @brief Return the intersection of two sorted ranges.
 *  @ingroup set_algorithms
 *  @param  __first1  Start of first range.
 *  @param  __last1   End of first range.
 *  @param  __first2  Start of second range.
 *  @param  __last2   End of second range.
 *  @param  __result  Start of output range.
 *  @return  End of the output range.
 *  @ingroup set_algorithms
 *
 *  This operation iterates over both ranges, copying elements present in
 *  both ranges in order to the output range.  Iterators increment for each
 *  range.  When the current element of one range is less than the other,
 *  that iterator advances.  If an element is contained in both ranges, the
 *  element from the first range is copied and both ranges advance.  The
 *  output range may not overlap either input range.
*/
template<typename _InputIterator1, typename _InputIterator2,
  typename _OutputIterator>
  _GLIBCXX20_CONSTEXPR
  inline _OutputIterator
  set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
     _InputIterator2 __first2, _InputIterator2 __last2,
     _OutputIterator __result)
  {
    // concept requirements
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
    __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
   typename iterator_traits<_InputIterator1>::value_type>)
    __glibcxx_function_requires(_LessThanOpConcept<
   typename iterator_traits<_InputIterator1>::value_type,
   typename iterator_traits<_InputIterator2>::value_type>)
    __glibcxx_function_requires(_LessThanOpConcept<
   typename iterator_traits<_InputIterator2>::value_type,
   typename iterator_traits<_InputIterator1>::value_type>)
    __glibcxx_requires_sorted_set(__first1, __last1, __first2);
    __glibcxx_requires_sorted_set(__first2, __last2, __first1);
    __glibcxx_requires_irreflexive2(__first1, __last1);
    __glibcxx_requires_irreflexive2(__first2, __last2);

    return _GLIBCXX_STD_Astd::__set_intersection(__first1, __last1,
		     __first2, __last2, __result,
		     __gnu_cxx::__ops::__iter_less_iter());
  }

/**
 *  @brief Return the intersection of two sorted ranges using comparison
 *  functor.
 *  @ingroup set_algorithms
 *  @param  __first1  Start of first range.
 *  @param  __last1   End of first range.
 *  @param  __first2  Start of second range.
 *  @param  __last2   End of second range.
 *  @param  __result  Start of output range.
 *  @param  __comp    The comparison functor.
 *  @return  End of the output range.
 *  @ingroup set_algorithms
 *
 *  This operation iterates over both ranges, copying elements present in
 *  both ranges in order to the output range.  Iterators increment for each
 *  range.  When the current element of one range is less than the other
 *  according to @p __comp, that iterator advances.  If an element is
 *  contained in both ranges according to @p __comp, the element from the
 *  first range is copied and both ranges advance.  The output range may not
 *  overlap either input range.
*/
template<typename _InputIterator1, typename _InputIterator2,
  typename _OutputIterator, typename _Compare>
  _GLIBCXX20_CONSTEXPR
  inline _OutputIterator
  set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
     _InputIterator2 __first2, _InputIterator2 __last2,
     _OutputIterator __result, _Compare __comp)
  {
    // concept requirements
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
    __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
   typename iterator_traits<_InputIterator1>::value_type>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
   typename iterator_traits<_InputIterator1>::value_type,
   typename iterator_traits<_InputIterator2>::value_type>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
   typename iterator_traits<_InputIterator2>::value_type,
   typename iterator_traits<_InputIterator1>::value_type>)
    __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
    __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
    __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
    __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);

    return _GLIBCXX_STD_Astd::__set_intersection(__first1, __last1,
		__first2, __last2, __result,
		__gnu_cxx::__ops::__iter_comp_iter(__comp));
  }

template<typename _InputIterator1, typename _InputIterator2,
  typename _OutputIterator,
  typename _Compare>
  _GLIBCXX20_CONSTEXPR
  _OutputIterator
  __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
     _InputIterator2 __first2, _InputIterator2 __last2,
     _OutputIterator __result, _Compare __comp)
  {
    while (__first1 != __last1 && __first2 != __last2)
if (__comp(__first1, __first2))
 {
   *__result = *__first1;
   ++__first1;
   ++__result;
 }
else if (__comp(__first2, __first1))
 ++__first2;
else
 {
   ++__first1;
   ++__first2;
 }
    return std::copy(__first1, __last1, __result);
  }

/**
 *  @brief Return the difference of two sorted ranges.
 *  @ingroup set_algorithms
 *  @param  __first1  Start of first range.
 *  @param  __last1   End of first range.
 *  @param  __first2  Start of second range.
 *  @param  __last2   End of second range.
 *  @param  __result  Start of output range.
 *  @return  End of the output range.
 *  @ingroup set_algorithms
 *
 *  This operation iterates over both ranges, copying elements present in
 *  the first range but not the second in order to the output range.
 *  Iterators increment for each range.  When the current element of the
 *  first range is less than the second, that element is copied and the
 *  iterator advances.  If the current element of the second range is less,
 *  the iterator advances, but no element is copied.  If an element is
 *  contained in both ranges, no elements are copied and both ranges
 *  advance.  The output range may not overlap either input range.
*/
template<typename _InputIterator1, typename _InputIterator2,
  typename _OutputIterator>
  _GLIBCXX20_CONSTEXPR
  inline _OutputIterator
  set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
   _InputIterator2 __first2, _InputIterator2 __last2,
   _OutputIterator __result)
  {
    // concept requirements
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
    __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
   typename iterator_traits<_InputIterator1>::value_type>)
    __glibcxx_function_requires(_LessThanOpConcept<
   typename iterator_traits<_InputIterator1>::value_type,
   typename iterator_traits<_InputIterator2>::value_type>)
    __glibcxx_function_requires(_LessThanOpConcept<
   typename iterator_traits<_InputIterator2>::value_type,
   typename iterator_traits<_InputIterator1>::value_type>)	
    __glibcxx_requires_sorted_set(__first1, __last1, __first2);
    __glibcxx_requires_sorted_set(__first2, __last2, __first1);
    __glibcxx_requires_irreflexive2(__first1, __last1);
    __glibcxx_requires_irreflexive2(__first2, __last2);

    return _GLIBCXX_STD_Astd::__set_difference(__first1, __last1,
		   __first2, __last2, __result,
		   __gnu_cxx::__ops::__iter_less_iter());
  }

/**
 *  @brief  Return the difference of two sorted ranges using comparison
 *  functor.
 *  @ingroup set_algorithms
 *  @param  __first1  Start of first range.
 *  @param  __last1   End of first range.
 *  @param  __first2  Start of second range.
 *  @param  __last2   End of second range.
 *  @param  __result  Start of output range.
 *  @param  __comp    The comparison functor.
 *  @return  End of the output range.
 *  @ingroup set_algorithms
 *
 *  This operation iterates over both ranges, copying elements present in
 *  the first range but not the second in order to the output range.
 *  Iterators increment for each range.  When the current element of the
 *  first range is less than the second according to @p __comp, that element
 *  is copied and the iterator advances.  If the current element of the
 *  second range is less, no element is copied and the iterator advances.
 *  If an element is contained in both ranges according to @p __comp, no
 *  elements are copied and both ranges advance.  The output range may not
 *  overlap either input range.
*/
template<typename _InputIterator1, typename _InputIterator2,
  typename _OutputIterator, typename _Compare>
  _GLIBCXX20_CONSTEXPR
  inline _OutputIterator
  set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
   _InputIterator2 __first2, _InputIterator2 __last2,
   _OutputIterator __result, _Compare __comp)
  {
    // concept requirements
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
    __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
   typename iterator_traits<_InputIterator1>::value_type>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
   typename iterator_traits<_InputIterator1>::value_type,
   typename iterator_traits<_InputIterator2>::value_type>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
   typename iterator_traits<_InputIterator2>::value_type,
   typename iterator_traits<_InputIterator1>::value_type>)
    __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
    __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
    __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
    __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);

    return _GLIBCXX_STD_Astd::__set_difference(__first1, __last1,
		   __first2, __last2, __result,
		   __gnu_cxx::__ops::__iter_comp_iter(__comp));
  }

template<typename _InputIterator1, typename _InputIterator2,
  typename _OutputIterator,
  typename _Compare>
  _GLIBCXX20_CONSTEXPR
  _OutputIterator
  __set_symmetric_difference(_InputIterator1 __first1,
	       _InputIterator1 __last1,
	       _InputIterator2 __first2,
	       _InputIterator2 __last2,
	       _OutputIterator __result,
	       _Compare __comp)
  {
    while (__first1 != __last1 && __first2 != __last2)
if (__comp(__first1, __first2))
 {
   *__result = *__first1;
   ++__first1;
   ++__result;
 }
else if (__comp(__first2, __first1))
 {
   *__result = *__first2;
   ++__first2;
   ++__result;
 }
else
 {
   ++__first1;
   ++__first2;
 }
    return std::copy(__first2, __last2, 
       std::copy(__first1, __last1, __result));
  }

/**
 *  @brief  Return the symmetric difference of two sorted ranges.
 *  @ingroup set_algorithms
 *  @param  __first1  Start of first range.
 *  @param  __last1   End of first range.
 *  @param  __first2  Start of second range.
 *  @param  __last2   End of second range.
 *  @param  __result  Start of output range.
 *  @return  End of the output range.
 *  @ingroup set_algorithms
 *
 *  This operation iterates over both ranges, copying elements present in
 *  one range but not the other in order to the output range.  Iterators
 *  increment for each range.  When the current element of one range is less
 *  than the other, that element is copied and the iterator advances.  If an
 *  element is contained in both ranges, no elements are copied and both
 *  ranges advance.  The output range may not overlap either input range.
*/
template<typename _InputIterator1, typename _InputIterator2,
  typename _OutputIterator>
  _GLIBCXX20_CONSTEXPR
  inline _OutputIterator
  set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
	     _InputIterator2 __first2, _InputIterator2 __last2,
	     _OutputIterator __result)
  {
    // concept requirements
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
    __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
   typename iterator_traits<_InputIterator1>::value_type>)
    __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
   typename iterator_traits<_InputIterator2>::value_type>)
    __glibcxx_function_requires(_LessThanOpConcept<
   typename iterator_traits<_InputIterator1>::value_type,
   typename iterator_traits<_InputIterator2>::value_type>)
    __glibcxx_function_requires(_LessThanOpConcept<
   typename iterator_traits<_InputIterator2>::value_type,
   typename iterator_traits<_InputIterator1>::value_type>)	
    __glibcxx_requires_sorted_set(__first1, __last1, __first2);
    __glibcxx_requires_sorted_set(__first2, __last2, __first1);
    __glibcxx_requires_irreflexive2(__first1, __last1);
    __glibcxx_requires_irreflexive2(__first2, __last2);

    return _GLIBCXX_STD_Astd::__set_symmetric_difference(__first1, __last1,
			__first2, __last2, __result,
			__gnu_cxx::__ops::__iter_less_iter());
  }

/**
 *  @brief  Return the symmetric difference of two sorted ranges using
 *  comparison functor.
 *  @ingroup set_algorithms
 *  @param  __first1  Start of first range.
 *  @param  __last1   End of first range.
 *  @param  __first2  Start of second range.
 *  @param  __last2   End of second range.
 *  @param  __result  Start of output range.
 *  @param  __comp    The comparison functor.
 *  @return  End of the output range.
 *  @ingroup set_algorithms
 *
 *  This operation iterates over both ranges, copying elements present in
 *  one range but not the other in order to the output range.  Iterators
 *  increment for each range.  When the current element of one range is less
 *  than the other according to @p comp, that element is copied and the
 *  iterator advances.  If an element is contained in both ranges according
 *  to @p __comp, no elements are copied and both ranges advance.  The output
 *  range may not overlap either input range.
*/
template<typename _InputIterator1, typename _InputIterator2,
  typename _OutputIterator, typename _Compare>
  _GLIBCXX20_CONSTEXPR
  inline _OutputIterator
  set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
	     _InputIterator2 __first2, _InputIterator2 __last2,
	     _OutputIterator __result,
	     _Compare __comp)
  {
    // concept requirements
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
    __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
   typename iterator_traits<_InputIterator1>::value_type>)
    __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
   typename iterator_traits<_InputIterator2>::value_type>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
   typename iterator_traits<_InputIterator1>::value_type,
   typename iterator_traits<_InputIterator2>::value_type>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
   typename iterator_traits<_InputIterator2>::value_type,
   typename iterator_traits<_InputIterator1>::value_type>)
    __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
    __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
    __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
    __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);

    return _GLIBCXX_STD_Astd::__set_symmetric_difference(__first1, __last1,
		__first2, __last2, __result,
		__gnu_cxx::__ops::__iter_comp_iter(__comp));
  }

template<typename _ForwardIterator, typename _Compare>
  _GLIBCXX14_CONSTEXPRconstexpr
  _ForwardIterator
  __min_element(_ForwardIterator __first, _ForwardIterator __last,
  _Compare __comp)
  {
    if (__first == __last)
return __first;
    _ForwardIterator __result = __first;
    while (++__first != __last)
if (__comp(__first, __result))
 __result = __first;
    return __result;
  }

/**
 *  @brief  Return the minimum element in a range.
 *  @ingroup sorting_algorithms
 *  @param  __first  Start of range.
 *  @param  __last   End of range.
 *  @return  Iterator referencing the first instance of the smallest value.
*/
template<typename _ForwardIterator>
  _GLIBCXX14_CONSTEXPRconstexpr
  _ForwardIterator
  inline min_element(_ForwardIterator __first, _ForwardIterator __last)
  {
    // concept requirements
    __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
    __glibcxx_function_requires(_LessThanComparableConcept<
   typename iterator_traits<_ForwardIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __last);
    __glibcxx_requires_irreflexive(__first, __last);

    return _GLIBCXX_STD_Astd::__min_element(__first, __last,
		__gnu_cxx::__ops::__iter_less_iter());
  }

/**
 *  @brief  Return the minimum element in a range using comparison functor.
 *  @ingroup sorting_algorithms
 *  @param  __first  Start of range.
 *  @param  __last   End of range.
 *  @param  __comp   Comparison functor.
 *  @return  Iterator referencing the first instance of the smallest value
 *  according to __comp.
*/
template<typename _ForwardIterator, typename _Compare>
  _GLIBCXX14_CONSTEXPRconstexpr
  inline _ForwardIterator
  min_element(_ForwardIterator __first, _ForwardIterator __last,
_Compare __comp)
  {
    // concept requirements
    __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
   typename iterator_traits<_ForwardIterator>::value_type,
   typename iterator_traits<_ForwardIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __last);
    __glibcxx_requires_irreflexive_pred(__first, __last, __comp);

    return _GLIBCXX_STD_Astd::__min_element(__first, __last,
		__gnu_cxx::__ops::__iter_comp_iter(__comp));
  }

template<typename _ForwardIterator, typename _Compare>
  _GLIBCXX14_CONSTEXPRconstexpr
  _ForwardIterator
  __max_element(_ForwardIterator __first, _ForwardIterator __last,
  _Compare __comp)
  {
    if (__first == __last) return __first;
    _ForwardIterator __result = __first;
    while (++__first != __last)
if (__comp(__result, __first))
 __result = __first;
    return __result;
  }

/**
 *  @brief  Return the maximum element in a range.
 *  @ingroup sorting_algorithms
 *  @param  __first  Start of range.
 *  @param  __last   End of range.
 *  @return  Iterator referencing the first instance of the largest value.
*/
template<typename _ForwardIterator>
  _GLIBCXX14_CONSTEXPRconstexpr
  inline _ForwardIterator
  max_element(_ForwardIterator __first, _ForwardIterator __last)
  {
    // concept requirements
    __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
    __glibcxx_function_requires(_LessThanComparableConcept<
   typename iterator_traits<_ForwardIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __last);
    __glibcxx_requires_irreflexive(__first, __last);

    return _GLIBCXX_STD_Astd::__max_element(__first, __last,
		__gnu_cxx::__ops::__iter_less_iter());
  }

/**
 *  @brief  Return the maximum element in a range using comparison functor.
 *  @ingroup sorting_algorithms
 *  @param  __first  Start of range.
 *  @param  __last   End of range.
 *  @param  __comp   Comparison functor.
 *  @return  Iterator referencing the first instance of the largest value
 *  according to __comp.
*/
template<typename _ForwardIterator, typename _Compare>
  _GLIBCXX14_CONSTEXPRconstexpr
  inline _ForwardIterator
  max_element(_ForwardIterator __first, _ForwardIterator __last,
_Compare __comp)
  {
    // concept requirements
    __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
   typename iterator_traits<_ForwardIterator>::value_type,
   typename iterator_traits<_ForwardIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __last);
    __glibcxx_requires_irreflexive_pred(__first, __last, __comp);

    return _GLIBCXX_STD_Astd::__max_element(__first, __last,
		__gnu_cxx::__ops::__iter_comp_iter(__comp));
  }

5755#if __cplusplus201402L >= 201402L
/// Reservoir sampling algorithm.
template<typename _InputIterator, typename _RandomAccessIterator,
         typename _Size, typename _UniformRandomBitGenerator>
  _RandomAccessIterator
  __sample(_InputIterator __first, _InputIterator __last, input_iterator_tag,
    _RandomAccessIterator __out, random_access_iterator_tag,
    _Size __n, _UniformRandomBitGenerator&& __g)
  {
    using __distrib_type = uniform_int_distribution<_Size>;
    using __param_type = typename __distrib_type::param_type;
    __distrib_type __d{};
    _Size __sample_sz = 0;
    while (__first != __last && __sample_sz != __n)
{
 __out[__sample_sz++] = *__first;
 ++__first;
}
    for (auto __pop_sz = __sample_sz; __first != __last;
 ++__first, (void) ++__pop_sz)
{
 const auto __k = __d(__g, __param_type{0, __pop_sz});
 if (__k < __n)
   __out[__k] = *__first;
}
    return __out + __sample_sz;
  }

/// Selection sampling algorithm.
template<typename _ForwardIterator, typename _OutputIterator, typename _Cat,
         typename _Size, typename _UniformRandomBitGenerator>
  _OutputIterator
  __sample(_ForwardIterator __first, _ForwardIterator __last,
    forward_iterator_tag,
    _OutputIterator __out, _Cat,
    _Size __n, _UniformRandomBitGenerator&& __g)
  {
    using __distrib_type = uniform_int_distribution<_Size>;
    using __param_type = typename __distrib_type::param_type;
    using _USize = make_unsigned_t<_Size>;
    using _Gen = remove_reference_t<_UniformRandomBitGenerator>;
    using __uc_type = common_type_t<typename _Gen::result_type, _USize>;

    __distrib_type __d{};
    _Size __unsampled_sz = std::distance(__first, __last);
    __n = std::min(__n, __unsampled_sz);

    // If possible, we use __gen_two_uniform_ints to efficiently produce
    // two random numbers using a single distribution invocation:

    const __uc_type __urngrange = __g.max() - __g.min();
    if (__urngrange / __uc_type(__unsampled_sz) >= __uc_type(__unsampled_sz))
      // I.e. (__urngrange >= __unsampled_sz * __unsampled_sz) but without
// wrapping issues.
      {
 while (__n != 0 && __unsampled_sz >= 2)
   {
     const pair<_Size, _Size> __p =
__gen_two_uniform_ints(__unsampled_sz, __unsampled_sz - 1, __g);

     --__unsampled_sz;
     if (__p.first < __n)
{
  *__out++ = *__first;
  --__n;
}

     ++__first;

     if (__n == 0) break;

     --__unsampled_sz;
     if (__p.second < __n)
{
  *__out++ = *__first;
  --__n;
}

     ++__first;
   }
      }

    // The loop above is otherwise equivalent to this one-at-a-time version:

    for (; __n != 0; ++__first)
if (__d(__g, __param_type{0, --__unsampled_sz}) < __n)
 {
   *__out++ = *__first;
   --__n;
 }
    return __out;
  }

5848#if __cplusplus201402L > 201402L
5849#define __cpp_lib_sample 201603
/// Take a random sample from a population.
template<typename _PopulationIterator, typename _SampleIterator,
         typename _Distance, typename _UniformRandomBitGenerator>
  _SampleIterator
  sample(_PopulationIterator __first, _PopulationIterator __last,
  _SampleIterator __out, _Distance __n,
  _UniformRandomBitGenerator&& __g)
  {
    using __pop_cat = typename
std::iterator_traits<_PopulationIterator>::iterator_category;
    using __samp_cat = typename
std::iterator_traits<_SampleIterator>::iterator_category;

    static_assert(
 __or_<is_convertible<__pop_cat, forward_iterator_tag>,
is_convertible<__samp_cat, random_access_iterator_tag>>::value,
 "output range must use a RandomAccessIterator when input range"
 " does not meet the ForwardIterator requirements");

    static_assert(is_integral<_Distance>::value,
    "sample size must be an integer type");

    typename iterator_traits<_PopulationIterator>::difference_type __d = __n;
    return _GLIBCXX_STD_Astd::
__sample(__first, __last, __pop_cat{}, __out, __samp_cat{}, __d,
 std::forward<_UniformRandomBitGenerator>(__g));
  }
5877#endif // C++17
5878#endif // C++14

5880_GLIBCXX_END_NAMESPACE_ALGO
5881_GLIBCXX_END_NAMESPACE_VERSION
5882} // namespace std

5884#endif /* _STL_ALGO_H */

←

/usr/bin/../lib/gcc/x86_64-redhat-linux/10/../../../../include/c++/10/bits/predefined_ops.h

1// Default predicates for internal use -*- C++ -*-

3// Copyright (C) 2013-2020 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library.  This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.

11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14// GNU General Public License for more details.

16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.

20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23// <http://www.gnu.org/licenses/>.

25/** @file predefined_ops.h
*  This is an internal header file, included by other library headers.
*  You should not attempt to use it directly. @headername{algorithm}
*/

30#ifndef _GLIBCXX_PREDEFINED_OPS_H1
31#define _GLIBCXX_PREDEFINED_OPS_H1	1

33namespace __gnu_cxx
34{
35namespace __ops
36{
struct _Iter_less_iter
{
  template<typename _Iterator1, typename _Iterator2>
    _GLIBCXX14_CONSTEXPRconstexpr
    bool
    operator()(_Iterator1 __it1, _Iterator2 __it2) const
    { return *__it1 < *__it2; }
54
←
The left operand of '<' is a garbage value
};

_GLIBCXX14_CONSTEXPRconstexpr
inline _Iter_less_iter
__iter_less_iter()
{ return _Iter_less_iter(); }

struct _Iter_less_val
{
53#if __cplusplus201402L >= 201103L
  constexpr _Iter_less_val() = default;
55#else
  _Iter_less_val() { }
57#endif

  _GLIBCXX20_CONSTEXPR
  explicit
  _Iter_less_val(_Iter_less_iter) { }

  template<typename _Iterator, typename _Value>
    _GLIBCXX20_CONSTEXPR
    bool
    operator()(_Iterator __it, _Value& __val) const
    { return *__it < __val; }
};

_GLIBCXX20_CONSTEXPR
inline _Iter_less_val
__iter_less_val()
{ return _Iter_less_val(); }

_GLIBCXX20_CONSTEXPR
inline _Iter_less_val
__iter_comp_val(_Iter_less_iter)
{ return _Iter_less_val(); }

struct _Val_less_iter
{
82#if __cplusplus201402L >= 201103L
  constexpr _Val_less_iter() = default;
84#else
  _Val_less_iter() { }
86#endif

  _GLIBCXX20_CONSTEXPR
  explicit
  _Val_less_iter(_Iter_less_iter) { }

  template<typename _Value, typename _Iterator>
    _GLIBCXX20_CONSTEXPR
    bool
    operator()(_Value& __val, _Iterator __it) const
    { return __val < *__it; }
};

_GLIBCXX20_CONSTEXPR
inline _Val_less_iter
__val_less_iter()
{ return _Val_less_iter(); }

_GLIBCXX20_CONSTEXPR
inline _Val_less_iter
__val_comp_iter(_Iter_less_iter)
{ return _Val_less_iter(); }

struct _Iter_equal_to_iter
{
  template<typename _Iterator1, typename _Iterator2>
    _GLIBCXX20_CONSTEXPR
    bool
    operator()(_Iterator1 __it1, _Iterator2 __it2) const
    { return *__it1 == *__it2; }
};

_GLIBCXX20_CONSTEXPR
inline _Iter_equal_to_iter
__iter_equal_to_iter()
{ return _Iter_equal_to_iter(); }

struct _Iter_equal_to_val
{
  template<typename _Iterator, typename _Value>
    _GLIBCXX20_CONSTEXPR
    bool
    operator()(_Iterator __it, _Value& __val) const
    { return *__it == __val; }
};

_GLIBCXX20_CONSTEXPR
inline _Iter_equal_to_val
__iter_equal_to_val()
{ return _Iter_equal_to_val(); }

_GLIBCXX20_CONSTEXPR
inline _Iter_equal_to_val
__iter_comp_val(_Iter_equal_to_iter)
{ return _Iter_equal_to_val(); }

template<typename _Compare>
  struct _Iter_comp_iter
  {
    _Compare _M_comp;

    explicit _GLIBCXX14_CONSTEXPRconstexpr
    _Iter_comp_iter(_Compare __comp)
: _M_comp(_GLIBCXX_MOVE(__comp)std::move(__comp))
    { }

    template<typename _Iterator1, typename _Iterator2>
      _GLIBCXX14_CONSTEXPRconstexpr
      bool
      operator()(_Iterator1 __it1, _Iterator2 __it2)
      { return bool(_M_comp(*__it1, *__it2)); }
  };

template<typename _Compare>
  _GLIBCXX14_CONSTEXPRconstexpr
  inline _Iter_comp_iter<_Compare>
  __iter_comp_iter(_Compare __comp)
  { return _Iter_comp_iter<_Compare>(_GLIBCXX_MOVE(__comp)std::move(__comp)); }

template<typename _Compare>
  struct _Iter_comp_val
  {
    _Compare _M_comp;

    _GLIBCXX20_CONSTEXPR
    explicit
    _Iter_comp_val(_Compare __comp)
: _M_comp(_GLIBCXX_MOVE(__comp)std::move(__comp))
    { }

    _GLIBCXX20_CONSTEXPR
    explicit
    _Iter_comp_val(const _Iter_comp_iter<_Compare>& __comp)
: _M_comp(__comp._M_comp)
    { }

182#if __cplusplus201402L >= 201103L
    _GLIBCXX20_CONSTEXPR
    explicit
    _Iter_comp_val(_Iter_comp_iter<_Compare>&& __comp)
: _M_comp(std::move(__comp._M_comp))
    { }
188#endif

    template<typename _Iterator, typename _Value>
_GLIBCXX20_CONSTEXPR
bool
operator()(_Iterator __it, _Value& __val)
{ return bool(_M_comp(*__it, __val)); }
  };

template<typename _Compare>
  _GLIBCXX20_CONSTEXPR
  inline _Iter_comp_val<_Compare>
  __iter_comp_val(_Compare __comp)
  { return _Iter_comp_val<_Compare>(_GLIBCXX_MOVE(__comp)std::move(__comp)); }

template<typename _Compare>
  _GLIBCXX20_CONSTEXPR
  inline _Iter_comp_val<_Compare>
  __iter_comp_val(_Iter_comp_iter<_Compare> __comp)
  { return _Iter_comp_val<_Compare>(_GLIBCXX_MOVE(__comp)std::move(__comp)); }

template<typename _Compare>
  struct _Val_comp_iter
  {
    _Compare _M_comp;

    _GLIBCXX20_CONSTEXPR
    explicit
    _Val_comp_iter(_Compare __comp)
: _M_comp(_GLIBCXX_MOVE(__comp)std::move(__comp))
    { }

    _GLIBCXX20_CONSTEXPR
    explicit
    _Val_comp_iter(const _Iter_comp_iter<_Compare>& __comp)
: _M_comp(__comp._M_comp)
    { }

226#if __cplusplus201402L >= 201103L
    _GLIBCXX20_CONSTEXPR
    explicit
    _Val_comp_iter(_Iter_comp_iter<_Compare>&& __comp)
: _M_comp(std::move(__comp._M_comp))
    { }
232#endif

    template<typename _Value, typename _Iterator>
_GLIBCXX20_CONSTEXPR
bool
operator()(_Value& __val, _Iterator __it)
{ return bool(_M_comp(__val, *__it)); }
  };

template<typename _Compare>
  _GLIBCXX20_CONSTEXPR
  inline _Val_comp_iter<_Compare>
  __val_comp_iter(_Compare __comp)
  { return _Val_comp_iter<_Compare>(_GLIBCXX_MOVE(__comp)std::move(__comp)); }

template<typename _Compare>
  _GLIBCXX20_CONSTEXPR
  inline _Val_comp_iter<_Compare>
  __val_comp_iter(_Iter_comp_iter<_Compare> __comp)
  { return _Val_comp_iter<_Compare>(_GLIBCXX_MOVE(__comp)std::move(__comp)); }

template<typename _Value>
  struct _Iter_equals_val
  {
    _Value& _M_value;

    _GLIBCXX20_CONSTEXPR
    explicit
    _Iter_equals_val(_Value& __value)
: _M_value(__value)
    { }

    template<typename _Iterator>
_GLIBCXX20_CONSTEXPR
bool
operator()(_Iterator __it)
{ return *__it == _M_value; }
  };

template<typename _Value>
  _GLIBCXX20_CONSTEXPR
  inline _Iter_equals_val<_Value>
  __iter_equals_val(_Value& __val)
  { return _Iter_equals_val<_Value>(__val); }

template<typename _Iterator1>
  struct _Iter_equals_iter
  {
    _Iterator1 _M_it1;

    _GLIBCXX20_CONSTEXPR
    explicit
    _Iter_equals_iter(_Iterator1 __it1)
: _M_it1(__it1)
    { }

    template<typename _Iterator2>
_GLIBCXX20_CONSTEXPR
bool
operator()(_Iterator2 __it2)
{ return *__it2 == *_M_it1; }
  };

template<typename _Iterator>
  _GLIBCXX20_CONSTEXPR
  inline _Iter_equals_iter<_Iterator>
  __iter_comp_iter(_Iter_equal_to_iter, _Iterator __it)
  { return _Iter_equals_iter<_Iterator>(__it); }

template<typename _Predicate>
  struct _Iter_pred
  {
    _Predicate _M_pred;

    _GLIBCXX20_CONSTEXPR
    explicit
    _Iter_pred(_Predicate __pred)
: _M_pred(_GLIBCXX_MOVE(__pred)std::move(__pred))
    { }

    template<typename _Iterator>
_GLIBCXX20_CONSTEXPR
bool
operator()(_Iterator __it)
{ return bool(_M_pred(*__it)); }
  };

template<typename _Predicate>
  _GLIBCXX20_CONSTEXPR
  inline _Iter_pred<_Predicate>
  __pred_iter(_Predicate __pred)
  { return _Iter_pred<_Predicate>(_GLIBCXX_MOVE(__pred)std::move(__pred)); }

template<typename _Compare, typename _Value>
  struct _Iter_comp_to_val
  {
    _Compare _M_comp;
    _Value& _M_value;

    _GLIBCXX20_CONSTEXPR
    _Iter_comp_to_val(_Compare __comp, _Value& __value)
: _M_comp(_GLIBCXX_MOVE(__comp)std::move(__comp)), _M_value(__value)
    { }

    template<typename _Iterator>
_GLIBCXX20_CONSTEXPR
bool
operator()(_Iterator __it)
{ return bool(_M_comp(*__it, _M_value)); }
  };

template<typename _Compare, typename _Value>
  _Iter_comp_to_val<_Compare, _Value>
  _GLIBCXX20_CONSTEXPR
  __iter_comp_val(_Compare __comp, _Value &__val)
  {
    return _Iter_comp_to_val<_Compare, _Value>(_GLIBCXX_MOVE(__comp)std::move(__comp), __val);
  }

template<typename _Compare, typename _Iterator1>
  struct _Iter_comp_to_iter
  {
    _Compare _M_comp;
    _Iterator1 _M_it1;

    _GLIBCXX20_CONSTEXPR
    _Iter_comp_to_iter(_Compare __comp, _Iterator1 __it1)
: _M_comp(_GLIBCXX_MOVE(__comp)std::move(__comp)), _M_it1(__it1)
    { }

    template<typename _Iterator2>
_GLIBCXX20_CONSTEXPR
bool
operator()(_Iterator2 __it2)
{ return bool(_M_comp(*__it2, *_M_it1)); }
  };

template<typename _Compare, typename _Iterator>
  _GLIBCXX20_CONSTEXPR
  inline _Iter_comp_to_iter<_Compare, _Iterator>
  __iter_comp_iter(_Iter_comp_iter<_Compare> __comp, _Iterator __it)
  {
    return _Iter_comp_to_iter<_Compare, _Iterator>(
 _GLIBCXX_MOVE(__comp._M_comp)std::move(__comp._M_comp), __it);
  }

template<typename _Predicate>
  struct _Iter_negate
  {
    _Predicate _M_pred;

    _GLIBCXX20_CONSTEXPR
    explicit
    _Iter_negate(_Predicate __pred)
: _M_pred(_GLIBCXX_MOVE(__pred)std::move(__pred))
    { }

    template<typename _Iterator>
_GLIBCXX20_CONSTEXPR
bool
operator()(_Iterator __it)
{ return !bool(_M_pred(*__it)); }
  };

template<typename _Predicate>
  _GLIBCXX20_CONSTEXPR
  inline _Iter_negate<_Predicate>
  __negate(_Iter_pred<_Predicate> __pred)
  { return _Iter_negate<_Predicate>(_GLIBCXX_MOVE(__pred._M_pred)std::move(__pred._M_pred)); }

402} // namespace __ops
403} // namespace __gnu_cxx

405#endif