diff --git a/tests/test-hyperbolic-calculator.cpp b/tests/test-hyperbolic-calculator.cpp
index 1d22028..664b006 100644
--- a/tests/test-hyperbolic-calculator.cpp
+++ b/tests/test-hyperbolic-calculator.cpp
@@ -152,7 +152,7 @@
   NexthopList& bHopList = entryB->getNexthopList();
   BOOST_REQUIRE_EQUAL(bHopList.getNextHops().size(), 2);
 
-  for (std::list<NextHop>::iterator it = bHopList.begin(); it != bHopList.end(); ++it) {
+  for (std::set<NextHop, NextHopComparator>::iterator it = bHopList.begin(); it != bHopList.end(); ++it) {
     std::string faceUri = it->getConnectingFaceUri();
     uint64_t cost = it->getRouteCostAsAdjustedInteger();
 
@@ -166,7 +166,7 @@
   NexthopList& cHopList = entryC->getNexthopList();
   BOOST_REQUIRE_EQUAL(cHopList.getNextHops().size(), 2);
 
-  for (std::list<NextHop>::iterator it = cHopList.begin(); it != cHopList.end(); ++it) {
+  for (std::set<NextHop, NextHopComparator>::iterator it = cHopList.begin(); it != cHopList.end(); ++it) {
     std::string faceUri = it->getConnectingFaceUri();
     uint64_t cost = it->getRouteCostAsAdjustedInteger();
 
diff --git a/tests/test-link-state-calculator.cpp b/tests/test-link-state-calculator.cpp
index 8cc00a7..e3a6b3e 100644
--- a/tests/test-link-state-calculator.cpp
+++ b/tests/test-link-state-calculator.cpp
@@ -244,7 +244,7 @@
   NexthopList& bHopList = entryB->getNexthopList();
   BOOST_REQUIRE_EQUAL(bHopList.getNextHops().size(), 1);
 
-  NextHop& nextHopForB = bHopList.getNextHops().front();
+  const NextHop& nextHopForB = *(bHopList.getNextHops().begin());
 
   BOOST_CHECK(nextHopForB.getConnectingFaceUri() == ROUTER_B_FACE &&
               nextHopForB.getRouteCostAsAdjustedInteger() == LINK_AB_COST);
@@ -256,7 +256,7 @@
   NexthopList& cHopList = entryC->getNexthopList();
   BOOST_REQUIRE_EQUAL(cHopList.getNextHops().size(), 1);
 
-  NextHop& nextHopForC = cHopList.getNextHops().front();
+  const NextHop& nextHopForC = *(cHopList.getNextHops().begin());
 
   BOOST_CHECK(nextHopForC.getConnectingFaceUri() == ROUTER_C_FACE &&
               nextHopForC.getRouteCostAsAdjustedInteger() == LINK_AC_COST);
diff --git a/tests/test-nexthop-list.cpp b/tests/test-nexthop-list.cpp
index 1ab18da..f4290ef 100644
--- a/tests/test-nexthop-list.cpp
+++ b/tests/test-nexthop-list.cpp
@@ -86,32 +86,77 @@
 
 BOOST_AUTO_TEST_CASE(TieBreaker)
 {
+  // equal-cost hops are sorted lexicographically
   NextHop hopA;
   hopA.setRouteCost(25);
-  hopA.setConnectingFaceUri("AAA");
+  hopA.setConnectingFaceUri("AAAZZ");
 
   NextHop hopZ;
   hopZ.setRouteCost(25);
-  hopZ.setConnectingFaceUri("ZZZ");
+  hopZ.setConnectingFaceUri("ZZA");
 
   NexthopList list;
   list.addNextHop(hopA);
   list.addNextHop(hopZ);
 
-  list.sort();
-
   NexthopList::iterator it = list.begin();
   BOOST_CHECK_EQUAL(it->getConnectingFaceUri(), hopA.getConnectingFaceUri());
 
   list.reset();
-
   list.addNextHop(hopZ);
   list.addNextHop(hopA);
 
-  list.sort();
-
   it = list.begin();
   BOOST_CHECK_EQUAL(it->getConnectingFaceUri(), hopA.getConnectingFaceUri());
+
+
+  // equal-cost and lexicographically equal hops are sorted by the length of their face uris
+  NextHop longUriHop;
+  longUriHop.setRouteCost(25);
+  longUriHop.setConnectingFaceUri("AAAAAA");
+
+  NextHop shortUriHop;
+  shortUriHop.setRouteCost(25);
+  shortUriHop.setConnectingFaceUri("AAA");
+
+  list.reset();
+  list.addNextHop(longUriHop);
+  list.addNextHop(shortUriHop);
+
+  it = list.begin();
+  BOOST_CHECK_EQUAL(it->getConnectingFaceUri(), shortUriHop.getConnectingFaceUri());
+}
+
+BOOST_AUTO_TEST_CASE(SortOnAddAndRemove)
+{
+  NexthopList list;
+
+  NextHop hopA("A", 10);
+  NextHop hopB("B", 5);
+  NextHop hopC("C", 25);
+
+  list.addNextHop(hopA);
+  list.addNextHop(hopB);
+  list.addNextHop(hopC);
+
+  BOOST_REQUIRE_EQUAL(list.getSize(), 3);
+
+  double lastCost = 0;
+  for (const auto& hop : list) {
+    BOOST_CHECK(hop.getRouteCost() > lastCost);
+    lastCost = hop.getRouteCost();
+  }
+
+  // removing a hop keep the list sorted
+  list.removeNextHop(hopA);
+
+  BOOST_REQUIRE_EQUAL(list.getSize(), 2);
+
+  lastCost = 0;
+  for (const auto& hop : list) {
+    BOOST_CHECK(hop.getRouteCost() > lastCost);
+    lastCost = hop.getRouteCost();
+  }
 }
 
 BOOST_AUTO_TEST_SUITE_END()