STL Veri Yapısı - vector

Vector Nedir?
vector, deque, list sequence container olarak anılırlar.

Hangi Senede Eklendi
1998 yılında eklendi ancak 1994 yılından beri var diyebiliriz. Açıklaması şöyle.

Introduced in C++98, part of the Working Draft at least since WG21/N0545 September 1994

Bellek Alanı
Vector, aynı bir array gibi sıralı yani aralıksız bellek alanı sunar. Contigous kısıtı yüzünden aslında vector sınıfının içerde bir array kullanması zorunludur. Array kullanmayan bir gerçekleştirim mümkün görünmüyor.

"A vector is a sequence container that supports random access iterators. In addition, it supports (amortized) constant time insert and erase operations at the end; insert and erase in the middle take linear time. Storage management is handled automatically, though hints can be given to improve efficiency. The elements of a vector are stored contiguously, meaning that if v is a vector where T is some type other than bool, then it obeys the identity &v[n] == &v[0] + n for all 0 <= n < v.size()."

Vector Sınıfı ve Exception Safety
C++ standardında vector için bazı exception cümleleri geçiyor. Bu cümlelerin ne anlama geldikler burada açıklanmış.

Strong Exception Safety
Herhangi bir işlem başarızsız olsa bile, vector'ün eski halinde kalması anlamına gelir. Örnek bir cümle şöyle olabilir.

If an exception is thrown while inserting a single element at the end and T is CopyInsertable or is_nothrow_move_constructible<T>::value is true, there are no effects.

Vector Sınıfı Veriyi Sahiplenir
Vector sınıfı, kendisine eklenen veriyi sahiplenir. Yani verinin CopyAssignable olması gerekir. Dolayısıyla şöyle bir kod derlenmez.

std::vector<(File&)> files;

Verinin destructor'ını çağırmadan vector'den ayırmanın bir yolu yoktur. Herhangi bir reallocation işleminde X tipinden bir vector veriyi şöyle siler.

x.~T();

Vector Sınıfı Kalıtır mı?
Vector Visual Studio'da kalıtım kullanıyor. Şöyle :
class vector : public _vector_alloc

Constructor - Fill
Constructor Metodları yazısına taşıdım.

Constructor - Range
Constructor Metodları yazısına taşıdım.

Constructor - Initializer List
Constructor Metodları yazısına taşıdım.

Copy Constructor metodu
Constructor Metodları yazısına taşıdım.

capacity metodu
Veriyapısının kapasitesi contructor veya resever() ile verilebilir. Şöyle yaparız.

std::vector<int> a;
a.reserve(65536);
cout << "a.capacity is " << a.capacity() << endl; // prints 65536

clear metodu
Bu metodun en hızlı nasıl çalışabileceğine dair açıklama burada.

data metodu
Açıklaması şöyle.

Returns: A pointer such that [data(), data() + size()) is a valid range. For a non-empty vector, data() == addressof(front()).

İmzası şöyle

T* data() noexcept;

std::vector::pointer typedef yerine niçin T döndürüldüğü burada açıklanıyor.

Örnek
Bu metod vector ilk yaratıldığında null dönebilir.

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> v;
    cout << v.data() << endl;

    v.push_back(1);
    cout << v.data() << endl;

    v.pop_back();
    cout << v.data() << endl;

    v.shrink_to_fit();
    cout << v.data() << endl;

    return 0;
}

Çıktı olarak şunu alırız.

0x0
0x7f896b403300
0x7f896b403300
0x0

Örnek
Vector'ün içindeki belleği başka bir şey ile değiştirmek için şöyle yaparız.

int *foo()
{
  std::vector<int> v(10,1);

  int *ret = v.data();
  new (&v) std::vector<int>; // Replace `v` with an empty vector. Old storage is leaked.
  return ret;
}

emplace ve emplace_back metodu
Eleman Ekleme Metodları yazısına taşıdım.

erase metodu
Eleman Silme Metodları yazısına taşıdım.

front metodu

front() ilk elemana referans döndüğü için, elemanı değiştirebilmek mümkün. Örnek:

int main (int argc, char *argv[]) {
    std::vector<int> jambone;

    jambone.push_back(2);
    jambone.front() = 4;
    std::cout<< jambone.front();
}

insert metodu
Eleman Ekleme Metodları yazısına taşıdım.

max_size metodu
Bu metod std::list, std::dequeue gibi diğer veri yapılarında da var. Vector'e eklenebilecek en fazla nesne sayısını belirtir. Bu sayıya ulaşamadan bellek bitebilir. Bu durumda yine std::bad_alloc fırlatılır.
Örnek
Şöyle yaparız

std::vector <int> nums;
int max = nums.max_size();
std::cout << "Max: " << max << std::endl;

Çıktı olarak şunu alırız

Max: 1073741823

operator = metodu - assignment operator
İlk vector'deki elemanları silip ikinci vector'deki elemanları atar. Örnekte v1 3 elemana sahip v2 ise 2 elemana sahip. İlk iki elemanı atamak için std::string'in = operatörü çağrılır. Son eleman içinse destructor metodunu çağrılır.

std::vector<std::string> v1;
v1.push_back("Hello");
v1.push_back("There");
v1.push_back("World");

std::vector<std::string> v2;
v2.push_back("Good");
v2.push_back("Bye");

v1 = v2;

operatör [] metodu
Metodun imzası şöyle. Elemana referans döner.

reference operator[](size_type n);

Metodun içi şöyledir.

reference operator[](size_type __n)
{ return *(this->_M_impl._M_start + __n); }

Bu metod at() ile aynı şeyi yapar. Farkı ise verilen indeks değerinin vector boyunu aşıp aşmadığının kontrol edilmemesi. C++ mantığında "pay for what you use" olduğu için ne yaptığını bilenler için çok daha hızlı çalışan bir metod daha sunulmuş. Yeni bir elemen eklemediği şöyle açıklanıyor.

Unlike std::map::operator[], this operator never inserts a new element into the container.

Bu  operatörün const ve olmayan iki çeşidi var.

reference       operator[]( size_type pos );
const_reference operator[]( size_type pos ) const;

const reference döndüren metod const vector ile kullanılıyor ve vector'ün içinin değiştirilmesini engelliyor.

void f(std::vector<int> & v1, std::vector<int> const & v2)
{
   //v1 is non-const vector
   //v2 is const vector

   auto & x1 = v1[0]; //invokes the non-const version
   auto & x2 = v2[0]; //invokes the const version

   v1[0] = 10; //okay : non-const version can modify the object
   v2[0] = 10; //compilation error : const version cannot modify 

   x1 = 10; //okay : x1 is inferred to be `int&`
   x2 = 10; //error: x2 is inferred to be `int const&`
}

push_back metodu

Eleman Ekleme Metodları yazısına taşıdım.

resize metodu- Hem kapasite ayır hem de değer ile doldur
Eskiden "Increase capacity and size" diye de düşünürdüm. Sanki C ile kodlarken realloc ile aynı derdim. Yani eskiden böyle yaparken

int* data = new int[3];
//...
int* mydata = realloc(data,6*sizeof(int));

Şimdi vector ile şöyle yapıyoruz derdim.

vector<int> data( 3 );
//...
data.resize (6);

C++98 ile metodun imzası aşağıda.

void resize( size_type count, T value = T() );

C++11 ile metodun imzası şöyledir.

void resize (size_type n);
void resize (size_type n, const value_type& val);

Ta ki resize () metodunun vector'ün boyunu kısaltabilecegini anlayıncaya kadar :) Aslında realloc () ta kısaltma için kullanılabilir ama ben uzatmak için kullanmaya çok alışmışım.

Buradaki soruda resize metodunun ne işe yaradığı çok iyi açıklanmış. Eğer verilen uzunluk mevcut uzunluktan küçükse,vektör kısalır ve sondaki elemanlar silinir.

If n is smaller than the current container size, the content is reduced to its first n elements, removing those beyond (and destroying them).

Diyelim ki vector'ün boyunu 10 eleman kadar kısaltmak istiyoruz. Şöyle yaparız.

v.resize(v.size()-10);

Bu kod aslında şu kod ile aynıdır.

v.erase(v.end() - 10, v.end());

Eğer verilen uzunluk mevcut uzunluktan büyük ise vektör uzatılır. Aşağıdaki kod parçası çalışma şeklini kabaca gösteriyor.

if (sz > size())                    //Uzat
    insert(end(), sz-size(), c);
else if (sz < size()) {            //Kısalt
    iterator i = begin();
    advance(i, sz);
    erase(i, end());
}
else
    ; // do nothing

Eğer vektörün uzaması gerekiyorsa ucuna default constructed ya da 0 olarak başlatılmış elemanlar eklenir. İşlem bitince default constructed nesne yok edilir. Vöktörün uzaması ve doldurulması yüzünden resize metodu, reserve metoduna göre biraz daha verimsiz olabilir.

Dikkat edilmesi gereken nokta, vector içindeki bir düğüm diğer düğümlere pointer tutuyorsa, resize pointerların geçerliliğini bozabilir.

Bir diğer fark ise, reserve tam olarak verilen kapasite kadar yer ayırır. resize biraz daha fazla ayırır/ayırabilir.

reserve metodu- Sadece Kapasite ayır
Açıklaması şöyle.

void reserve (size_type n);

Request a change in capacity

Requests that the vector capacity be at least enough to contain n elements.

If n is greater than the current vector capacity, the function causes the container to reallocate its storage increasing its capacity to n (or greater).

In all other cases, the function call does not cause a reallocation and the vector capacity is not affected.

This function has no effect on the vector size and cannot alter its elements.

"Only increase capacity" diye de düşünebiliriz. Bjarne Stroustrup bu metodun performansı çok fazla artırmayabileceğini söylüyor.

People sometimes worry about the cost of std::vector growing incrementally. I used to worry about that and used reserve() to optimize the growth. After measuring my code and repeatedly having trouble finding the performance benefits of reserve() in real programs, I stopped using it except where it is needed to avoid iterator invalidation (a rare case in my code). Again: measure before you optimize.

Boş bir vector'e reserve() ile yer ayırıp daha sonra data() metodu ile belleğe erişmek yanlıştır.

Metod istenilen yer kadar kapasite ayırır, veri ile doldurmaz. Ayrıca gerekiyorsa kapasiteyi artırır, asla küçültmez. C++11 ile move semantics devreye girer ve performas artar. Örnekte ilk başta 1 eleman var. Sonra 10 elemanlık yer ayrılıyor bu durumda mevcut elemanın taşınması gerekir.  Move constructor ile bu işlem maliyetsizdir.

struct bar{
  std::vector<int> data;
};
std::vector<bar> foo(1);
foo.back().data.push_back(3);
foo.reserve(10); // two allocations and a delete occur in C++03

pop_back
Eleman Silme Metodları yazısına taşıdım.

resize metodu
Açıklaması şöyle

std::vector<T>::resize() changes the size of the array. If you resize it smaller than its current size, the excess objects are destructed. If you resize it larger than its current size, the "new" objects added at the end are default-initialized.

shrink_to_fit
Açıklaması şöyle.

Shrink to fit---This may cause a reallocation, but has no effect on the vector size and cannot alter its elements.

Vector'de iki tane önemli alan var, bunlar size ve capacity. shrink_to_fit() capacity değerini değiştirir ve genellikle vector bir kere ilklendiridikten sonra bir daha nesne eklenmeyecekse kullanılır. Açıklaması şöyle.

You'd typically use this when you are done building a vector and will never add another item to it.

Kapasiteyi değiştirdiği için yeni bir bellek alanı yaratarak herşeyi taşır. Açıklaması şöyle.

So if shrink_to_fit is going to change the capacity, then it can only do so by performing reallocation.

Örnek
Şöyle yaparız.

myVector.erase(myVector.begin(), myVector.begin() + 3);
myVector.shrink_to_fit();

size metodu
Örnek
Eğer döngü içinde süreki size() çağrısı yapmak istemiyorsak şöyle yaparız

for (std::size_t i = 0, vect_size = vect.size(); i < vect_size; ++i)
{
}

size_type Tipi

vector<T>::size_type

STL container sınıflarının tanımlamasını istediği bir şey. Genellikle size_t ile aynı şeydir. Vector'ün en fazla ne kadar eleman alabileceğini gösterir.

swap metodu
İmzası şöyle

void swap( vector& other );

İki vektörün içlerinin değiş tokuş edilmesini sağlar. Bu metod constant time'da çalışır. Sebebi ise allocator olarak heap kullanılması. Eğer iki vector farklı allocator'lar kullanıyorsa davranış undefined olabilir.

Örnek
Şöyle yaparız.

std::vector<std::string> First{"example", "second" , "C++" , "Hello world" };
std::vector<std::string> Second{"Hello"};

First.swap(Second);

Örnek
Parametre const vector olmadığı için şu kod derlenmez.

vector<int> func()
{
  vector<int> a(3,100);
  return a;
}

int main()
{
  vector<int> b(2,300);
  //b.swap(func());   /* why is this not working? */
  func().swap(b);  /* and why is this working? */
  return 0;
}