Merhaba arkadaşlar,
Haftalık C++ kod örneklerimize devam ediyoruz. Bu haftaki problemimiz std::vector gibi konteynerlere (nedir arkadaş bu STL konteyner sevdası yahu 🙂 duyar gibiyim) bir yandan veri eklerken bir yandan da bunları sıralı tutabilir miyiz?
Bu probleme geçmeden önce konteyner konusuna ufak bir eğilelim, çünkü buradaki problemi çözerken bir miktar değinmemiz gerekecek. Bu sınıfların detaylarına girmeyeceğim ama merak edenler bu sayfaya göz atabilirler. Burada her bir sınıfa ilişkin detaylı bilgi, performans ve servisler sıralanmaktadır.
STL günlük hayatta ihtiyaç duyabileceğimiz veri yapılarına (queue, stack, linked list, vs) ilişkin bir çok konteyner sınıfını içerisinde barındırıyor. Genel olarak bunlar oldukça hızlı ve verimli bir şekilde gerçeklenmiş durumda. Hepsi ortak arayüzler sunuyorlar ve iyi bir şekilde dökümante edilmiş durumdalar. Genel olarak bu konteynerler dört ana gruba ayrılıyor:
- Sıralı Konteynerler (“Sequence containers”)
- Aynı tip verileri sıralı bir şekilde saklayan veri yapılarını ifade etmek için kullanılırlar,
- Bu grup altında array (statik veri dizisi), vector (dinamik veri dizisi), forward_list (tek yönlü bağlı liste), list (çift yönlü bağlı liste) ve deque (çift yönlü kuyruk) konteynerleri var.
- İlişkili Konteynerler (“Associative containers”)
- Hızlı erişime olanak sağlamak adına sıralı veri yapıları sunan konteynerleri kapsar,
- Bu grup altında set (tekli sıralı küme), map (tekli ilişkili dizi, anahtarlara göre sıralı) , multiset (çoklu sıralı küme), multimap (çoklu ilişkili dizi, anahtarlara göre sıralı) konteynerleri var.
- Sırasız İlişkili Konteynerler (“Unordered associative containers”)
- İlişkili dizilerden farklı olarak sırasız fakat hızlı erişim ( en kötü durumda O(n) ) adına hash kullanan veri yapılarını ifade eden konteynerleri içerisinde barındırır,
- Bu sınıflar C++ 11 ile birlikte sunulmaya başlandılar,
- Bu grup altında unordered_set, unordered_map, unordered_multiset ve unordered_multimap konteynerlerini içerisinde barındırır. Bunlar ilişkili konteynerlerin hash kullanan karşılıklarıdır.
- Konteyner Adaptörleri (“Container adapters”)
- Bunlar alında kendi başlarına bir konteyner olmayan, daha çok yukarıdakileri kullanan/sarmalayan sınıflar olarak düşünülebilir,
- Bu grup altında stack (“LIFO – Last in first out” yığın veri yapısı), queue (“LILO – Last in last out” kuyruk veri yapısı) ve priority_queue konteynerleridir. Bunlara ilişkin kabiliyet ve servisler vector, deque ve list ile de sunulabilmekte.
Şimdi gelelim problemimize elimizde sıralı konteynerler var (ör. vector) ve eklediğimiz her eleman ile sıranın bozulmadan korunmasını istiyoruz bunu kolay bir şekilde nasıl yapabiliriz?
İlk yöntem her ekleme sonrası “algorithm” kütüphanesi tarafından sunulan sort() metodunu kullanmak olabilir ki tahmin edeceğiniz üzere pek ucuz bir yöntem olmayacaktır 🙂 Neyse aşağıda örnek bir vector ilklendirelim ve bunu sıralayalım.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include <iostream> #include <vector> #include <string> #include <algorithm> #include <iterator> #include <cassert> using namespace std; void printContent(auto& container) { for (const auto &w : container) { cout << w << " "; } cout << endl; } int main() { vector<string> v {"selim", "rasim", "kazım", "kutlu", "osman", "can","ali"}; // is_sorted detaylari için https://en.cppreference.com/w/cpp/algorithm/is_sorted assert(false == is_sorted(begin(v), end(v))); sort(begin(v), end(v)); assert(true == is_sorted(begin(v), end(v))); return 0; } |
Evet sıralı eklemek için yine “algorithm” kütüphanesinden bir metottan yardım alacağız. Bu metot lower_bound(). Aşağıda bu metodun tanımını görebilirsiniz:
|
1 2 |
template <class ForwardIterator, class T> ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val); |
Metot kısaca [First, Last) aralığındaki verilen val değerinden küçük olmayan ilk elemanı işaret eden iterator’ü dönüyor.
Örneğin: {10, 20, 30, 40, 50} girdisi için 10 ve 50 arasında 35 değeri için bu metot 3 dönecek, 15 için ise 1 dönecek.
Aşağıda bu metodun ve kardeşinin (upper_bound()) kullanıma ilişkin örnek bir kod ta görebilirsiniz:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
#include <iostream> #include <algorithm> #include <vector> using namespace std; int main () { vector<int> v {10,20,30,30,20,10,10,20}; // Once bir siralayalim sort (v.begin(), v.end()); // 10 10 10 20 20 20 30 30 auto low = std::lower_bound (begin(v), end(v), 20); // ^ auto up = std::upper_bound (begin(v), end(v), 20); // ^ std::cout << "lower_bound pozisyonu: " << (low- begin(v)) << endl; std::cout << "upper_bound pozisyonu: " << (up - begin(v)) << endl; return 0; } |
Şimdi geldi sıra assolistimize (addSorted) 🙂
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include <iostream> #include <vector> #include <string> #include <algorithm> #include <iterator> #include <cassert> using namespace std; void printContent(auto& container) { for (const auto &w : container) { cout << w << " "; } cout << endl; } // Assolistimiz void addSorted(vector<string> &v, const string &word) { const auto insertPos (lower_bound(begin(v), end(v), word)); v.insert(insertPos, word); } int main() { vector<string> v {"selim", "rasim", "kazım", "kutlu", "osman", "can","ali"}; printContent(v); // is_sorted detaylari için https://en.cppreference.com/w/cpp/algorithm/is_sorted assert(false == is_sorted(begin(v), end(v))); sort(begin(v), end(v)); assert(true == is_sorted(begin(v), end(v))); printContent(v); addSorted(v, "fatih"); printContent(v); addSorted(v, "ahmet"); printContent(v); addSorted(v, "lale"); printContent(v); return 0; } |
addSorted() metodu nasıl çalışıyor? Aslında bütün espri lower_bound() metodunda bütün listeyi bu metoda geçiriyoruz ve o da bize değeri ekleyeceğimiz yeri dönüyor. Daha sonra da vector sınıfının insert() metodu ile elemanı ekliyoruz.
Tabi şimdi bunu diğer konteynerler de kullanamaz mıyız diye sorduğunu duyar gibiyim. Elbette sevgili yazılımperver dostum elbette. Bunun için “template” ları kullanacağız. Aşağıda daha jenerik addSorted() metodumuz ve bunu list ile olan kullanımını bulabilirsin.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include <iostream> #include <list> #include <string> #include <algorithm> #include <iterator> using namespace std; void printContent(auto& container) { for (const auto &w : container) { cout << w << " "; } cout << endl; } template <typename C, typename T> void addSorted(C &v, const T &item) { const auto insert_pos (lower_bound(begin(v), end(v), item)); v.insert(insert_pos, item); } int main() { list<string> v; addSorted<list<string>, string>(v, "deneme"); printContent(v); addSorted<list<string>, string>(v, "fatih"); printContent(v); addSorted<list<string>, string>(v, "ahmet"); printContent(v); addSorted<list<string>, string>(v, "lale"); printContent(v); return 0; } |
Bir sonraki haftalık C++ yazımda görüşmek üzere.
Kendinize iyi bakın.
Aslında unordered’lar da Associative konteynerler. 3 ana gruba ayrılsa başta daha mantıklı gibi. İyi çalışmalar
Doğrudur, sırasız konteyner’ler de aslında “associative”, fakat map ve set gibi olanlardan da farklılar (hem kullanılan veri yapıları hem de anahtarların yönetilmesi anlamında). Bu sebeple ayrılıyorlar. Bu bağlamda ilgili grup ismini güncelledim.
Elbette, “Associative” vs “Sequential” diye de bir ayrıma gidilebilir ama genel kabül gören yaklaşım bu.