![[:tr]Haftalık C++ 2 – Konteynerler ve sıralı tutma [:en]Weekly C++ 2 – Containers and keeping sorted [:]](https://sp-ao.shortpixel.ai/client/to_webp,q_glossy,ret_img,w_32,h_32/https://yazilimperver.net/wp-content/uploads/2017/12/FeaturedImage-e1580417052514.png){kind=small}
[:tr]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.[:en]Hello everybody,
We continue to our Weekly C++ posts. This week’s problem is to check if it is possible to keep the containers like std::vector sorted as inserting new elements. Well the short answer is yes!
Before delving into problem, let me briefly talk about containers as we need to mention the nature of containers while dealing with problem. I will not explain all details but if you are interested in details you can check this page out. You can find a summary of all classes and operations.
STL contains many data structures that you may need during developing your applications. Generally, these are optimized and efficient classes which are being used extensively in production code. Most of them have similar interfaces and very well documented. We can group these containers as follow:
- Sequence containers
- Covers the data structures that store same type of data sequentially,
- 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) are the containers that listed under this group.
- Associative containers
- Covers the sorted data structures that can be quickly searched,
- 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ı) are the containers that listed under this group.
- Unordered containers
- Different from the previous group of containers, these containers are not ordered, however, they use hash data structure for fast access and search,
- These are introduced with C++ 11 ,
- unordered_set, unordered_map, unordered_multiset ve unordered_multimap are the containers that listed under this groups. These are the hash-based version of associative containers.
- Container adapters
- This group of containers are wrapper to sequential container which provide different interfaces,
- stack (“LIFO – Last in first out” yığın veri yapısı), queue (“LILO – Last in last out” kuyruk veri yapısı) ve priority_queue are the containers that listed under this group. In fact, similar behavior and capabilities can be achieved with containers using vector, deque and list.
Now lets go back to our problem. We have a sequential container (e.g. vector) and we would like to keep it sorted with consequtive insertion operations. How can we achieve this?
Well, obviously the first method is to use the sort() method provided by “algorithm” library which as you may guess will not be cheap 🙂 Now, lets initialize a vector and then sort it:
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"}; // For details of is_sorted check out: 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; } |
Well, to resolve this problem, we will employ another method from “algorithm” library which is lower_bound() method. You can find the signature of this method below:
1 2 | template <class ForwardIterator, class T> ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val); |
Briefly this method returns the iterator that points the index of first element which is not less (which of course might be equal) than provided value in given range of [First, Last) .
For instance, for provided {10, 20, 30, 40, 50} input and range of [10, 50] and 35 input value it will return 3 and for input value 15 it will return 1.
You can find an example usage of this method with its sister (upper_bound()):
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}; // First sort the input 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 index: " << (low- begin(v)) << endl; std::cout << "upper_bound index: " << (up - begin(v)) << endl; return 0; } |
Finally, let’s define our method: 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; } // Our method 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); // For details of is_sorted check out 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; } |
how addSorted() method works? In fact, lower_bound() performs the most of the task that we need and return the place that we should add new element. Then what we need to do is simply call insert() method of vector.
Now you may wonder if we can utilize this method with other containers. Well, sure, as long as they are sequential container. To do so, we will get help from templates. Below you can find the generic version of addSorted() method and example usage with list container.
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; } |
See you soon in another Weekly C++ post.[:]
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.