Good data structure for efficient insert/querying on arbitrary properties
c#, data-structures
Solution
For in memory, you have a few options.
Most options will be O(n). That being said, Dictionary lookups can approach O(1).
One option is to store your customers in multiple Dictionaries, each with a key set to the Name, Id, and Age. If you use the same object references in the dictionaries, you can make any single lookup O(1), without a huge amount of overhead.
Granted, this becomes less practical as your criteria count rises, but with 3, it's not too bad.
If you want more flexibility, then a database is an appropriate option. Many databases have the option of working as a completely in-memory database, including SQLite, which would allow arbitrary queries at much better than O(n) speed.
Problem
I'm working on a project where Arrays are the default data structure for everything, and every query is a linear search in the form of: - Need a customer with a particular name? `customer.Find(x => x.Name == name)` - Need a customer with a particular unique id? `customer.Find(x => x.Id == id)` - Need a customer of a particular type and age? `customer.Find(x => x is PreferredCustomer && x.Age >= age)` - Need a customer of a particular name and age? `customer.Find(x => x.Name == name && x.Age == age)` In almost all instances, the criteria for lookups is well-defined. For example, we only search for customers by one or more of the properties Id, Type, Name, or Age. We rarely search by anything else. Is a good data structure to support arbitrary queries of these types with lookup better than O(n)? Any out-of-the-box implementations for .NET?