IP-Adressen artige Strings sortieren

shinji

Hallo!

Ich habe hier dutzende Strings in einem Format, ähnlich einer IPv4-Adresse. Diese Strings muss sortieren. Bei IPv4-Adressen geht dies ja relativ einfach mit

# Pseudocode einer Compare-Methode!!!
# IP-Adresse1: AAA.BBB.CCC.DDD
# IP-Adresse2: EEE.FFF.GGG.HHH

x += AAA << 24;
x += BBB << 16;
x += CCC << 8;
x += DDD;

y += EEE << 24;
y += FFF << 16;
y += GGG << 8;
y += HHH;

return (x==y ? 0: x < y ? -1 : 1);

Meine String sehen aber so aus:

XXXX.YYYYY.ZZZZZZZZ

mit

0 <= X <= 1023
0 <= Y <= 16383
0 <= Z <= 16777215

jetzt sollte 1.10.1000 natürlich NACH der 1.4.202345 kommen.
Ich bekomme das gerade nicht hin. Jemand eine Idee?

Fytch

Entweder du konvertierst die Ziffernfolgen in einen integralen Typen, oder du zählst zuerst die Anzahl der Ziffern, sortierst wenn ungleich und vergleichst nur im Falle der Gleichheit (der Anzahl) anhand der Ziffern selbst.

Wenn du den String immer mit 0 auf das Format XXXX.YYYYY.ZZZZZZZZ aufbläst, sollte auch ein Stringvergleich funktionieren.

Columbo

Ich bekomme das gerade nicht hin. Jemand eine Idee?

Wie hast du die Daten vorliegen? Hast du einen String, oder hast du einen Skalar...?

camper

evtl. ungefähr so?

int compare(string s1, string s2)
{
    auto len = min( s1.size(), s2.size() );
    auto mis = mismatch( s1.begin(), s1.begin() + len, s2.begin() );
    if ( mis.first == s1.end() && mis.second = s2.end() )        // s1 == s2
        return 0;
    auto f1 = find( mis.first, s1.end(), '.' ) - mis.first;
    auto f2 = find( mis.second, s2.end(), '.' ) - mis.second;
    if ( f1 != f2 )                                              // s1 != s2 (field size)
        return f1 < f2 ? -1 : 1;
    return *mis.first < *mis.second ? -1 : 1;                    // s1 != s2 (value)
}

ungetestet. Kann man bestimmt noch eleganter formulieren.

Hast Du dieses Format erfunden?

Warum arbeitest Du nicht mit einer Klasse, die die Komponenten einzeln vorhält?
So ein string erscheint mir arg unhandlich.

Irgendwie so in der Art:

#include <algorithm>
#include <iostream>
#include <string>
#include <tuple>

#include <cassert>
#include <cinttypes>
#include <cstdint>

class addr{
  std::uint16_t m_x;
  std::uint16_t m_y;
  std::uint32_t m_z;
public:
  addr(uint x=0u, uint y=0u, uint z=0u) : m_x(x), m_y(y), m_z(z){
    assert(!(1023<x));
    assert(!(16383<y));
    assert(!(16777215<z));
  }
  uint x() const { return m_x; }
  uint y() const { return m_y; }
  uint z() const { return m_z; }

  bool operator<(const addr& a) const {
    return std::tie(m_x,m_y,m_z)<std::tie(a.m_x,a.m_y,a.m_z);
  }
};

std::string to_string(const addr& a){
  static const auto N = sizeof("XXXX.YYYYY.ZZZZZZZZ");
  char str[N];
  std::snprintf(str, N, "%" PRIu16 ".%" PRIu16 ".%" PRIu32, a.x(), a.y(), a.z());
  return str;
}

std::ostream& operator<<(std::ostream& out, const addr& a){
  return out << to_string(a);
}

int main(){
  addr arr[]{{1,10,1000},{1,4,202345},{1,10,0}, {1023, 16383, 16777215}};
  std::sort(std::begin(arr), std::end(arr));
  for(const auto& a : arr)
    std::cout << a << '\n';
}

hustbaer

@shinji
Strings dieser Art sortiert man, indem man sie in mehrere Teile aufsplittet, und dann die Teile einzeln vergleicht. In deinem Fall ist das trivial, du kannst einfach immer "." als Trennzeichen verwenden.

Dann musst du die Strings beim Vergleichen nur noch "rechtsbündig vergleichen". D.h. wenn die Strings unterschiedlich lang sind, dann gewinnt der längere, und wenn sie gleich lang sind, dann kannst du einfach ganz normal nen String-Vergleich machen.

Alternativ kannst du die einzelnen Teile auch mit führenden Nullen auf gleiche Länge bringen und dann wieder einen einzigen String daraus zusammensetzen. Und dann diese wieder zusammengesetzten Strings vergleichen. (Das entspricht quasi dem was manni66 vorgeschlagen hat.)

hustbaer

@Furble Wurble
Cool, diese #defines (PRIu16 etc.) kannte ich noch gar nicht.