C++
std :: set och std :: multiset

Introduktion

Anmärkningar

Infoga värden i en uppsättning

Tre olika sätt att infoga kan användas med uppsättningar.

• Först en enkel insättning av värdet. Denna metod returnerar ett par som låter den som ringer kontrollera om insatsen verkligen inträffade.
• För det andra, en insats genom att ge en antydan om var värdet kommer att infogas. Målet är att optimera insättningstiden i ett sådant fall, men att veta var ett värde ska sättas in är inte det vanliga fallet. Var försiktig i så fall; sättet att ge ett tips skiljer sig åt med kompilatorversioner .
• Slutligen kan du infoga ett intervall värden genom att ge en start- och slutpekare. Den första kommer att inkluderas i infogningen, den slutande är utesluten.

#include <iostream>
#include <set>

int main ()
{
  std::set<int> sut;
  std::set<int>::iterator it;
  std::pair<std::set<int>::iterator,bool> ret;

  // Basic insert
  sut.insert(7);
  sut.insert(5);
  sut.insert(12);
  
  ret = sut.insert(23);
  if (ret.second==true)
    std::cout << "# 23 has been inserted!" << std::endl;
    
  ret = sut.insert(23); // since it's a set and 23 is already present in it, this insert should fail
  if (ret.second==false)
    std::cout << "# 23 already present in set!" << std::endl;
 
  // Insert with hint for optimization
  it = sut.end();
  // This case is optimized for C++11 and above
  // For earlier version, point to the element preceding your insertion
  sut.insert(it, 30); 

  // inserting a range of values
  std::set<int> sut2;
  sut2.insert(20);
  sut2.insert(30);
  sut2.insert(45);
  std::set<int>::iterator itStart = sut2.begin();
  std::set<int>::iterator itEnd = sut2.end();
  
  sut.insert (itStart, itEnd); // second iterator is excluded from insertion

  std::cout << std::endl << "Set under test contains:" << std::endl;
  for (it = sut.begin(); it != sut.end(); ++it)
  {
    std::cout << *it << std::endl;
  }

  return 0;
}

Output kommer att vara:

# 23 has been inserted!                                                                                                                                                                                                                                                                                                   
# 23 already present in set!                                                                                                                                                                                                                                                                                              
                                                                                                                                                                                                                                                                                                                          
Set under test contains:                                                                                                                                                                                                                                                                                                  
5                                                                                                                                                                                                                                                                                                                         
7                                                                                                                                                                                                                                                                                                                         
12                                                                                                                                                                                                                                                                                                                        
20                                                                                                                                                                                                                                                                                                                        
23                                                                                                                                                                                                                                                                                                                        
30                                                                                                                                                                                                                                                                                                                        
45   

Infoga värden i en multiset

Alla infogningsmetoder från uppsättningar gäller också för multiset. Ändå finns det en annan möjlighet, som är att tillhandahålla en initialisatorlista:

auto il = { 7, 5, 12 };
std::multiset<int> msut;
msut.insert(il);

Ändra standardsort för en uppsättning

set och multiset har standardjämförelsemetoder, men i vissa fall kan du behöva överbelasta dem.

Låt oss föreställa oss att vi lagrar strängvärden i en uppsättning, men vi vet att strängarna endast innehåller numeriska värden. Som standard är sorteringen en leksikografisk strängjämförelse, så ordningen stämmer inte med den numeriska sorteringen. Om du vill använda en sortering som motsvarar vad du skulle ha med int värden, behöver du en funktor för att överbelasta jämförelsemetoden:

#include <iostream>
#include <set>
#include <stdlib.h> 

struct custom_compare final
{
    bool operator() (const std::string& left, const std::string& right) const
    {
        int nLeft = atoi(left.c_str());
        int nRight = atoi(right.c_str());
        return nLeft < nRight;
    }
};

int main ()
{
    std::set<std::string> sut({"1", "2", "5", "23", "6", "290"});
  
    std::cout << "### Default sort on std::set<std::string> :" << std::endl;
    for (auto &&data: sut)
        std::cout << data << std::endl;
  
    std::set<std::string, custom_compare> sut_custom({"1", "2", "5", "23", "6", "290"},
                                                     custom_compare{}); //< Compare object optional as its default constructible.
  
    std::cout << std::endl << "### Custom sort on set :" << std::endl;
    for (auto &&data : sut_custom)
        std::cout << data << std::endl;
  
    auto compare_via_lambda = [](auto &&lhs, auto &&rhs){ return lhs > rhs; };
    using set_via_lambda = std::set<std::string, decltype(compare_via_lambda)>;
    set_via_lambda sut_reverse_via_lambda({"1", "2", "5", "23", "6", "290"},
                                          compare_via_lambda);
  
    std::cout << std::endl << "### Lambda sort on set :" << std::endl;
    for (auto &&data : sut_reverse_via_lambda)
        std::cout << data << std::endl;

    return 0;
}

Output kommer att vara:

### Default sort on std::set<std::string> :
1
2
23
290
5
6
### Custom sort on set :
1
2
5
6
23
290  

### Lambda sort on set :
6
5
290
23
2
1

I exemplet ovan kan man hitta 3 olika sätt att lägga till jämför operationer till std::set , var och en av dem är användbara i sitt eget sammanhang.

Standard sortering

Detta kommer att använda jämförelseoperatören för nyckeln (första mallargument). Ofta ger nyckeln redan ett bra standard för std::less<T> -funktionen. Om inte den här funktionen är specialiserad, använder den objektets operator< . Detta är särskilt användbart när andra kod också försöker använda viss beställning, eftersom detta möjliggör konsistens över hela kodbasen.

Att skriva koden på detta sätt kommer att minska ansträngningen att uppdatera din kod när nyckeländringarna är API, som: en klass som innehåller 2 medlemmar som ändras till en klass som innehåller 3 medlemmar. Genom att uppdatera operator< i klassen uppdateras alla händelser.

Som du kan förvänta dig är att använda standardsorten ett rimligt standard.

Anpassad sortering

Lägga till en anpassad sortering via ett objekt med en jämföroperator används ofta när standardjämförelsen inte överensstämmer. I exemplet ovan beror detta på att strängarna avser heltal. I andra fall används det ofta när du vill jämföra (smarta) pekare baserat på objektet de hänvisar till eller eftersom du behöver olika begränsningar för att jämföra (exempel: jämföra std::pair med värdet på first ).

När du skapar en jämförande operatör bör detta vara en stabil sortering. Om resultatet från jämföroperatören ändras efter infogning har du odefinierat beteende. Som en bra praxis bör din jämföroperatör endast använda konstantdata (const-medlemmar, const-funktioner ...).

Som i exemplet ovan kommer du ofta att träffa klasser utan medlemmar som jämför operatörer. Detta resulterar i standardkonstruktörer och kopieringskonstruktörer. Standardkonstruktören låter dig utelämna instansen vid konstruktionstiden och kopieringskonstruktören krävs eftersom uppsättningen tar en kopia av jämföroperatören.

Lambda sortering

Lambdas är ett kortare sätt att skriva funktionsobjekt. Detta gör det möjligt att skriva jämföroperatören på mindre linjer, vilket gör den totala koden mer läsbar.

Nackdelen med användningen av lambdas är att varje lambda får en specifik typ vid sammanställningstiden, så decltype(lambda) kommer att vara annorlunda för varje sammanställning av samma kompilationsenhet (cpp-fil) som över flera kompilationsenheter (när de ingår via rubrikfil) ). Av detta skäl rekommenderas det att använda funktionsobjekt som jämför operatör när de används i rubrikfiler.

Denna konstruktion stöter ofta på när en std::set används inom den lokala räckvidden för en funktion istället, medan funktionsobjektet föredras när det används som funktionsargument eller klassmedlemmar.

Andra sorteringsalternativ

Eftersom jämföroperatören för std::set är ett mallargument kan alla utrullningsbara objekt användas som jämföroperatör och exemplen ovan är endast specifika fall. De enda begränsningarna som dessa kallbara objekt har är:

• De måste vara kopierbara
• De måste kunna kallas med två argument av nyckeltypen. (implicita konverteringar är tillåtna, men rekommenderas inte eftersom det kan skada prestanda)

Söker värden i uppsättning och multiset

Det finns flera sätt att söka efter ett givet värde i std::set eller i std::multiset :

För att få iteratorn för den första förekomsten av en nyckel kan funktionen find() användas. Det returnerar end() om nyckeln inte finns.

  std::set<int> sut;
  sut.insert(10);
  sut.insert(15);
  sut.insert(22);
  sut.insert(3); // contains 3, 10, 15, 22    

  auto itS = sut.find(10); // the value is found, so *itS == 10
  itS = sut.find(555); // the value is not found, so itS == sut.end()   

  std::multiset<int> msut;
  sut.insert(10);
  sut.insert(15);
  sut.insert(22);
  sut.insert(15);
  sut.insert(3); // contains 3, 10, 15, 15, 22  

  auto itMS = msut.find(10);

Ett annat sätt är att använda funktionen count() , som räknar hur många motsvarande värden som har hittats i set / multiset (i fall av en set kan returvärdet endast vara 0 eller 1). Med samma värden som ovan kommer vi att ha:

int result = sut.count(10); // result == 1
result = sut.count(555); // result == 0

result = msut.count(10); // result == 1
result = msut.count(15); // result == 2

När det gäller std::multiset kan det finnas flera element med samma värde. För att få detta intervall kan equal_range() användas. Det returnerar std::pair med iterator respektive nedre gräns (inklusive) och övre gräns (exklusiv). Om nyckeln inte finns, skulle båda iteratorerna peka på närmaste överlägsen värde (baserat på jämförningsmetod som används för att sortera det givna multiset ).

auto eqr = msut.equal_range(15);
auto st = eqr.first; // point to first element '15'
auto en = eqr.second; // point to element '22'

eqr = msut.equal_range(9); // both eqr.first and eqr.second point to element '10'

Radera värden från en uppsättning

Den mest uppenbara metoden, om du bara vill återställa din uppsättning / multiset till en tom, är att använda clear :

  std::set<int> sut;
  sut.insert(10);
  sut.insert(15);
  sut.insert(22);
  sut.insert(3); 
  sut.clear(); //size of sut is 0

Sedan kan erase användas. Det erbjuder några möjligheter som ser något ut som inlägget:

std::set<int> sut;
std::set<int>::iterator it;
          
sut.insert(10);
sut.insert(15);
sut.insert(22);
sut.insert(3); 
sut.insert(30);
sut.insert(33);
sut.insert(45);
    
// Basic deletion
sut.erase(3);
    
// Using iterator
it = sut.find(22);
sut.erase(it);
          
// Deleting a range of values
it = sut.find(33);
sut.erase(it, sut.end());
    
std::cout << std::endl << "Set under test contains:" << std::endl;
for (it = sut.begin(); it != sut.end(); ++it)
{
  std::cout << *it << std::endl;
}

Output kommer att vara:

Set under test contains:                                                                                                                                                                                                                                                                                                  
10                                                                                                                                                                                                                                                                                                                        
15                                                                                                                                                                                                                                                                                                                        
30 

Alla dessa metoder gäller också multiset . Observera att om du ber om att ta bort ett element från en multiset , och det finns flera gånger, kommer alla motsvarande värden att raderas .