Arhn - архитектура программирования

Сортировать объекты при вставке (если они существуют, добавьте данные)

У меня есть небольшая проблема, и я не знаю, как с ней справиться.

У меня есть структура под названием Person:

struct Person
{
    string name;
    vector <string> address;
};

У меня также есть вектор этих структур.

vector<Person> people;

Мне нужно: Отсортировать человека по имени в векторе людей (по возрастанию), но если человек с таким же именем существует в векторе, то добавить ему другой адрес (address.push_back(address);). Мне нужно поместить новый объект Person (или добавить адрес) в нужное место при вставке (не сортировать вектор после вставки).

c++ sorting vector
03.04.2015

  • Почему бы не использовать, например. std::map? С именем в качестве ключа и Person в качестве данных? 03.04.2015

Ответы:


1

Если это домашнее задание, то я думаю, что вы должны реализовать какой-то алгоритм вместо использования сложной структуры данных, которая будет выполнять сортировку «автоматически».

Вот подсказка: если элемент, который мы ищем, не существует в векторе, то алгоритм бинарного поиска остановится прямо на позиции, которой принадлежит новый элемент.

Java-реализация бинарного поиска делает именно это — она возвращает точку вставки — специальное значение, которое можно преобразовать в позицию в массиве, куда должен быть вставлен новый элемент, сохраняя при этом свойство «отсортировано».

В С++ вам придется реализовать это самостоятельно. Что-то вроде этого: Двоичный поиск, чтобы найти диапазон в котором находится число .

Можно попробовать переопределить поведение Java с помощью std::lower_bound().

03.04.2015

2

Вам нужно использовать отсортированную структуру данных, например std::map (бинарное дерево поиска). Это позволит отсортировать ваши данные, а вставки/запросы будут иметь временную сложность O (log n).

См. std::map для поддерживаемых операций.

Вектор может быть неэффективным, поскольку вы хотите вставлять, а перераспределение может быть очень дорогим в зависимости от размера ваших данных.

03.04.2015
Новые материалы
Коллекции публикаций по глубокому обучению
Последние пару месяцев я создавал коллекции последних академических публикаций по различным подполям глубокого обучения в моем блоге https://amundtveit.com - эта публикация дает обзор 25..
Представляем: Pepita
Фреймворк JavaScript с открытым исходным кодом Я знаю, что недостатка в фреймворках JavaScript нет. Но я просто не мог остановиться. Я хотел написать что-то сам, со своими собственными..
Советы по коду Laravel #2
1-) Найти // You can specify the columns you need // in when you use the find method on a model User::find(‘id’, [‘email’,’name’]); // You can increment or decrement // a field in..
Работа с временными рядами спутниковых изображений, часть 3 (аналитика данных)
Анализ временных рядов спутниковых изображений для данных наблюдений за большой Землей (arXiv) Автор: Рольф Симоэс , Жильберто Камара , Жильберто Кейрос , Фелипе Соуза , Педро Р. Андраде ,..
3 способа решить квадратное уравнение (3-й мой любимый) -
1. Методом факторизации — 2. Используя квадратичную формулу — 3. Заполнив квадрат — Давайте поймем это, решив это простое уравнение: Мы пытаемся сделать LHS,..
Создание VR-миров с A-Frame
Виртуальная реальность (и дополненная реальность) стали главными модными терминами в образовательных технологиях. С недорогими VR-гарнитурами, такими как Google Cardboard , и использованием..
Демистификация рекурсии
КОДЕКС Демистификация рекурсии Упрощенная концепция ошеломляющей О чем весь этот шум? Рекурсия, кажется, единственная тема, от которой у каждого начинающего студента-информатика..