You've found that the abstraction isn't useful for doing your task. That's not leaking. That's like complaining that your ice cream maker can't cook rice. That's not what it's for.
In fact, this is a common manner for abstractions to become leaky. You find you are in need some guarantee not present in the abstraction. You choose to add whether or not that guarantee is satisfied to the shared interface. Congratulations! You've added a leak to the abstraction.
But that's not the only option available. If you need a guarantee not provided by an abstraction, you could ignore the abstraction and use something that actually provides the guarantees you need.
Abstractions are equivalences, not equalities. You shouldn't expect an abstraction to make a linked list the same thing as a vector - they aren't, and they never will be - but they are equivalent for certain purposes, and a good abstraction can capture that equivalence. The performance of those two different collections is not the same, but that's not a leak unless the abstraction tried to claim that it somehow would be the same.
> You shouldn't expect an abstraction to make a linked list the same thing as a vector - they aren't, and they never will be
I would even argue that's the point of an abstraction. Hide the details that don't matter to the caller. If performance is a detail that matters, and the abstraction doesn't capture it, then you're using the wrong abstraction.
In fact, this is a common manner for abstractions to become leaky. You find you are in need some guarantee not present in the abstraction. You choose to add whether or not that guarantee is satisfied to the shared interface. Congratulations! You've added a leak to the abstraction.
But that's not the only option available. If you need a guarantee not provided by an abstraction, you could ignore the abstraction and use something that actually provides the guarantees you need.