std::vector::insert

Angol

Főnév

std::vector::insert (tsz. std::vector::inserts)

1. (informatika) A C++ std::vector dinamikusan bővíthető tömbként funkcionál, melynek egyik legfontosabb művelete az insert metódus. Ez a függvény lehetővé teszi, hogy a vektor közepébe – vagy bármely tetszőleges pozícióba – elemeket szúrjunk be. Az insert használata rugalmas, hiszen egyszerre egyetlen elemet, többször ismétlődő másolatot, egy másik tartományban lévő elemeket, vagy éppen egy inicializáló lista tartalmát képes beilleszteni. Az alábbiakban részletezzük az insert overloadjait, viselkedését, hatékonyságát, valamint tippeket adunk a helyes és biztonságos használathoz.

---

1. Az insert alapvető overloadjai

A std::vector<T> osztályban négy fő insert verzió található:

1. Egyetlen elem beszúrása iteratorral

   iterator insert(const_iterator pos, const T& value);
   iterator insert(const_iterator pos, T&& value);
   

   A pos pozíció elé szúrja be a value változót. Visszatérési értéke a beszúrt elem pozíciójára utaló iterator.

2. Többszörös másolat beszúrása

   iterator insert(const_iterator pos, size_type count, const T& value);
   

   A pos helyre count darab value példányát szúrja be. Az első szúrás helyét mutató iteratorral tér vissza.

3. Tartomány beszúrása

   template< class InputIt >
   iterator insert(const_iterator pos, InputIt first, InputIt last);
   

   A [first, last) tartományban található elemeket másolja be a pos előtti pozícióba. Fontos, hogy ez a verzió általános iterátorokat vár, így akár std::list vagy más konténer tartományát is befűzhetjük.

4. Inicializáló lista beszúrása

   iterator insert(const_iterator pos, std::initializer_list<T> ilist);
   

   Az ilist minden elemét sorrendben beilleszti a pos elé.

---

2. Működési elv és iterátorok érvényessége

• Reallocáció Ha az aktuális kapacitás (capacity()) nem elegendő a beszúrandó elemek számához, a vector új memóriahelyet foglal, átmásolja a régieket, majd felszabadítja a korábbi területet. Ilyenkor minden korábbi pointer, referencia és iterátor érvénytelenné válik.
• Nem reallocáló beszúrás Amennyiben a kapacitás elegendő, csak a beszúrási pozíció utáni elemeket tolja el jobbra, és beírja az új elemeket. Ebben az esetben a pozíciótól a vektor végéig található iterátorok érvénytelenné válnak, a korábbi többi viszont megmarad.
• Visszatérési érték Minden insert overload visszaadja az első beszúrt elemre mutató iterator-t. Ez akkor különösen hasznos, ha a beszúrási művelet során iterátort kell frissíteni vagy láncolt műveletek következnek.

---

3. Idő- és tárkomplexitás

Overload	Időkomplexitás
insert(pos, value)	Amortizált O(1) vagy O(N) (reallocáció miatt)
insert(pos, count, value)	O(N + count)
insert(pos, first, last)	O(N + distance(first, last))
insert(pos, ilist)	O(N + ilist.size())

• Realokáció: A vektor kapacitásnövelése költséges, mert az összes elemet át kell másolni (vagy mozgatni). Emiatt a beszúrás amortizált O(1), de a valóságban ritkán szűkös kapacitás mellett előfordulnak O(N) műveletek.
• Eltolás: Minden beszúráskor a pos után álló elemeket egyesével el kell tolni, így beszúráskor a hátralévő elemek számától függő lineáris költség jelentkezik.

---

4. Használati példák

4.1. Egyetlen elem beszúrása

std::vector<int> v = {1, 2, 4, 5};
auto it = std::find(v.begin(), v.end(), 4);
v.insert(it, 3);  // v: 1, 2, 3, 4, 5

4.2. Több másolat beszúrása

std::vector<std::string> vs = {"a", "d"};
vs.insert(vs.begin() + 1, 2, "b"); 
// vs: "a", "b", "b", "d"

4.3. Tartomány beszúrása

std::list<int> lst = {100, 200, 300};
std::vector<int> v2 = {1, 2, 3};
v2.insert(v2.end(), lst.begin(), lst.end());
// v2: 1, 2, 3, 100, 200, 300

4.4. Inicializáló lista beszúrása

std::vector<char> vc = {'x', 'y', 'z'};
vc.insert(vc.begin() + 1, {'a', 'b', 'c'});
// vc: 'x', 'a', 'b', 'c', 'y', 'z'

---

5. Gyakori buktatók és best practice-ek

1. Iterator invalidáció

   • Mindig ellenőrizd, hogy a beszúrás után új iteratorokat kérsz, ne tarts meg régieket!
   • Ha láncolt műveleteket végzel (insert-et követően erase, insert), mindig frissítsd a mutatókat a visszatérési érték alapján.

2. Előzetes kapacitásfoglalás (reserve)

   • Ha sok elemet húzol be, érdemes előre lefoglalni a szükséges kapacitást, így elkerülhető a többszöri reallocáció:

     v.reserve(v.size() + count);
     v.insert(v.end(), count, value);
     

3. emplace vs. insert

   • Ha közvetlenül objektumokat építesz be, az emplace (pl. emplace(it, args...)) a helyén konstruálja őket, kihagyva egy másolást vagy mozgatást. Kisebb overhead jellemzi.

4. Beágyazott függvényhívások

   • A beszúrást nem érdemes rekurzívan vagy logikai ciklusokkal túlméretezve hívni, mert könnyen quadratikus viselkedéshez vezethet.

5. Kivételbiztonság

   • Az insert garantálja az erősen kivételbiztos viselkedést: ha az új elemek másolása vagy mozgatása közben kivétel keletkezik, a vektor eredeti állapota megmarad.

---

6. Teljes példaprogram

#include <iostream>
#include <vector>
#include <algorithm>
#include <list>

int main() {
    // 1. Kezdeti vektor
    std::vector<int> v = {10, 20, 30};

    // 2. reserve használata
    v.reserve(10);

    // 3. Egy elem beszúrása
    auto it = std::find(v.begin(), v.end(), 20);
    v.insert(it, 15);  // v: 10, 15, 20, 30

    // 4. Több elem beszúrása
    v.insert(v.end(), 2, 99);  // v: 10, 15, 20, 30, 99, 99

    // 5. Tartomány beszúrása listából
    std::list<int> lst = {1, 2, 3};
    v.insert(v.begin(), lst.begin(), lst.end()); 
    // v: 1, 2, 3, 10, 15, 20, 30, 99, 99

    // 6. Inicializáló lista beszúrása
    v.insert(v.begin() + 4, {7, 8, 9});  
    // v: 1,2,3,10,7,8,9,15,20,30,99,99

    // Kiíratás
    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';

    return 0;
}

---

Összefoglalás

• A std::vector::insert rugalmasságot és erős kivételbiztonságot kínál bármilyen beszúrási művelethez.
• Négy fő overload áll rendelkezésre: egyes, többszörös, tartomány és inicializáló lista alapú.
• A reserve használata, illetve az emplace alkalmazása segít hatékonyabbá tenni a kódot.
• Legyünk mindig tudatosak az iterátorok érvényességével kapcsolatban: a beszúrás utáni iterátorokat frissítsük a visszatérési érték segítségével.
• Ismerjük a komplexitásokat, hogy ne érjen bennünket meglepetés nagy tömbök esetén!

További információk

• std::vector::insert - Szótár.net (en-hu)
• std::vector::insert - Sztaki (en-hu)
• std::vector::insert - Merriam–Webster
• std::vector::insert - Cambridge
• std::vector::insert - WordNet
• std::vector::insert - Яндекс (en-ru)
• std::vector::insert - Google (en-hu)
• std::vector::insert - Wikidata
• std::vector::insert - Wikipédia (angol)