How can I efficiently generate a Set<Id> from a List<SObject> structure?

This trick only works on the Id field, but you can use the Map constructor that accepts an SObject list to do this without consuming a script statement for each element in the List.

For example:

List<SObject> results = Database.query(someSOQL);
Set<Id> resultIds = (new Map<Id,SObject>(results)).keySet();

What this second line does is create a new Map<Id,SObject> from the results list using a special constructor, and then take the map's set of keys via the keySet() method. Then the map falls out of scope and it's heap space is released, leaving you with a very governor-efficient set.

If you are not using Dynamic SOQL, you can skinny this down to a one-liner like this...

Set<Id> ids = (new Map<Id, Lead>([SELECT Id FROM Lead])).keySet();

This is how you would do it with Dynamic SOQL but you must cast...

Set<Id> ids = (new Map<Id, Lead>((List<Lead>)Database.query(query))).keySet();

This unresolved bug is why you must cast the returned List<SObject>

There is an issue with the accepted methodology that can come up if you are not sure each element is in the list only once. It won't matter if you are sure the input is a SOQL result, but if you are writing a utility where you need to get the desired Set<Id> without knowing the source of the List<SObject>, it may be necessary to adopt a different approach.

The bug can be demonstrated fairly simply, though I don't have a less contrived use case handy.

Lead record = [SELECT Id FROM Lead LIMIT 1];
List<Lead> recordsWithDuplicate = new List<Lead> { record, record };
Set<Id> recordIds = new Map<Id, Lead>(recordsWithDuplicate);

The above snippet results in:

System.ListException: Row with duplicate Id at index: 1

To avoid that, you can use putAll, though it may actually be slower than just using a for loop.

Map<Id, Lead> recordsMap = new Map<Id, Lead>();
recordsMap.putAll(recordsWithDuplicate);
Set<Id> recordIds = recordsMap.keySet();

---

One more note, I take issue with the contention that the results of Database.query must be cast to get the Set<Id>. The following compiles and executes without issue:

public static Set<Id> getRecordIds(SObjectType token)
{
    return new Map<Id, SObject>(Database.query('SELECT Id FROM ' + token)).keySet();
}