C++: Was ist der schnellste Weg ist, eine geordnete Tabelle von IP-Adresse

Question

Das ist das Problem aufrechtzuerhalten i Begegnung am:

1. Ein DNS-Abfrage-Ergebnisse in einer Liste der IP-Adresse in einer zufälligen Reihenfolge. Fo ex, wenn es 4 Adresse gibt, Abfrage 2 mal Ergebnisse in 4 Adresse kommt in anderer Reihenfolge.

2. Nun müssen Sie eine geordnete Tabelle einrichten, die auf die Adressen in O (1) zugreifen kann.

3. Mögliche Lösung wäre Reihenfolge der IP-Adresse jedes Mal. Wenn also beispielsweise 2, 1, 7, 4 empfangen werden, können wir sie sortieren, und das Ergebnis ist immer 1, 2, 4, 7, und indem wir die IP-Adresse in einen Vektor setzen, können wir sie mit O (1)

   indizieren
4. Das Problem entsteht, wenn das DNS 5 Adresse ergibt, sagen wir, die neue Adresse ist 3. Jetzt wird 3 zwischen der Tabelle hinzugefügt und Bestellung ist vermasselt, da das 3. Element sollte 4. Wir müssen hinzufügen Neue Elemente am Ende der Tabelle
5. Das Löschen des Elements muss ebenfalls ordnungsgemäß gehandhabt werden, da ein leerer Tabellensteckplatz das Problem verursachen kann.

Kann dies mit O (1) oder schlechteste O (lügt n)

Das Problem getan wird, ist eine Bestellung von IP jedes Mal adressiert eine geordnete Liste als Eingabe gegeben zu halten

Answer 1

etwas so was?

#include <unordered_map> 
#include <array> 
#include <algorithm> 
#include <initializer_list> 
#include <cassert> 

struct ip_address 
{ 
    ip_address(std::initializer_list<std::uint8_t> il) 
    { 
    auto max = std::min(il.size(),_ip4_data.size()); 
    assert(max == 4); 
    std::copy_n(il.begin(), max, _ip4_data.begin()); 
    } 
    auto& data() const { return _ip4_data; } 
    auto& data() { return _ip4_data; } 
    const uint8_t& operator[](std::size_t i) const { 
    return _ip4_data[i]; 
    } 
    std::array<std::uint8_t, 4> _ip4_data; 
}; 

bool operator==(const ip_address& l, const ip_address& r) 
{ 
    return l.data() == r.data(); 
} 

namespace std 
{ 
    template<> struct hash<ip_address> { 
    std::size_t operator()(const ip_address& r) const 
    { 
     // reverse the byte order so that the lsb of the ip 
     // has the greatest effect on the hash value 
     return std::size_t((r[3] << 24) & 0xff000000 
         + (r[2] << 16) & 0x00ff0000 
         + (r[1] << 8) & 0x0000ff00 
         + r[0] & 0x000000ff); 
    } 
    }; 
} 


using client_server_map = std::unordered_map<ip_address, ip_address>; 

int main() 
{ 
    client_server_map cs_map; 

    cs_map.emplace(ip_address{10, 0, 0, 1}, ip_address{192, 168, 0, 1}); 
    cs_map.emplace(ip_address{10, 0, 0, 2}, ip_address{192, 168, 0, 2}); 
    cs_map.erase(ip_address{10, 0, 0, 1}); 
}