A módosító algoritmusok a standard library legfontosabb
újrafelhasználható építőelemei: ugyanaz a std::copy,
std::transform vagy std::remove_if működik
std::vector-on, std::list-en és nyers tömbön
is. Ez a rugalmasság azonban szerződéseken alapul: az algoritmus csak
iteratorokat lát, nem ismeri a mögöttes tároló méretét, kapacitását és
élettartam-szabályait. A rész az Iterator-kategóriák
és fél-nyílt tartomány (29.1) iterator-modelljére és a std::array, std::vector és folytonos tárolás (28.1)
tárolószerződéseire épül. A cél, hogy a módosító algoritmusokat ne
„tűzze fel” véletlenül, hanem ismerje fel az output kapacitás, az
átfedés és a predikátum élettartamának feltételeit.
A legtöbb módosító algoritmus egy [first, last) input
tartományt és egy d_first output iteratort
(kimeneti iterator) kap. Az output iterator olyan iterator, amelyen a
*d_first = value írás és a ++d_first léptetés
elvégezhető; az algoritmus ezen keresztül ír, de a mögöttes tároló
kapacitásáról semmit nem tud. Ha az output tartomány kisebb, mint
amennyi elemet az algoritmus írni fog, a viselkedés nem definiált (UB).
A standard library itt nem dob kivételt és nem ad hibakódot: ez a hívó
felelőssége.
A std::back_inserter egy
std::back_insert_iterator-t ad, amely a tároló
push_back tagfüggvényét hívja, így a méret automatikusan
nő. Ez biztonságos ismeretlen méretű output esetén, de allokálhat, és a
reallokáció invalidálhatja a tárolóra mutató iterátorokat. A
std::front_inserter a push_front-öt, a
std::inserter az insert-et hívja. A
reserve előzetes hívása csökkenti a reallokációk számát, de
a back_inserter ugyanabba a tárolóba írása így is
kerülendő, mert a push_back a last iterátort
(a régi end()-et) invalidálhatja.
A std::copy(first, last, d_first) az
[first, last) elemeit másolja a d_first-től
kezdve, és visszatér a d_first + (last - first)-fel. A
std::copy_n(first, n, d_first) az első n
elemet másolja; a std::copy_if(first, last, d_first, pred)
csak a predikátum által igaznak ítélt elemeket másolja, és az output
pozíció csak ezeknél lép. A
std::copy_backward(first, last, d_last) hátulról előre
másol, és a d_last-től visszafelé ír; ez akkor kell, amikor
az output a bemenet jobb oldalára esik.
A std::move(first, last, d_first) algoritmus ugyanaz,
mint a copy, de mozgat. Fontos, hogy ez nem azonos a
std::move(x) kategóriakonverzióval: az előbbi egy
algoritmus, amely a forrás elemeket moved-from állapotba hozza, az
utóbbi csak egy rvalue referenciát ad. A mozgatott forrás elemek
továbbra is léteznek, a destruktoruk lefut, de az értékük
meghatározatlan; csak azt szabad rajtuk tenni, amit a típus garantál
(például egy std::string üres, egy
std::unique_ptr null lesz). A
std::move_backward a jobbra tolás mozgatós változata.
A std::transform(first, last, d_first, op) az
op-ot minden elemre alkalmazza, és az eredményt a
d_first-től írja. A bináris változat
std::transform(first1, last1, first2, d_first, binary_op)
két input tartományból dolgozik; a first2 tartomány hossza
legalább last1 - first1, a visszatérési érték pedig
d_first + min(last1 - first1, last2 - first2). Az unary
változat in-place is használható (d_first == first), mert
az op az aktuális elemet olvassa, és az eredményt ugyanoda
írja. A bináris változatnál az in-place csak akkor biztonságos, ha a
második input nem fedi át a módosított tartományt; ha átfed, az eredmény
a műveleti sorrendtől függ, ezért külön output tárolót érdemes
használni.
A std::fill(first, last, value) egy értéket ír minden
elemre; a std::fill_n(first, n, value) az első
n elemre. A std::generate(first, last, gen) a
generátort hívja minden elemre; a
std::generate_n(first, n, gen) az első n
elemre. A std::iota(first, last, value) a
<numeric> headerben növekvő értékeket ír. A
fill_n és a generate_n n
paramétere nem lehet negatív; a negatív érték UB, és a kapacitást sem
ellenőrzik.
A std::copy előfeltétele, hogy a d_first ne
essen a [first, last) tartományba. Ha mégis, a
copy balról jobbra ír, és felülírhatja a még nem olvasott
elemeket; ez UB. A std::copy_backward előfeltétele tükrös:
a d_last ne essen a
(first, last] tartományba ([C++20]
[alg.copy]). A két végpont tehát fordítva viselkedik, mint a
copy-nál:
d_last == last tilos: ez a
last-be végződő önmásolás, a forrás és a cél
egybeesik;d_last == first megengedett: a cél a
forrás előtt, a first-nél végződik (megfelelő méretű
hellyel előtte);d_last a last után (például
last + 1) megengedett: ez a jobbra tolás.A copy_backward jobbról balra ír, ezért a jobbra
tolásnál biztonságos. A balra tolásnál a copy a helyes,
mert az output a first előtt van. Például a
std::copy(v.begin() + 1, v.end(), v.begin()) balra tol, és
biztonságos; a
std::copy_backward(v.begin(), v.end() - 1, v.end()) jobbra
tol, és biztonságos. A
std::copy(v.begin(), v.end(), v.begin() + 1) UB, mert az
output a bemenet belsejében van.
// copy_backward_bounds.cpp — C++20: a d_last nem lehet a (first, last] tartományban
#include <algorithm>
#include <cassert>
#include <vector>
int main() {
std::vector<int> v{1, 2, 3, 4, 5, 0};
// Jobbra tolás eggyel: first=v[0], last=v[5], d_last=v.end() — a v.end()
// a (first, last] tartományon KÍVÜL van, tehát megengedett.
std::copy_backward(v.begin(), v.end() - 1, v.end());
assert((v == std::vector<int>{1, 1, 2, 3, 4, 5}));
// d_last == first: a cél a forrás ELŐTT végződik — megengedett.
std::vector<int> w{0, 0, 0, 7, 8, 9};
std::copy_backward(w.begin() + 3, w.end(), w.begin() + 3);
assert((w == std::vector<int>{7, 8, 9, 7, 8, 9}));
// TILOS: d_last == last (önmásolás a last-be végződve) — előfeltétel-sértés:
// std::copy_backward(v.begin(), v.end(), v.end());
}Buildjegyzőkönyv (lab-gcc profil).
g++ -std=c++20 -Wall -Wextra -Wpedantic -D_GLIBCXX_DEBUG copy_backward_bounds.cpp
figyelmeztetés nélkül fordul, és mindkét assert teljesül: a
d_last = last + 1 jobbra tolás és a
d_last == first eset is a várt tartalmat adja.
A std::transform unary in-place megengedett. A
std::copy_if viszont nem használható
önmagára: az előfeltétele, hogy a bemeneti és a kimeneti tartomány ne
fedje át egymást ([C++20] [alg.copy]). Átfedő hívás akkor is
előfeltétel-sértés, ha egy adott implementáción véletlenül a várt
eredményt adja. (Egy ilyen tömörítő kiírásnál a kimeneti pozíció a
feldolgozott pozícióhoz képest lemarad, nem előreszalad; ez magyarázza,
miért „működhet”, de nem teszi szabályossá.) In-place szűrésre a
std::remove_if + erase, illetve C++20-ban a
std::erase_if való; a copy_if külön kimeneti
tárolóba ír.
A std::back_inserter ugyanabba a tárolóba írása szintén
hibás, mert a push_back reallokálhat, és az input
iterátorok invalidálódnak; a reserve ezen nem segít. Az
önbeszúrás sem megoldás: a
v.insert(v.end(), v.begin(), v.end()) hívás sérti a
sorozattárolók insert(p, i, j) előfeltételét, amely szerint
az i és j nem mutathat magába a tárolóba
([sequence.reqmts]); ezt a reserve sem írja felül. A helyes
út külön forrásmásolat:
// inplace_filter.cpp — C++20: szűrés helyben és duplázás biztonságosan
#include <algorithm>
#include <cstdio>
#include <iterator>
#include <vector>
int main() {
std::vector<int> v{1, 2, 3, 4, 5, 6};
// In-place szűrés: erase_if (C++20), nem önmagára másoló copy_if.
std::erase_if(v, [](int x) { return x % 2 == 0; }); // 1 3 5
// Szűrt másolat: copy_if külön kimenetbe.
std::vector<int> big;
std::copy_if(v.begin(), v.end(), std::back_inserter(big),
[](int x) { return x > 1; }); // 3 5
// Önhozzáfűzés: előbb külön forrásmásolat, aztán insert.
const std::vector<int> copy = v;
v.insert(v.end(), copy.begin(), copy.end()); // 1 3 5 1 3 5
for (int x : v) std::printf("%d ", x);
std::printf("| ");
for (int x : big) std::printf("%d ", x);
std::printf("\n");
}A negatív próba a libstdc++ debug módjával mutatja meg az önbeszúrás hibáját:
// vector_self_insert_debug.cpp — NEGATÍV próba: önbeszúrás saját iterátorokból
#include <vector>
int main() {
std::vector<int> v{1, 2, 3};
v.reserve(16); // a reserve nem írja felül
v.insert(v.end(), v.begin(), v.end()); // előfeltétel-sértés: i, j a v-be mutat
}Buildjegyzőkönyv (lab-gcc profil). Az
inplace_filter.cpp -D_GLIBCXX_DEBUG és
ASan/UBSan mellett hibátlanul fut, kimenete
1 3 5 1 3 5 | 3 5. A
vector_self_insert_debug.cpp -D_GLIBCXX_DEBUG
mellett
attempt to insert with an iterator range [first, last) from this container
hibával leáll.
A std::remove(first, last, value) és a
std::remove_if(first, last, pred) nem töröl a tárolóból. Az
el nem távolított elemeket előremozgatja, és visszaadja az új logikai
end-et (new_end). A [new_end, last) elemek
moved-from állapotban vannak: az objektumok léteznek, a destruktoruk
később lefut, de az értékük meghatározatlan, ezért nem szabad rájuk
támaszkodni. A size() nem változik, és a
std::remove nem allokál; a vector iterátorai
érvényesek maradnak, de a [new_end, last) elemek értéke
megváltozik. A remove_if megőrzi a megmaradó elemek relatív
sorrendjét. A művelet költsége O(n) összehasonlítás és
legfeljebb O(n) mozgatás.
A std::unique(first, last) csak a szomszédos
duplikátumokat távolítja el; a nem szomszédos duplikátumok megmaradnak.
Ezért a teljes deduplikációhoz előbb rendezni kell:
std::sort + std::unique + erase.
A unique is logikai eltávolítás, és visszaadja az új
logikai end-et. A std::list és a
std::forward_list esetében van remove,
remove_if és unique tagfüggvény, amely
ténylegesen töröl, és csak a törölt elemekre mutató iterátorokat
invalidálja; a std::remove a listán is csak logikai
eltávolítás, ezért ott a tagfüggvényt használjuk. Az asszociatív
tárolóknál a std::remove nem használható, mert az elemek
kulcsa nem módosítható; ott az erase tagfüggvény a
helyes.
A logikai eltávolítást a fizikai törléssel az erase-remove idiom kapcsolja össze:
v.erase(std::remove(v.begin(), v.end(), x), v.end());
v.erase(std::remove_if(v.begin(), v.end(), pred), v.end());A vector::erase(first, last) a
[first, last) elemeket destruálja, a mögötte lévőket
előremozgatja, és csökkenti a size()-ot; a kapacitás nem
változik. Az erase-remove esetében a last a
v.end(), ezért a farok törlése nem mozgat, csak a
destruktorokat hívja; az összköltség O(n). Az
erase invalidálja a törölt elemekre és az utánuk
következőkre mutató iterátorokat; a törölt elemek előttiek érvényesek
maradnak.
C++20-ban a std::erase(v, x) és a
std::erase_if(v, pred) szabad függvények a std
névtérben minden szabványos tárolóhoz elérhetők (a pontos készletet és a
library verzióját a laborprofilban kell ellenőrizni). A
std::erase(v, x) a x-szel egyenlő elemeket
távolítja el, a std::erase_if(v, pred) a predikátumot
használja; mindkettő visszatér a törölt elemek számával. A
vector esetében a std::erase_if a
remove_if + erase kombinációt hajtja végre, és
a sorrendet megőrzi; a list esetében a
list::remove_if-et hívja, amely ténylegesen töröl, és csak
a törölt elemekre mutató iterátorokat invalidálja. A
std::erase nem azonos a vector::erase
tagfüggvénnyel: az előbbi érték vagy predikátum alapján töröl, az utóbbi
iteratorokkal dolgozik. A C++20-as std::erase_if
elérhetősége a __cpp_lib_erase_if feature-test macroval
ellenőrizhető.
A predikátumot az algoritmus a hívás ideje alatt használja, és érték
szerint másolhatja; a predikátum által hivatkozott objektumoknak a hívás
teljes ideje alatt élniük kell. A predikátumnak tisztának kell lennie az
input tartományra nézve: nem módosíthatja az elemeket, és nem
módosíthatja a tárolót. Ha a predikátum push_back-et,
erase-t vagy más olyan műveletet hív, amely invalidálja az
algoritmus iterátorait, a viselkedés nem definiált. Például a
std::remove_if(v.begin(), v.end(), [&v](int x) { v.push_back(x); return false; })
UB, mert a push_back reallokálhat, és a
remove_if iterátorai invalidálódnak. A helyes megoldás: a
módosításokat a remove_if előtt vagy után végezzük, vagy
külön output tárolót használjunk. Az erase-remove esetében a
remove_if predikátuma nem hívhat erase-t
ugyanarra a tárolóra.
A predikátum élettartama akkor válik kritikussá, ha a predikátumot
eltároljuk (például std::function-be tesszük), és később
hívjuk: a captured referencia dangling lehet. Az algoritmusok nem
tárolják el a predikátumot a hívás után, ezért a hívás alatti élettartam
a lényeg. A predikátum másolása ne legyen mellékhatásos, mert az
algoritmus a saját másolatán dolgozhat.
A példa egy naplófeldolgozó. A parse_logs a
std::transform-ot és a std::back_inserter-t
használja; a main a std::remove_if +
erase-t, a std::transform in-place-t és a
std::copy_if + back_inserter-t. A
reserve a kapacitást biztosítja. A kód C++20-at igényel; a
laborprofilban rögzített GCC vagy Clang verzióval fordítandó.
#include <algorithm>
#include <cassert>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>
struct LogLine {
std::string level;
std::string message;
};
std::vector<LogLine> parse_logs(const std::vector<std::string>& raw) {
std::vector<LogLine> out;
out.reserve(raw.size());
std::transform(raw.begin(), raw.end(), std::back_inserter(out),
[](const std::string& line) {
auto pos = line.find(' ');
if (pos == std::string::npos) {
return LogLine{"UNKNOWN", line};
}
return LogLine{line.substr(0, pos), line.substr(pos + 1)};
});
return out;
}
int main() {
std::vector<std::string> raw = {
"INFO started", "DEBUG cache miss", "ERROR disk full",
"DEBUG retry", "INFO stopped"
};
auto logs = parse_logs(raw);
assert(logs.size() == 5);
auto new_end = std::remove_if(logs.begin(), logs.end(),
[](const LogLine& l) { return l.level == "DEBUG"; });
logs.erase(new_end, logs.end());
assert(logs.size() == 3);
std::transform(logs.begin(), logs.end(), logs.begin(),
[](const LogLine& l) {
return LogLine{l.level, "[kept] " + l.message};
});
std::vector<LogLine> errors;
std::copy_if(logs.begin(), logs.end(), std::back_inserter(errors),
[](const LogLine& l) { return l.level == "ERROR"; });
assert(errors.size() == 1);
for (const auto& l : logs) {
std::cout << l.level << ": " << l.message << '\n';
}
}A build parancs:
g++ -std=c++20 -Wall -Wextra -Wpedantic -O2 -o logdemo logdemo.cppFuttatás:
./logdemoKimenet (lab-gcc profil):
INFO: [kept] started
ERROR: [kept] disk full
INFO: [kept] stoppedA három megmaradt sor a DEBUG sorok eltávolítása után
látszik; a transform a [kept] prefixet adta, a
copy_if pedig egy ERROR elemet másolt az
errors tárolóba. Buildjegyzőkönyv
(lab-gcc profil): a program -D_GLIBCXX_DEBUG
és ASan/UBSan mellett is a fenti kimenettel futott.
A leggyakoribb hiba, hogy a std::copy outputja kisebb,
mint a bemenet. A std::copy nem ellenőrzi a kapacitást, és
nem dob kivételt; ha a d_first által írt tartomány túl
rövid, a viselkedés nem definiált. Ilyenkor
std::back_inserter-t vagy előre biztosított kapacitást kell
használni. A második gyakori hiba a
std::copy(v.begin(), v.end(), v.begin() + 1) jobbra tolás:
az output a bemenet belsejében van, ezért UB; helyette
std::copy_backward(v.begin(), v.end() - 1, v.end()) kell. A
harmadik, hogy a std::remove eredményét nem használjuk: a
remove nem töröl, csak a logikai end-et adja vissza;
erase nélkül a méret nem változik, és a „törölt” elemek a
végén maradnak. A negyedik, hogy a std::unique-ot rendezés
nélkül használjuk: csak a szomszédos duplikátumokat távolítja el. Az
ötödik, hogy a std::list-en std::remove-ot
használunk a list::remove helyett: a
std::remove a listán is csak logikai, a tagfüggvény
ténylegesen töröl. A hatodik, hogy a predikátum módosítja a tárolót: ez
UB. A hetedik, hogy a std::move algoritmust összekeverjük a
std::move kategóriakonverzióval. A nyolcadik, hogy a
fill_n-t negatív n-nel hívjuk: ez UB.
A módosító algoritmusok szerződése három ponton dől el: az output
kapacitás, az átfedés és az élettartam. Az output iterator nem ismeri a
tároló kapacitását, ezért a hívónak kell biztosítania a helyet; a
back_inserter kényelmes, de allokálhat és invalidálhat. A
copy és a copy_backward iránya eltérő, ezért
az átfedő másolásnál a megfelelőt kell választani. A remove
és a remove_if logikai eltávolítás; a fizikai törléshez
erase kell, vagy C++20-ban
std::erase/std::erase_if. A predikátum ne
módosítsa a tárolót, és a captured objektumok élettartama tartsa ki a
hívást.
Magyarázd el, miért nem csökkenti a std::remove a
std::vector méretét, és mi a különbség a
std::remove és a vector::erase között. Mi a
[new_end, last) elemek állapota, és mely iterátorok
invalidálódnak az erase után?
Adott egy std::vector<std::string>. Távolítsd el
az üres sztringeket, majd alakítsd kisbetűssé a megmaradókat. Használj
erase-remove-ot és std::transform-ot. Biztosítsd az output
kapacitást, és indokold, miért biztonságos az in-place transform.
Az alábbi kód UB-t tartalmaz:
std::vector<int> v{1, 2, 3, 4, 5};
std::copy(v.begin(), v.end(), v.begin() + 1);Találd meg a hibát, írd le a helyes változatot, és indokold, miért
lesz az eredmény {1, 1, 2, 3, 4}.
Írj egy függvényt, amely egy std::vector<int>-ből
eltávolítja a negatív számokat, és visszaadja a törölt elemek számát.
Használj C++20-as std::erase_if-et, majd hasonlítsd össze
az erase-remove változattal az invalidáció szempontjából.
A std::remove nem töröl, hanem az el nem távolított
elemeket előremozgatja, és visszaadja az új logikai end-et. A
size() változatlan marad; a [new_end, last)
elemek moved-from állapotban vannak, értékük meghatározatlan, de az
objektumok léteznek. A vector::erase destruálja a
[first, last) elemeket, előremozgatja a mögötte lévőket, és
csökkenti a size()-ot. Az erase invalidálja a
törölt elemekre és az utánuk következőkre mutató iterátorokat; a törölt
elemek előttiek érvényesek maradnak. Ellenőrzés:
assert(v.size() == expected);.
#include <algorithm>
#include <cassert>
#include <cctype>
#include <string>
#include <vector>
void normalize(std::vector<std::string>& lines) {
lines.erase(std::remove_if(lines.begin(), lines.end(),
[](const std::string& s) { return s.empty(); }),
lines.end());
std::transform(lines.begin(), lines.end(), lines.begin(),
[](std::string s) {
std::transform(s.begin(), s.end(), s.begin(),
[](unsigned char c) {
return static_cast<char>(
std::tolower(c));
});
return s;
});
}
int main() {
std::vector<std::string> lines{"Hello", "", "WORLD", "", "C++"};
normalize(lines);
assert((lines == std::vector<std::string>{"hello", "world", "c++"}));
}Az erase-remove eltávolítja az üres sztringeket; a
transform in-place a lines-on dolgozik. Az
in-place biztonságos, mert a lambda a std::string-et érték
szerint veszi át, így a saját másolatán dolgozik, és a visszatérési
értéket a transform a *it-hez rendeli. A
std::tolower unsigned char-ra castolva kerüli
a negatív karakterek UB-ját. Ellenőrzés: az assert a várt
három elemet ellenőrzi.
A hiba, hogy a std::copy outputja a
[v.begin(), v.end()) belsejében van
(v.begin() + 1), ezért a copy balról jobbra
haladva felülírja a még nem olvasott elemeket; ez UB. A helyes
változat:
std::copy_backward(v.begin(), v.end() - 1, v.end());A copy_backward az utolsó elemtől kezd visszafelé, ezért
nem írja felül a még nem olvasott elemeket. Az input
[v.begin(), v.end() - 1) = {1, 2, 3, 4}, az
output [v.begin() + 1, v.end()) = {2, 3, 4, 5}
helyére kerül, így az eredmény {1, 1, 2, 3, 4}. Ellenőrzés:
assert((v == std::vector<int>{1, 1, 2, 3, 4}));.
#include <cstddef>
#include <cassert>
#include <vector>
std::size_t remove_negatives(std::vector<int>& v) {
return std::erase_if(v, [](int x) { return x < 0; });
}
int main() {
std::vector<int> v{1, -2, 3, -4, 5};
auto removed = remove_negatives(v);
assert(removed == 2);
assert((v == std::vector<int>{1, 3, 5}));
}A std::erase_if a vector esetében a
remove_if + erase kombinációt hajtja végre, és
visszatér a törölt elemek számával. Az erase-remove változat ugyanazt a
hatást éri el, de a törölt elemek számát a
std::distance(new_end, v.end()) adja. Mindkettő invalidálja
a törölt elemekre és az utánuk következőkre mutató iterátorokat; a
vector esetében a törölt elemek előttiek érvényesek
maradnak. A std::erase_if elérhetőségét a
__cpp_lib_erase_if feature-test macroval kell ellenőrizni.
Ellenőrzés: a két assert.
A fejezet a C++20 nyelvi és könyvtári alapra épül; a C++23-as
változásokat nem tárgyalja. A szabvány pontos paragrafusait, az
implementációk eltéréseit és a std::erase_if elérhetőségét
a laborprofilban kell ellenőrizni. A szöveg nem tartalmaz
szabványidézetet, és a kódpéldák nincsenek lefuttatva; a kimenetek
illusztrációk, nem mért eredmények. A std::erase_if
feature-test macroja __cpp_lib_erase_if; ennek tényleges
értékét a fordítónál és a standard library verziójánál kell
ellenőrizni.