C++23: Dört yeni ilişkisel kapsayıcı
Dört ilişkisel kapsayıcı std::flat_map, std::flat_multimap, std::flat_set VE std::flat_multiset C++23’te sıralanmış ilişkisel kapların basit bir alternatifidirler std::map, std::multimap, std::set VE std::multiset. C++23’te bunlara iki nedenden dolayı sahibiz: bellek kullanımı ve performans.
Duyuru
Rainer Grimm uzun yıllardır yazılım mimarı, ekip lideri ve eğitim yöneticisi olarak çalışmaktadır. C++, Python ve Haskell programlama dilleri üzerine makaleler yazmayı seviyor ama aynı zamanda özel konferanslarda sık sık konuşmayı da seviyor. Modernes C++ adlı blogunda yoğun bir şekilde C++ tutkusundan bahsediyor.
C++23 ile 12 ilişkisel konteynerimiz var. On iki? Doğru!
ilişkisel kapsayıcılar
Tüm ilişkisel konteynerlerin ortak noktası, bir anahtarı bir değerle ilişkilendirmeleridir. Bu nedenle değeri anahtarı kullanarak alabilirsiniz. C++98 ilişkisel kapları sıralanmış ilişkisel kaplardır, C++11 ilişkisel kapları ise sıralanmamış ilişkisel kaplardır.
Duyuru
İlişkisel kapsayıcıları sınıflandırmak için üç basit soruyu yanıtlamanız gerekir:
İlişkisel konteynerlerin performans özelliklerini anlamak için daha fazla bilgi vermek istiyorum.
Düzgün ilişkisel kaplar
Sıralanan ilişkisel kapların anahtarları sıralanır. Varsayılan olarak en küçük ilişki (p>
Bu emrin ilginç sonuçları var.
std::map<int, std::string> int2String{
{3, "three"}, {2, "two"}, {1, "one"},
{5, "five"}, {6, "six"}, {4, "four"},
{7, "seven"} };
Dengeli ikili arama ağacı aşağıdaki yapıya sahip olabilir:
Sırasız ilişkisel kapsayıcılar
Sırasız ilişkisel kapsayıcıların ana fikri, anahtarın karma işlevi kullanılarak kovaya eşlenmesidir. Değer basitçe anahtara eklenir.
Sırasız ilişkisel kaplar, anahtarları kovalarda saklar. Anahtarın hangi pakete gideceği, anahtarı benzersiz bir sayıyla eşleştiren karma işlevine bağlıdır. Bu sayı modül grubu sayısına bölünür. Farklı anahtarlar aynı pakete eşlendiğinde buna çarpışma denir. İyi bir karma işlevi, anahtarları eşit şekilde dağıtır. Değer basitçe anahtara bağlıdır.
Hash fonksiyonunu kullanmanın sırasız ilişkisel kapsayıcı için önemli sonuçları vardır.
std::unordered_map<std::string, int> str2Int{
{"Grimm",491634333356},
{"Grimm-Jaud", 49160123335},
{"Schmidt",4913333318},
{"Huber",490001326} };
Grafik, karma işlevi kullanılarak anahtarların ilgili gruba nasıl atandığını gösterir.
Dört ilişkisel kapsayıcı std::flat_map, std::flat_multimap, std::flat_set VE std::flat_multiset C++23’te sıralanmış ilişkisel kapların basit bir alternatifidirler std::map, std::multimap, std::set VE std::multiset.
konteyner adaptörleri
C++23’teki ilişkisel düz sıralı konteynerler, C++98 benzerleriyle aynı arayüzü paylaşır.
Basit sıraya sahip ilişkisel kapsayıcılar, anahtarları ve değerleri için ayrı sıralı kapsayıcılar gerektirdiğinden kapsayıcı bağdaştırıcıları olarak adlandırılır. Bu sıralı kapsayıcının rastgele erişim yineleyicisini desteklemesi gerekir. Varsayılan olarak bir std::vector kullanılmış, aynı zamanda bir std::array ah std::deque Mümkün.
Aşağıdaki kod parçacığı bildirimini gösterir: std::flat_map VE std::flat_set:
template<class Key, class T,
class Compare = less<Key>,
class KeyContainer = vector<Key>,
class MappedContainer = vector<T>>
class flat_map;
template<class Key,
class Compare = less<Key>,
class KeyContainer = vector<Key>>
class flat_set;
Düz sıralı ilişkisel konteynerlerin nedeni performanstır.
Düz sıralı konteynerler ile bunların düz olmayan muadillerinin karşılaştırılması
THE ilişkisel konteyner düzenli düz sipariş edilen kaplardan farklı saklama süreleri ve karmaşıklık sunar. Daha az depolama alanı kaplarlar ve sıralanmamış benzerlerine göre daha hızlı okunurlar. Rastgele erişim yineleyicisi sağlarlar.
THE düzenli çağrışımsal kapsayıcı düz değil Bir öğeyi eklerken veya silerken performansı artırın. Ayrıca yineleyicilerin bir öğe eklendikten veya silindikten sonra da geçerli kalmasını sağlarlar. Çift yönlü yineleyiciyi desteklerler.
Şu ana kadar herhangi bir sayı gösteremiyorum çünkü hiçbir derleyici düz sıralı ilişkisel kapsayıcıları desteklemez. “Std::map ve std::unordered_map ile daha özel arkadaşlar” performans testimi şu durumlarda güncelleyeceğim: std::flat_map mevcut.
Sıradaki ne?
A std::mdspan bitişik bir nesne dizisinin tescilli olmayan çok boyutlu bir görünümüdür. Bu bitişik nesne dizisi, a boyutunda bir işaretçi olan basit bir C dizisi olabilir. std::arrayA std::vector ah std::string Olmak.
(rm)
Haberin Sonu
C++23: Dört yeni ilişkisel kapsayıcı
Dört ilişkisel kapsayıcı std::flat_map, std::flat_multimap, std::flat_set VE std::flat_multiset C++23’te sıralanmış ilişkisel kapların basit bir alternatifidirler std::map, std::multimap, std::set VE std::multiset. C++23’te bunlara iki nedenden dolayı sahibiz: bellek kullanımı ve performans.
Duyuru
Rainer Grimm uzun yıllardır yazılım mimarı, ekip lideri ve eğitim yöneticisi olarak çalışmaktadır. C++, Python ve Haskell programlama dilleri üzerine makaleler yazmayı seviyor ama aynı zamanda özel konferanslarda sık sık konuşmayı da seviyor. Modernes C++ adlı blogunda yoğun bir şekilde C++ tutkusundan bahsediyor.
C++23 ile 12 ilişkisel konteynerimiz var. On iki? Doğru!
- C++98: std::map, std::set, std::multimap VE std::multiset
- C++11: std::unordered_map, std::unordered_set, std::unordered_multimap VE std::unordered_multiset
- C++23: std::flat_map, std::flat_set, std::flat_multimap VE std::flat_multiset
ilişkisel kapsayıcılar
Tüm ilişkisel konteynerlerin ortak noktası, bir anahtarı bir değerle ilişkilendirmeleridir. Bu nedenle değeri anahtarı kullanarak alabilirsiniz. C++98 ilişkisel kapları sıralanmış ilişkisel kaplardır, C++11 ilişkisel kapları ise sıralanmamış ilişkisel kaplardır.
Duyuru
İlişkisel kapsayıcıları sınıflandırmak için üç basit soruyu yanıtlamanız gerekir:
- Anahtarlar düzenli mi?
- Anahtarın ilişkili bir değeri var mı?
- Bir anahtar birden fazla görünebilir mi?
İlişkisel konteynerlerin performans özelliklerini anlamak için daha fazla bilgi vermek istiyorum.
Düzgün ilişkisel kaplar
Sıralanan ilişkisel kapların anahtarları sıralanır. Varsayılan olarak en küçük ilişki (p>
Bu emrin ilginç sonuçları var.
- Anahtar bir sipariş ilişkisini desteklemelidir.
- İlişkisel kapsayıcılar genellikle kırmızı-siyah ağaçlar olarak uygulanır. Bunlar dengeli ikili arama ağaçlarıdır.
- Anahtara ve dolayısıyla değere erişim süresi logaritmiktir.
std::map<int, std::string> int2String{
{3, "three"}, {2, "two"}, {1, "one"},
{5, "five"}, {6, "six"}, {4, "four"},
{7, "seven"} };
Dengeli ikili arama ağacı aşağıdaki yapıya sahip olabilir:
Sırasız ilişkisel kapsayıcılar
Sırasız ilişkisel kapsayıcıların ana fikri, anahtarın karma işlevi kullanılarak kovaya eşlenmesidir. Değer basitçe anahtara eklenir.
Sırasız ilişkisel kaplar, anahtarları kovalarda saklar. Anahtarın hangi pakete gideceği, anahtarı benzersiz bir sayıyla eşleştiren karma işlevine bağlıdır. Bu sayı modül grubu sayısına bölünür. Farklı anahtarlar aynı pakete eşlendiğinde buna çarpışma denir. İyi bir karma işlevi, anahtarları eşit şekilde dağıtır. Değer basitçe anahtara bağlıdır.
Hash fonksiyonunu kullanmanın sırasız ilişkisel kapsayıcı için önemli sonuçları vardır.
- Anahtar için karma işlevi mevcut olmalıdır.
- Çarpışmaların üstesinden gelmek için anahtarların eşitlik karşılaştırmasını desteklemesi gerekir.
- Karma fonksiyonunun yürütme süresi sabit olduğundan, sırasız bir ilişkisel konteynerin anahtarlarına erişim süresi, anahtarlar eşit olarak dağıtıldığında sabittir.
std::unordered_map<std::string, int> str2Int{
{"Grimm",491634333356},
{"Grimm-Jaud", 49160123335},
{"Schmidt",4913333318},
{"Huber",490001326} };
Grafik, karma işlevi kullanılarak anahtarların ilgili gruba nasıl atandığını gösterir.
Dört ilişkisel kapsayıcı std::flat_map, std::flat_multimap, std::flat_set VE std::flat_multiset C++23’te sıralanmış ilişkisel kapların basit bir alternatifidirler std::map, std::multimap, std::set VE std::multiset.
konteyner adaptörleri
C++23’teki ilişkisel düz sıralı konteynerler, C++98 benzerleriyle aynı arayüzü paylaşır.
Basit sıraya sahip ilişkisel kapsayıcılar, anahtarları ve değerleri için ayrı sıralı kapsayıcılar gerektirdiğinden kapsayıcı bağdaştırıcıları olarak adlandırılır. Bu sıralı kapsayıcının rastgele erişim yineleyicisini desteklemesi gerekir. Varsayılan olarak bir std::vector kullanılmış, aynı zamanda bir std::array ah std::deque Mümkün.
Aşağıdaki kod parçacığı bildirimini gösterir: std::flat_map VE std::flat_set:
template<class Key, class T,
class Compare = less<Key>,
class KeyContainer = vector<Key>,
class MappedContainer = vector<T>>
class flat_map;
template<class Key,
class Compare = less<Key>,
class KeyContainer = vector<Key>>
class flat_set;
Düz sıralı ilişkisel konteynerlerin nedeni performanstır.
Düz sıralı konteynerler ile bunların düz olmayan muadillerinin karşılaştırılması
THE ilişkisel konteyner düzenli düz sipariş edilen kaplardan farklı saklama süreleri ve karmaşıklık sunar. Daha az depolama alanı kaplarlar ve sıralanmamış benzerlerine göre daha hızlı okunurlar. Rastgele erişim yineleyicisi sağlarlar.
THE düzenli çağrışımsal kapsayıcı düz değil Bir öğeyi eklerken veya silerken performansı artırın. Ayrıca yineleyicilerin bir öğe eklendikten veya silindikten sonra da geçerli kalmasını sağlarlar. Çift yönlü yineleyiciyi desteklerler.
Şu ana kadar herhangi bir sayı gösteremiyorum çünkü hiçbir derleyici düz sıralı ilişkisel kapsayıcıları desteklemez. “Std::map ve std::unordered_map ile daha özel arkadaşlar” performans testimi şu durumlarda güncelleyeceğim: std::flat_map mevcut.
Sıradaki ne?
A std::mdspan bitişik bir nesne dizisinin tescilli olmayan çok boyutlu bir görünümüdür. Bu bitişik nesne dizisi, a boyutunda bir işaretçi olan basit bir C dizisi olabilir. std::arrayA std::vector ah std::string Olmak.
(rm)
Haberin Sonu