Доступ к элементу массива struct.

Question

Так у меня есть-структуру

struct car{ 
    string ownerName; 
    float price; 
    int year; 
}; 

и я объявил массив этих структур машина * автомобили = новый автомобиль [1000] Каждый автомобиль имеет индекс, например, автомобиль с индексом 0 имеет имя Джона Смит.

Итак, мой вопрос - знать имя владельца, как мне получить доступ к индексу автомобиля. Я знаю, что по-другому я напишу cars [0] .name, , чтобы получить имя, но как бы сделать это назад?

Answer 1

Два возможных способа прийти мне в голову. Один пишет функцию, которая находит индекс по имени.

#include <string>  
using namespace std; 

car *find_by_name(car* cars, const string& name, int from, int to) { 
    car* car_ptr = NULL; 
    for(int i = from; i < to; i++) { 
     if (cars[i].ownerName == name) { 
      car_ptr = cars+i; 
      break; 
     } 
    } 
    return car_ptr; 
} 

Как вы можете заметить, эта функция очень дорога (O (n)). Другой, самый простой, на мой взгляд, использует Map или HashMap, чтобы сделать это.

#include <map> 
#include <string> 
#include <iostream> 
using namespace std; 

car set_new_val(map<string, car*>& my_map, const string& name, const float price, const int year) { 
    car* car_heap = new car(); 
    car_heap->ownerName = name; 
    car_heap->price = price; 
    car_hep->year = year; 
    my_map.insert(pair<string, car*>(name, car_heap)); 
} 

car* find_car_by_name(const map<string, car*>& my_map, const string& name) { 
    map<string, car*>::iterator it; 

    if ((it = my_map.find(name)) == my_map.end()) 
     return NULL; 
    return it->second; 
} 

int main(int argc, char* argv[]) { 
    map<string, car*> my_cars_data; 
    set_new_val(my_cars_data, "James", 2233000.5, 2013); 
    set_new_val(my_cars_data, "Dave", 1222000.5, 2011); 
    set_new_val(my_cars_data, "Aaron", 1222000.75, 2012); 

    car* james_car = find_car_by_name(my_cars_data, "James"); 
    cout << "Year " << james_car->year << endl; 
    car* null_car = find_car_by_name(my_cars_data, "Santa"); 
    if (null_car == NULL) 
     cout << "No owner with the name Santa is recorded" << endl; 
    ... 
    ... 

    free_map(my_map); 
    return 0; 

В соответствии с C++ 11, поиск по ключу с помощью Map занимает O (ЛГНО) (HashMap представляет собой О (1)), для более подробного чтения here. Это большой профессионал, если вы обрабатываете массу данных (не говоря уже о том, что их проще поддерживать).

Answer 2

Если вы используете последовательный контейнер (массив, вектор ...), вам нужно искать имя. В несортированном массиве требуется линейный поиск.

// linear search 

string name = "joe"; 
auto it = find_if(begin(cars), end(cars), 
    [&name](const car& c) { return c.ownerName == name; }); 

auto index = it - begin(cars); 

Если у вас есть проблемы с производительностью при таком подходе можно сортировать массив и использовать бинарный поиск (предпочтительнее, если ваш массив автомобилей не меняется) или использовать ассоциативный контейнер, который дает вам быстрый доступ к элемент с помощью ключа (карты, multi_map, unordered_map ...)

// binary search 

struct { 
    bool operator()(const car& lh, const car& rh) { return lh.ownerName < rh.ownerName; }; 
    bool operator()(const car& lh, const std::string& rh) { return lh.ownerName < rh; }; 
    bool operator()(const std::string& lh, const car& rh) { return lh < rh.ownerName; }; 

} byName; 

sort(begin(cars), end(cars), byName); 
auto it2 = lower_bound(begin(cars), end(cars), name, byName); 
if (it != end(cars) && it->ownerName == name) 
{ 
    auto index2 = it - begin(cars); 
}